leetcode数组,链表相关基础题目整理
leetcode26.删除排序数组中的重复项
关键字：数组
题目链接
解题思路：双指针迭代
使用一前一后两个指针，遍历迭代数组，如果两个指针指向的数字相等，那么右指针向后移；如果两个指针指向的数字不等，那么就将右指针指向的数字赋值给左指针指向的下一个位置，赋值完毕后，右指针向后移动；直至遍历到数组的最后一个位置。可以参考 删除重复项-带优化思路 这篇题解。
代码如下：
class Solution {
public int removeDuplicates(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
int left = 0;
int right = 1;
while(right < nums.length){
if(nums[left] != nums[right]){
nums[++left] = nums[right];
}
right++;
}
return left + 1;
}
}
本思路的时间复杂度为O(n),额外空间复杂度为O(1)。
执行结果:
leetcode6.加一
关键字：数组
题目链接
题解：
对于本题共有三种情况：
- 只加1不进位
对于数组[6,7]而言，加一之后返回[6,8];我们只需要对数组的最后一个数字进行判断，加一之再对10取模，如果不等于0，我们就可以将数组直接返回。 - 进位，但没有越位
进位不越位是什么意思呢？举个栗子：对于数组[7,9,9]，加一之后应返回[8,0,0]。还是从数组最后一位向第一位迭代，直到首位加一对10取模不等于0返回，这样和第一种情况实际上相同，只不过我们需要对数组的每一位都进行一次遍历 - 越位
越位只有一种情况，就是数组中的每一个数字都是9，举例：[9,9,9]加一后返回[1,0,0,0]。我们只需要将原数组赋给一个新的数组，新数组的长度为原数组长度加一，然后再将第一位置1即可。
代码如下：
class Solution {
public int[] plusOne(int[] digits) {
for(int i = digits.length - 1;i>=0;i--){
digits[i]++;
digits[i] %= 10;
if(digits[i] != 0){
return digits;
}
}
digits = new int[digits.length + 1];
digits[0] = 1;
return digits;
}
}
这种思路，时间复杂度为O(n),出现越位的情况时，额外空间复杂度为O(n)，不越位额外空间复杂度O(1).
执行代码如下：
leetcode88.合并两个有序数组
关键字：数组
题目链接
题解一：正向迭代
使用三个指针，依次迭代推移，建议自己写写画画把这种基本的思路写出来，代码如下：
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = 0;
int p2 = 0;
int p3 = m;
while(p1 < p3 && p2 < n){
if(nums1[p1] <= nums2[p2]){
p1++;
}else{
for(int i = p3 - 1;i >= p1;i--){
nums1[i + 1] = nums1[i];
}
nums1[p1++] = nums2[p2++];
p3++;
}
}
while(p2 < n){
nums1[p3++] = nums2[p2++];
}
}
}
这种写法的时间复杂最坏的情况为O(n * m),没有使用额外的空间，所以额外空间复杂度为O(1).
执行结果如下：
题解二：反向迭代
正向迭代会导致逻辑复杂，最好的办法是从后向前遍历数组，设置指针len1与len2分别指向nums1和nums2的尾部，从尾部的值开始比较遍历，设置指针len指向nums1的最末尾(合并后的数组长度为n+m,所以len = n+m-1)，每次遍历比较大小值后填充。
代码如下：
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int len1 = m - 1;
int len2 = n - 1;
int len = n + m - 1;
while(len1 >= 0 && len2 >= 0){
nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
}
System.arraycopy(nums2,0,nums1,0,len2 + 1);
}
}
反向迭代会将时间复杂度缩小至O(n+m)级别，并且没有使用额外的空间，额外空间复杂度为O(1)。
执行结果：
leetcode189.旋转数组
关键字：数组
题目链接
题解一：暴力求解
最原始的方法就是将原数组旋转k次
class Solution {
public void rotate(int[] nums, int k) {
int first = 0;
int temp = 0;
for(int i = 0; i < k;i++){
first = nums[nums.length - 1];
for(int j = 0; j < nums.length;j++){
temp = nums[j];
nums[j] = first;
first = temp;
}
}
}
}
执行结果：
题解二：空间换时间
顾名思义，开辟长度为len的额外的数组空间，将旋转后的数组拷贝至辅助数组，其中对应的index关系为help[(i + k)%len] = nums[i] ，填满辅助数组以后，再将辅助数组拷贝至原数组中即可。
代码如下：
class Solution {
public void rotate(int[] nums, int k) {
if(nums == null || nums.length == 0){
return;
}
int[] help = new int[nums.length];
for(int i = 0;i < nums.length;i++){
help[(i + k) % nums.length] = nums[i];
}
for(int i = 0;i < nums.length;i++){
nums[i] = help[i];
}
}
}
执行结果：
题解三：
第三种思路是用反转来替换旋转：
对于数组[1,2,3,4,5,6,7] ，k = 3；旋转之后的数组为：[5,6,7,1,2,3,4]
实际上，相当于：
- 将数组反转
[7,6,5,4,3,2,1] - 将前k个数反转
[5,6,7,4,3,2,1] - 将index from k to len - 1，也就是剩余的部分反转
[5,6,7,1,2,3,4]
我们通过这样的思想很容易写出代码：
class Solution {
public void rotate(int[] nums, int k) {
if(nums == null || nums.length == 0){
return;
}
int len = nums.length;
k %= len;
reverse(nums,0,len - 1);
reverse(nums,0,k - 1);
reverse(nums,k,len - 1);
}
private void reverse(int[] nums,int start,int end){
while(start < end){
swap(nums,start++,end--);
}
}
private void swap(int[] nums,int i,int j){
nums[i] = nums[i] ^ nums[j];
nums[j] = nums[i] ^ nums[j];
nums[i] = nums[i] ^ nums[j];
}
}
这种思路的时间复杂度为：O(n),额外空间复杂度为O(1)
执行结果：
leetcode21.合并两个有序链表
关键字：链表，递归
题目链接
题解一：Merge
本题其实和MergeSort中的Merge过程一模一样，只不过我们平时都是拿数组进行训练，本题将数组变成了链表而已，还是使用dummyHead作为头节点，返回dummyHead.next即可，代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(-1);
ListNode cur = dummyHead;
while (l1 != null && l2 != null) {
if(l1.val <= l2.val){
cur.next = new ListNode(l1.val);
cur = cur.next;
l1 = l1.next;
}else{
cur.next = new ListNode(l2.val);
cur = cur.next;
l2 = l2.next;
}
}
while(l1 != null){
cur.next = new ListNode(l1.val);
cur = cur.next;
l1 = l1.next;
}
while(l2 != null){
cur.next = new ListNode(l2.val);
cur = cur.next;
l2 = l2.next;
}
return dummyHead.next;
}
}
本代码中，时间复杂度为两个链表的总长度O(n+m),另外并没有在原有的链表上进行操作，所以额外空间复杂度为O(n+m).
执行代码结果：
题解二：Recursion
本题比较巧妙的办法就是递归，看代码也非常好理解，无论是链表还是二叉树都离不开递归，代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next,l2);
return l1;
}else{
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}
}
递归操作和merge操作的时间复杂度和额外空间复杂度是一样的，因为从时间复杂度上来看，递归操作最多也需要从头遍历两个链表的长度，额外空间上需要n+m个栈帧，所以额外空间复杂度也为O(n+m).
执行结果：
题解三：对题解一进行优化
有没有办法不浪费额外的空间呢，实际上在merge的过程中，只要避免创建新的节点即可；代码也不是很难理解：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(-1);
ListNode cur = dummyHead;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 == null ? l2 : l1;
return dummyHead.next;
}
}
时间复杂度O(n+m)，因为在原有的链表上操作，空间复杂度优化至O(1).
执行结果如下：
leetcode25.k个一组翻转链表
关键字：链表
题目链接
题解：
图片转自 王小二 在 leetcode上面的题解:图解k个一组翻转链表
正如题解中所说，一图胜千言
代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode pre = dummyHead;
ListNode end = dummyHead;
while(end.next != null){
for(int i = 0;i < k && end != null;i++){
end = end.next;
}
if(end == null){
break;
}
ListNode start = pre.next;
ListNode next = end.next;
end.next = null;
pre.next = reverse(start);
start.next = next;
pre = start;
end = pre;
}
return dummyHead.next;
}
private ListNode reverse(ListNode head){
ListNode pre = null;
ListNode next = null;
while(head != null){
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}
执行结果：
关于数组与链表的其他基础题目以及题解,在这里给出我的文章链接：
leetcode283.移动零
leetcode11.盛最多水的容器
leetcode70.爬楼梯
leetcode1.两数之和
leetcode15.三数之和
leetcode206.反转链表
leetcode24.两两交换链表中的节点
leetcode141.环形链表
leetcode142.环形链表II
