问题

给定一个链表，旋转链表，将链表每个节点向右移动 \(k\) 个位置，其中 \(k\)是非负数。

示例 1:

输入: \(1->2->3->4->5->NULL, k = 2\)
输出: \(4->5->1->2->3->NULL\)
解释:
向右旋转 1 步: \(5->1->2->3->4->NULL\)
向右旋转 2 步: \(4->5->1->2->3->NULL\)

示例 2:

输入: \(0->1->2->NULL, k = 4\)
输出: \( 2->0->1->NULL\)
解释:
向右旋转 1 步: \(2->0->1->NULL\)
向右旋转 2 步: \(1->2->0->NULL\)
向右旋转 3 步: \(0->1->2->NULL\)
向右旋转 4 步: \(2->0->1->NULL\)

解法1

一开始可以发现，有如下三种特殊情况是可以直接不进行任何处理，直接返回head的：

• \(head\)为\(null\)，整个链表都是\(null\)
• \(head\)的\(next\)为空，代表链表只有一个元素，此时不论右移多少次，都是本身
• \(k=0\)

考虑\(k\)的取值, 如果\(k\)的值正好是链表长度的整数倍，这种情况右移后还是原链表本身。返回即可。
接下来，如果\(k\)远远超过链表的长度，我们也没必要进行过多的右移，获取\(k\)对链表长度的余数即为右移的次数。
一个难点在于，在单向链表中找到一个元素的父亲节点的时间复杂度很高。此时第一个想法是翻转链表、新链表左移、再次翻转链表。
也写出了第一版代码。

代码1

java实现

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        //三种情况，链表为空、链表只有一个元素、移动位置为0
        if (head == null ||head.next == null || k == 0) {
            return head;
        }
        ListNode tail = head;
        ListNode temp = head;
        //判断长度
        int i = 1;
        while (temp.next != null) {
            temp = temp.next;
            i++;
        }
        
        k = k % i;
        //当旋转整数倍时，没有必要挪动数据，直接返回head
        if (k == 0) {
            return head;
        }
        
        //翻转链表
        head = reverse(head);
        while(k>0) {
            tail.next = head;
            tail = head;
            head = head.next;
            tail.next = null;
            k--;
        }
        head = reverse(head);
        return head;
        
    }
    
    //翻转链表
    ListNode reverse (ListNode head) {
        ListNode prev = head;
        ListNode curr = head.next;
        while (curr!=null) {
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        head.next = null;
        return prev;
    }
}

解法2

解法1的问题在于有两次翻转链表，虽然只是\(O(n)\)的时间复杂度，但是本着能少一步是一步的原则，还是能省则省。
继续观察示例1，发现，右移\(2\)位，实际上是左移\(3\)位，而左移是解法1里就实现了的。这就不需要翻转链表就可以直接移动了。

代码2

java实现

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        //三种情况，链表为空、链表只有一个元素、移动位置为0
        if (head == null ||head.next == null || k == 0) {
            return head;
        }
        ListNode tail = head;
        ListNode temp = head;
        //判断长度
        int i = 1;
        while (tail.next != null) {
            temp = tail;
            tail = tail.next;
            i++;
        }
        
        k = k % i;
        //当旋转整数倍时，没有必要挪动数据，直接返回head
        if (k == 0) {
            return head;
        }
        //增加了一步k的计算
        k = i-k;
        
        //翻转链表
        //注释掉解法1的翻转链表
        //head = reverse(head);
        while(k>0) {
            tail.next = head;
            tail = head;
            head = head.next;
            tail.next = null;
            k--;
        }
        //注释掉解法1的翻转链表
        //head = reverse(head);
        return head;
        
    }
    
    //翻转链表
    ListNode reverse (ListNode head) {
        ListNode prev = head;
        ListNode curr = head.next;
        while (curr!=null) {
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        head.next = null;
        return prev;
    }
}

仔细观察代码，实际上是去掉了翻转链表，对k进行了更进一步的操作而已。相比解法一，代码更加的清晰。

问题

给定一个数组\( nums\) 和一个值 \(val\)，你需要原地移除所有数值等于 \(val\) 的元素，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 \(O(1)\) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

给定 \(nums = [3,2,2,3], val = 3\),
函数应该返回新的长度 \(2\), 并且 \(nums\) 中的前两个元素均为 \(2\)。
你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 \(nums = [0,1,2,2,3,0,4,2], val = 2\),
函数应该返回新的长度 \(5\), 并且 \(nums\) 中的前五个元素为 \(0, 1, 3, 0, 4\)。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解法

使用双指针，从数组的两头分别扫描，左指针停在等于\(val\)的位置，右指针停在不等于\(val\)，然后交换两个指针的值，进行下一轮扫描。

代码

java实现

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            //左指针停在等于val的位置
            while (left < nums.length && nums[left] != val) {left++;}
            //右指针停在不等val的位置
            while (right > 0 && num[right] == val) {right--;}
            //判断两个指针的位置是不是正确，正确的话就交换，否则说明已经超过位置了，直接跳出即可
            if (left<right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            } else {
                break;
            }
        }
        return left;    
    }
}

问题

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 \(O(1)\) 额外空间的条件下完成。

示例 1:

给定数组\( nums = [1,1,2]\),
函数应该返回新的长度 \(2\), 并且原数组 \(nums\) 的前两个元素被修改为 \(1, 2\)。
你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 \(nums = [0,0,1,1,1,2,2,3,3,4]\),
函数应该返回新的长度 \(5\), 并且原数组 \(nums\) 的前五个元素被修改为 \(0, 1, 2, 3, 4\)。
你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝

int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解法

快慢指针，慢指针只有在快指针的数大于慢指针前一个数时才推进。

代码

java实现

class Solution {
    public int removeDuplicates(int[] nums) {
        int index=0;
        for(int n:nums) {
            if(index<1||n>nums[index-1]) {
                nums[index++]=n;
            }
        }
        return index;
    }
}

问题

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 \(O(1)\) 额外空间的条件下完成。

示例 1:

给定 \(nums = [1,1,1,2,2,3]\),

函数应返回新长度 \(length = 5\), 并且原数组的前五个元素被修改为 \(1, 1, 2, 2, 3\) 。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 \(nums = [0,0,1,1,1,1,2,3,3]\),

函数应返回新长度 \(length = 7\), 并且原数组的前五个元素被修改为 \(0, 0, 1, 1, 2, 3, 3\) 。

你不需要考虑数组中超出新长度后面的元素。
说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}

解法

使用快慢指针，快指针每次循环都往前推进，慢指针只有在指针位置小于2（前面两位必然需要向前推进）或者慢指针前推2位的数小于快指针的数时，才向前推进，并且将快指针的值赋值到慢指针位置。

源码

class Solution {
    public int removeDuplicates(int[] nums) {
        int fast=0;
        int slow=0;
        while(fast<nums.length) {
            //慢指针只有在小于2或者前数2位小于快指针时才往前推进
            if (slow < 2 || nums[fast] > nums[slow-2]) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
}

问题

给定一个包含 \(n + 1\) 个整数的数组 \(nums\)，其数字都在 \(1\) 到 \(n\) 之间（包括 \(1\) 和 \(n\)），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: \([1,3,4,2,2]\)
输出: \(2\)

示例 2:

输入: \([3,1,3,4,2]\)
输出: \(3\)

说明：

不能更改原数组（假设数组是只读的）。
只能使用额外的 \(O(1)\) 的空间。
时间复杂度小于 \(O(n^2)\) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

解法

查看题目，其数字均在\(1\) 到 \(n\) 之间，因此，可以将数字当作数组下标，指向下一个数组元素，那么就可以把数组\(nums\)当成一个链表，题目就成为了将查询链表的环的入口。
链表判断环可以使用快慢指针。

代码

java实现

class Solution {
    public int findDuplicate(int[] nums) {
        int fast = 0;
        int slow = 0;
        while (true) {
            fast = nums[nums[fast]];
            slow = nums[slow];
            if (fast == slow) {
                fast = 0;
                while(fast != slow) {
                    fast = nums[fast];
                    slow = nums[slow];
                }
                return nums[slow];
            }
        }
    }
}

问题

假设你正在爬楼梯。需要 \(n\) 阶你才能到达楼顶。

每次你可以爬 \(1\) 或 \(2\) 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 \(n\) 是一个正整数。

示例 1：

输入： \(2\)
输出： \(2\)
解释： 有两种方法可以爬到楼顶。

1. \(1\) 阶 + \(1\) 阶
2. \(2\) 阶

示例 2：

输入： \(3\)
输出： \(3\)
解释： 有三种方法可以爬到楼顶。

1. \(1\) 阶 + \(1\) 阶 + \(1\) 阶
2. \(1\) 阶 + \(2\) 阶
3. \(2\) 阶 + \(1\) 阶

解答1

此题目可以说是最经典（另一种说法是最“容易”）的动态规划的题目。
动态规划是将一个大问题分解为多个简单的子问题来求解的方法。
动态规划常常适用于有重叠子问题与最优子结构的问题。

思路

1. 设\(f(n)\)为总的方法数量
2. 可以看到，到第\(n\)阶的方法其实一共有两种方式
   • 从第\(n-1\)阶爬一步到达第\(n\)阶
   • 从第\(n-2\)阶爬两步到达第\(n\)阶
3. 因此可以总结出公式
   \(f(n) = \begin{cases} 1, & \text{\)n = 1\(} \\ 2,& \text{\)n = 2\(} \\ f(n-1) +f(n-2), & \text{\)n>2\(} \end{cases}\)可以发现，这个就是斐波那契数列的变种。

##代码1

java实现

class Solution {
    public int climbStairs(int n) {
        return resolve(n);
    }
    public int resolve(int n) {
        if (n==1) {
            return 1;
        }
        if (n==2) {
            return 2;
        }
        return resolve(n-1)+resolve(n-2);
    }
}

代码非常的简洁，马上丢到leetcode上跑一次，居然执行了10801 ms。击败了0.98%的人。。。

解法2

解法1虽然勉强能跑，但是有一个非常严重的问题是，重复计算量过大。
\(f(n)与f(n-1)均用到了f(n-2)\)但是因为并没有暂存的地方，导致\(f(n-2)\)被计算了两次。
比如计算\(f(5)\)：

    
    strict graph { 
      a -- b
      a -- b
      b -- a [color=blue]
    } 
    ```
此时考虑到以往的数据会被重复使用，那么何不做一个数组暂存数据呢。
## 代码2
### java实现
```java
class Solution {
    public int climbStairs(int n) {
        int[] cache = new int[n+1];
        return resolve(n);
    }
    public int resolve(int n, int[] cache) {
        if (n==1) {
            return 1;
        }
        if (n==2) {
            return 2;
        }
        if (cache[n] ==0) {
            cache[n] = resolve(n-1,cache) +resolve(n-2,cache);
        }
        return cache[n];
    }
}

此方法4ms执行完成。

解法3

上述两种方法，均是递归调用，如何转为迭代呢？

代码3

java实现

class Solution {
    public int climbStairs(int n) {
        int[] cache = new int[n+1];
        cache[0] = cache[1] = 1;
        for(int i=2;i<=n;i++) {
            cache[i] = cache[i-1] + cache[i-2];
        }
        return cache(n);
    }
}

问题

给定一个包含非负数的数组和一个目标整数 \(k\)，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 \(2\)，总和为 \(k\) 的倍数，即总和为 \(n*k\)，其中 \(n\) 也是一个整数。

示例 1:

输入: \([23,2,4,6,7], k = 6\)
输出: True
解释: \([2,4]\) 是一个大小为 \(2\) 的子数组，并且和为 \(6\)。

示例 2:

输入: \([23,2,6,4,7], k = 6\)
输出: True
解释: \([23,2,6,4,7]\)是大小为 \(5\) 的子数组，并且和为 \(42\)。

说明:

数组的长度不会超过10,000。
你可以认为所有数字总和在 32 位有符号整数范围内。

解答1

遍历不同长度的子数组，判断是不是能被整除即可。有一个优化点在于可以用动态规划的思路。在len+1长度的子数组遍历时，可以用到len长度的子数组已经计算好的值，不需要再次计算了。

需要clone一份nums数据，空间复杂度是\(O(n)\)

源码1

java实现

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        //新增一个数组保存上一轮的全部sum数据
        //这里容易出错的地方在于将sums的数据初始化为0。会造成基础数据就不对。
        int[] sums = nums.clone();
        //从len=2开始，进行长度不同的遍历
        for(int len=2;len<=nums.length;len++) {
            for(int i = 0; i<=nums.length-len; i++) {
                //此时将sums[i]的数据与nums[i+len-1]的数据相加获得新值
                sums[i] += nums[i+len-1];
                //排除掉[0,0],0 的特殊情况
                if(sums[i] ==0) {
                    return true;
                }
                //判断当前值是不是可以整除，可以直接返回true
                if (k!=0&& sums[i]%k==0) {
                    return true;
                }
            }
        }       
        //默认情况
        return false;
    }
}

解答2

引入一个概念，前缀和（prefix sum）。

给定一个数组\(x\)，数组元素为\(x_0,x_1,x_2,...x_{n-1},x_n\)
如果有数组\(y\),满足如下条件
\(y_0=x_0\)
\(y_1=x_0+x_1\)
\(y_2=x_0+x_1+x_2\)
\(...\)
\(y_{n-1}=x_0+x_1+x_2+...+x_{n-1}\)
\(y_n=x_0+x_1+x_2+...+x_{n-1}+x_{n}\)
那么称\(y\)为\(x\)的前缀和数组
例子

此时可以发现，数组\(x\)的子序列和均可由前缀和数组\(y\)获得，如\({x_a}\)至\({x_b}\)子序列的和，可以由\(y_b-y_{a-1}\)得到。而且也可以用到动态规划的思路，一次遍历生成\(y\)数组，然后接下来的遍历就可以复用\(y\)数组了。

源码2

java实现

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        //生成前缀和数组，此时已经可以判断一次了
        int[] presums = new int[nums.length];
        for(int i=0;i<nums.length;i++) {
            if (i==0) {
                presums[0]=nums[0];
            } else {
                presums[i] = presums[i-1] + nums[i];
                if (presums[i] == 0) {
                    return true;
                }
                if (k!=0 && presums[i]%k==0) {
                    return true;
                }
            }
        }
        //此时遍历连续子数组的和
        for (int i=1;i<presums.length;i++) {
            for(int len=2;len<=i;len++) {
                //这一步是获取从i-len+1到i的子数组的和
                int sub = presums[i]-presums[i-len];
                if(sub ==0) {
                    return true;
                }
                if (k!=0 && sub%k==0) {
                    return true;
                }
            }
        }
        //默认情况
        return false;
    }
}

代码整体没有难度，需要关注的点在于遍历子数组的和时的边界问题，因为题目要求是最少长度为2，所以len这里需要赋值为2，len<=i的原因在于需要将presums[0]首位数扣除。

解法3

仍然需要解法2的前缀和的概念。
假设有两个索引值\(a与b,y_a = m*k + mod_a,y_b = n*k + mod_b\)其中\(mod_a与mod_b\)为\(y_a与y_b整除k的余数\)。不难发现这么一个情况，如果\(mod_a==mod_b并且 b-a>1\)，那么\(a\)到\(b\)的子数组和就是满足要求的数组。
此时可以考虑，将每一个\(mod\)与其索引值放入一个map中，key为\(mod\),value为索引值。每次循环时，判断新值的\(mod\)是否保存在map中，如果存在，那么判断两个索引值之间的差值是否大于1，大于1就返回true即可
有一种特殊情况，就是\(nums_0==0\)并且\(nums_i\%k==0\)，为了处理这种情况，设置键值对(0,-1)
需要处理连续两个0以及k=0的特殊情况

源码3

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        //先处理特殊情况
        //当nums的长度小于2时，必然false
        if (nums.length<2) return false;
        //当相邻两个值均为0时，必然true
        for(int i=0;i<nums.length-1;i++) {
            if(nums[i]==0&&nums[i+1]==0) return true;
        }
        //此时排除掉上一种情况时，如果k==0，那么必然为false
        if (k==0) return false;
        //开始循环
        //构造一个map放入mod与索引
            Map<Integer,Integer> map = new HashMap<>();
        //写入特殊情况的键值对(0,-1)
        map.put(0,-1);
        //构造一个全局变量供每次循环累加使用
        int sum=0;
        for(int i=0;i<nums.length;i++) {
            sum +=nums[i];
            //取余
            int mod = sum%k;
            //判断map中是否已经包含了mod值，
            if (map.containsKey(mod)) {
                //当两个索引值相减大于1时，说明有2个元素及以上的子数组满足条件
                if (i-map.get(i) > 1) {
                    return true;
                }
            } else {
                //将键值对放入map中
                map.put(mod, i);
            }
        }
        //默认情况
        return false;
    }
}

总结

此题目的解法众多，但是快速找到一个时间复杂度与空间复杂度均低的解法还是需要一些思考的。解法1与解法2在leetcode中的耗时大概在66ms左右，解法3耗时在13ms左右。

问题

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 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

解答

此题没有难度，遍历数组，分为两种情况

• 数组当前值nums[i]大于等于target，此时，直接返回i即可，因为不管是大于还是等于，target的位置都是在i处
• 遍历后仍然没有返回，此时说明target大于全部的nums中的数据，此时返回nums.length

代码

java实现

class Solution {
    public int searchInsert(int[] nums, int target) {
        for(int i=0;i<nums.length;i++) {
            //第一种情况
            if (nums[i]>=target) {
                return i;
            }
        }
        //第二种情况
        return nums.length;
    }
}

问题

给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。

数学表达式如下:

如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1，
使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。

示例 1:

输入: [1,2,3,4,5]
输出: true

示例 2:

输入: [5,4,3,2,1]
输出: false

解答

1. 使用两个int变量m1与m2，初始化为整型最大值。
2. 开始遍历数组,此时分三种情况
   • m1大于等于数组当前值nums[i]，此时，将数组当前值nums[i]赋值给m1
   • m1小于数组当前值nums[i]、m2大于数组当前值nums[i]，此时，将数组当前值赋值给m2。这里有个隐含的状态是，m2更新代表着我们已经找到了一个递增的二元子序列。接下来的查找中只需要找到一个值大于m2就说明存在递增的三元子序列，直接返回true即可。
   • m2也小于数组当前值nums[i]，因为前两种情况进入时已经找到了递增的二元子序列，此时直接返回true即可。
3. 当在遍历中没有返回时，代表数组中最多只有递增的二元子序列，直接返回false即可

注意在循环中，实际上每次判断都会尽量减小m1与m2的值，毕竟m2的值越小，在接下来的数据中大于m2的可能性就更高

代码

java实现

class Solution {
    public boolean increasingTriplet(int[] nums) {
        //两个变量。初始化为整型最大值。
        int m1 = Integer.MAX_VALUE;
        int m2 = Integer.MAX_VALUE;
        for(int i = 0; i < nums.length; i++) {
            //上述的第一种情况
            if (m1>=nums[i]) {
                m1=nums[i];
            } else {
                //上述的第二种情况
                if (m2>=nums[i]) {
                    m2=nums[i];
                } else {
                    //上述的第三种情况
                    return true;
                }
        }
        //遍历过程中没有返回的情况。
        return false;
    }
}