数据结构与算法_动态数组及单向链表练习题

88合并两个有序数组
给定两个有序整数数组 nums1 和 nums2&＃xff0c;将 nums2 合并到 nums1 中&＃xff0c;使得 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间&＃xff08;空间大小大于或等于 m &＃43; n&＃xff09;来保存 nums2 中的元素。
示例:

输入:
nums1 &＃61; [1,2,3,0,0,0], m &＃61; 3
nums2 &＃61; [2,5,6], n &＃61; 3
输出: [1,2,2,3,5,6]

解题思路&＃xff1a;

1. 因为两个数组都是有序的&＃xff0c;定义index1的起始位置nums1的数组长度m-1&＃xff0c;index2的起始位置nums2的数组长度为n-1&＃xff0c;index的起始位置为最终得到的nums1的长度m&＃43;n-1&＃xff1b;
2. 将数组nums1和数组nums2都从后到前遍历&＃xff0c;当nums1[index]>nums2[index2]&＃xff0c;将nums1[index]&＃61;nums1[index1]&＃xff0c;再将指针index和指针index1前移&＃xff1b;
3. 否则&＃xff0c;将nums1[index]&＃61;nums2[index2]&＃xff0c;并且指针前移&＃xff1b;
4. 当数组nums1先移动完成&＃xff0c;即index1<0时&＃xff0c;将nums1[i]&＃61;nums2[i]&＃xff0c;i<&＃61;index2;
5. 当数组nums2先移动完成时&＃xff0c;nums1的原先位置的顺序不变即可。

代码&＃xff1a;

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int index1 &＃61; m - 1;int index2 &＃61; n - 1;int index &＃61; m &＃43; n - 1;while (true) {if (index1 <0 || index2 <0) {break;}if (nums1[index1] > nums2[index2]) {nums1[index--] &＃61; nums1[index1--];} else {nums1[index--] &＃61; nums2[index2--];}}if (index2 >&＃61; 0) {for (int i &＃61; 0; i <&＃61; index2; i&＃43;&＃43;) {nums1[i] &＃61; nums2[i];}}}
}


35插入位置
给定一个排序数组和一个目标值&＃xff0c;在数组中找到目标值&＃xff0c;并返回其索引。如果目标值不存在于数组中&＃xff0c;返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。

示例 1:
输入: [1,3,5,6], 5
输出: 2

示例 2:
输入: [1,3,5,6], 2
输出: 1

示例 3:
输入: [1,3,5,6], 7
输出: 4

示例 4:
输入: [1,3,5,6], 0
输出: 0

解题思路&＃xff1a;用二分查找法查找。

1. 定义索引0为low&＃xff0c;定义索引nums.length-1为high&＃xff0c;定义mid&＃61;(low&＃43;high)/2为中间值&＃xff1b;
2. while循环解决&＃xff0c;条件为low<&＃61;high&＃xff1b;
3. 当给定值大于中间值&＃xff0c;low&＃61;mid&＃43;1&＃xff1b;
4. 当给定值小于中间值&＃xff0c;high&＃61;mid-1;l
5. 当给定值小于中间值&＃xff0c;return low;
6. 如果循环结束没有找到&＃xff0c;则返回low为插入地方。

代码

class Solution {public int searchInsert(int[] nums, int target) {if (nums &＃61;&＃61; null || nums.length &＃61;&＃61; 0) {return 0;}int low &＃61; 0;int high &＃61; nums.length - 1;int mid &＃61; (low &＃43; high) / 2;if (nums[low] &＃61;&＃61; target) {return low;}if (nums[high] &＃61;&＃61; target) {return high;}while (low <&＃61; high) {if (nums[mid] &＃61;&＃61; target) {return mid;}if (nums[mid] }


66加一
给定一个由整数组成的非空数组所表示的非负整数&＃xff0c;在该数的基础上加一。
最高位数字存放在数组的首位&＃xff0c; 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外&＃xff0c;这个整数不会以零开头。

示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

示例 2:
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

解题思路&＃xff1a;

1. 定义一个值代表进位carry&＃xff0c;num代表当前位的值&＃xff1b;
2. 将数组从后向前遍历&＃xff0c;给最后一位加1&＃xff0c;即num&＃61;digits[length-1]&＃43;1&＃xff1b;
3. 并将num%10的值赋给当前&＃xff0c;digits[i]&＃61;num%10;
4. carry&＃61;num/10;当进位carry&＃61;&＃61;0是时&＃xff0c;跳出循环&＃xff1b;
5. 循环结束&＃xff0c;当carry&＃61;&＃61;1时&＃xff0c;从新定义新数组&＃xff0c;且长度时原来的数组长度&＃43;1&＃xff1b;将1赋给新数组的第一位。

class Solution {public int[] plusOne(int[] digits) {int carry &＃61; 1;int num &＃61; 0;for (int i &＃61; digits.length - 1; i >&＃61; 0; i--) {num &＃61; digits[i] &＃43; carry;digits[i] &＃61; num % 10;carry &＃61; num / 10;if (carry &＃61;&＃61; 0) {break;}}if (carry &＃61;&＃61; 1) {int[] arr &＃61; new int[digits.length &＃43; 1];arr[0] &＃61; 1;return arr;} else {return digits;}}
}


20.有效的括号
给定一个只包括 ‘(’&＃xff0c;’)’&＃xff0c;’{’&＃xff0c;’}’&＃xff0c;’[’&＃xff0c;’]’ 的字符串&＃xff0c;判断字符串是否有效。
有效字符串需满足&＃xff1a;

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:
输入: “()”
输出: true

示例 2:
输入: “()[]{}”
输出: true

示例 3:
输入: “(]”
输出: false

示例 4:
输入: “([)]”
输出: false

示例 5:
输入: “{[]}”
输出: true

解题思路&＃xff1a;用栈去查找
当进栈元素和栈顶-1或者-2相等&＃xff0c;则出栈栈顶元素&＃xff0c;完成一组匹配&＃xff1b;
最后当栈为空&＃xff0c;则完全匹配&＃xff0c;返回true&＃xff1b;
否则不匹配&＃xff0c;返回false。

class Solution {public boolean isValid(String s) {Stack stack &＃61; new Stack();for (int i &＃61; 0; i }


240搜索二维矩阵II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性&＃xff1a;

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。


示例:
现有矩阵 matrix 如下&＃xff1a;
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

给定 target &＃61; 5&＃xff0c;返回 true。
给定 target &＃61; 20&＃xff0c;返回 false。

解题思路&＃xff1a;
从左下开始查找&＃xff0c;小于该坐标元素值&＃xff0c;朝上走&＃xff0c;大于该坐标元素值&＃xff0c;超左走&＃xff1b;
bu最后判定横向不大于matrix[0].length-1并且不小于0&＃xff0c;纵向不大于matrix.length-1并且不小于0作为超处数组的限定条件&＃xff1b;
找到了&＃xff0c;返回true&＃xff0c;如果遍历完整个数组都没有找到&＃xff0c;返回false。

代码

class Solution {public boolean searchMatrix(int[][] matrix, int target) {if(matrix&＃61;&＃61;null||matrix.length&＃61;&＃61;0||matrix[0].length&＃61;&＃61;0){return false;}int row&＃61;matrix.length;int col&＃61;matrix[0].length;int x&＃61;row-1;int y&＃61;0;while(true){if(x<0||y>&＃61;col){return false;}if(matrix[x][y]target){x--;}else{return true;}}}
}


209长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s &＃xff0c;找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组&＃xff0c;返回 0。

示例:
输入: s &＃61; 7, nums &＃61; [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

解题思路&＃xff1a;用滑窗机制解决。

1. 定义len存放最短长度&＃xff0c;sum存放滑窗的元素的总和&＃xff0c;两个指针对应滑窗的头和尾&＃xff1b;
2. 当滑窗内的sun小于给定值s&＃xff0c;则尾指针后移&＃xff1b;
3. 当滑窗内的sum大于或等于给定值s&＃xff0c;头指针后移&＃xff0c;并把当前的滑窗长度记录&＃xff1b;
4. 当滑窗尾指针移到最后一个元素&＃xff0c;即到length-1时&＃xff0c;返回长度len。

public class Solution {public int minSubArrayLen(int s, int[] nums) {if (nums &＃61;&＃61; null || nums.length &＃61;&＃61; 0) {return 0;}int len &＃61; 0;int i &＃61; 0;int sum &＃61; 0;for (int j &＃61; 0; j &＃61; s) {len &＃61; len &＃61;&＃61; 0 ? j - i &＃43; 1 : Math.min(len, j - i &＃43; 1);sum -&＃61; nums[i&＃43;&＃43;];}}return len;}
}


54螺旋矩阵
给定一个包含 m x n 个元素的矩阵&＃xff08;m 行, n 列&＃xff09;&＃xff0c;请按照顺时针螺旋顺序&＃xff0c;返回矩阵中的所有元素。

示例 1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

示例 2:
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

解题思路&＃xff1a;

如图&＃xff0c;是数字的转动方向。
向右走&＃xff1a;detX&＃61;0 delY&＃61;1
向下走&＃xff1a;detX&＃61;1 delY&＃61;0
向左走&＃xff1a;detX&＃61;0 delY&＃61;-1
向上走&＃xff1a;detX&＃61;-1 delY&＃61;0
即&＃xff1a;
deltX&＃61;{0,1,0,-1}
deltY&＃61;{1,0,-1,0}
因此&＃xff0c;确定了转动方向的变化量&＃xff0c;再限制不能超出的条件和不能转到已经走过的值&＃xff1b;
即&＃xff0c;规定一个等大的boolean类型的数组&＃xff0c;当走过尾true&＃xff0c;没走过为false;
还有下一次不能走出数组&＃xff0c;横向小于matrix.length-1并且不小于0&＃xff0c;纵向小于matrix[0].length-1并且不小于0即可。

代码&＃xff1a;

public class Solution{public List spiralOrder(int[][] matrix) {ArrayList list &＃61; new ArrayList();if (matrix &＃61;&＃61; null || matrix.length &＃61;&＃61; 0 || matrix[0].length &＃61;&＃61; 0) {return list;}int x &＃61; 0;int y &＃61; 0;int R &＃61; matrix.length;int C &＃61; matrix[0].length;boolean[][] visited &＃61; new boolean[R][C];int[] deltX &＃61; { 0, 1, 0, -1 };int[] deltY &＃61; { 1, 0, -1, 0 };int dir &＃61; 0;for (int i &＃61; 0; i &＃61; 0 && nx &＃61; 0 && ny }


2.两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中&＃xff0c;它们各自的位数是按照 逆序 的方式存储的&＃xff0c;并且它们的每个节点只能存储 一位 数字。
如果&＃xff0c;我们将这两个数相加起来&＃xff0c;则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外&＃xff0c;这两个数都不会以 0 开头。

示例&＃xff1a;
输入&＃xff1a;(2 -> 4 -> 3) &＃43; (5 -> 6 -> 4)
输出&＃xff1a;7 -> 0 -> 8
原因&＃xff1a;342 &＃43; 465 &＃61; 807

解题思路&＃xff1a;用头指针head&＃xff0c;尾指针rear和进位carry完成。

1. 定义一个新链表的头指针尾head&＃xff0c;尾指针指向头指针的位置&＃xff0c;定义变量carry 为进位。
2. 循环完成&＃xff0c;当l1!&＃61;0时加上l1&＃xff1b;当l2不为0时加上l2在加上进位carry&＃xff1b;
3. 将总和对10取余赋给rear.next&＃xff1b;并且总和除以10赋给carry&＃xff1b;
   4.循环完成后&＃xff0c;返回head.next&＃xff0c;因为head不存有效元素。

public class Solution2 {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode head &＃61; new ListNode(0);ListNode rear &＃61; head;int carry &＃61; 0;while (true) {if (l1 &＃61;&＃61; null && l2 &＃61;&＃61; null && carry &＃61;&＃61; 0) {break;}int num &＃61; (l1 &＃61;&＃61; null ? 0 : l1.val) &＃43; (l2 &＃61;&＃61; null ? 0 : l2.val) &＃43; carry;ListNode n &＃61; new ListNode(num % 10);rear.next &＃61; n;rear &＃61; n;carry &＃61; num / 10;l1 &＃61; l1 &＃61;&＃61; null ? null : l1.next;l2 &＃61; l2 &＃61;&＃61; null ? null : l2.next;}return head.next;}
}


19.删除链表的倒数第N个节点
给定一个链表&＃xff0c;删除链表的倒数第 n 个节点&＃xff0c;并且返回链表的头结点。

示例&＃xff1a;
给定一个链表: 1->2->3->4->5, 和 n &＃61; 2.
当删除了倒数第二个节点后&＃xff0c;链表变为 1->2->3->5.

解题思路&＃xff1a;
双指针&＃xff0c;第一个指针先走&＃xff0c;走过n个元素后&＃xff0c;然后两个指针一起走。当第一个指针走到为空时停下&＃xff0c;即第二个指针指向的节点的下一个节点为删除的节点。

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {if (head &＃61;&＃61; null || head.next &＃61;&＃61; null) {return null;}ListNode r &＃61; head;ListNode l &＃61; head;for (int i &＃61; 0; i }


21.合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例&＃xff1a;
输入&＃xff1a;1->2->4, 1->3->4
输出&＃xff1a;1->1->2->3->4->4

解题思路&＃xff1a;
双指针。使指针p1,p2分别指向节点l1,l2&＃xff0c;即p1,p2指向两个链表的头节点&＃xff1b;定义新链表头节点为head,并且p指向head;
将两个指针从头往后遍历.
如果p1.val<&＃61;p2.val,p.next &＃61; p1;p1 &＃61; p1.next;
如果p1.val>p2.val,p.next &＃61; p2;p2 &＃61; p2.next;
如果p1!&＃61;null,p2&＃61; &＃61;null;p.next &＃61; p1;break;
如果p1&＃61; &＃61;null,p2!&＃61;null;p.next &＃61; p2;break;
如果p1&＃61; &＃61;null,p2&＃61; &＃61;null;break;

class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode head &＃61; new ListNode(0);ListNode p &＃61; head;ListNode p1 &＃61; l1;ListNode p2 &＃61; l2;while (true) {if (p1 &＃61;&＃61; null && p2 &＃61;&＃61; null) {break;}if (p1 !&＃61; null && p2 &＃61;&＃61; null) {p.next &＃61; p1;break;} else if (p1 &＃61;&＃61; null && p2 !&＃61; null) {p.next &＃61; p2;break;} else if (p1.val <&＃61; p2.val) {p.next &＃61; p1;p1 &＃61; p1.next;} else {p.next &＃61; p2;p2 &＃61; p2.next;}p &＃61; p.next;}return head.next;}
}


328.奇偶链表
给定一个单链表&＃xff0c;把所有的奇数节点和偶数节点分别排在一起。请注意&＃xff0c;这里的奇数节点和偶数节点指的是节点编号的奇偶性&＃xff0c;而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)&＃xff0c;时间复杂度应为 O(nodes)&＃xff0c;nodes 为节点总数。

示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

示例 2:
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL

解题思路&＃xff1a;
双指针&＃xff0c;一个从奇数位走&＃xff0c;另一个从偶数位走&＃xff0c;当两个都走完时&＃xff0c;从奇数位的最后一位指向偶数位的第一位&＃xff0c;然后返回链表即可。

class Solution {public ListNode oddEvenList(ListNode head) {if (head &＃61;&＃61; null || head.next &＃61;&＃61; null) {return head;}ListNode ji &＃61; head;ListNode ou &＃61; head.next;ListNode ouStart &＃61; ou;while (true) {if (ou &＃61;&＃61; null || ou.next &＃61;&＃61; null) {break;}ji.next &＃61; ji.next.next;ou.next &＃61; ou.next.next;ji &＃61; ji.next;ou &＃61; ou.next;}ji.next &＃61; ouStart;return head;}
}


141.环形链表
给定一个链表&＃xff0c;判断链表中是否有环。

为了表示给定链表中的环&＃xff0c;我们使用整数 pos 来表示链表尾连接到链表中的位置&＃xff08;索引从 0 开始&＃xff09;。 如果 pos 是 -1&＃xff0c;则在该链表中没有环。

示例 1&＃xff1a;
输入&＃xff1a;head &＃61; [3,2,0,-4], pos &＃61; 1
输出&＃xff1a;true
解释&＃xff1a;链表中有一个环&＃xff0c;其尾部连接到第二个节点。

示例 2&＃xff1a;
输入&＃xff1a;head &＃61; [1,2], pos &＃61; 0
输出&＃xff1a;true
解释&＃xff1a;链表中有一个环&＃xff0c;其尾部连接到第一个节点。

示例 3&＃xff1a;
输入&＃xff1a;head &＃61; [1], pos &＃61; -1
输出&＃xff1a;false
解释&＃xff1a;链表中没有环。

解题思路&＃xff1a;
双指针&＃xff0c;一个指针一次走两个节点&＃xff0c;另一个指针一次走一个节点。
当第一个节点走到空&＃xff0c;则没有环&＃xff1b;
当第一个节点追上第二个节点&＃xff0c;则是第一个节点过环后追上&＃xff0c;即有环。

public class Solution {public boolean hasCycle(ListNode head) {if (head &＃61;&＃61; null || head.next &＃61;&＃61; null) {return false;}ListNode fast &＃61; head;ListNode slow &＃61; head;while (true) {if (fast &＃61;&＃61; null || fast.next &＃61;&＃61; null) {return false;}slow &＃61; slow.next;fast &＃61; fast.next.next;if (slow &＃61;&＃61; fast) {return true;}} }
}


142.环形链表II
给定一个链表&＃xff0c;返回链表开始入环的第一个节点。 如果链表无环&＃xff0c;则返回 null。
为了表示给定链表中的环&＃xff0c;我们使用整数 pos 来表示链表尾连接到链表中的位置&＃xff08;索引从 0 开始&＃xff09;。 如果 pos 是 -1&＃xff0c;则在该链表中没有环。

说明&＃xff1a;不允许修改给定的链表。

示例 1&＃xff1a;
输入&＃xff1a;head &＃61; [3,2,0,-4], pos &＃61; 1
输出&＃xff1a;tail connects to node index 1
解释&＃xff1a;链表中有一个环&＃xff0c;其尾部连接到第二个节点。

示例 2&＃xff1a;
输入&＃xff1a;head &＃61; [1,2], pos &＃61; 0
输出&＃xff1a;tail connects to node index 0
解释&＃xff1a;链表中有一个环&＃xff0c;其尾部连接到第一个节点。

示例 3&＃xff1a;
输入&＃xff1a;head &＃61; [1], pos &＃61; -1
输出&＃xff1a;no cycle
解释&＃xff1a;链表中没有环。

解题思路&＃xff1a;
和上一个雷同&＃xff0c;但是走的方法不同。
一个节点先走一个&＃xff0c;另一个节点从头走一个&＃xff0c;并比较&＃xff0c;当两个走的次数相同碰到则不记&＃xff1b;
第一个再原来的基础上走一个&＃xff0c;另一个从头走两个&＃xff0c;当两个走的次数相同碰到则不记&＃xff1b;
。。。。。
以此类推&＃xff0c;当两个指针走的次数不同&＃xff0c;但是碰到了&＃xff0c;则有环&＃xff0c;并且入环的位值是第二个节点的位置。其他情况下均无环。

public class Solution {public ListNode detectCycle(ListNode head) {if (head &＃61;&＃61; null || head.next &＃61;&＃61; null) {return null;}ListNode fast&＃61;head;ListNode slow&＃61;head;int step&＃61;0;while(fast!&＃61;null){fast&＃61;fast.next;step&＃43;&＃43;;slow&＃61;head;for (int i &＃61; 1; i <&＃61; step; i&＃43;&＃43;) {if(slow&＃61;&＃61;fast&&step!&＃61;i){return slow;}slow&＃61;slow.next;}}return null; }
}