1. 寻找数组的中心索引 724题 easy

思路：由于可能会存在多个中心索引，我们返回的是第一个。。。
所以从左至右递推，index指针从0向右移动，随之改变left right的和，得到首处left===right即可。

  1. var pivotIndex = function(nums) {
  2.     let index = 0
  3.     let left = 0
  4.     let result = -1;
  5.     let right = nums.reduce((acc,curr)=>{acc+=curr;return acc},0)-nums[0]
  6.     while(index<=nums.length-1){
  7.         if(left===right){
  8.             result = index
  9.             break
  10.         }
  11.         left += nums[index]
  12.         right -= nums[index+1]
  13.         index++
  14.     }
  15.     return result
  16. };

2. 至少是其他数字两倍的最大数 747题 easy

查找数组中的最大元素是否至少是数组中每个其他数字的两倍。
思路：

  • 先找最大的，然后再逐次判断是否为两倍
    • 迭代两次，好蠢
  • 迭代一次，找到最大与次大的元素即可

3. 加一 66题 Easy

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
输入: [1,2,3]
输出: [1,2,4]

思路：

  • 直接在数组上操作，但是有进位的问题
  • 转化成数字做加减然后再拆分，但是又大数运算的问题
    • 6145390195186705543+1 = 6145390195186705000

用do while把第一次很蠢的代码优化了一下，执行效果好多了

  1. const plusOne = function(digits) {
  2.   let carryFlag = false;
  3.   let index = digits.length - 1;
  4.   do {
  5.     if (index < 0) {
  6.       return [1].concat(digits);
  7.     }
  8.     if (digits[index] < 9) {
  9.       digits[index] += 1;
  10.       return digits;
  11.       carryFlag = false;
  12.     }
  13.     digits[index] = 0;
  14.     carryFlag = true
  15.     index -= 1;
  16.   } while (carryFlag === true);
  17.   // 首次判断是否需要进位
  18. };

4. 颜色分类 75题 middle

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
原地对它们进行排序
这个题目只规定数字只有0，1，2
你能想出一个仅使用常数空间的一趟扫描算法吗？

  • 计数排序的思想
    • 先扫描一次记录数字+个数，再输出
    • 每一个数的增加 都需要格外的空间来存储，且会扫描两趟
  1. var sortColors = function(nums) {
  2.     let zeroCount = 0;
  3.     let oneCount = 0;
  4.     let twoCount = 0;
  5.     nums.forEach((num)=>{
  6.         num===0 && (zeroCount +=1);
  7.         num===1 && (oneCount +=1);
  8.         num===2 && (twoCount +=1);
  9.     })
  10.     let result = new Array(nums.length)
  11.     nums.fill(0,0,zeroCount)
  12.     nums.fill(1,zeroCount,zeroCount+oneCount)
  13.     nums.fill(2,zeroCount+oneCount,zeroCount+oneCount+twoCount)
  14. };
  • 三路快排，这里我还没找到比较好的资料

5. 数组中的第K个最大元素 215题 middle

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
我的思路：维护一个降序[a,b,c,d]的队列，最小的在末尾，如果有大于最小值的，加入到队列中，挤出最小值。
这样的复杂度 是 n*排序算法(数据量为K)
三路快排是最快的

6. 合并两个有序数组 88题 easy

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]
我的思路：要充分利用好两个数组的有序性，将总个数少的数组的元素依次插入另一个数组中。
[1,2,3,2,5,6]