算法思维总结

总结
算法
发布日期:   2022-07-22
更新日期:   2022-10-31
文章字数:   5.2k
阅读时长:   20 分
阅读次数:  

算法题技巧总结

递归

  1. 确定递归函数的参数和返回值：确定每次递归中需要处理的参数，并且要想清楚每次递归的返回值来确定递归函数的返回值类型；
  2. 确定终止条件：递归在什么条件下停止并返回；
  3. 确定单层递归的逻辑：确定每一层递归需要处理的信息，这里是递归重复调用的代码。

二叉树

遍历方式

递归

/**
 * 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 {number[]}
 */
var preorderTraversal = function(root) {
    let result = [];

    // 递归
    let traverse = (node) => {
        if (node === null) {
            return ;
        }
				
      	// 前序遍历位置
        result.push(node.val);
        traverse(node.left);
      	// 中序遍历位置
      	// result.push(node.val);
        traverse(node.right);
      	// 后序遍历位置
      	// result.push(node.val);
    }

    traverse(root);
    return result;
};

迭代

（1）前序遍历

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    /* 迭代法实现 */
    let result = [];
    let stack = [];
    if (root === null) {
        return result;
    }

    stack.push(root);


    // 注意入栈顺序是先右孩子再左孩子，这样出栈就是根->左->右
    while (stack.length) {
        let node = stack.pop();
        result.push(node.val);

        if (node.right) {
            stack.push(node.right);
        }
        if (node.left) {
            stack.push(node.left);
        }
    }

    return result;
};

（2）中序遍历

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    let stack = [];
    let inorder = [];

    while (root !== null || stack.length) {
        if (root !== null) {
            // 遍历左子树，压栈
            stack.push(root);
            root = root.left;
        } else {
            // 中节点出栈
            let node = stack.pop();
            inorder.push(node.val);
            // 遍历右子树,压栈
            root = root.right;
        }
    }
    return inorder;
};

（3）后序遍历

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    let postOrder = [];
    let stack = [];
    if (root === null) {
        return postOrder;
    }
    stack.push(root);

    while (stack.length) {
        let node = stack.pop();
        postOrder.push(node.val);

        // 只改变了前序遍历左右子树的入栈顺序（中--》出栈--》左---》右）---出栈顺序变成了中右左
        if (node.left) {
            stack.push(node.left);
        }
        if (node.right) {
            stack.push(node.right);
        }
    }

    // 这里颠倒数组顺序就变成了左右中
    postOrder.reverse();
    return postOrder;
};

迭代遍历（统一模板）

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var orderTraversal = function(root) {
    let stack = [];
    let preOrder = []; // inorder, postorder
    
    if (root === null) {
        return preOrder;
    }
    stack.push(root);

    while (stack.length) {
        let node = stack.pop();

        if (node !== null) {
            // 这里体现遍历顺序---入栈的顺序和遍历顺序相反（出栈）
            if (node.right) {
                stack.push(node.right); // 右
            }
            if (node.left) {
                stack.push(node.left); //左
            }
            stack.push(node); // 中
            stack.push(null); // 标记要放入结果集的节点
        } else {
            node = stack.pop();
            preOrder.push(node.val);
        }
    }

    return preOrder;
};

子问题

层序遍历的子问题

二叉树的深度与高度

对称二叉树

路径问题

function dfs(curNode, target) {
  ...
}
function dfs(curNode, result, path, number) {
  ...
}

  • 给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。（该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点）

    • ==这道题需要好好理解。==
    • 解法 1：深度优先搜索（主函数中也有递归的逻辑，遍历每个节点，以每个节点作为路径起点计算满足路径和为 target 的路径数量）
    function rootSum(root, targetSum) {
  ...
}
    • 解法 2：前缀和（也是递归，计算每个并存储每个节点的前缀和）。
    function dfs(node, prefix, curSum, targetSum) {
  ...
}

构建二叉树

function reBuild (preOrder, inOrder, preStart, preEnd, inStart, inEnd) {
  ...
}

判断能否构成一颗二叉树（BST）

  • 输入两棵二叉树 A，B，判断 B 是不是 A 的子结构。
  • 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true，否则返回 false 。 
function traverse (sequence, start, end) {
  ...
}

二叉树中的搜索

  • 给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的 next 指针。

    • 解法 1：先找到根节点，然后中序遍历整棵树，最后匹配目标节点；解法 2：分析中序遍历的特点，分组判断。
    • 解法 2（有点绕）：
      1. 节点的右子树不为空，找到该节点右子树最左边的节点并返回；
      2. 节点右子树为空，且该节点是其父节点的左节点，直接返回其父节点；
      3. 节点右子树为空，该节点是其父节点的右节点，则该节点一直沿着next指针往上走，直到指针指向的节点的左子节点是指针上一次指向的节点，返回当前指针的 next；
    • 二叉树的下一个结点_牛客题霸_牛客网 (nowcoder.com)

  • 给定一棵结点数为 n 的二叉搜索树，请找出其中的第 k 小的 TreeNode 的结点值。

  • 给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的 val 值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

  • 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

    // 搜索一条边的写法：
if (递归函数(root->left)) {
  ...
  return ...;
}
if (递归函数(root->right)) {
	...
  return ...;
}
    // 搜索整个树写法：
let left = 递归函数(root->left);
let right = 递归函数(root->right);
// left与right的逻辑处理;
...

其他

  • 请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
  • 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。

回溯

动态规划

01背包

有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i]，得到的价值是 value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

二维 dp 数组：

  • dp[i][j] 表示从下标 [0, i] 的物品里任意取，放进容量为 j 的背包，价值总和最大为 dp[i][j]。

  • 递推公式：$dp[i][j]=max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])$；

    • 不放物品 i 时的最大价值：$dp[i-1][j]$；
    • 放物品 i 时的最大价值：$dp[i-1][j-weight[i]]+value[i]$；

  • 从前往后遍历

    // weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
	// 从前往后遍历
  for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
    if (j < weight[i]) dp[i][j] = dp[i - 1][j]; 
    else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

  }
}

二维 dp 数组的两个 for 遍历的先后顺序可以颠倒，一维 dp 数组的两个 for 循环先后顺序一定是先遍历物品，再遍历背包容量。

一维 dp 数组：

  • dp[j] 表示：容量为 j 的背包，所背的物品价值最大为 dp[j]；

  • 递推公式：$dp[j]=max(dp[j], dp[j-weight[i]]+value[i])$；

    for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量-从后往前遍历
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

  • 从后往前遍历，保证物品只放入一次；

01 背包的子问题

（1）物品能否装满背包问题（最多能装多少物品）

完全背包

有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i]，得到的价值是 value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。完全背包和 01 背包问题唯一不同的地方就是，每种物品有无限件。

==01 背包和完全背包唯一不同就是体现在遍历顺序上。==

01 背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
  for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
    dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

  }
}

在完全背包中，对于一维 dp 数组来说，遍历顺序可以交换。 如果求组合数就是外层 for 循环遍历物品，内层 for 遍历背包，如果求排列数就是外层 for 遍历背包，内层 for 循环遍历物品。为什么是这样的？因为如果在先遍历物品的话，那么物品放入背包的顺序是固定的；而内层遍历物品则会出现同样的物品，放入顺序不同。

完全背包问题的子问题

一、装满背包至少需要多少个物品的问题

  1. dp[j]: 装满容量为j的背包至少需要的物品个数；
  2. 递推公式：dp[j] = min(dp[j], dp[j - weight[i]] + 1);
  3. 初始化：dp[0] = 1；（这是一般情况，具体需要结合题意）
  4. 遍历顺序：都可以。

题目：322. 零钱兑换 - 力扣（LeetCode）、279. 完全平方数 - 力扣（LeetCode）

二、装满背包有多少种方法的问题

  1. dp[i]: 装满容量为 i 的背包有 dp[i] 种方法；
  2. 递推公式：dp[i] += dp[i - weight[j]]；
  3. 初始化：dp[0] = 1;
  4. 遍历顺序：外层物品内层背包求组合数，外层背包内层物品求排列数；

题目：377. 组合总和 Ⅳ - 力扣（LeetCode）

三、物品能否装满背包的问题

  1. dp[i]: 利用已有的物品可以装满容量为 i 的背包；
  2. 递推公式：dp[i] = true；（判断什么条件下可以装满背包需要结合题意）
  3. 初始化：dp[0] = true；
  4. 遍历顺序：如果装满背包对放入物品的顺序有要求，那么外层背包内层物品，否则一般是外层物品内层背包；

题目：139. 单词拆分 - 力扣（LeetCode）

多重背包

有 n 种物品和一个容量为 v 的背包。第 i 种物品最多有 mi 件可用，每件耗费的空间是 ci ，价值是 wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。

将不同数量的物品展开，多重背包问题就转换成 01 背包问题了。

for (let i = 0, length = amountArr.length; i < length; i++) {
    while (amountArr[i] > 1) {
      weightArr.push(weightArr[i]);
      valueArr.push(valueArr[i]);
      amountArr[i]--;
    }
  }
  const goodsNum: number = weightArr.length;
  const dp: number[] = new Array(bagSize + 1).fill(0);
  // 遍历物品
  for (let i = 0; i < goodsNum; i++) {
    // 遍历背包容量
    for (let j = bagSize; j >= weightArr[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j - weightArr[i]] + valueArr[i]);
    }
  }
}

栈和队列

栈（stack）是一个先进后出的数据结构，队列（queue）是一个先进先出的数据结构。

可以用两个栈模拟队列，一个栈存储数据，另一个栈用来临时保存主栈中的数据（删除数据时，临时保存数据）；

关于栈的子问题：

（1）使用辅助栈

（2）利用栈解决匹配问题

关于队列的子问题：

（1）使用辅助队列

栈和队列的结合：

  • 剑指 Offer 59 - I. 滑动窗口的最大值

    • 关键是将“在窗口内找到最大值”这个操作的复杂度降低至 $O(1)$。空间换时间，于是构建一个非严格递减的双端队列 Dequeue，队头始终是窗口内的最大值。
    • Dequeue 的操作包括：
      • pop：每次弹出的时候，比较当前要弹出的数值是否等于队首元素的数值，如果相等则弹出。
      • push：如果 push 的数值大于队尾元素的数值，那么就将队尾的数值弹出，直到 push 的数值小于等于队尾元素的数值为止。
      • front：返回队首元素的值—窗口中的最大值。
    /* 双端队列 */
function MyQueue() {
    this.queue = []
};

// 每次弹出的时候，比较当前要弹出的数值是否等于队首元素的数值，如果相等则弹出。
MyQueue.prototype.pop = function(value) {
    if (this.queue.length && value === this.queue[0]) {
        this.queue.shift();
    }
}

// 如果push的数值大于队尾元素的数值，那么就将队尾的数值弹出，直到push的数值小于等于队尾元素的数值为止。
MyQueue.prototype.push = function(value) {
    while (this.queue.length && value > this.queue[this.queue.length - 1]) {
        this.queue.pop();
    }
    this.queue.push(value);
}

// 返回队首元素的值---窗口中的最大值
MyQueue.prototype.front = function() {
    return this.queue[0];
}

链表

虚拟头节点

定义一个虚拟头节点 dummy 和一个遍历链表的指针 cur。dummy 的 next 指针指向head ，即dummy.next = head ，cur 指针初始化为 cur = dummy。这样就不用考虑更新头节点后，头节点改变的情况（比如，头节点被删除了）。

双指针

字符串

双指针

JavaScript 常用字符串操作

String.prototype.includes(searchString[, position])：判断一个字符串是否包含在另一个字符串中，根据情况返回 true 或 false。

String.prototype.indexOf(searchValue [, fromIndex])：**indexOf()** 方法返回调用它的 String 对象中第一次出现的指定值的索引，从 fromIndex 处进行搜索。如果未找到该值，则返回 -1。

String.prototype.match(regexp)：检索返回一个字符串匹配正则表达式的结果。

String.prototype.matchAll(regexp)：返回一个包含所有匹配正则表达式的结果及分组捕获组的迭代器。

String.prototype.repeat(count)：构造并返回一个新字符串，该字符串包含被连接在一起的指定数量的字符串的副本。

String.prototype.replace(egexp|substr, newSubStr|function)：**replace()** 方法返回一个由替换值（replacement）替换部分或所有的模式（pattern）匹配项后的新字符串。模式可以是一个字符串或者一个正则表达式，替换值可以是一个字符串或者一个每次匹配都要调用的回调函数。如果pattern是字符串，则仅替换第一个匹配项。

  • 在进行全局的搜索替换时，正则表达式需包含 g 标志。

String.prototype.replaceAll(regexp|substr, newSubstr|function)：**replaceAll()** 方法返回一个新字符串，新字符串所有满足 pattern 的部分都已被replacement 替换。pattern可以是一个字符串或一个 RegExp， replacement可以是一个字符串或一个在每次匹配被调用的函数。

  • 当使用一个 regex时，您必须设置全局（“ g”）标志

String.prototype.split([separator[, limit])：**split()** 方法使用指定的分隔符字符串将一个String对象分割成子字符串数组，以一个指定的分割字串来决定每个拆分的位置。

String.prototype.substring(indexStart[, indexEnd])：**substring()** 方法返回一个字符串在开始索引到结束索引之间的一个子集，或从开始索引直到字符串的末尾的一个子集。

String.prototype.toLowerCase()：**toLowerCase()** 会将调用该方法的字符串值转为小写形式，并返回。

String.prototype.toUpperCase()：**toUpperCase()** 方法将调用该方法的字符串转为大写形式并返回（如果调用该方法的值不是字符串类型会被强制转换）。

String.prototype.trim()：**trim() **方法会从一个字符串的两端删除空白字符。在这个上下文中的空白字符是所有的空白字符 (space, tab, no-break space 等) 以及所有行终止符字符（如 LF，CR 等）。

数组

JavaScript 中的常用操作

常用数学公式及概念

排列组合

排列数：$A_{n}^{m}=n(n-1)(n-2) \ldots(n-m+1)=\frac{n !}{(n-m) !}$；

组合数：$C_{n}^{m}=\frac{A_{n}^{m}}{m !}=\frac{n !}{(n-m) ! m !}$

文章作者: elegantlee
文章链接: https://elegantlee.github.io/2022/07/22/suan-fa/suan-fa-si-wei-zong-jie/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 elegantlee !
总结
赏
评论
  目录