算法 - 数组 - 简单

解法思想：

首位指针：[]
快慢指针: [1、]
解决局部延伸到全局：[4、]

1、删除排序数组中的重复项（原地替换的思想）

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1:

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

解答：

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

2、买卖股票的最佳时机 II（画图找规律）

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 
这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 
这笔交易所能获得利润 = 6-3 = 3 。

解答：

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let result = 0
    for(let i = 1; i < prices.length; i++){
        if(prices[i] > prices[i-1]){
            result += prices[i] - prices[i - 1]
        }
    }
    return result
};

3、只出现一次的数字（异或运算符的使用）

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]输出: 1

解答：

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let init = nums[0];
    for(let i = 1; i < nums.length; i++){
        init ^=  nums[i];
    }
    return init;
};

4、最长公共前缀（提取公共字符串的方法）

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

**

var longestCommonPrefix = function (strs) {
  if (strs.length === 0) return ''
  if (strs.length === 1) return strs[0];
  return strs.reduce(getSameStr, strs[0]);
};
function getSameStr(a, b) {
  let res = ''
  for (let j = 0; j < a.length; j++) {
    if (a[j] === b[j]) {
      res += a[j];
    } else {
      return res;
    }
  }
  return res
}

5、按奇偶排序数组 II（找规律题）

给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。

对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。

示例：

输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

解法（非原地解法）：

/**
 * @param {number[]} A
 * @return {number[]}
 */
var sortArrayByParityII = function(A) {
    const ret = [];
    const odd = [];
    const even = [];
    for(let i = 0; i < A.length; i++){
        if(A[i] & 1){
            odd.push(A[i]);
        } else {
            even.push(A[i]);
        }
    }
    for( let i = 0 ; i < A.length / 2 ; i++ ){
        ret.push(even[i] , odd[i])
    }
    return ret;
};

6、合并两个有序数组（双指针法）

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

说明：

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例：

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

解答：

var merge = function (nums1, m, nums2, n) {
  let len = m + n - 1;
  m--, n--;
  while (m >= 0 && n >= 0) {
    if (nums1[m] > nums2[n]) {
      nums1[len] = nums1[m--]
    } else {
      nums1[len] = nums2[n--]
    }
    len--;
  }
  if(m === -1){
    return nums1.splice(0, len+1, ...nums2.slice(0, n + 1));
  }
  if(n === -1){
    return nums1;
  }
};

7、两数之和(难度在如何一次遍历解决问题)

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

实现：

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

8、岛屿的周长（土地相交时的规律,训练二维数组）

给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。

网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例 1：

输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边

代码：

var islandPerimeter = function (grid) {
  let border = 0;
  let land = 0;
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === 1) {
        land++;
        if (i < grid.length - 1 && grid[i + 1][j] === 1) {
          border++
        }
        if (j < grid[0].length - 1 && grid[i][j + 1] === 1) {
          border++
        }
      }
    }
  }
  return 4 * land - 2 * border;
};

9、键盘行（数组方法filter和every的运用）

给定一个单词列表，只返回可以使用在键盘同一行的字母打印出来的单词。键盘如下图所示。

示例：

输入: ["Hello", "Alaska", "Dad", "Peace"]
输出: ["Alaska", "Dad"]

解答：**

var findWords = function(words) {
    let obj = {
      q:0, w:0, e:0, r:0, t:0, y:0, u:0, i:0, o:0, p:0,
      a:1, s:1, d:1, f:1, g:1, h:1, j:1, k:1, l:1,
      z:2, x:2, c:2, v:2, b:2, n:2, m:2
    }
    return words.filter(item => {
        item = item.toLowerCase()
      let num = obj[item[0]]
      return item.split('').every(t => obj[t] === num)
    })
  };

10、杨辉三角（金字塔数组的规律，比如grid[i][0]和grid[i][i]的关系）

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:

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

**
解法：

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
  if (numRows === 0) { return [] }
  const result = Array.from(new Array(numRows), () => [])
  for (let i = 0; i < numRows; i++) {
    result[i][0] = 1; result[i][i] = 1;
    for (let j = 1; j < i; j++) {
      result[i][j] = result[i - 1][j - 1] + result[i - 1][j]
    }
  }
  return result
};

11、两个数组的交集（技巧，利用map减少同一数组的多次遍历）

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

解答：

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    const map1 = {};
    const res = [];
    for(let i = 0; i < nums1.length; i++){
        map1[nums1[i]] = true;
    }
    for(let i = 0; i < nums2.length; i++){
        if(map1[nums2[i]]){
            res.push(nums2[i])
            map1[nums2[i]] = false
        }
    }
    return res;
};

12、1比特与2比特字符(找规律)

有两种特殊字符。第一种字符可以用一比特0来表示。第二种字符可以用两比特(10 或 11)来表示。
现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符。给定的字符串总是由0结束。

示例 1:

输入: 
bits = [1, 0, 0]
输出: True
解释: 
唯一的编码方式是一个两比特字符和一个一比特字符。所以最后一个字符是一比特字符。

示例 2:

输入: 
bits = [1, 1, 1, 0]
输出: False
解释: 
唯一的编码方式是两比特字符和两比特字符。所以最后一个字符不是一比特字符。

解答：

/**
 * @param {number[]} bits
 * @return {boolean}
 */
var isOneBitCharacter = function(bits) {
    let last1count = 0;
    for (let i = bits.length - 2; i >= 0; i--) {
        if(bits[i] === 1) {
            last1count++;
        } else {
            break;
        }
    }
    return last1count % 2 === 0 
};

13、最大子序和（动态规划）

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
  let res = nums[0];
  const dp = [nums[0]];
  for(let i=1;i < nums.length;i++){
      if(dp[i-1]>0){
        dp[i]=nums[i]+dp[i-1]
      }else{
       dp[i]=nums[i]
      }

    res=Math.max(dp[i],res)
  }
    return res
};

14、最小栈（专门用一个栈存最小值）

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

示例:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

解答：

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.stack = [];
    this.minStack = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stack.push(x);
    if(this.minStack.length === 0 || x < this.minStack[this.minStack.length - 1]){
        this.minStack.push(x)
    } else {
         this.minStack.push( this.minStack[this.minStack.length - 1])
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    this.stack.pop();
    this.minStack.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.minStack[this.stack.length - 1];
};

15、外观数列（递归）

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

countAndSay(1) = “1”
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221

第一项是数字 1 
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"

解答：

/**
 * @param {number} n
 * @return {string}
 */
var countAndSay = function(n) {
    if(n === 1) return '1';
    return generatorCount(countAndSay(n-1));

};
function generatorCount(n){
    let initStr = n[0];
    let a =''
    for(let i = 0; i < n.length; i++){
        if(n[i] === n[i+1]){
            initStr += n[i+1]
        }else{
            a += initStr.length + initStr[0];
            initStr = n[i+1];
        }
    }
    return a;
}

16、棒球比赛 （栈的典型应用）

你现在是一场采特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。

比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：

整数 x - 表示本回合新获得分数 x
“+” - 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。
“D” - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。
“C” - 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。
请你返回记录中所有得分的总和。

示例 1：

输入：ops = ["5","2","C","D","+"]
输出：30
解释：
"5" - 记录加 5 ，记录现在是 [5]
"2" - 记录加 2 ，记录现在是 [5, 2]
"C" - 使前一次得分的记录无效并将其移除，记录现在是 [5].
"D" - 记录加 2 * 5 = 10 ，记录现在是 [5, 10].
"+" - 记录加 5 + 10 = 15 ，记录现在是 [5, 10, 15].
所有得分的总和 5 + 10 + 15 = 30

解答：

/**
 * @param {string[]} ops
 * @return {number}
 */
var calPoints = function(ops) {
    const stack = [];
    for(let i = 0, len = ops.length; i < len; i++){
        switch(ops[i]){
            case 'C':
                stack.pop();
                break;
            case 'D':
                stack.push(stack[stack.length - 1] * 2);
                break;
            case '+':
                const pop = stack.pop();
                const value = +pop + +stack[stack.length - 1];
                stack.push(pop);
                stack.push(value);
                break;
            default:
                stack.push(ops[i]);
        }
    }
    return stack.reduce((a, b)=>(+a)+(+b));
};

17、下一个更大元素 I（单调栈的典型应用）

给定两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

示例 1:

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
    对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
    对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
    对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。

18、 判定字符是否唯一（set应用场景之一）

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
示例 1：
输入: s = “leetcode”
输出: false

示例 2：
输入: s = “abc”
输出: true

解法：

/**
 * @param {string} astr
 * @return {boolean}
 */
var isUnique = function(astr) {
    return new Set(astr).size === astr.length;
};

19、剑指 Offer 03. 数组中重复的数字

找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

解法：

/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
    const map = {};
    for(let item of nums){
        if(map[item]){
            return item;
        } else {
            map[item] = true;
        }
    }
    return false;
};

20、螺旋矩阵(熟练运用while和for循环遍历，以及对二维数组对控制)

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

示例 2:

输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

解法：

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function (matrix) {
  if (matrix.length == 0) return []
  const res = []
  let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
  let num = 1, total = matrix[0].length * matrix.length;
  while (num <= total) {
    for (let i = left; num <= total && i <= right; i++) {res.push(matrix[top][i]);num++}
    top++
    for (let i = top; num <= total && i <= bottom; i++) {res.push(matrix[i][right]);num++}
    right--
    for (let i = right; num <= total && i >= left; i--) {res.push(matrix[bottom][i]); num++}
    bottom--
    for (let i = bottom; num <= total && i >= top; i--) {res.push(matrix[i][left]);num++}
    left++
  }
  return res
};

21、查找常用字符(先解决两个元素之间如何计算，推而广之到数组每一个元素)

给定仅有小写字母组成的字符串数组 A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。例如，如果一个字符在每个字符串中出现 3 次，但不是 4 次，则需要在最终答案中包含该字符 3 次。

你可以按任意顺序返回答案。

示例 1：
输入：[“bella”,”label”,”roller”]
输出：[“e”,”l”,”l”]
示例 2：

输入：[“cool”,”lock”,”cook”]
输出：[“c”,”o”]

解法：

/**
 * @param {string[]} A
 * @return {string[]}
 */
const getCommon = (a, b) => {

  // 设置哈希映射存储字母出现次数
  const map = new Map();

  // 遍历 a 字符串，并存储字母及其次数
  for (let i = 0; i < a.length; i++) {
    const aData = map.get(a[i]);
    if (!aData) {
      map.set(a[i], 1);
    } else {
      map.set(a[i], aData + 1);
    }
  }

  // 设置共同字符串
  const result = [];

  // 遍历 b 字符串，将其含有和 a 相同的取出来
  for (let i = 0; i < b.length; i++) {
    const bData = map.get(b[i]);
    if (bData) {
      result.push(b[i]);
      map.set(b[i], bData - 1);
    }
  }

  // 返回结果

  return result;
};

/**
 * @name 主函数
 * @param {string[]} A 需要判断的数组
 * @return {string[]} 返回相同字符串组成的数组
 */
const commonChars = (A) => {
  return A.reduce(getCommon)
};

22、按奇偶排序数组 II（双数组）

给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。

对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。

示例：

输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

解法：

/**
 * @param {number[]} A
 * @return {number[]}
 */
// 非原地解法
var sortArrayByParityII = function(A) {
    const ret = [];
    const odd = [];
    const even = [];
    for(let i = 0; i < A.length; i++){
        if(A[i] & 1){
            odd.push(A[i]);
        } else {
            even.push(A[i]);
        }
    }
    for( let i = 0 ; i < A.length / 2 ; i++ ){
        ret.push(even[i] , odd[i])
    }
    return ret;
};

23、转置矩阵(加深对二维数组的理解)

给定一个矩阵 A， 返回 A 的转置矩阵。

矩阵的转置是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。

示例 1：

输入：[[1,2,3],[4,5,6],[7,8,9]]
输出：[[1,4,7],[2,5,8],[3,6,9]]
示例 2：

输入：[[1,2,3],[4,5,6]]
输出：[[1,4],[2,5],[3,6]]

/**
 * @param {number[][]} A
 * @return {number[][]}
 */
var transpose = function(A) {
    return Array.from({ length: A[0].length }, (_, index) => A.map((_)=> _[index]))
};

24、两数之和 II - 输入有序数组

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

解法：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let l = 0;
    let r = nums.length - 1;
    while(l < r){
        let sum = nums[l] + nums[r];
        if(sum === target){
            return [l+1, r+1]
        } else if(sum > target){
            r--
        } else {
            l++
        }
    }
    return [-1, -1]
};

25、有效的山脉数组

给定一个整数数组 A，如果它是有效的山脉数组就返回 true，否则返回 false。

让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：

A.length >= 3
在 0 < i < A.length - 1 条件下，存在 i 使得：
A[0] < A[1] < … A[i-1] < A[i]
A[i] > A[i+1] > … > A[A.length - 1]


示例 1：

输入：[2,1]
输出：false
示例 2：

输入：[3,5,5]
输出：false
示例 3：

输入：[0,3,2,1]
输出：true

解法：

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var validMountainArray = function (arr) {
  let i = 0
  let len = arr.length
  while (i + 1 < len && arr[i] < arr[i + 1]) {
    i++
  }
  if (i === 0 || i + 1 === len) return false
  while (i + 1 < len && arr[i] > arr[1 + i]) {
    i++
  }
  return i + 1 === len
}

26、一维数组的动态和

给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。

请返回 nums 的动态和。

示例 1：

输入：nums = [1,2,3,4]
输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。
示例 2：

输入：nums = [1,1,1,1,1]
输出：[1,2,3,4,5]
解释：动态和计算过程为 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] 。
示例 3：

输入：nums = [3,1,2,10,1]
输出：[3,4,6,16,17]

解答：

function runningSum<T extends number[]>(nums: T): T {
    let sum = 0
    for(let i = 0; i < nums.length; i++){
        nums[i] = (sum += nums[i])      
    }
    return nums
};

27、斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。

示例 1：

输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

function fib(n: number): number {
    const dp: number[] = []
    dp[0] = 0; dp[1] = 1; let i:number = 2;
    if( i ===0 || i === 1) return i;
    for(; i <= n; i++){
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
};

28、移动零

难度简单929
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

1. 必须在原数组上操作，不能拷贝额外的数组。
2. 尽量减少操作次数。

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

    return nums
};

29、有多少小于当前数字的数字(排序能知道比自己小或者大的数字有多少)

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。
换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。
以数组形式返回答案。

示例 1：
输入：nums = [8,1,2,2,3]
输出：[4,0,1,1,3]
解释：
对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。
对于 nums[1]=1 不存在比它小的数字。
对于 nums[2]=2 存在一个比它小的数字：（1）。
对于 nums[3]=2 存在一个比它小的数字：（1）。
对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。

示例 2：
输入：nums = [6,5,4,8]
输出：[2,1,0,3]

解法：

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var smallerNumbersThanCurrent = function(nums) {
    const map = {}
    const nums2 = [...nums]
    nums2.sort((a, b) => a-b);
    for(let i = nums2.length - 1; i >= 0 ; i--){
        map[nums2[i]] = i
    }
    for(let i = 0; i < nums.length; i++){
        nums[i] = map[nums[i]]
    }
    return nums;
};

30、有序数组的平方（排序方法的运用）

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

解法：

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
    nums.sort((a, b)=> Math.abs(a) - Math.abs(b))
    for(let i = 0; i < nums.length; i++){
        nums[i] = Math.pow(nums[i], 2)
    }
    return nums
};

31、搜索插入位置（典型二分查找）

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2

示例 2:
输入: [1,3,5,6], 2
输出: 1

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let i = 0;
    let j = nums.length - 1;
    while(i <= j){
        const index = i + j >> 1
        let middleNum = nums[index]
        if(middleNum === target){
            return index
        } else if (middleNum > target){
            j = index - 1
        } else {
            i = index + 1
        }
    }
    return i
};