5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad" Output: "bab" Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd" Output: "bb"

思考路程 1 算法时间复杂度O（n²）空间复杂度O（n）

/**
 * @param {string} s
 * @return {string}
 */
export default (s) => {
  let len = s.length;
  if (!s) return "";
  if (len <= 1) return s;

  let arr = [];
  let start = 0;
  let end = s.length;
  let max = 0;

  // arr[j] 表示上一次遍历存储的是否是回文，复用这个arr空间，不断进行覆盖
  // 比如abcba
  // i = 5, j = 5 arr[5] = true
  // i = 4, j = 5 arr[5] = false
  // i = 4, j = 4 arr[4] = true
  // i = 3, j = 5 arr[5] = false
  // i = 3, j = 4 arr[4] = false
  // i = 3, j = 3 arr[3] = false
  // i = 2, j = 5 arr[5] = false
  // i = 2, j = 4 arr[4] = true
  // i = 2, j = 3 arr[3] = false
  // i = 2, j = 2 arr[2] = true
  // i = 1, j = 5 arr[5] = true 复用上一次的arr[4]
  for (let i = len - 1; i >= 0; i--) {
    for (let j = len - 1; j >= i; j--) {
      arr[j] = s.charAt(i) === s.charAt(j) && (j - i <= 2 || arr[j - 1]);
      if (arr[j] && j - i + 1 > max) {
        start = i;
        end = j + 1;
        max = j - i + 1;
      }
    }
  }

  return s.substring(start, end);
};

72. Edit Distance

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

Insert a character
Delete a character
Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution" Output: 5 Explanation: intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u')

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
export default (word1, word2) => {
  // dp
  let dp = [];
  const s1 = word1.length;
  const s2 = word2.length;
  for (let i = 0; i <= s1; i++) {
    dp[i] = [];
  }
  // dp[i][j] 代表长度为i的字符串word1，到长度为j的字符串word2需要经过最小改变次数
  for (let i = 0; i <= s1; i++) {
    for (let j = 0; j <= s2; j++) {
      dp[i][j] = 0;
    }
  }

  for (let i = 0; i <= s1; i++) {
    dp[i][0] = i;
  }

  for (let i = 0; i <= s2; i++) {
    dp[0][i] = i;
  }

  for (let i = 1; i <= s1; i++) {
    for (let j = 1; j <= s2; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
      }
    }
  }
  return dp[s1][s2];
};

小朋友过河问题

小朋友过桥问题：在一个夜黑风高的晚上，有n（n <= 50）个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不大于两人通过，他们只有一个手电筒，所以每次过桥的两个人需要把手电筒带回来，i号小朋友过桥的时间为T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。

思考
假设前i个人过河花费的最少时间为opt[i]，那么考虑前i-1个人过河的情况，即河这边还有1个人，河那边有i-1个人，并且这时候手电筒肯定在对岸，
所以opt[i] = opt[i-1] + a[1] + a[i] (让花费时间最少的人把手电筒送过来，然后和第i个人一起过河)

如果河这边还有两个人，一个是第i号，另外一个无所谓，河那边有i-2个人，并且手电筒肯定在对岸，所以opt[i] = opt[i-2] + a[1] + a[i] + 2*a[2] (让花费时间最少的人把电筒送过来，然后第i个人和另外一个人一起过河，由于花费时间最少的人在这边，所以下一次送手电筒过来的一定是花费次少的，送过来后花费最少的和花费次少的一起过河，解决问题)

所以 opt[i] = min{opt[i-1] + a[1] + a[i] , opt[i-2] + a[1] + a[i] + 2*a[2] }。

这里为什么只考虑两种情况呢？
为什么不考虑河这边有三个人，因为可以根据opt[1]和opt[2]就可以确定所有的了。

时间复杂度 O(n), 空间复杂度O（1）

export default (numsArr = [], n = 50) => {
  if (numsArr.length === 1) return numsArr[0];

  numsArr.sort((a, b) => a - b);

  // opt[i] 表示i个人过河的最短时间
  // pre 表示i-2个人过河的最短时间，preNext表示i-1个人过河的最短时间
  let pre = numsArr[0];
  let preNext = numsArr[1];

  for (let i = 2; i < n; i++) {
    let temp = Math.min(preNext + numsArr[0] + numsArr[i], pre + numsArr[0] + numsArr[i] + 2 * numsArr[1]);
    pre = preNext;
    preNext = temp;
  }
  return preNext;
};

01 背包问题

有 N 件物品和一个容量为 V 的背包。第 i 件物品的体积是 Ci，其价值是 Wi。求解，在不超过背包容量情况下，将哪些物品装入背包可使价值总和最大。

思考 1 f[i][v]表示前 i 种物品恰好放入一个容量为 v 的背包可以获得的最大价值。决策为第 i 个物品在前 i-1 个物品放置完毕后，是选择放还是不放，状态转移方程为：

f[i][v] = max{ f[i-1][v], f[i-1][v – ci] +Wi }

时间复杂度 O(VN)，空间复杂度 O(VN) （空间复杂度可利用滚动数组进行优化达到 O(V) ）

export default (n, v, cArr = [], wArr = []) => {
  // 设置n个物品，res[i][v] 表示把i个物品放到空间为v的背包中
  let res = [];
  for (let i = 0; i <= n; i++) {
    res[i] = [];
  }
  for (let i = 0; i <= n; i++) {
    for (let j = 0; j <= v; j++) {
      res[i][j] = 0;
    }
  }
  // 把1个物品放到0-v的空间里边，获取动态规划的初始值
  for (let i = 0; i <= v; i++) {
    for (let j = 0; j < wArr.length; j++) {
      if (wArr[j] > res[1][i] && cArr[j] <= i) {
        res[1][i] = wArr[j];
      }
    }
  }
  // i 表示n个物品
  // j表示背包的体积
  //
  for (let i = 0; i <= n; i++) {
    for (let j = 0; j <= v; j++) {
      if (i >= 1 && j >= cArr[i - 1]) {
        res[i][j] = Math.max(res[i - 1][j], res[i - 1][j - cArr[i - 1]] + wArr[i - 1]);
      }
    }
  }
  return res[n][v];
};

国王和金矿

有一个国家发现了 5 座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是 10 人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？

金矿储存量 [500,200,300,350,400] 需要人数 [5, 3 , 4, 3 , 5]

// m 表示人数，n表示金矿的数量 时间复杂度O(m*n) 空间复杂度O（m）

// 金矿的数量n，工人数设为m，每个金矿的含有的金子数量为g[],采集每个金矿需要的人数为p[]
export default (n, m, g = [], p = []) => {
  let preResults = [];
  let res = [];

  // for(let i = 0; i<=m;i++) {

  // }
  for (let i = 0; i <= m; i++) {
    if (i < p[0]) {
      preResults[i] = 0;
    } else {
      preResults[i] = g[0];
    }
  }

  // 金矿数
  for (let i = 2; i <= n; i++) {
    // 工人数
    for (let j = 0; j <= m; j++) {
      if (j < p[i - 1]) {
        res[j] = preResults[j];
      } else {
        if (j >= p[i - 1] && i >= 1) {
          const _temp = preResults[j - p[i - 1]] || 0;
          res[j] = Math.max(preResults[j], _temp + g[i - 1]);
        }
      }
    }
    if (i < n) {
      preResults = [...res];
    }
  }
  // console.log(res);

  return res[m];
};

1277. Count Square Submatrices with All Ones

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] Output: 15 Explanation: There are 10 squares of side 1. There are 4 squares of side 2. There is 1 square of side 3. Total number of squares = 10 + 4 + 1 = 15.

Example 2:

Input: matrix = [ [1,0,1], [1,1,0], [1,1,0] ] Output: 7 Explanation: There are 6 squares of side 1. There is 1 square of side 2. Total number of squares = 6 + 1 = 7.

Constraints:

1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1

思考
1 二维数组 matrix，如果用动态规划，肯定是 dp[i][j],然后就是找出状态转移方程.
2 dp[i][j] 表示以 matrix[i][j]右下结尾的构成的正方形的边长
比如

matrix          dp
[0, 1, 1, 1]    [0, 1, 1, 1]
[1, 1, 1, 1] => [1, 1, 2, 2]
[0, 1, 1, 1]    [0, 1, 2, 3]

3 然后把 dp 每个值相加就可以了， 这里需要注意的比如 dp[2][3] = 3，不仅表示 dp[2][3] 此时可以组成一个长度为 3 的正方形， 同时也表示如果把 matrix[2][3]加入进来的时候，因为 dp[2][3]，此时有一个边长为 3 的正方形，所以此时肯定比没有加入 matrix[2][3]的时候，多一个一个长度为 3 的正方形，一个长度为 2 的正方形，一个长度为 1 的正方形，所以一共多了 3 个正方形，所以 dp[2][3]同时代表了如果把 matrix[2][3]加入的时候，多出来了几个正方形。

时间复杂度 O（mn）空间复杂度 O（1）

338. Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example 1:

Input: 2 Output: [0,1,1]

Example 2:

Input: 5 Output: [0,1,1,2,1,2]

Follow up:

It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

思考 1 dp[i] 和 dp[i-1]的关系, 很简单 dp[i] = dp[i-1].push(n 中含有 1 的个数)
这里有个诀窍就是 n & n-1 中含有 1 的个数等于 n 中含有 1 的个数+1
count1bitNum(n & n-1) = count1bitNum(n) - 1
比如 count1bitNum(6 & 5) = count1bitNum(6) - 1 =>count1bitNum(4) = count1bitNum(6) - 1

为什么呢？
因为 n&n-1 就是相当于去掉 n 的最后一个 1，比如 6 & 5 = 110 & 101 = 100，刚好去掉 6 也就是 110 的最后一个 1

时间复杂度 O（n）空间复杂度 O（n）

/**
 * @param {number} num
 * @return {number[]}
 */
// const get1num = (n) => {
//   let ret = 0;
//   while (n > 0) {
//     ret += n & 1;
//     n >>= 1;
//   }
//   return ret;
// };
// 根据 get1num(n & n-1) + 1 = get1num(n) => res[n & n-1] + 1 = res[n]
export default (num) => {
  if (num === 0) return [0];
  if (num === 1) return [0, 1];
  let res = [0, 1];
  for (let i = 2; i <= num; i++) {
    res.push(res[i & (i - 1)] + 1);
  }
  return res;
};

97. Interleaving String

Given s1, s2, and s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" Output: false

Example 3:

Input: s1 = "", s2 = "", s3 = "" Output: true

Constraints:

0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1, s2, and s3 consist of lower-case English letters.

思考
1 dp[i][j] 等于s1中i的位置和s2中j位置的字符组成的s3,所以就是找到状态转移方程，
dp[i][j] = (dp[i-1][j] & s3[i+j-1] == s1[i-1]) || (dp[i][j-1] & s2[j-1] == s3[i+j-1])
然后找到初始值dp[0][0] = true;

/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
export default (s1, s2, s3) => {
  if (!s1 && !s2 && !s3) return true;
  if (s3.length !== s1.length + s2.length) return false;
  let dp = [];
  for (let i = 0; i <= s1.length; i++) {
    dp[i] = [];
  }
  dp[0][0] = true;
  for (let i = 0; i <= s1.length; i++) {
    for (let j = 0; j <= s2.length; j++) {
      if (i >= 1 && j >= 1) {
        dp[i][j] = (dp[i - 1][j] && s1[i - 1] === s3[i + j - 1]) || (dp[i][j - 1] && s3[i + j - 1] === s2[j - 1]);
      } else if (i >= 1 && j < 1) {
        dp[i][j] = dp[i - 1][j] && s1[i - 1] === s3[i + j - 1];
      } else if (i < 1 && j >= 1) {
        dp[i][j] = dp[i][j - 1] && s3[i + j - 1] === s2[j - 1];
      }
    }
  }
  // console.log(dp);
  return dp[s1.length][s2.length];
};

902. Numbers At Most N Given Digit Set

Given an array of digits, you can write numbers using each digits[i] as many times as we want. For example, if digits = ['1','3','5'], we may write numbers such as '13', '551', and '1351315'.

Return the number of positive integers that can be generated that are less than or equal to a given integer n.

Example 1:

Input: digits = ["1","3","5","7"], n = 100 Output: 20 Explanation: The 20 numbers that can be written are: 1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

Example 2:

Input: digits = ["1","4","9"], n = 1000000000 Output: 29523 Explanation: We can write 3 one digit numbers, 9 two digit numbers, 27 three digit numbers, 81 four digit numbers, 243 five digit numbers, 729 six digit numbers, 2187 seven digit numbers, 6561 eight digit numbers, and 19683 nine digit numbers. In total, this is 29523 integers that can be written using the digits array.

Example 3:

Input: digits = ["7"], n = 8 Output: 1

Constraints:

1 <= digits.length <= 9
digits[i].length == 1
digits[i] is a digit from '1' to '9'.
All the values in digits are unique.
1 <= n <= 109

/**
 * @param {string[]} digits
 * @param {number} n
 * @return {number}
 */
// digits 是有序的
export default (digits, n) => {
  let NS = "" + n;
  let dsize = digits.length;
  let digit = NS.length;
  let res = 0;
  // 先计算出所有小于n位数的总和
  for (let i = 1; i < digit; i++) {
    res += Math.pow(dsize, i);
  }
  // 利用dp，计算有多少个和n同样位数的数字的个数
  // 比如["3", "4", "5", "6"], 64
  // 放置3在第一位，则3，4，5，6可以随便放在第二位
  // 放置4在第一位，则3，4，5，6可以随便放在第二位
  // 放置5在第一位，则3，4，5，6可以随便放在第二位
  // 放置6在第一位的时候，这个时候，需要跳出循环，继续下一位的比较,这时候就变成了第一位放置了6，然后看下一位放啥
  // 因为第一位已经固定了6，则只剩下一位了
  // 放置3在第二位，成立
  // 放置4在第二位，因为4 === 4，所以两者相同，继续跳出
  // 最后循环结束
  // 这是典型的数字dp算法
  for (let i = 0; i < digit; i++) {
    let hasSamePre = false;
    for (let j = 0; j < dsize; j++) {
      if (digits[j] < NS[i]) {
        res += Math.pow(dsize, digit - i - 1);
      } else if (digits[j] === NS[i]) {
        hasSamePre = true;
        break;
      }
    }
    if (!hasSamePre) return res;
  }
  return res + 1;
};

871. Minimum Number of Refueling Stops

A car travels from a starting position to a destination which is target miles east of the starting position.

Along the way, there are gas stations. Each station[i] represents a gas station that is station[i][0] miles east of the starting position, and has station[i][1] liters of gas.

The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses 1 liter of gas per 1 mile that it drives.

When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.

What is the least number of refueling stops the car must make in order to reach its destination? If it cannot reach the destination, return -1.

Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there. If the car reaches the destination with 0 fuel left, it is still considered to have arrived.

Example 1:

Input: target = 1, startFuel = 1, stations = [] Output: 0 Explanation: We can reach the target without refueling.

Example 2:

Input: target = 100, startFuel = 1, stations = [[10,100]] Output: -1 Explanation: We can't reach the target (or even the first gas station).

Example 3:

Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]] Output: 2 Explanation: We start with 10 liters of fuel. We drive to position 10, expending 10 liters of fuel. We refuel from 0 liters to 60 liters of gas. Then, we drive from position 10 to position 60 (expending 50 liters of fuel), and refuel from 10 liters to 50 liters of gas. We then drive to and reach the target. We made 2 refueling stops along the way, so we return 2.

Note:

1 <= target, startFuel, stations[i][1] <= 10^9
0 <= stations.length <= 500
0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target

/**
 * @param {number} target
 * @param {number} startFuel
 * @param {number[][]} stations
 * @return {number}
 */
export default (target, startFuel, stations) => {
  if (startFuel >= target) return 0;
  // dp[i] 表示路上停留i次可以到达的最长距离
  let dp = [];
  dp[0] = startFuel;

  // for (int i = 0; i < s.length; ++i)
  // for (int t = i; t >= 0 && dp[t] >= s[i][0]; --t)
  // dp[t + 1] = Math.max(dp[t + 1], dp[t] + s[i][1]);

  for (let i = 0; i < stations.length; ++i) {
    // 为了避免重复的，假如从0到i计算的话，假设dp[1] = 100, 在计算dp[2]的时候，不能重复在计算dp[1]的时候，选择的
    // 加油站，也就是每个加油站只能计算一次
    for (let j = i; j >= 0 && dp[j] >= stations[i][0]; j--) {
      if (!dp[j + 1]) dp[j + 1] = 0;
      dp[j + 1] = Math.max(dp[j + 1], dp[j] + stations[i][1]);
    }
  }
  for (let i = 0; i < dp.length; i++) {
    if (dp[i] >= target) return i;
  }

  return -1;
};

96. Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

Example:

Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's:

1 3 3 2 1 \ / / / \
3 2 1 1 3 2 / / \
2 1 2 3

Constraints:

1 <= n <= 19

思考 1 涉及到树的都可以使用递归

算法时间复杂度 O(n*n) 空间复杂度O（n）

/**
 * @param {number} n
 * @return {number}
 */
export default (n) => {
  let g = new Array(n + 1);
  // g[i] 表示有i个元素可以表示的搜索二叉树数目
  g[0] = 1;
  g[1] = 1;
  g.fill(0, 2, n + 1);
  for (let i = 2; i <= n; i++) {
    // g[i] 等于小于所有小于i的数的二叉搜索树的个数和所有大于i的二叉搜索树的个数的和
    for (let j = 1; j <= i; j++) {
      g[i] += g[j - 1] * g[i - j];
    }
  }
  return g[n];
};

91. Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1 'B' -> 2 ... 'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

思考 1 很容易得出 dp[i] = dp[i-2] + dp[i-1], 也就是最后两位当做一个数的次数和最后一位当做一个数的次数， 然后 dp[1] = 1，dp[2] = 2 并且 str!== "10", 当 str==="10"的时候，应该 dp[2]=1

/**
 * @param {string} s
 * @return {number}
 */
const map = {
  A: 1,
  B: 2,
  C: 3,
  D: 4,
  E: 5,
  F: 6,
  G: 7,
  H: 8,
  I: 9,
  J: 10,
  K: 11,
  L: 12,
  M: 13,
  N: 14,
  O: 15,
  P: 16,
  Q: 17,
  R: 18,
  S: 19,
  J: 20,
  U: 21,
  V: 22,
  W: 23,
  X: 24,
  Y: 25,
  Z: 26,
};
export default (s) => {
  let dp = [];
  if (s === "0") return 0;
  dp[0] = 0;
  if (s.charAt(0) === "0") {
    dp[1] = 0;
  } else {
    dp[1] = 1;
  }
  if (s.length >= 2) {
    let _s = s.substring(0, 2);
    if (_s === "10" || _s === "20") {
      dp[2] = 1;
      dp[1] = 0;
    } else if (+_s >= 1 && +_s <= 26 && s.charAt(0) !== "0") {
      dp[2] = 2;
    } else if (+_s > 26 && s.charAt(1) !== "0") {
      dp[2] = 1;
    } else if (+_s > 26 && s.charAt(1) === "0") {
      return 0;
    } else {
      dp[2] = 0;
    }
  }
  for (let i = 2; i < s.length; i++) {
    if (s.charAt(i) === "0") {
      if (s.charAt(i - 1) !== "0" && +s.substring(i - 1, i + 1) < 27) {
        dp[i + 1] = dp[i - 1];
      } else {
        return 0;
      }
    } else {
      console.log(+s.substring(i - 1, i + 1));
      if (+s.substring(i - 1, i + 1) > 26 || s.charAt(i - 1) === "0") {
        dp[i + 1] = dp[i];
      } else {
        dp[i + 1] = dp[i - 1] + dp[i];
      }
    }
  }
  console.log(dp);
  return dp[s.length];
};

85. Maximal Rectangle

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] Output: 6 Explanation: The maximal rectangle is shown in the above picture.

Example 2:

Input: matrix = [] Output: 0

Example 3:

Input: matrix = [["0"]] Output: 0

Example 4:

Input: matrix = [["1"]] Output: 1

Example 5:

Input: matrix = [["0","0"]] Output: 0

Constraints:

rows == matrix.length
cols == matrix.length
0 <= row, cols <= 200
matrix[i][j] is '0' or '1'.

思考 1 首先一行一行的计算，计算出每行其中的数字为 1 的矩形，left[i][j]表示 i，j 位置为 1 的时候，矩形的最左边的起始位置， right[i][j]表示 i，j 位置为 1 的时候，矩形的最右边的结束位置，height[i][j]表示这个矩形的高度。

比如 matrix 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0

1 第一行计算， height 0 0 0 1 1 0 0 这个很明显，当只有一行的时候，组成的矩形的高度肯定等于每个元素 left 0 0 0 3 3 0 0 这里如果只有一行，那如果组成矩形，最左边开始的位置肯定就是第一个等于 1 的位置，而后面的，比如 matrix[0][4] 肯定是继续向前面寻找，知道找到连续的第一个等于 1 的元素，也就是 matrix[0][3]，所以如果 matrix[0][4]组成的矩形，肯定最左边是 matrix[0][3] right 7 7 7 5 5 7 7 右边从右边开始寻找，如果等于 0，那肯定不能组成矩形的右边，则让它等于每行的长度，直到发现等于 1 的时候，则等于当前的 index+1，因为是计算矩形面积，（right-left）* height

第二行计算 height 0 0 1 2 2 0 0 高度很好计算，就是每一行的 1 的高度 left 0 0 1 2 2 0 0 这里也很好理解，比如 matirx[1][3]的时候，如果只有一行，则 left[3] 等于 1，但是因为是要组成一个矩形，就得考虑上一行的，因为上一行是 3，所以如果包含 matirx[1][3]的矩形，开始位置得是 3，这里可以得出 left 的递推公式 left[i][j] = Math.max(left[i-1][j], cur_left) cur_left 就是当前这一行，如果包含 left[i][j]的开始位置 right 7 7 5 5 5 7 7 这里 right 从右边开始计算，如果等于 0，则让它等于这一行的宽度，如果等于 1，则找到最右边连续是 1 的位置，比如 matrix[1][2] 等于 min(right[0][2], 5) 5 等于这一行包含 matrix[1][2]连续是 1 的最右边的位置， 所以 matrix[i][j] 等于 min(right[i-1][j], cur_right) cur_right 等于这一行包含 matrix[i][j]连续是 1 的最右边的位置

/**
 * @param {character[][]} matrix
 * @return {number}
 */

export default (matrix) => {
  if (matrix.length === 0) return 0;
  if (matrix.length === 1 && matrix[0].length === 1) return matrix[0][0];
  let height = new Array(matrix[0].length);
  let left = new Array(matrix[0].length);
  let right = new Array(matrix[0].length);
  let max = 0;
  height.fill(0);
  left.fill(0);
  right.fill(matrix[0].length);

  for (let i = 0; i < matrix.length; i++) {
    let cur_left = 0;
    let cur_right = matrix[i].length;
    for (let j = 0; j < matrix[i].length; j++) {
      if (matrix[i][j] === "1") {
        height[j] = height[j] + 1;
        left[j] = Math.max(left[j], cur_left);
      } else {
        left[j] = 0;
        cur_left = j + 1;
        height[j] = 0;
      }
    }
    for (let j = matrix[i].length - 1; j >= 0; j--) {
      if (matrix[i][j] === "1") {
        right[j] = Math.min(right[j], cur_right);
      } else {
        right[j] = matrix[i].length;
        cur_right = j;
      }
    }
    for (let j = 0; j < matrix[i].length; j++) {
      if ((right[j] - left[j]) * height[j] > max) {
        max = (right[j] - left[j]) * height[j];
      }
    }
  }
  return max;
};

213. House Robber II

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [2,3,2] Output: 3 Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Example 2:

Input: [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.

思考 1 如果没有环，是很好的解决的，可是加上环，自己就没想到如何解决了。 看了解答，才知道直接转化成简单的两个数组就好了，也就是抢劫第一家和不抢劫第一家，然后就变成了两个数组了，如果是抢劫第一家，则肯定是不抢劫最后一家，如果不抢劫第一家，则肯定抢劫最后一家。

为什么没有想到呢？ 转化，根据已经知道的，解决不知道了，先找到问题，然后定义好问题。

export default (nums) => {
  if (nums.length === 0 || !nums) return 0;
  if (nums.length === 1) return nums[0];
  if (nums.length > 1) {
    return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
  }
};

function rob(nums, begin, end) {
  if (nums.length === 0 || !nums) return 0;
  let dp = [];
  dp[begin] = nums[begin];
  dp[begin + 1] = Math.max(nums[begin], nums[begin + 1]);
  for (let i = begin + 2; i <= end; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }
  return dp[end];
}

139. Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"] Output: true Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] Output: false

思考
1 动态规划一般是一维数组或者是两维数组，比如这题中存在一个s和wordDict，很明显是使用一维数组，既然有两个，一个是s，还有一个是wordDict，肯定是有一个不变，然后另外一个变化 所以这里可以尝试wordDict不变，s变化，或者尝试s变化，wordDict不变，思考后，发现如果wordDict变化的话，有些逻辑问题，也就是很多测试用例通不过。

所以这里让s变化，dp[i] 表示s(0,i)是否可以被wordDict表示，所以那dp[i+1]可以想到如果j到i+1可以组成的单词，存在wordDict中，同时dp[j]为true，则dp【i+1]肯定也为true

2 其实最容易想到的递归，但是如果用js写递归，很容易就时间超时了，所以可以设置一些条件，节省时间。

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
const wordBreak = (s, wordDict) => {
  let res = false;
  if (wordDict.length === 1) {
    return wordDict[0] === s;
  }
  for (let i = 0; i < wordDict.length; i++) {
    let tempS = s;
    let res1 = true;
    if (s.indexOf(wordDict[i]) === -1) continue;
    tempS = tempS.replace(new RegExp(wordDict[i], "gi"), ",");
    let temps1 = tempS.replace(new RegExp(wordDict[i], "gi"), "");
    let nexWorDict = wordDict.slice(0, i).concat(wordDict.slice(i + 1));
    if (!temps1) {
      res1 = true;
    } else {
      for (let j = 0; j < tempS.split(",").length; j++) {
        const _st = tempS.split(",")[j];
        if (_st && nexWorDict.length > 0) {
          res1 = res1 && wordBreak(_st, nexWorDict);
        }
      }
    }
    res = res || res1;
    if (res) return res;
  }
  return res;
};

export default wordBreak;

不递归，用dp解决

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
const wordBreak = (s, wordDict) => {
  // dp[i]表示s[0, i]是否可以被wordDict表示
  let dp = [];
  // dp[]
  dp[0] = true;
  for (let i = 1; i <= s.length; i++) {
    dp[i] = false;
    for (let j = 0; j <= i; j++) {
      console.log(s.substring(j, i));
      if (dp[j] && wordDict.includes(s.substring(j, i))) {
        dp[i] = true;
      }
    }
  }
  return dp[s.length];
};

export default wordBreak;

140. Word Break II

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "catsanddog" wordDict = ["cat", "cats", "and", "sand", "dog"] Output: [ "cats and dog", "cat sand dog" ]

Example 2:

Input: s = "pineapplepenapple" wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] Output: [ "pine apple pen apple", "pineapple pen apple", "pine applepen apple" ] Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog" wordDict = ["cats", "dog", "sand", "and", "cat"] Output: []

const helper = function (table, idx, path, res) {
  if (idx < 0) {
    res.push(path);
    return;
  }
  // 得到word
  const words = table[idx];

  for (let i = 0; i < words.length; i++) {
    let newPath = path ? words[i][1] + " " + path : words[i][1];
    helper(table, words[i][0], newPath, res);
  }
};
/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {string[]}
 */
const wordBreak = function (s, wordDict) {
  let dp = [];

  for (let i = 0; i < s.length; i++) {
    dp[i] = [];
  }
  // dp[i]表示到i的时候，以i为结束的单词
  // 因为dp[i]是个数组，所以数组的长度表示以i为结束的单词数量
  // dp[i]中每个元素的也是一个长度为2的数组，第一个元素表示单词的起始位置，第二个元素表示单词
  // 经过该循环后，就形成了一个类似链表的数组
  for (let i = 0; i < s.length; i++) {
    if (i === 0 || dp[i - 1].length) {
      wordDict.forEach((word) => {
        if (s.substring(i, i + word.length) === word) {
          dp[i + word.length - 1].push([i - 1, word]);
        }
      });
    }
  }

  if (!dp[s.length - 1].length) return [];

  //back-tracking to get all values

  let res = [],
    path = "";

  helper(dp, s.length - 1, path, res);

  return res;
};
export default wordBreak;

44. Wildcard Matching

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like ? or *.

Example 1:

Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa" p = "" Output: true Explanation: '' matches any sequence.

Example 3:

Input: s = "cb" p = "?a" Output: false Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

Input: s = "adceb" p = "ab" Output: true Explanation: The first '' matches the empty sequence, while the second '' matches the substring "dce".

Example 5:

Input: s = "acdcb" p = "a*c?b" Output: false

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
export default (s, p) => {
  let sStart = 0;
  let pStart = 0;
  // * position in p
  let PstartIndex = -1;
  // s startIndex and PstartIndex next position
  let SstartIndex = 0;

  while (sStart < s.length) {
    if (pStart < p.length && (s.charAt(sStart) === p.charAt(pStart) || p.charAt(pStart) === "?")) {
      pStart++;
      sStart++;
    } else if (pStart < p.length && p.charAt(pStart) === "*") {
      PstartIndex = pStart;
      pStart++;
      SstartIndex = sStart;
      // if sStart  === s.length-1 but get false, restart
    } else if (PstartIndex !== -1) {
      // SstartIndex++;
      SstartIndex++;
      sStart = SstartIndex;
      pStart = PstartIndex + 1;
    } else {
      return false;
    }
  }

  while (pStart < p.length && p.charAt(pStart) === "*") {
    pStart++;
  }
  return pStart >= p.length;
};

903. Valid Permutations for DI Sequence

We are given S, a length n string of characters from the set {'D', 'I'}. (These letters stand for "decreasing" and "increasing".)

A valid permutation is a permutation P[0], P[1], ..., P[n] of integers {0, 1, ..., n}, such that for all i:

If S[i] == 'D', then P[i] > P[i+1], and;
If S[i] == 'I', then P[i] < P[i+1].

How many valid permutations are there? Since the answer may be large, return your answer modulo 10^9 + 7.

Example 1:

Input: "DID" Output: 5 Explanation: The 5 valid permutations of (0, 1, 2, 3) are: (1, 0, 3, 2) (2, 0, 3, 1) (2, 1, 3, 0) (3, 0, 2, 1) (3, 1, 2, 0)

Note:

1 <= S.length <= 200
S consists only of characters from the set {'D', 'I'}.

/**
 * @param {string} S
 * @return {number}
 */
export default (S) => {
  let dp = [];
  const len = S.length;
  const mod = Math.pow(10, 9) + 7;
  // S=DID
  // len = 4,所以这里有0，1，2，3四个数字需要放置，
  // dp[i][j] 表示i个数字放置完毕，在剩下的数字里边选择第j位的个数
  // 比如d[3][0] 表示在0，1，2，3中已经选择了三个数字，按照DID的要求已经放置完毕了，然后在剩下的数字里边选择位置为0的数字
  for (let i = 0; i <= len; i++) {
    dp[i] = [];
  }
  // 因为有0，1，2，3 四个数字
  // dp[0][0] = 1, [0]
  // dp[0][1] = 1, [1]
  // dp[0][2] = 1, [2]
  // dp[0][3] = 1, [3]
  for (let i = 0; i <= len; i++) {
    dp[0][i] = 1;
  }
  // 计算dp[len][0]
  for (let i = 0; i < len; i++) {
    if (S.charAt(i) == "I") {
      // 因为已经有i个数字已经被放置好了
      // 比如当i=0的时候，一共需要放0，1，2，3，i=0，就是已经0的位置上已经放置了一个了，
      // 也就是说还有三个数字需要放置，也就是len-i
      for (let j = 0, cur = 0; j < len - i; j++) {
        // 取模
        cur = cur + dp[i][j];
        if (cur > mod) {
          cur = cur % mod;
        }
        dp[i + 1][j] = cur;
      }
    } else {
      // 当S.charAt(i) == "D"的时候，也就是需要降序，
      // 比如有0， 1，2，3， 如果需要放置dp[1][2],则只有一种可能，那就是等于dp[0][3],
      // 不然如果放置了dp[1][2]的时候，在2的位置放置的元素肯定比前面的大，也就是不符合S.charAt(i) == "D"
      for (let j = len - i - 1, cur = 0; j >= 0; j--) {
        cur = cur + dp[i][j + 1];
        if (cur > mod) {
          cur = cur % mod;
        }
        dp[i + 1][j] = cur;
      }
    }
  }
  return dp[len][0];
};

467. Unique Substrings in Wraparound String

Consider the string s to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so s will look like this: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....". // unique 唯一 Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.

Note: p consists of only lowercase English letters and the size of p might be over 10000.

Example 1:

Input: "a" Output: 1

Explanation: Only the substring "a" of string "a" is in the string s.

Example 2:

Input: "cac" Output: 2 Explanation: There are two substrings "a", "c" of string "cac" in the string s.

Example 3:

Input: "zab" Output: 6 Explanation: There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.

/**
 * @param {string} p
 * @return {number}
 */
// 主要思想就是发现s中是连续的"zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxy"，
// 如果发现在p中所有连续的以z，a,b,c。。。结束的字符串的长度等于我们要求的解
export default (p) => {
  if (!p) return 0;
  if (p.length === 1) {
    return 1;
  }
  const dp = new Array(26);
  dp.fill(0);

  for (let i = 0; i < p.length; i++) {
    dp[p.charCodeAt(i) - 97] = 1;
  }
  // console.log(dp);
  let maxCount = 0;
  for (let i = 0; i < p.length; i++) {
    // if (i === 0) {
    //   dp[p.charCodeAt(0) - 97] = 1;
    // }

    if (p.charCodeAt(i) - p.charCodeAt(i - 1) === 1 || p.charCodeAt(i - 1) - p.charCodeAt(i) === 25) {
      maxCount++;
    } else {
      maxCount = 1;
    }
    // console.log(maxCount);
    dp[p.charCodeAt(i) - 97] = Math.max(dp[p.charCodeAt(i) - 97], maxCount);
  }
  // console.log(dp);
  return dp.reduce((a, b) => a + b);
};