作业

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

可以设立双指针（一快一慢）。快指针不断++。当快指针和慢指针的元素不相等时，将快指针指向的元素赋值给慢指针的下一个元素：

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let j = 0;
    for(let i = 1; i < nums.length; i++) {
        if(nums[i] !== nums[j]) {
            nums[j+1] = nums[i]
            j++
        }
    }
    return j + 1
};

189. 旋转数组

2种解法：

• 在数组最后截取出来k个元素，然后 unshift 到数组头部
• 遍历k次，每次弹出数组最后一个放在最前面

  /**
  * @param {number[]} nums
  * @param {number} k
  * @return {void} Do not return anything, modify nums in-place instead.
  */
  var rotate = function(nums, k) {
    for(let i = 0; i < k; i++) {
        nums.unshift(nums.pop())
    }
    return nums
  };

21. 合并两个有序链表

该题可以使用递归法：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, 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
    }
};

88. 合并两个有序数组

测试用例：

[3, 5, 0, 0, 0]
2
[1, 2, 6]
3

设立三个指针：p1，p2，p。分别指向 nums1数组自身实际存在最后一个值的下标，nums2数组自身实际存在最后一个值的下标，两个数组合并后的总长度最后一个值下标。

按照从后向前进行遍历。如果p2的值大于p1的值，那么放在nums1的最后面 (替换0)；如果小于或者等于，则将p1自身的值复制到p指针的位置。跑完一遍while后：

3, 5, 3, 5, 6

因为p2是慢指针，只有值存到了p1内才会继续移动。所以此时p2指针指向了nums2的1号下标。

此时需要手动矫正，将nums1内从0开始，删除下标为1及其之前的元素；然后将nums2内剩余没复制过去的元素，复制过去（index为1）

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    let p1 = m - 1;
    let p2 = n - 1;
    let p = m + n - 1;
    while(p1 > -1 && p2 > -1) {
        nums1[p--] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--]
    }
    nums1.splice(0, p2 + 1)
    nums1.unshift(...nums2.splice(0, p2 + 1))
};

1. 两数之和

本题借助Map表的思维，将target和当前值的差值存放为key(数组index)。向后遍历过程中，如果当前遍历到的值在Map表内，则代表有相对差值，匹配成功。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let map = [];
    for (let i = 0; i < nums.length; i++) {
        let dis = target - nums[i];
        if (map[nums[i]] === undefined) {
            map[dis] = i
        } else {
            return [map[nums[i]], i]
        }
    }
};

283. 移动零

设立快慢指针，慢指针指向0的位置，快指针不断向后指。如果找到不是0的元素，则和慢指针交换元素。如果这两个指针没重叠，则将快指针的位置设置为0

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let j = 0;
    let i = 0;
    while(i < nums.length) {
        if (nums[i] !== 0) {
            nums[j] = nums[i]
            if (i !== j) {
                nums[i] = 0
            }
            j++
        }
        i++
    }
    return nums
};

66. 加一

将数字数组从后向前遍历。数字挨个+1。

• 如果加1后的数字➗10取余数为0，则代表要进位，继续向前遍历+1。
• 如果取余数不为0，则代表不需要进位。直接返回数组即可
• 如果碰上999，9999，999999这种数字，倒序循环后并不会生成最高位的1，则需要手动补1

  /**
  * @param {number[]} digits
  * @return {number[]}
  */
  var plusOne = function(digits) {
    for (let i = digits.length - 1; i > -1; i--) {
        digits[i]++
        digits[i] = digits[i] % 10;
        if(digits[i] !== 0) {
            return digits
        }
    }
    return [1, ...digits]
  };