1.分汤

题目：

有 A 和 B 两种类型的汤。一开始每种类型的汤有 N 毫升。有四种分配操作：

提供 100ml 的汤A 和 0ml 的汤B。
提供 75ml 的汤A 和 25ml 的汤B。
提供 50ml 的汤A 和 50ml 的汤B。
提供 25ml 的汤A 和 75ml 的汤B。
当我们把汤分配给某人之后，汤就没有了。每个回合，我们将从四种概率同为0.25的操作中进行分配选择。如果汤的剩余量不足以完成某次操作，我们将尽可能分配。当两种类型的汤都分配完时，停止操作。

注意不存在先分配100 ml汤B的操作。

需要返回的值： 汤A先分配完的概率 + 汤A和汤B同时分配完的概率 / 2。

思路：动态规划，dp[i][j] 表示 A 的汤为i， B 的汤为j 的时候，结果的概率。 状态转移方程

dp[i][j] = 0.25 * (dp[i-4][j] + dp[i-1][j-1] + dp[i-2][j-2] + dp[i-1][j-3]);
初始条件 dp[0][0] = 0.5; dp[0]j = 1; dp[i]0 = 0;
因为每次都是25ml 增加和减少，所以可以把 N / 25 来处理，当无法整除的时候，要加1，因为 多出来那部分，必须进行到下一轮下一部分

时间复杂度O(1)，空间复杂度O(1)。因为最多500次

/**
 * @param {number} N
 * @return {number}
 */
var soupServings = function(N) {
  let num = Math.ceil(N / 25);
  if (num >= 500) {
    return 1.0;
  }
  const dp = new Array(num + 1).fill("").map(() => new Array(num + 1).fill(0));
  dp[0][0] = 0.5;
  for (let i = 1; i <= num; i++) {
    dp[0][i] = 1;
  }
  for (let i = 1; i <= num; i++) {
    for (let j = 1; j <= num; j++) {
      dp[i][j] =
        0.25 *
        (dp[i - 4 > 0 ? i - 4 : 0][j] +
          dp[i - 3 > 0 ? i - 3 : 0][j - 1 > 0 ? j - 1 : 0] +
          dp[i - 2 > 0 ? i - 2 : 0][j - 2 > 0 ? j - 2 : 0] +
          dp[i - 1 > 0 ? i - 1 : 0][j - 3 > 0 ? j - 3 : 0]);
    }
  }
  return dp[num][num];

};

2.情感丰富的文字

题目：

有时候人们会用重复写一些字母来表示额外的感受，比如 "hello" -> "heeellooo", "hi" -> "hiii"。我们将相邻字母都相同的一串字符定义为相同字母组，例如："h", "eee", "ll", "ooo"。

对于一个给定的字符串 S ，如果另一个单词能够通过将一些字母组扩张从而使其和 S 相同，我们将这个单词定义为可扩张的（stretchy）。扩张操作定义如下：选择一个字母组（包含字母 c ），然后往其中添加相同的字母 c 使其长度达到 3 或以上。

例如，以 "hello" 为例，我们可以对字母组 "o" 扩张得到 "hellooo"，但是无法以同样的方法得到 "helloo" 因为字母组 "oo" 长度小于 3。此外，我们可以进行另一种扩张 "ll" -> "lllll" 以获得 "helllllooo"。如果 S = "helllllooo"，那么查询词 "hello" 是可扩张的，因为可以对它执行这两种扩张操作使得 query = "hello" -> "hellooo" -> "helllllooo" = S。

输入一组查询单词，输出其中可扩张的单词数量。

思路：双指针。字符串要扩张得到目标字符串，条件有两个，一个是字符的相对顺序要一样。因为只能复制字符，不能新增字符。二是连续的字符长度如果不相同时，一定要大于等于3
所以可以双指针按顺序比较，然后记录当前这个相连的相同字符数量l1和l2.
l1表示S的相同相连字符数量，l2表示数组中当前字符串的相同相连字符数量
在遍历时，首先比较当前位置的字符是否相同，不同则直接返回false；、
然后得到当前的l1和l2，如果l2>l1，那么也是直接返回false
如果l1!==l2且l1===2，说明不能满足大于等于3，也是返回false
其他情况则可以扩张，进入下一轮遍历
时间复杂度O(n*(max(m,k)))，空间复杂度O(1) n是数组长度，m和k是S的长度和数组中单词长度的最大值

/**
 * @param {string} S
 * @param {string[]} words
 * @return {number}
 */
var expressiveWords = function(S, words) {
  const l = S.length;
  return words.filter((item) => {
    const s1 = item.length;
    if (s1 >= l) return false;
    let i1 = 0,
      i2 = 0;
    let l1, l2;
    while (i1 < l && i2 < s1) {
      l1 = 1;
      l2 = 1;
      if (S[i1] !== item[i2]) return false;
      while (S[i1] === S[i1 + 1]) {
        i1++;
        l1++;
      }
      while (item[i2] === item[i2 + 1]) {
        i2++;
        l2++;
      }
      if (l2 > l1) return false;
      if (l1 !== l2 && l1 === 2) return false;
      i1++;
      i2++;
      continue;
    }
    if (i1 !== l || i2 !== s1) return false;
    return true;
  }).length;
};

3.最大平均值的和分组

题目：

我们将给定的数组 A 分成 K 个相邻的非空子数组 ，我们的分数由每个子数组内的平均值的总和构成。计算我们所能得到的最大分数是多少。

注意我们必须使用 A 数组中的每一个数进行分组，并且分数不一定需要是整数。

思路：

建立dp数组，dp[i][j]表示分为i组时，0-j的元素的平均值的最大和
那么对于所有的i<=m<j,有
dp[i][j]=max(dp[i][j],dp[i-1][m]+(∑(m->j)/(j-m))，
也就是分组少一次时的结果加上后续剩余元素的平均值，的最大值

时间复杂度O(m*n2)，空间复杂度O(mn)

/**
 * @param {number[]} A
 * @param {number} K
 * @return {number}
 */
var largestSumOfAverages = function(A, K) {
  const l = A.length;
  const sum = new Array(l).fill(0);
  sum[0] = A[0];
  for (let i = 1; i < l; i++) {
    sum[i] = sum[i - 1] + A[i];
  }
  const dp = new Array(K + 1).fill("").map(() => new Array(l).fill(0));
  for (let i = 0; i < l; i++) {
    dp[1][i] = sum[i] / (i + 1);
  }
  for (let i = 1; i <= K; i++) {
    dp[i][i - 1] = sum[i - 1];
  }
  for (let i = 2; i <= K; i++) {
    for (let j = i; j < l; j++) {
      for (let m = j - 1; m >= i - 2; m--) {
        dp[i][j] = Math.max(
          dp[i][j],
          dp[i - 1][m] + (sum[j] - sum[m]) / (j - m)
        );
      }
    }
  }
  return dp[K][l - 1];
};

4.二叉树剪枝

题目：

给定二叉树根结点 root ，此外树的每个结点的值要么是 0，要么是 1。

返回移除了所有不包含 1 的子树的原二叉树。

( 节点 X 的子树为 X 本身，以及所有 X 的后代。)

思路：dfs。两种方式：dfs的函数可以返回当前子树的非0节点的数量，然后判断左右子树如果非0节点数量是0，那么子树为null，

时间复杂度O(n) 空间复杂度O(h)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var pruneTree = function(root) {
  const dfs = (root) => {
    if (!root) return 0;
    const left = dfs(root.left);
    const right = dfs(root.right);
    if (!left) {
      root.left = null;
    }
    if (!right) {
      root.right = null;
    }
    return left + right + (root.val === 0 ? 0 : 1);
  };
  dfs(root);
  if (!root.val && !root.left && !root.right) return null;
  return root;
};

也可以直接返回结果。如果左右结果是null且当前节点是0，那么当前节点返回null

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var pruneTree = function(root) {
  const dfs = (root) => {
    if (!root) return null;
    root.left = dfs(root.left);
    root.right = dfs(root.right);
    if (!root.val && !root.left && !root.right) return null;
    return root;
  };
  return dfs(root);
};

5.模糊坐标

题目：

我们有一些二维坐标，如 "(1, 3)" 或 "(2, 0.5)"，然后我们移除所有逗号，小数点和空格，得到一个字符串S。返回所有可能的原始字符串到一个列表中。

原始的坐标表示法不会存在多余的零，所以不会出现类似于"00", "0.0", "0.00", "1.0", "001", "00.01"或一些其他更小的数来表示坐标。此外，一个小数点前至少存在一个数，所以也不会出现“.1”形式的数字。

最后返回的列表可以是任意顺序的。而且注意返回的两个数字中间（逗号之后）都有一个空格。

思路：分治法。先分成左右两部分，然后分别枚举小数点的位置

时间复杂度O(n3)空间复杂度O(n3)

/**
 * @param {string} S
 * @return {string[]}
 */
var ambiguousCoordinates = function(S) {
  const ans = []
  const len = S.length
  for (let i = 2; i < len; i++) {
    const left = S.substring(1, i)
    const right = S.substring(i, len - 1)
    if ((left.length > 1 && +left === 0) || (right.length > 1 && +right === 0)) continue
    for (let num1 of getNums(left)) {
      for (let num2 of getNums(right)) {
        ans.push('(' + num1 + ', ' + num2 + ')')
      }
    }
  }
  return ans

  function getNums(str) {
    const len = str.length
    const set = new Set()
    if (len === 1) {
      set.add(parseInt(str))
    } else {
      for (let i = 1; i <= len; i++) {
        const left = str.substring(0, i)
        const right = str.substring(i)
        if ((+left + '').length !== left.length) break
        if ((+right === 0 && right.length !== 0) || right[right.length - 1] === '0') continue
        const num1 = left + '.' + right
        set.add(+num1)
      }
    }
    return set
  }

};