然矣
算法学习笔记（三）
文景色 | Ella 岚杉
  2024-04-01 00:00:00   2024-04-11 22:42:09    7.9k 字  34 分钟

前言

本笔记用于记录刷题过程中遇到的中等及以上难度的题和一些特殊算法思想，语言大部分会用 JavaScript 来刷题，也有的会用C++和Java

承接算法笔记（二），继续刷LeetCode75，同时也做每日一题，进行算法扫盲

题库LeetCode75

本题库涉及到的知识点一览

  • [x] 数组 / 字符串
  • [ ] 双指针
  • [ ] 滑动窗口
  • [x] 前缀和
  • [ ] 哈希表 / 哈希集合
  • [ ] 栈
  • [x] 队列
  • [ ] 链表
  • [ ] 二叉树 - 深度优先搜索
  • [ ] 二叉树 - 广度优先搜索
  • [x] 二叉搜索树
  • [ ] 图 - 深度优先搜索
  • [ ] 图 - 广度优先搜索
  • [ ] 堆 / 优先队列
  • [ ] 二分查找
  • [ ] 回溯
  • [ ] 动态规划 - 一维
  • [ ] 动态规划 - 多维
  • [x] 位运算
  • [ ] 前缀树
  • [x] 区间集合
  • [x] 单调栈

136.只出现一次的数字

题目：

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

解析：

虽然是简单题，但是没做过类似的位运算真的会被卡，不用位运算应该有三种，集合去重，哈希计数，集合去重*2减去原本数组元素，但是空间复杂度都会超，这里只有异或不用额外空间

复习一下异或的特性

任何数和 0 做异或运算，结果仍然是原来的数，即 。
任何数和其自身做异或运算，结果是 0，即 。
异或运算满足交换律和结合律，即 。

1
2
3
4
5
6
7
var singleNumber = function(nums) {
    let res=0;
    for(const num of nums){
        res^=num;
    }
    return res;
};

1318.或运算的最小翻转次数

题目：

给你三个正整数 a、b 和 c。
你可以对 a 和 b 的二进制表示进行位翻转操作，返回能够使按位或运算 a OR b == c 成立的最小翻转次数。
「位翻转操作」是指将一个数的二进制表示任何单个位上的 1 变成 0 或者 0 变成 1 。

解析：

异或秒了

分类讨论就是遍历每一位，当a和b都为0，而c为1，只用翻转一次；当a和b都为1，而c为0，要翻转两次。

如果直接ab或再与c异或会少翻转次数，通过ab与得到两个为1再与非c与，就可以补上少的一部分翻转次数

使用异或来数二进制数的1的个数

1
2
3
4
5
6
7
8
9
10
11
var minFlips = function(a, b, c) {
    const countOne=(x)=>{
        let ones=0;
        while(x>0){
            x&=(x-1);
            ones++;
        }
        return ones;
    }
    return countOne((a|b)^c)+countOne((a&b)&(~c));
};

894.所有可能的真二叉树

题目：

给你一个整数 n ，请你找出所有可能含 n 个节点的 真二叉树 ，并以列表形式返回。答案中每棵树的每个节点都必须符合 Node.val == 0 。
答案的每个元素都是一棵真二叉树的根节点。你可以按 任意顺序 返回最终的真二叉树列表。
真二叉树 是一类二叉树，树中每个节点恰好有 0 或 2 个子节点。

解析：

通过题目意思可以推测处真二叉树是指每个节点的子节点为0或者2的树。因为二叉树一定有一个根节点，所以真二叉树的节点个数一定是奇数。

  1. 从叶子的角度(dp)

一棵有 n 个节点的真二叉树恰好有个叶子。示例中返回列表的顺序是一层一层的返回，如果某个节点在上一层就是叶子结点了，那么在下一层对应的位置会返回两个null，因此可以考虑n与2n-1或者n与来表示当前节点和其对应的叶子结点。

定义 f[i] 为有 i 个叶子的所有真二叉树的列表。
枚举左子树有 j=1,2,⋯ ,i−1 个叶子，那么右子树有 i−j 个叶子。

左子树的所有真二叉树列表为 f[j]，右子树的所有真二叉树列表为 f[i−j]。从这两个列表中各选一棵真二叉树，作为根节点的左右子树，从而得到有 i 个叶子的真二叉树，这些真二叉树组成了 f[i]。

初始值：f[1] 为只包含一个节点的二叉树列表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const f = Array.from({length: 11}, () => []);
f[1].push(new TreeNode());
for (let i = 2; i < f.length; i++) { // 计算 f[i]
    for (let j = 1; j < i; j++) { // 枚举左子树叶子数
        for (const left of f[j]) { // 枚举左子树
            for (const right of f[i - j]) { // 枚举右子树
                f[i].push(new TreeNode(0, left, right));
            }
        }
    }
}

var allPossibleFBT = function(n) {
    return f[n % 2 ? (n + 1) / 2 : 0];
};

  1. 从节点角度

当 n 是奇数时，n 个结点的真二叉树满足左子树和右子树的结点数都是奇数，此时左子树和右子树的结点数之和是 n−1，假设左子树的数目为 i，则左子树的节点数目则为 n−1−i，则可以推出左子树与右子树的节点数目序列为：[(1,n−2),(3,n−4),(5,n−6),⋯ ,(n−2,1)]

自底向上进行动态规划:n=1的子树，就是根节点；[(1,1)]的子树序列，可以构成n=3的真二叉树；[(1,3),(3,1)]的子树序列，可以构成n=5的真二叉树；[(1,5),(3,3),(5,1)]的子树序列，可以构成n=7的真二叉树；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var allPossibleFBT = function (n) {
    if (n % 2 === 0) {
        return [];
    }

    const dp = Array(n + 1).fill().map(() => []);
    dp[1] = [new TreeNode(0)];
    for (let i = 3; i <= n; i += 2) {
        for (let j = 1; j < i; j += 2) {
            for (let leftSubtree of dp[j]) {
                for (let rightSubtree of dp[i - 1 - j]) {
                    const root = new TreeNode(0, leftSubtree, rightSubtree);
                    dp[i].push(root);
                }
            }
        }
    }
    return dp[n];

};

1600.王位继承顺序

题目：

一个王国里住着国王、他的孩子们、他的孙子们等等。每一个时间点，这个家庭里有人出生也有人死亡。
这个王国有一个明确规定的王位继承顺序，第一继承人总是国王自己。我们定义递归函数 Successor(x, curOrder) ，给定一个人 x 和当前的继承顺序，该函数返回 x 的下一继承人。
Successor(x, curOrder):
如果 x 没有孩子或者所有 x 的孩子都在 curOrder 中：
如果 x 是国王，那么返回 null
否则，返回 Successor(x 的父亲, curOrder)
否则，返回 x 不在 curOrder 中最年长的孩子
通过以上的函数，我们总是能得到一个唯一的继承顺序。
请你实现 ThroneInheritance 类：
ThroneInheritance(string kingName) 初始化一个 ThroneInheritance 类的对象。国王的名字作为构造函数的参数传入。
void birth(string parentName, string childName) 表示 parentName 新拥有了一个名为 childName 的孩子。
void death(string name) 表示名为 name 的人死亡。一个人的死亡不会影响 Successor 函数，也不会影响当前的继承顺序。你可以只将这个人标记为死亡状态。
string[] getInheritanceOrder() 返回 除去 死亡人员的当前继承顺序列表。

解析：

本题其实类似于多叉树的前序遍历，存储这棵树的方法可以是哈希映射，(父，子列表)的形式存储

本题逻辑不难，但是有个时间性能的点要注意，如果我的dead使用array来存储，最后会超时，但是用set来存储不会。数组里面的搜索是基于索引的都是 O(N) ，而set是基于键值对的O(1)，数组的indexOf()和includes()方法查找比较慢，而set的has()会快很多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * @param {string} kingName
 */
var ThroneInheritance = function(kingName) {
    this.king=kingName;
    this.edges=new Map();
    this.dead=new Set();
};

/** 
 * @param {string} parentName 
 * @param {string} childName
 * @return {void}
 */
ThroneInheritance.prototype.birth = function(parentName, childName) {
    if(!this.edges.has(parentName)){
        this.edges.set(parentName,[]);
    }
    this.edges.get(parentName).push(childName);
    
};

/** 
 * @param {string} name
 * @return {void}
 */
ThroneInheritance.prototype.death = function(name) {
    this.dead.add(name);
};

/**
 * @return {string[]}
 */
ThroneInheritance.prototype.getInheritanceOrder = function() {
    const res=[];
    const preorder=(name)=>{
        if(!this.dead.has(name)){
            res.push(name);
        }
        if(this.edges.has(name)){
            for(const child of this.edges.get(name)){
                preorder(child);
            }
        }
        
    }
    preorder(this.king);
    return res;
};

/**
 * Your ThroneInheritance object will be instantiated and called as such:
 * var obj = new ThroneInheritance(kingName)
 * obj.birth(parentName,childName)
 * obj.death(name)
 * var param_3 = obj.getInheritanceOrder()
 */

2192.有向无环图的祖先

题目：

给你一个正整数 n ，它表示一个 有向无环图 中节点的数目，节点编号为 0 到 n - 1 （包括两者）。
给你一个二维整数数组 edges ，其中 edges[i] = [fromi, toi] 表示图中一条从 fromi 到 toi 的单向边。
请你返回一个数组 answer，其中 answer[i]是第 i 个节点的所有 祖先 ，这些祖先节点 升序 排序。
如果 u 通过一系列边，能够到达 v ，那么我们称节点 u 是节点 v 的 祖先 节点。

解析：

第一反应可以逆向+dfs
注意这里用js创建邻接表用Array.from()方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[][]}
 */
var getAncestors = function(n, edges) {
    //创建[[],[],[],[]]
    const adj=Array.from({length:n},()=>[]);
    //反向建图
    for(const [x,y] of edges){
        adj[y].push(x);
    }
    const dfs=(x,adj,vis)=>{
        vis[x]=true;
        for(const y of adj[x]){
            if(!vis[y]){
                dfs(y,adj,vis);
            }
        }
    }
    const res=Array.from({length:n},()=>[]);
    const vis=Array(n);
    for(let i=0;i<n;i++){
        vis.fill(false);
        dfs(i,adj,vis);
        vis[i]=false;
        for(let j=0;j<n;j++){
            if(vis[j]){
                res[i].push(j);
            }
        }
    }
    return res;
};

1026.节点与其祖先之间的最大差值

题目：

给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。
（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

解析：

dfs+记录前面节点的最大值和最小值即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 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 maxAncestorDiff = function(root) {
    const dfs=(root,min,max)=>{
        if(root==null){
            return 0;
        }
        let res=Math.max(Math.abs(root.val-min),Math.abs(root.val-max));
        min=Math.min(min,root.val);
        max=Math.max(max,root.val);
        res=Math.max(dfs(root.left,min,max),res);
        res=Math.max(dfs(root.right,min,max),res);
        return res;
    }
    return dfs(root,root.val,root.val);
};

1483.树节点的第k个祖先

题目：

给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。
树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。
实现 TreeAncestor 类：
TreeAncestor（int n， int[] parent） 对树和父数组中的节点数初始化对象。
getKthAncestor(int node, int k) 返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点，返回 -1 。

解析：

暴力向上递归查找父节点会超时，学一下倍增的方法

官方题解又没太看懂，先通过例子来理解一下ST表和倍增的思路

假如有链表A->B->C->D->E->F->G，从任意节点跳k步可以到下一个节点，比如A跳两步到C，B跳两步到D

那么设 f[step][begin] 表示从 begin 开始跳 step 步到达的位置，f[0][begin] = begin，f[1][begin] = f[0][begin]->next ，f[2][begin] =f[1][begin]->next，那么f[4]可以表示为跳四步跳两步再跳两步，即f[4][begin] = f[2][f[2][begin]]。

至此跳任意k步都可以化为二进制的形式求和，而二进制的步长完全可以由前一步递推得到，这就是倍增思想，是st表的指导思想. 一般地有

当 step1+step2 == step时
f[step][begin] = f[step2][f[step1][begin]]

选取2作为一般步长保留计算结果取log(step) 节约空间 f[i][begin] 表示从 begin 位置起跳，跳 1<<i 步到达的点，利用 dp 可求得 f[i][j]

回到本题定义 ancestors[i][j] 表示节点 i 的第 个祖先。状态转移方程是 ancestors[i][j]=ancestors[ancestors[i][j−1]][j−1]，即当前节点的第 个祖先，是他的第 个祖先的第 个祖先。当第 个祖先不存在时，记为 −1。

getKthAncestor需要找到 k 的二进制表示中的所有 1（相当于把 k 分解为若干 ），然后对K进行移位，k的每个1位都表示跳数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * @param {number} n
 * @param {number[]} parent
 */

const LOG = 16;
var TreeAncestor = function(n, parent) {
    ancestors = new Array(n).fill(0).map(() => new Array(LOG).fill(-1));
    for (let i = 0; i < n; i++) {
        ancestors[i][0] = parent[i];
    }
    for (let j = 1; j < LOG; j++) {
        for (let i = 0; i < n; i++) {
            if (ancestors[i][j - 1] !== -1) {
                ancestors[i][j] = ancestors[ancestors[i][j - 1]][j - 1];
            }
        }
    }    
};

/** 
 * @param {number} node 
 * @param {number} k
 * @return {number}
 */
TreeAncestor.prototype.getKthAncestor = function(node, k) {
    for (let j = 0; j < LOG; j++) {
        if (((k >> j) & 1) !== 0) {
            node = ancestors[node][j];
            if (node === -1) {
                return -1;
            }
        }
    }
    return node;

};

/**
 * Your TreeAncestor object will be instantiated and called as such:
 * var obj = new TreeAncestor(n, parent)
 * var param_1 = obj.getKthAncestor(node,k)
 */

42.接雨水

题目：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

解析：

经典题目

1.dp
从左至右最高的扫过去，可以得到以左边边界为最大值的雨水；从右至左最高的扫过去，可以得到以右边边界为最大值的雨水。两者重叠部分就是能接到的雨水，可以理解为某一下标处能接到的雨水等于左右两边的最大值较小的那一个减去当前下标

leftMax[i] 表示下标 i及其左边的位置中，height的最大高度，rightMax[i]表示下标 i 及其右边的位置中，height的最大高度，正向和反向各遍历一次即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var trap = function(height) {
    const len = height.length;
    if(len==0){
        return 0;
    }
    const leftMax=new Array(len).fill(0);
    const rightMax=new Array(len).fill(0);
    leftMax[0]=height[0];
    rightMax[len-1]=height[len-1];
    for(let i=1;i<len;i++){
        leftMax[i]=Math.max(leftMax[i-1],height[i]);
    }
    for(let i=len-2;i>=0;i--){
        rightMax[i]=Math.max(rightMax[i+1],height[i]);
    }
    let res=0;
    for(let i=0;i<len;i++){
        res+=Math.min(rightMax[i],leftMax[i])-height[i];
    }
    return res;
};

代码可以进一步优化，不用两个数组，两个指针就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var trap = function(height) {
    const len = height.length;
    if(len==0){
        return 0;
    }
    const rightMax=new Array(len).fill(0);
    let leftMax=0;
    rightMax[len-1]=height[len-1];
    for(let i=len-2;i>=0;i--){
        rightMax[i]=Math.max(rightMax[i+1],height[i]);
    }
    let res=0;
    for(let i=0;i<len;i++){
        leftMax=Math.max(leftMax,height[i]);
        res+=Math.min(rightMax[i],leftMax)-height[i];
    }
    return res;
};
  1. 单调栈

创建一个栈来存储height的索引，依次遍历数组入栈，保证栈里的高度是递减的，当遇到比当前的栈顶元素的高度高时，栈顶元素出栈，栈顶元素索引左右两边的元素高度取最小值，减去栈顶元素的高度，再乘以两个元素索引之间的间距，一直循环直到栈里为空，再进入下一个索引比较

这样是可以保证当元素高度递减的时候，不停入栈，但是当出现一个更高的，就会停下来循环出栈，直到高度差被磨平(凹槽被填满)，再继续入栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let res=0;
    //栈里压入的是索引序号，要通过height获取高度值
    const stack=[];
    const len=height.length;
    for(let i=0;i<len;i++){
        while(stack.length&&height[i]>height[stack[stack.length-1]]){
            const top=stack.pop();
            if(!stack.length){
                break;
            }
            res+=(Math.min(height[i],height[stack[stack.length-1]])-height[top])*(i-stack[stack.length-1]-1);
        }
        stack.push(i);
    }
    return res;
};

1268.搜索推荐系统

题目：

给你一个产品数组 products 和一个字符串 searchWord ，products 数组中每个产品都是一个字符串。
请你设计一个推荐系统，在依次输入单词 searchWord 的每一个字母后，推荐 products 数组中前缀与 searchWord 相同的最多三个产品。如果前缀相同的可推荐产品超过三个，请按字典序返回最小的三个。
请你以二维列表的形式，返回在输入 searchWord 每个字母后相应的推荐产品的列表。

解析：

题目的意思是每键入一个字母，就全局比较一次前缀。最简单的方法应该是字典树，把product数组里的每一个字符串都存入字典树里，然后searchWord字符串键入就是进入下一层搜索

题目中需要先对product进行字典序排序，然后依次插入字典树，每个节点都维护一个数组记录一下当前插入的字符所属原字符串在product数组中的顺序，这个表只记录前3个就可

由于字典树构建空间消耗很大，当products数组已经排序后可以考虑二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * @param {string[]} products
 * @param {string} searchWord
 * @return {string[][]}
 */
var suggestedProducts = function(products, searchWord) {
    products.sort();
    const len=products.length;
    const res=[];
    for(let i=0;i<searchWord.length;i++){
        const cur=searchWord.substring(0,i+1);
        let l=0,r=len-1;
        while(l<r){
            //可以用位运算来/2
            const mid=(l+r)>>1;
            if(products[mid].localeCompare(cur) >= 0){
                r=mid;
            }else{
                l=mid+1;
            }
        }
        const list=[];
        //localeCompare方法如果引用字符串（referenceStr）存在于比较字符串（compareString）之前则为负数；如果引用字符串存在于比较字符串之后则为正数；相等的时候返回 0
        if(products[r].localeCompare(cur)>=0){
            for(let j=r;j<=Math.min(len-1,r+2);j++){
                if(products[j].length<cur.length||!products[j].startsWith(cur)){
                    break;
                }
                list.push(products[j]);
            }
        }
        res.push(list);
    }
    return res;
};

77.组合

题目：

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。

解析：

经典回溯，树的宽度是可选的范围大小，深度是选择次数，在本题里就是宽度是n，深度是k

还需要额外维护一个保存结果的二维数组和记录了遍历路径的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
    let res=[];
    let path=[];
    const backtracking=(n,k,next)=>{
        if(path.length==k){
            //// 将 path的副本推入 res，而不是直接推入 path，否则后面pop和push操作都会影响path
            res.push([...path]);
            return;
        }
        //这里如果剪枝的话，应该改成i<=n - (k - path.length) + 1
        //就是保证当后面还要选取的对象都包含在path里时，当前遍历可以停止了
        //例：n = 4, k = 3
        //path.size() = 0 时还需要3个数构成组合，最后3个数为{2, 3, 4}，故此时至多应遍历到2，即4-3+1=2
        //path.size() = 1 时还需要2个数构成组合，最后2个数为{3, 4}，故此时至多应遍历到3，即4-2+1=3
        //path.size() = 2 时还需要1个数构成组合，最后1个数为{4}，故此时至多应遍历到4，即4-1+1=4
        for(let i=next;i<=n;i++){
            path.push(i);
            backtracking(n,k,i+1);
            path.pop();
        }
    }
    backtracking(n,k,1);
    return res;
};

216.组合总和III

题目：

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

解析：

还是回溯，只不过多了一个条件就是求和，可以用n在每次查找过程中减去当前选择的元素，回溯的时候加上，最后n为0且path.length=k的path就是答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function(k, n) {
    let res=[],path=[];
    const backtracking=(k,n,next)=>{
        if (n < 0) {
            return;
        }
        if(path.length==k){
            if(n==0){
                res.push([...path]);
            }
            return;
        }
        for(let i=next;i<=9 - (k - path.length) + 1;i++){
            n-=i;
            path.push(i);
            backtracking(k,n,i+1);
            path.pop();
            n+=i;
        }
    }
    backtracking(k,n,1);
    return res;
};

394.字符串解码

题目：

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

解析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function (s) {
    let res = "";
    let num = 0;
    let stack = [];
    let stack_num = [];
    for (const ch of s) {
        if (ch == '[') {
            stack_num.push(num);
            stack.push(res);
            num = 0;
            res = "";
        } else if (ch == ']') {
            const tmp_num = stack_num.pop();
            res = stack.pop() + res.repeat(tmp_num);;
        } else if (ch >= '0' && ch <= '9') {
            num = num * 10 + parseInt(ch);
        } else {
            res+=ch;
        }

    }
    return res;
};

1702.修改后的最大二进制字符串

题目：

给你一个二进制字符串 binary ，它仅有 0 或者 1 组成。你可以使用下面的操作任意次对它进行修改：
操作 1 ：如果二进制串包含子字符串 “00” ，你可以用 “10” 将其替换。
比方说， “00010” -> “10010”
操作 2 ：如果二进制串包含子字符串 “10” ，你可以用 “01” 将其替换。
比方说， “00010” -> “00001”
请你返回执行上述操作任意次以后能得到的 最大二进制字符串 。如果二进制字符串 x 对应的十进制数字大于二进制字符串 y 对应的十进制数字，那么我们称二进制字符串 x 大于二进制字符串 y 。

解析：

思路就是二进制前面00越多越好，00可以由操作2构造出来，例如01110，可以用操作2把后面的0冒泡式往前推，变成00111，然后替换成10111

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {string} binary
 * @return {string}
 */
var maximumBinaryString = function (binary) {
    let res = binary.split("");
    for (let i = 0,j=0; i < res.length; i++) {
        if (res[i] == "0") {
            //找到当前0之后第一次出现0的位置
            //然后可以冒泡式把0往前推
            while(j<=i||(j<res.length&&res[j]=="1")){
                j++;
            }
            if(j<res.length){
                res[j]="1";
                res[i]="1";
                res[i+1]="0";
            }
        }
    }
    return res.join("");
};

进一步思考，最后的结果应该最多只有1个0，有两个0或以上就可以变成10的模式减少0，所以只需要知道第一次出现0的位置就可以构造答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {string} binary
 * @return {string}
 */
var maximumBinaryString = function (binary) {
    const n = binary.length;
    const i = binary.indexOf('0');
    if (i < 0) {
        return binary;
    }
    //有多少个0，结果0就要往后移几-1位
    const zeros = binary.split('0').length - 1;
    const res = Array(n).fill('1');
    res[i + zeros - 1] = '0';
    return res.join('');
};

1657.确定两个字符串是否接近

题目：

如果可以使用以下操作从一个字符串得到另一个字符串，则认为两个字符串 接近 ：
操作 1：交换任意两个 现有 字符。
例如，abcde -> aecdb
操作 2：将一个 现有 字符的每次出现转换为另一个 现有 字符，并对另一个字符执行相同的操作。
例如，aacabb -> bbcbaa（所有 a 转化为 b ，而所有的 b 转换为 a ）
你可以根据需要对任意一个字符串多次使用这两种操作。
给你两个字符串，word1 和 word2 。如果 word1 和 word2 接近 ，就返回 true ；否则，返回 false 。

解析：

题目的意思是只要两个字符串出现过的字母相同，出现过的次数相同，就是接近

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {string} word1
 * @param {string} word2
 * @return {boolean}
 */
var closeStrings = function (word1, word2) {
    if (word1.length != word2.length) {
        return false;
    }
    const set1=new Array(26).fill(0);
    const set2=new Array(26).fill(0);
    for(let i=0;i<word1.length;i++){
        set1[word1.charCodeAt(i)-'a'.charCodeAt()]++;
        set2[word2.charCodeAt(i)-'a'.charCodeAt()]++;
    }
    for(let i=0;i<26;i++){
        if((set1[i]===0)!==(set2[i]===0)){
            return false;
        }
    }
    set1.sort((a, b) => a - b);
    set2.sort((a, b) => a - b);
    //这里被坑了一下不能用==或者===来判断，因为判断的是引用而不是数组内容
    return set1.toString()==set2.toString();
};

2352.相等行列对

题目：

给你一个下标从 0 开始、大小为 n x n 的整数矩阵 grid ，返回满足 Ri 行和 Cj 列相等的行列对 (Ri, Cj) 的数目。
如果行和列以相同的顺序包含相同的元素（即相等的数组），则认为二者是相等的。

解析：

哈希表，就是把每一行转成string都存进哈希表里，然后遍历列对应查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[][]} grid
 * @return {number}
 */
var equalPairs = function(grid) {
    const len=grid.length;
    const hash={};
    for(const row of grid){
        const rowStr=row.toString();
        hash[rowStr]=(hash[rowStr]||0)+1;
    }
    let res=0;
    for(let i=0;i<len;i++){
        let col=[];
        for(let j=0;j<len;j++){
            col.push(grid[j][i]);
        }
        if(hash[col.toString()]){
            res+=hash[col.toString()];
        }
    }
    return res;
};

1161.最大层内元素和

题目：

给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。
请返回层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。

解析：

  1. dfs

带层号进行深度遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 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 maxLevelSum = function(root) {
    const sum=[];
    const dfs=(node,level)=>{
        if(level==sum.length){
            sum.push(node.val);
        }else{
            sum[level]+=node.val;
        }
        if(node.left){
            dfs(node.left,level+1);
        }
        if(node.right){
            dfs(node.right,level+1);
        }
    }
    dfs(root,0);
    let idx=0;
    for(let i=0;i<sum.length;i++){
        if(sum[i]>sum[idx]){
            idx=i;
        }
    }
    return idx+1;
};
  1. bfs

记录一下每层的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

var maxLevelSum = function (root) {
    let maxsum=root.val;
    let q = [];
    q.push(root);
    let maxlevel=1,level=1;
    while (q.length) {
        let sum=0,len=q.length;
        for (let i = 0; i < len; i++) {
            const node = q.shift();
            sum += node.val;
            if (node.left) {
                q.push(node.left);
            }
            if (node.right) {
                q.push(node.right);
            }
        }
        if(sum>maxsum){
            maxlevel=level;
            maxsum=sum;
        }
        level++;
    }
    return maxlevel;
};

328.奇偶链表

题目：

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

解析：

链表的题主要是要画图，这里额外使用奇偶两个指针，遍历一次把奇偶节点分开，然后再拼接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var oddEvenList = function(head) {
    if(head==null||head.next==null){
        return head;
    }
    let evenhead=head.next;
    let odd=head,even=head.next;
    while(even!=null&&even.next!=null){
        odd.next=even.next;
        odd=odd.next;
        even.next=odd.next;
        even=even.next;
    }
    odd.next=evenhead;
    return head;
};

2130.链表最大孪生和

题目：

在一个大小为 n 且 n 为 偶数 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点 。
比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。
孪生和 定义为一个节点和它孪生节点两者值之和。
给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。

解析：

快慢指针先找到后一半的起始节点，然后翻转前一半的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {number}
 */
var pairSum = function(head) {
    let s=head,f=head.next;
    while(f.next!=null){
        s=s.next;
        f=f.next.next;
    }
    let head1 =s.next;
    s.next=null;
    const reverseList = function(head) {
    let prev = null;
    let curr = head;
    while (curr) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
    };
    let head2=reverseList(head);
    let max=0;
    while(head1!=null){
        max=Math.max(head1.val+head2.val,max);
        head1=head1.next;
        head2=head2.next;
    }
    return max;
};

547.省份数量

题目：

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。

解析：

  1. dfs
    其实就是查找图里有多少连通的集合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number[][]} isConnected
 * @return {number}
 */
var findCircleNum = function (isConnected) {
    let provinces = 0;
    let vis = new Set();
    let cities = isConnected.length;
    const dfs = (isConnected, vis, cities, i) => {
        for (let j = 0; j < cities; j++) {
            if (isConnected[i][j] == 1 && !vis.has(j)) {
                vis.add(j);
                dfs(isConnected, vis, cities, j);
            }
        }
    }
    for (let i = 0; i < cities; i++) {
        if (!vis.has(i)) {
            dfs(isConnected, vis, cities, i);
            provinces++;
        }
    }
    
    return provinces;
};
  1. bfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @param {number[][]} isConnected
 * @return {number}
 */
var findCircleNum = function (isConnected) {
    let provinces = 0;
    let vis = new Set();
    let cities = isConnected.length;
    let queue=[];

    for (let i = 0; i < cities; i++) {
        if (!vis.has(i)) {
            queue.push(i);
            //这里只有一个while的原因是没有同一时刻的要求，只要联通就可以算作一个省
            while(queue.length){
                const city=queue.shift();
                vis.add(city);
                for(let j=0;j<cities;j++){
                    if(isConnected[city][j]==1&&!vis.has(j)){
                        queue.push(j);
                    }
                }
            }
            provinces++;
        }
    }
    
    return provinces;
};

1926.迷宫中离入口最近的出口

题目：

给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 ‘.’ 表示）和墙（用 ‘+’ 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。
请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。

解析：

应该是广度优先，遍历到边界就证明有出口，这里可以注意一下写法，把行列变化量作为数组，不然容易太多数组加减

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @param {character[][]} maze
 * @param {number[]} entrance
 * @return {number}
 */
var nearestExit = function (maze, entrance) {
    let queue = [];
    let move = [[0, -1], [-1, 0], [0, 1], [1, 0]];
    let rows = maze.length, cols = maze[0].length;
    maze[entrance[0]][entrance[1]] = "+";
    queue.push([...entrance,0]);
    while (queue.length) {
        let [i, j,step] = queue.shift();
        for (let m of move) {
            let curi = m[0] + i, curj = m[1] + j;
            if (curi >= 0 && curi < rows && curj >= 0 && curj < cols && maze[curi][curj] == ".") {
                if (curi == 0 || curi == rows - 1 || curj == 0 || curj == cols - 1) {
                    return step + 1;
                }
                maze[curi][curj] = "+";
                queue.push([curi, curj,step+1]);
            }
        }
    }
    return -1;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * @param {character[][]} maze
 * @param {number[]} entrance
 * @return {number}
 */
var nearestExit = function (maze, entrance) {
    let queue = [];
    let move = [[0, -1], [-1, 0], [0, 1], [1, 0]];
    let rows = maze.length, cols = maze[0].length;
    let step = 0;
    queue.push(entrance);
    while (queue.length) {
        let len = queue.length;
        //这里要有另外一个while的主要原因是不同路径是同一时刻延伸的，所以每一分钟都必须清空queue里所有值，再进入下一分钟
        while (len--) {
            let [i, j] = queue.shift();
            maze[i][j] = "+";
            for (let m of move) {
                let curi = m[0] + i, curj = m[1] + j;
                if (curi >= 0 && curi < rows && curj >= 0 && curj < cols && maze[curi][curj] == ".") {
                    if (curi == 0 || curi == rows - 1 || curj == 0 || curj == cols - 1) {
                        return step + 1;
                    }
                    maze[curi][curj] = "+";
                    queue.push([curi, curj]);
                }
            }
        }
        step++;
    }
    return -1;
};

接算法笔记（四）~

算法学习笔记（三）
2024/04/01/算法学习笔记（三）/
作者
文景色 | Ella
发布于
2024-04-01 00:00
许可
 评论
评论插件加载失败
正在加载评论插件
  1. 前言
    1. 题库LeetCode75
      1. 136.只出现一次的数字
      2. 1318.或运算的最小翻转次数
      3. 894.所有可能的真二叉树
      4. 1600.王位继承顺序
      5. 2192.有向无环图的祖先
      6. 1026.节点与其祖先之间的最大差值
      7. 1483.树节点的第k个祖先
      8. 42.接雨水
      9. 1268.搜索推荐系统
      10. 77.组合
      11. 216.组合总和III
      12. 394.字符串解码
      13. 1702.修改后的最大二进制字符串
      14. 1657.确定两个字符串是否接近
      15. 2352.相等行列对
      16. 1161.最大层内元素和
      17. 328.奇偶链表
      18. 2130.链表最大孪生和
      19. 547.省份数量
      20. 1926.迷宫中离入口最近的出口
      21. 接算法笔记（四）~
  1. 前言
    1. 题库LeetCode75
      1. 136.只出现一次的数字
      2. 1318.或运算的最小翻转次数
      3. 894.所有可能的真二叉树
      4. 1600.王位继承顺序
      5. 2192.有向无环图的祖先
      6. 1026.节点与其祖先之间的最大差值
      7. 1483.树节点的第k个祖先
      8. 42.接雨水
      9. 1268.搜索推荐系统
      10. 77.组合
      11. 216.组合总和III
      12. 394.字符串解码
      13. 1702.修改后的最大二进制字符串
      14. 1657.确定两个字符串是否接近
      15. 2352.相等行列对
      16. 1161.最大层内元素和
      17. 328.奇偶链表
      18. 2130.链表最大孪生和
      19. 547.省份数量
      20. 1926.迷宫中离入口最近的出口
      21. 接算法笔记（四）~