想去看非洲大草原

今日鸡汤

对外界的焦虑，来自自己对自己的看法，对自己的看法会篡改你在外界收到的真实信息。

https://github.com/gaoshengnan/LeetCode

数组PART

双指针

26. 删除排序数组中的重复项

一般数组问题，都用双指针或多指针做，尤其是要移动的或者替换的情况，通过维护两个指针来确定一个窗口进行操作。

public int removeDuplicates(int[] nums) {
        int start = 0;
        int end = 0;
        int current = 0;

        while(end <= nums.length -1){
            while(end < nums.length && nums[end] == nums[start]){
                end++;
            }
            if(end >= nums.length) break;
            nums[++current] = nums[end];
            start = end;
            end++;
        }
        return current + 1;
    }

88. 合并两个有序数组

双指针，由于num1已经预留了位置，因此从后往前选数插入。

public void merge(int[] nums1, int m, int[] nums2, int n) {
        int last =  m + n - 1;
        int n1Index = m - 1;
        int n2Index  = n  - 1;

        while(n1Index >= 0 && n2Index >= 0){
            if(nums1[n1Index] > nums2[n2Index]){
                nums1[last--] = nums1[n1Index--];
            } else{
                nums1[last--] = nums2[n2Index--];
            }
        }
        while(n2Index >= 0){
            nums1[last--] = nums2[n2Index--];
        }
    }

283. 移动零

数组移动，且在原数组上操作，记得数组值可以覆盖，只需要用指针把当前操作的下标值记录好即可。
第一种方法，不断把所有非零的数往左边堆，每次移动一个就将非零指针往后移。之后再从非零指针的位置开始把右边的脏数据清零。

public void moveZeroes(int[] nums) {
        int nonZeroIndex = 0;

        for(int i = 0;i < nums.length;i++){
            if(nums[i] != 0){
                nums[nonZeroIndex] = nums[i];
                nonZeroIndex++;
            }
        }

        for(int j = nonZeroIndex; j < nums.length;j++){
            nums[j] = 0;
        }
    }

第二种方法，利用快排哨兵的思想，用0作为哨兵，把不等于0的数放在左边，把等于零的数放在右边。遍历一次，如果当前数非零，就交换，否则直接后移。

public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public void moveZeroes(int[] nums) {
        int low = 0;

        for(int i = 0;i < nums.length;i++){
            if(nums[i] != 0){
                swap(nums, i, low);
                low++;
            } 
        }
    }

15. 三数之和

之前做 Two Sum，用了神奇的MAP方法，3sum用到的是三指针。
首先先给数组从小到大排序，从头用i遍历一遍数组，每轮遍历里：
1、用两个指针left和right分别从i+1和end开始记录位置。
2、判断 nums[i] + nums[left] + nums[right]的值：
1）刚好等于0，发现一组解，加入list中，left右移，right左移；
2）<0，说明left太小了，left右移；
3）>0，说明right太大了，right左移；

去重的点：
1）在i遍历的时候，如果nums[i]和nums[i-1]相同，则略过
2）在每轮遍历和等于零时，left和right需要一直移动，直到不重复。

奇怪的解法

66. 加一

普通的数组移位，当有进位或最后一位的时候需要加一。

public int[] plusOne(int[] digits) {
       int len = digits.length;
       boolean over = false;

       for(int i =  len - 1;i >= 0;i--){
           int num = digits[i];
           if(over || i == len - 1){
               num += 1;
           } 
           if(num < 10){
               digits[i] = num;
               over = false;
               break;
           } else{
               digits[i] = 0;
               over = true;
           }
       }
       if(over){
           int[] newdigits = new int[len + 1];
           newdigits[0] = 1;
           return newdigits;
       }
       return digits;
   }

189. 旋转数组

这个方法基于这个事实：当我们旋转数组 k 次， k%n 个尾部元素会被移动到头部，剩下的元素会被向后移动。
所以分三步：

1. 数组所有数反转
2. 反转前k个
3. 反转后n-k个

public void swap(int[] nums, int start, int end){
        int temp = nums[end];
        nums[end] = nums[start];
        nums[start] = temp;
    }

    public void rotatePart(int[] nums, int start, int end){
        while(start < end){
            swap(nums, start, end);
            start++; end--;
        }
    }

    public void rotate(int[] nums, int k) {
        int len = nums.length;
        if(len == 0 || len == 1 || k == 0) return;
        if(k >= len){
            k = k % len;
        }
        
        rotatePart(nums, 0, len - 1);
        rotatePart(nums, 0, k - 1) ;
        rotatePart(nums, k, len - 1);
    }

动态规划PART

70. 爬楼梯

类似斐波那契数列，尝试几个：

f(0) = 1
f(1) = 1
f(2) = f(1) + f(0)
f(3) = f(2) + f(1)
f(4) = f(3) + f(2)

可以发现规律，f(n)只与f(n-1)和f(n-2)有关，因此不需要开辟数组存表，只需要弄两个变量存上次和上上次的值就行了。

public int climbStairs(int n) {
        int ll = 1;
        int l = 1;
        int result = 0;
        if(n <= 1)  return 1;

        for(int i = 2;i <= n;i++){
            result = ll + l;
            l = ll;
            ll =  result;
        }
        return result;
    }

链表PART

21. 合并两个有序链表

链表题，主要是指针的移动，以及非空的判断，记得在挂节点的时候要用一个指针指向下一个节点保留它的位置，头结点也需要一个指针记录位置。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode psmall;
        ListNode plarge;
        ListNode start;
        if(l1 == null)  return l2;
        if(l2 == null)  return l1;

        if(l1.val < l2.val){
            psmall = l1;
            plarge = l2;
            start =  l1;
        } else{
            psmall = l2;
            plarge = l1;
            start = l2;
        }

        while(psmall != null && plarge != null){
            if(psmall.val <= plarge.val){
                if(psmall.next != null){
                    if(psmall.next.val > plarge.val){
                        // Append plarge
                        ListNode plargeNext = plarge.next;
                        plarge.next = psmall.next;
                        psmall.next = plarge;
                        plarge = plargeNext;
                        psmall = psmall.next;
                    }else{
                        psmall = psmall.next;
                    }
                } else{
                    psmall.next = plarge;
                    break;
                }
            }
        }
        return start;
    }

142. 环形链表 II

之前用双指针法判断链表是否有环，两个指针一块一慢，一个走两格，一个走一格，快追慢，如果有环，是一定追的上的。
这道题增加了需要返回环入口的节点位置要求。需要走两轮，第一轮用快慢两个指针检查是否有环，第二轮用走一步的指针找到入口位置。
设置 a 为链表头到环入口的节点数，b为环的节点数。
慢指针走过的路程为s=a + b
快指针走过的路程为f = a + nb
同时由于快指针每次走两步，慢指针每次走一步，当他们相遇时一定满足：f = 2s
结合上面三个式子，可以得出：s = nb 和 f=2nb
接下来考虑怎样走才能找到入口，如果从头一直走的话，走到入口的步数为a + nb（只要走过a之后一直绕圈就行了），而现在s已经走过nb，因此只要再走过a就可以了。
于是在第二轮，让fast从head开始，跟slow一起走，当他们相遇时，fast一定走过了a步，他们俩也就同时停在了入口，返回即可。

public ListNode detectCycle(ListNode head) {
        // Round1: Check if there is a loop.

        ListNode slow = head;
        ListNode fast = head;

        while(fast != null){
            if(slow.next != null){
                slow = slow.next;
            } else{
                return null;
            }
            if(fast.next != null){
                if(fast.next.next != null){
                    fast = fast.next.next;
                } else{
                    return null;
                }
            } else{
                return null;
            }
            
            if(slow == fast)    break;
        }
        // fast move to the end, no loop
        if(fast == null)    return null;
        else{
            // Round2: Find start index.
            fast = head;
            while(fast != null){
                if(fast == slow)    return fast;
                fast = fast.next;
                slow = slow.next;
            }
        }
        return null;
    }