手写算法: 组合总和

39. 组合总和

思路

分析题意，因为说可以无限制重复被选取，所以首先要考虑到回溯的问题。

1. 那么就应该想到根的结构，往下遍历再向上

2. 构建 dfs 函数，传入 start, temp, sum

3. 每次判断 sum 和 target

• 如果 sum ＞ target， return
• 如果 sum === target， 则将当前的比师复制到 result 中，结束循环

4. 遍历数组，每次从 start 开始，前面的数之前已经遍历过，忽略。

拿到当前的数，与差值相比，如果大于差值，不符合要求，直接退出前循环。

5. 把当前值塞入 temp 中，继续向下遍历。

6. 遍历完向上回溯，直到所有都走完、return result.

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
  let result = [];
  const dfs = (start, temp, sum) => {
    if (sum > target) return;
    if (sum === target) {
      result.push(temp.slice());
      return;
    }
    // 枚举当前可选的数，从start开始
    for (let i = start; i < candidates.length; i++) {
      // 选定当前这个数
      const item = candidates[i];
      // 如果当前的数大于差值，则不符合条件，中断此次循环
      if (item > target - sum) continue;
      // 推入临时路径
      temp.push(item);
      // 继续向下遍历，从i开始，下一次不会用i之前的数
      dfs(i, temp, sum + item);
      // 深度遍历完后，回缩到上一层，继续遍历同层右边的元素
      temp.pop();
    }
  };
  dfs(0, [], 0);
  return result;
};

手写题: 创建 LazyMan()

130. 创建 LazyMan()

注意测试用例，先等待后输出

// interface Laziness {
//   sleep: (time: number) => Laziness
//   sleepFirst: (time: number) => Laziness
//   eat: (food: string) => Laziness
// }

/**
 * @param {string} name
 * @param {(log: string) => void} logFn
 * @returns {Laziness}
 */
function LazyMan(name, logFn) {
  // your code here
  let commands = [['greet', name]];

  let actions = {
    greet: name => logFn(`Hi, I'm ${name}.`),
    eat: food => logFn(`Eat ${food}.`),
    sleep: async time => {
      await new Promise(resolve => {
        setTimeout(resolve, time * 1000);
      });
      logFn(`Wake up after ${time} second${time > 1 ? 's' : ''}.`);
    },
  };

  Promise.resolve().then(exec);

  async function exec() {
    for (const [action, param] of commands) {
      await actions[action](param);
    }
  }

  return {
    eat(food) {
      commands.push(['eat', food]);
      return this;
    },
    sleep(time) {
      commands.push(['sleep', time]);
      return this;
    },
    sleepFirst(time) {
      commands.unshift(['sleep', time]);
      return this;
    },
  };
}

LazyMan('Jack', console.log)
  .eat('banana')
  .sleep(10)
  .eat('apple')
  .sleep(1);