525. 连续数组

• 日期：2021/6/3
• 难度：中等
• 思路：给一个只有0和1的数组，找拥有相同个的0和1的最长数组。设置一个状态变量now，遍历数组，遇到0就-1，遇到1则+1，状态相同时，中间含有0和1的个数相同。用map记住now在不同数字下最前面的下标，用当前下标减去最前下标，不断更新res。

function findMaxLength(nums: number[]): number {
  let now = 0, res = 0;
  let mapp = new Map();
  mapp.set(0,-1);
  for(let i=0;i< nums.length; i++) {
    if(nums[i]) {
      now++;
    } else {
      now--;
    }
    if(mapp.has(now)) {
      res = Math.max(res, i - mapp.get(now));
    } else {
      mapp.set(now, i);
    }
  }
  return res;
};

1049. 最后一块石头的重量 II

• 日期：2021/6/8
• 难度：中等
• 思路：给出n个数，数字之间可以消除。如果x == y，则不剩下；如果x > y，则剩下x-y，问最后剩下数字最小为多少。设数字总和为total，avg = toal / 2，把数字分两组，每组的总和尽可能可靠近avg。需要对数字进行总和不超过avg筛选，转化为value = weight的背包问题。

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeightII = function(stones) {
  const n = stones.length
  let total = 0
  for (let i = 0; i < n; i++) {
    total += stones[i]
  }
  const avg = total >> 1
  let dp = new Array(avg + 1).fill(0)
  for (let i = 0; i < n; i++) {
    for (let j = avg; j >= stones[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i])
    }
  }
  return(total - 2 * dp[avg])
};

Q.E.D.