跳到主要内容

4 篇博文 含有标签「算法」

查看所有标签

· 阅读需 7 分钟

最近几天在学习算法方面的知识,在动态规划这块,想起了去年面试字节时二面的算法题,当时因为水平有限没有在面试中做出来,今天又重新做了一下,有所收获,在此记录.(有关这道题在CSDN上的题解简直狗屁不通,垃圾堆里果然都是垃圾,当然这道题在谷歌上也没有较为官方的题解,请读者带着思考的方式看题解,勿全信,如有不对之处,请在评论区指正)

猴子分香蕉​

题目​

动物园有猴山，每天需要给猴子们发香蕉,猴子会排队依次取食。猴子们铺张浪费,会多拿食物,但最多不会拿超过自身食量的二倍且不会超过当前还存在的香蕉的一半,最后—个猴子除外(即最后—个猴子可以拿完剩余的所有香蕉)。

最少需要准备多少香蕉,能保证所有猴子都能吃饱?

输入输出

[4,3] -> 8
[4,3,5] -> 18
[4,3,5,7] -> 28

分析​

先来理解题目意思,最少需要准备多少香蕉的隐含意思是不管前面的猴子怎么贪吃,多拿了不少香蕉,也要保证到最后一直猴子时,剩余的香蕉数量要满足猴子的食量,否则那最后一直猴子就会挨饿,不满足所有猴子都吃饱这一条件.理解这一点很重要.

从输入输出来倒推分析,以[4,3,5,7] -> 28这组数据为例. 取香蕉的策略是每只猴子都尽可能贪心多拿

  1. 首先28的一半为14,并且4*2为8,取小值8,因此第1只猴子取8,剩余20
  2. 20的一半为10,并且3*2为6,取小值6,因此第2只猴子取6,剩余14
  3. 14的一半为7,并且5*2为10,取小值7,因此第3只猴子取7,剩余7
  4. 到最后一直猴子,剩7给7,满足最后一只猴子的食量,猴子全部吃饱

假设准备的香蕉少于28,以27为例

  1. 首先27的一半为13.5,并且4*2为8,取小值8,因此第1只猴子取8,剩余19
  2. 19的一半为9,5,并且3*2为6,取小值6,因此第2只猴子取6,剩余13
  3. 13的一半为6.5,并且5*2为10,取小值6.5,因此第3只猴子取6.5,剩余6.5
  4. 到最后一直猴子,剩6.5给6.5, 6.5 < 7, 不满足最后一只猴子的食量,猴子无法全部吃饱

因此28确实是需要准备的最少香蕉数量

开始动态规划解题

  1. 首先定义状态,我们可以看到,不管那种情况,最后需要满足的条件都是最后一只猴子也要吃饱,也仅仅只需要吃饱,不需要多吃,因此预期上我们给最后一只猴子准备的香蕉数就是猴子本身的食量.由此可以看出这道题肯定是要倒着递推的.因此我们把dp[i]定义为要喂[i, ..., last]猴子需要的食物
  2. 根据题目给出的条件,推递推方程. dp[i]是[i, ..., last]猴子需要的食物, 那么dp[i+1]是[i+1, ..., last]猴子需要的食物 第i只猴子分的香蕉数就是dp[i] - dp[i+1], 猴子数组我们定为monkey,那么可以得到下面不等式
1. dp[i] - dp[i+1] <= 2*monkey[i] // 不会拿超过自身食量的二倍
2. dp[i] - dp[i+1] <= dp[i] / 2 // 不会超过当前还存在的香蕉的一半
3. dp[i] - dp[i+1] >= monkey[i] // 每只猴子吃饱不饿
4. 由2,3还可以推出 monkey[i]<= dp[i] / 2

整理得

dp[i] >= dp[i+1] + monkey[i]
dp[i] >= 2 * monkey[i]
dp[i] <= 2 * dp[i+1]
dp[i] <= dp[i+1] + 2 * monkey[i]

得递推公式

    dp[i] = Math.max(
      Math.min(2 * dp[i + 1], dp[i + 1] + 2 * monkey[i]),
      dp[i + 1] + monkey[i],
            monkey[i] * 2
    );

进一步分析,min当中的第二项其实已经保证了max第二项的肯定成立,因此max第二项其实是多余的,可以删去,最后得到递推公式

    dp[i] = Math.max(
      Math.min(2 * dp[i + 1], dp[i + 1] + 2 * monkey[i]),
            monkey[i] * 2
    );
  1. 最终代码
function giveBanana(monkey = []) {
  if (!monkey || !monkey.length) return 0;
  let dp = new Array(monkey.length).fill(0);
  dp[dp.length - 1] = monkey[dp.length - 1];
  for (let i = dp.length - 2; i >= 0; i--) {
    dp[i] = Math.max(
      Math.min(2 * dp[i + 1], dp[i + 1] + 2 * monkey[i]),
            monkey[i] * 2
    );
  }
  return dp[0];
}

console.log(giveBanana([4, 3])); // 8
console.log(giveBanana([4, 3, 5])); // 18
console.log(giveBanana([4, 3, 5, 7])); // 28

总结​

本题的主要的三个注意点

  1. 倒着推
  2. 状态的定义
  3. 获得递推方程较难

希望对网上搜索这道题的小伙伴有所帮助.

· 阅读需 5 分钟

模板​

// BFS 找到的路径一定是最短的，但代价就是空间复杂度比 DFS 大很多

// 计算从起点 start 到终点 target 的最近距离
function bfs(start, target) {
  const queue = []; // 核心数据结构
  const visited = new Set(); // 避免走回头路, 如果是对树处理就可以不需要visited了

  queue.push(start); // 将起点加入队列
  visited.add(start); // 记录扩散的步数
  let level = 0;

  while (queue.length) {
    const len = queue.length;
    /* 将当前队列中的所有节点向四周扩散 */
    for (let i = 0; i < len; i++) {
      const cur = queue.shift();
      /* 划重点：这里判断是否到达终点 */
      if (cur === target) {
        return level;
      }
      /* 将 cur 的相邻节点加入队列 */
      for (let x of cur.neighbors) {
        if (visited.has(x) === false) {
          queue.push(x);
          visited.add(x);
        }
      }
    }
    /* 划重点：更新步数在这里 */
    level++;
  }
}

真题​

二叉树的最小深度​

/*
 * @lc app=leetcode.cn id=111 lang=javascript
 *
 * [111] 二叉树的最小深度
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
  if (!root) return 0;
  const queue = [root];
  let depth = 1,
    cur;
  while (queue.length) {
    const len = queue.length;
    for (let i = 0; i < len; i++) {
      cur = queue.shift();
      if (!cur.left && !cur.right) return depth;
      cur.left && queue.push(cur.left);
      cur.right && queue.push(cur.right);
    }
    depth++;
  }
  return depth;
};

// @lc code=end

二叉树的层次遍历 II​

/*
 * @lc app=leetcode.cn id=107 lang=javascript
 *
 * [107] 二叉树的层次遍历 II
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
  if (!root) return [];
  let queue = [];
  let levelArr = [];
  let res = [];
  queue.push(root);
  queue.push("#");
  while (queue.length) {
    let p = queue.shift();
    if (p === "#") {
      res.push(levelArr);
      levelArr = [];
      queue.length && queue.push("#");
    } else {
      levelArr.push(p.val);
      p.left && queue.push(p.left);
      p.right && queue.push(p.right);
    }
  }
  return res.reverse();
};

打开转盘锁​

/*
 * @lc app=leetcode.cn id=752 lang=javascript
 *
 * [752] 打开转盘锁
 */

// @lc code=start
/**
 * @param {string[]} deadends
 * @param {string} target
 * @return {number}
 */
var openLock = function(deadends, target) {
  const deads = new Set(deadends);
  const queue = [];
  const visited = new Set();
  queue.push("0000");
  visited.add("0000");
  let step = 0,
    cur,
    len,
    i,
    j;

  while (queue.length) {
    len = queue.length;
    for (i = 0; i < len; i++) {
      cur = queue.shift();
      if (cur === target) return step;
      if (deads.has(cur)) continue;
      for (j = 0; j < 4; j++) {
        const up = addOne(cur, j);
        if (!visited.has(up)) {
          queue.push(up);
          visited.add(up);
        }

        const down = minusOne(cur, j);
        if (!visited.has(down)) {
          queue.push(down);
          visited.add(down);
        }
      }
    }
    step++;
  }
  return -1;
};

function addOne(str, position) {
  str = str.split("");
  let cur = +str[position];
  cur = (cur + 1) % 10;
  str[position] = cur;
  return str.join("");
}
function minusOne(str, position) {
  str = str.split("");
  let cur = +str[position];
  cur = (cur - 1 + 10) % 10;
  str[position] = cur;
  return str.join("");
}
// @lc code=end

单词接龙​

/*
 * @lc app=leetcode.cn id=127 lang=javascript
 *
 * [127] 单词接龙
 */

// @lc code=start
/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
var ladderLength = function(beginWord, endWord, wordList) {
  const wordSize = beginWord.length;
  const allow = new Set(wordList);
  if (!allow.has(endWord)) return 0;
  const queue = [beginWord];
  const visited = new Set(queue);
  let step = 1,
    len,
    i,
    j,
    k,
    newWord,
    cur;
  while (queue.length) {
    len = queue.length;
    for (i = 0; i < len; i++) {
      cur = queue.shift();
      if (cur === endWord) return step;
      for (j = 0; j < wordSize; j++) {
        for (k = 0; k < 26; k++) {
          newWord = getNewWord(cur, j, k);
          if (newWord !== cur && allow.has(newWord) && !visited.has(newWord)) {
            queue.push(newWord);
            visited.add(newWord);
          }
        }
      }
    }
    step++;
  }
  return 0;
};

function getNewWord(str, pos, letter) {
  str = str.split("");
  str[pos] = String.fromCharCode(letter + 97);
  return str.join("");
}
// @lc code=end

滑动谜题​

/*
 * @lc app=leetcode.cn id=773 lang=javascript
 *
 * [773] 滑动谜题
 */

// @lc code=start
/**
 * @param {number[][]} board
 * @return {number}
 */
var slidingPuzzle = function(board) {
  let start = board[0].concat(board[1]).join("");
  const target = "123450";
  const neighborMap = [
    [1, 3],
    [0, 2, 4],
    [1, 5],
    [0, 4],
    [1, 3, 5],
    [2, 4],
  ];
  let queue = [start];
  let visited = new Set(queue);
  let step = 0;

  while (queue.length) {
    let len = queue.length;
    for (let i = 0; i < len; i++) {
      let curBoard = queue.shift();
      if (curBoard === target) {
        return step;
      }
      let zeroIndex = curBoard.indexOf("0");

      let neighbor = neighborMap[zeroIndex];
      neighbor.forEach((neighborPos) => {
        let newBoard = swap(curBoard, zeroIndex, neighborPos);

        if (!visited.has(newBoard)) {
          queue.push(newBoard);
          visited.add(newBoard);
        }
      });
    }
    step++;
  }
  return -1;
};

function swap(str, i, j) {
  str = str.split("");
  [str[i], str[j]] = [str[j], str[i]];
  return str.join("");
}
// @lc code=end

· 阅读需 9 分钟

模板​

var leetcodeXXX = function(nums) {
  let res = [];
  let track = [];

  function backtrack(start) {
    if (满足条件) {
      // 将当前所做的选择列表传入结果列表中
      res.push(track.slice());
      return;
    }
    for (
      let i = start /* 这里取0还是取start需要看具体情况 */;
      i < nums.length;
      i++
    ) {
      // 减枝操作
      // 判断哪些情况下可以跳过,这一步也可以放到子递归中去处理
      if (需要跳过) continue;

      // 做出选择
      track.push(nums[i]);
      // 拿着刚刚做出的选择看结果
      backtrack(i + 1);
      // 撤回刚刚做出的选择
      track.pop(nums[i]);
    }
  }
  // 启动回溯算法
  backtrack();
  return res;
};

理解​

解决一个回溯问题，实际上就是一个决策树的遍历过程 决策树必须包含问题的所有解 只需要思考 3 个问题： 1、路径：也就是已经做出的选择。 2、选择列表：也就是你当前可以做的选择。 3、结束条件：也就是到达决策树底层，无法再做选择的条件。

回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。 某种程度上说，动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质，可以用 dp table 或者备忘录优化，将递归树大幅剪枝，这就变成了动态规划

真题​

全排列​

/*
 * @lc app=leetcode.cn id=46 lang=javascript
 *
 * [46] 全排列
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
  let res = [];
  let track = [];
  function backtrack(chooses) {
    if (chooses.length === track.length) {
      res.push(track.slice());
      return;
    }
    for (let i = 0; i < chooses.length; i++) {
      if (track.includes(chooses[i])) continue;
      // 作出选择
      track.push(chooses[i]);

      backtrack(chooses);

      // 所做的选择反悔
      track.pop();
    }
  }
  backtrack(nums);
  return res;
};
// @lc code=end

组合​

/*
 * @lc app=leetcode.cn id=77 lang=javascript
 *
 * [77] 组合
 */

// @lc code=start
/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
  let res = [];
  let track = [];
  function backtrack(start) {
    if (track.length === k) {
      res.push(track.slice());
      return;
    }

    for (let i = start; i <= n; i++) {
      track.push(i);
      backtrack(i + 1);
      track.pop();
    }
  }
  backtrack(1);
  return res;
};
// @lc code=end

子集​

/*
 * @lc app=leetcode.cn id=78 lang=javascript
 *
 * [78] 子集
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
  let res = [],
    track = [];
  function backtrack(nums, start) {
    res.push(track.slice());
    for (let i = start; i < nums.length; i++) {
      track.push(nums[i]);
      backtrack(nums, i + 1, track);
      track.pop();
    }
  }
  backtrack(nums, 0);
  return res;
};

// @lc code=end

四数之和​

/*
 * @lc app=leetcode.cn id=18 lang=javascript
 *
 * [18] 四数之和
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
// 回溯算法, 疯狂减枝
var fourSum = function(nums, target) {
  let res = [];
  let track = [];
  nums.sort((a, b) => a - b);
  if (
    nums.length &&
    (nums[nums.length - 1] * 4 < target || nums[0] * 4 > target)
  ) {
    return [];
  }

  function backtrack(start = 0, Sum) {
    if (Sum === target && track.length === 4) {
      res.push(track.slice());
      return;
    }
    if (track.length > 4) return;
    for (let i = start; i < nums.length; i++) {
      if (nums.length - i < 4 - track.length) continue;
      if (i > start && nums[i] === nums[i - 1]) continue;
      if (
        i < nums.length - 1 &&
        Sum + nums[i] + (3 - track.length) * nums[i + 1] > target
      )
        continue;

      if (
        i < nums.length - 1 &&
        Sum + nums[i] + (3 - track.length) * nums[nums.length - 1] < target
      )
        continue;

      track.push(nums[i]);
      backtrack(i + 1, Sum + nums[i]);
      track.pop(nums[i]);
    }
  }
  backtrack(0, 0);
  return res;
};
// @lc code=end

// console.log(fourSum([1, 0, -1, 0, -2, 2], 0));

括号生成​

/*
 * @lc app=leetcode.cn id=22 lang=javascript
 *
 * [22] 括号生成
 */

// @lc code=start
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
  let track = [];
  let res = [];
  /**
   * leftNum 剩余左括号数量
   * rightNum 剩余右括号数量
   */
  function backtrack(leftNum, rightNum) {
    // 合格的括号对满足以下条件
    // 1. 任意字串[0,...,i]，左括号数量都大于右括号数量
    // 2. 对于所有合法的括号对，左括号数都等于右括号数

    // 剩余左括号数大于剩余右括号数，说明字串的左括号数小于右括号数，不符合条件
    if (leftNum > rightNum) return;
    // 剩余左括号数或者剩余右括号数不足，不符合条件
    if (leftNum < 0 || rightNum < 0) return;
    // 经过第一个判断，左括号数量肯定大于等于右括号数量，如果剩余左右括号数都为0，说明就是合格的括号对
    if (leftNum === 0 && rightNum === 0) {
      res.push(track.join(""));
      return;
    }

    // 做选择
    track.push("(");
    backtrack(leftNum - 1, rightNum);
    // 回溯
    track.pop();

    // 做选择
    track.push(")");
    backtrack(leftNum, rightNum - 1);
    // 回溯
    track.pop();
  }

  // 剩余左右括号数各给n个
  backtrack(n, n);
  return res;
};
// @lc code=end

N 皇后​

/*
 * @lc app=leetcode.cn id=51 lang=javascript
 *
 * [51] N 皇后
 */

// @lc code=start
/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
  const getMatrix = (n, stuff = "") => {
    const res = [];
    for (let i = 0; i < n; i++) {
      const list = [];
      for (let j = 0; j < n; j++) {
        list.push(stuff);
      }
      res.push(list);
    }
    return res;
  };
  const res = [];
  const emptyBoard = getMatrix(n, ".");
  backtrack(emptyBoard, 0, res);
  return res;
};

function backtrack(matrix, row, res) {
  if (matrix.length === row) {
    res.push(matrix.map((item) => item.join("")));
    return;
  }

  const rowData = matrix[row];
  for (let col = 0; col < rowData.length; col++) {
    if (!isValid(matrix, row, col)) {
      continue;
    }
    rowData[col] = "Q";
    backtrack(matrix, row + 1, res);
    rowData[col] = ".";
  }
}

function isValid(matrix, row, col) {
  const size = matrix.length;
  for (let i = 0; i < size; i++) {
    if (
      matrix[i][col] === "Q" ||
      matrix[row][i] === "Q" ||
      matrix[i][row + col - i] === "Q" ||
      matrix[i][i + col - row] === "Q"
    )
      return false;
  }

  return true;
}
// @lc code=end

解数独​

/*
 * @lc app=leetcode.cn id=37 lang=javascript
 *
 * [37] 解数独
 */

// @lc code=start
/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
  const maxRow = 9,
    maxCol = 9;
  function isValid(i, j, ch) {
    for (let k = 0; k < 9; k++) {
      if (board[i][k] === ch) return false;
      if (board[k][j] === ch) return false;
      const chunkI = Math.floor(i / 3);
      const chunkJ = Math.floor(j / 3);
      const chunkIStart = chunkI * 3;
      const chunkJStart = chunkJ * 3;
      const iIndex = chunkIStart + Math.floor(k / 3);
      const jIndex = chunkJStart + (k % 3);
      if (board[iIndex][jIndex] === ch) return false;
    }
    return true;
  }

  function backtrack(i, j) {
    if (j === maxCol) {
      return backtrack(i + 1, 0);
    }
    if (i === maxRow) {
      return true;
    }

    if (board[i][j] !== ".") {
      return backtrack(i, j + 1);
    }

    for (let t = 1; t <= 9; t++) {
      const ch = String(t);
      if (!isValid(i, j, ch)) continue;
      board[i][j] = ch;

      if (backtrack(i, j + 1)) {
        return true;
      }
      board[i][j] = ".";
    }
    return false;
  }
  backtrack(0, 0);
};
// @lc code=end

let matrix = [
  ["5", "3", ".", ".", "7", ".", ".", ".", "."],
  ["6", ".", ".", "1", "9", "5", ".", ".", "."],
  [".", "9", "8", ".", ".", ".", ".", "6", "."],
  ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
  ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
  ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
  [".", "6", ".", ".", ".", ".", "2", "8", "."],
  [".", ".", ".", "4", "1", "9", ".", ".", "5"],
  [".", ".", ".", ".", "8", ".", ".", "7", "9"],
];
solveSudoku(matrix);
console.log(matrix);

目标和​

/*
 * @lc app=leetcode.cn id=494 lang=javascript
 *
 * [494] 目标和
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} S
 * @return {number}
 */
var findTargetSumWays = function(nums, S) {
  let res = 0;
  let count = 0;
  function backtrack(i) {
    if (i === nums.length) {
      if (res === S) {
        count++;
      }
      return;
    }
    res += nums[i];
    backtrack(i + 1);
    res -= nums[i];

    res -= nums[i];
    backtrack(i + 1);
    res += nums[i];
  }
  backtrack(0);
  return count;
};
// @lc code=end

· 阅读需 1 分钟

二叉树遍历​

void traverse(TreeNode root) {
    // 前序遍历代码
    traverse(root.left);
    // 中序遍历代码
    traverse(root.right);
    // 后序遍历代码
}

N 叉树遍历​

void traverse(ListNode root) {
    for(child of root.children){
        // 前序遍历代码
    traverse(child);
    // 后序遍历代码
    }
}

二叉搜索树遍历​

void BST(TreeNode root, int target) {
    if (root.val == target)
        // 找到目标，做点什么
    if (root.val < target)
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}

链表遍历​

这里链表遍历得着重说明一下，为什么将它放到树的遍历模板中呢？因为链表可以看作是一颗每个节点都只有一个子节点的树，因此也可以用树遍历的思想遍历链表

void traverse(ListNode head) {
    // 前序遍历代码
    traverse(head.next);
    // 后序遍历代码
}