然矣
算法学习笔记（二）
文景色 | Ella 岚杉
  2024-03-07 00:00:00   2024-04-17 01:33:49    7.8k 字  32 分钟

前言

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

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

题库LeetCode75

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

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

238.除自身以外数组的乘积

题目：

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请不要使用除法，且在 O(n) 时间复杂度内完成此题。

解析：

经典的前缀和和后缀和，不做多解释了，不过可以稍微优化一下，毕竟维护两个数组内存消耗太大了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    const len=nums.length;
    let ans=new Array(len).fill(1);
    let L=1;
    for(let i=0;i<len;i++){
        ans[i]*=L;
        L*=nums[i];
    }
    let R=1;
    for(let i=len-1;i>=0;i--){
        ans[i]*=R;
        R*=nums[i];
    }
    return ans;
};

206.反转链表进阶

题目：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。使用递归完成

解析：

简单解法就是迭代，双指针，保存当前和之前节点，然后遍历修改指向对象

比较复杂的是递归，需要理解想让指向，可以通过，然后要注意的下一个节点要指向null

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 {ListNode}
 */

var reverseList = function(head) {
    if(head==null||head.next==null){
        return head
    }
    //靠这一步一直递归到列表的最后一个节点
    const newHead=reverseList(head.next);
    /*
    第一轮出栈，head为5，head.next为空，返回5
    第二轮出栈，head为4，head.next为5，执行head.next.next=head也就是5.next=4，
        把当前节点的子节点的子节点指向当前节点
        此时链表为1->2->3->4<->5，由于4与5互相指向，所以此处要断开4.next=null
        此时链表为1->2->3->4<-5
        返回节点5
    第三轮出栈，head为3，head.next为4，执行head.next.next=head也就是4.next=3，
        此时链表为1->2->3<->4<-5，由于3与4互相指向，所以此处要断开3.next=null
        此时链表为1->2->3<-4<-5
        返回节点5
    第五轮出栈，head为1，head.next为2，执行head.next.next=head也就是2.next=1，
        此时链表为1<->2<-3<-4<-5，由于1与2互相指向，所以此处要断开1.next=null
        此时链表为1<-2<-3<-4<-5
        返回节点5
    出栈完成，最终头节点5->4->3->2->1
     */
    head.next.next=head;
    head.next=null;
    return newHead
};s

1969.数组元素的最小非零乘积

题目：

给你一个正整数 p 。你有一个下标从 1 开始的数组 nums ，这个数组包含范围 [1, 2p - 1] 内所有整数的二进制形式（两端都 包含）。你可以进行以下操作 任意 次：
从 nums 中选择两个元素 x 和 y 。
选择 x 中的一位与 y 对应位置的位交换。对应位置指的是两个整数 相同位置 的二进制位。
比方说，如果 x = 1101 且 y = 0011 ，交换右边数起第 2 位后，我们得到 x = 1111 和 y = 0001 。
请你算出进行以上操作 任意次 以后，nums 能得到的 最小非零 乘积。将乘积对 109 + 7 取余 后返回。
注意：答案应为取余 之前 的最小值。

解析：
​
贪心：为了使整体的乘积最小，缩小时优先缩小最小的元素，增加时优先增加最大的元素

证明：假设a < b < c。选择a缩小1时，此时三者乘积为 (a−1)bc，整体较 abc 缩小了 bc，缩小的幅度最大；当选择b增加1时，此时三者乘积为(a−1)(b+1)c，整体较(a−1)bc 增加了 (a−1)c，增加的幅度最小，得证。

两个数在进行相同的位交换时，本质即将一个元素缩小 ，另外一个元素增加，为了让这两个数乘积最小，应该尽量把小的那个数换成1。

根据上述分析，进行相同位交换时，优先缩小数组中最小的元素，再增加数组中最大的元素。

可以以p为分界线，小于p的为一组，大于p的为一组，大小组的每一个元素(除了)外，遵循最大配最小，第二大配第二小的原则，两两配对(每组两个数之和为)，交换后的必然为和1，乘积是。

最后，最小乘积为

由于幂次很大，计算时需要用到快速幂，之前有题目用到了快速幂(指路算法笔记（一）1137.第N个泰波那契数
https://ella1019.site/2024/03/07/%E7%AE%97%E6%B3%95%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0%EF%BC%88%E4%B8%80%EF%BC%89/#1137-%E7%AC%ACN%E4%B8%AA%E6%B3%B0%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number} p
 * @return {number}
 */
const MOD = 1_000_000_007n;

function pow(x, p) {
    let res = 1n;
    while (p--) {
        res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}

var minNonZeroProduct = function(p) {
    const k = (1n << BigInt(p)) - 1n;
    return k * pow(k - 1n, p - 1) % MOD;
};

338.比特位计数

题目：

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

解析：

借由本题学习一下位运算相关的知识

  1. Brian Kernighan 算法
    对于任意整数x，令 ，该运算将x的二进制表示的最后一个1变成 0，以及后面的0都变成1，而1前面的数不会变。进行&操作之后原本最后一个1以及后面所有的0都会变成0，这样成功实现了减少一个1的目的，可以用这个方法来计数所有的1的个数

    总的时间复杂度为O(nlogn)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    /**
     * @param {number} n
     * @return {number[]}
     */
    var countBits = function (n) {
        const bits = new Array(n + 1).fill(0);
        const countOnes = (x) => {
            let ones = 0;
            while (x > 0) {
                x &= (x - 1);
                ones++;
            }
            return ones;
        }
        for (let i = 0; i < n + 1; i++) {
            bits[i] = countOnes(i);
        }
        return bits;
    };

  2. 动态规划(最高有效位)
    主要是利用2的整数幂( )对应的二进制表示都是最高位是1，其余位都是0，这里尝试抽象出状态变化

    举一个例子，13的二进制表达为1101，它的最高位是1000，即为8( )，减去最高位后5的二进制表达式为101，1的个数比13要少1

    那么只需要遍历然后判断2的整数幂即可

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    var countBits = function(n) {
        const bits = new Array(n + 1).fill(0);
        let highBit = 0;
        for (let i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            bits[i] = bits[i - highBit] + 1;
        }
        return bits;
    };

  3. 动态规划(最低有效位)
    同样的，也可以从最低位入手，将二进制表示x右移一位，等价于。

    如果x是偶数，则

    如果x是奇数，则

    上述两种情况可以进一步简化。由于可以通过 x>>1得到，x除以2的余数可以通过得到，因此有：

    1
    2
    3
    4
    5
    6
    7
    var countBits = function(n) {
    const bits = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        bits[i] = bits[i >> 1] + (i & 1);
    }
    return bits;
    };

  4. 动态规划(最低设置位)
    就是整合前面的规律，得到 

    1
    2
    3
    4
    5
    6
    7
    var countBits = function(n) {
        const bits = new Array(n + 1).fill(0);
        for (let i = 1; i <= n; i++) {
            bits[i] = bits[i & (i - 1)] + 1;
        }
        return bits;
    };

322.零钱兑换

题目：

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。

解析：

  1. 动态规划

    这里的状态转移方程应该是 ，F(i)为组成金额i所需最少的硬币数量，表示第j枚硬币的面值，这里枚举所有的硬币面值，选数量最少的。

    这里循环的内外顺序没有区别

    时间复杂度为O(amount*coins.length)，空间复杂度为O(amount)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    var coinChange = function(coins, amount) {
        let num=new Array(amount+1).fill(amount+1);
        num[0]=0;
        for(let i=1;i<amount+1;i++){
            for(const coin of coins){
                if(coin<=i){
                    num[i]=Math.min(num[i],num[i-coin]+1);
                }
            }
        }
        return num[amount] > amount ? -1 : num[amount];
    };

  2. 贪心

    本题我的第一反应就是贪心，优先大面值，余数小面值，不行的话就大面值回滚一个再小面值，但是会超时？而且有些奇葩用例最先找到的并不是数量最少的，还是得全部遍历(例如amount=14，coins[1,7,10]，贪心会选择[10,1,1,1,1]，但正确答案应该是[7,7])？算下来还不如直接dp

518.零钱兑换Ⅱ

题目：

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。

解析：

本题是完全背包问题(不限量)的计数类型。注意循环顺序有讲究，外物品(钱类别)内背包(金额)，原因是这里返回的是组合数，不是排列数(不同顺序也算一种，即元素重复)，排列数循环反过来

dp[j]：凑成总金额j的货币组合数为dp[j]，dp[j] 就是所有的dp[j - coins[i]]（考虑coins[i]的情况）相加

本题递推公式 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function (amount, coins) {
    let num = new Array(amount + 1).fill(0);
    num[0] = 1;
    for (const coin of coins) {
        for (let i = coin; i < amount + 1; i++) {
            num[i] += num[i - coin];
        }
    }
    return num[amount];
};

443.压缩字符串

题目：

给你一个字符数组 chars ，请使用下述算法压缩：
从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：
如果这一组长度为 1 ，则将字符追加到 s 中。
否则，需要向 s 追加字符，后跟这一组的长度。
压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。
请在 修改完输入数组后 ，返回该数组的新长度。
你必须设计并实现一个只使用常量额外空间的算法来解决此问题。

解析：

没有特别需要说明的，就是正常遍历，用两个指针记录子串长度

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 {character[]} chars
 * @return {number}
 */
var compress = function (chars) {
    let r = 0, w = 0;
    const len = chars.length;
    while (r < len) {
        let index = r;
        while (chars[index] == chars[r] && index < len) {
            index++;
        }
        let cnt = index - r;
        chars[w++] = chars[r];
        if (cnt > 1) {
            let str = cnt.toString();
            for (let i = 0; i < str.length; i++) {
                chars[w++] = str[i];
            }
        }
        r = index;
    }
    return w;

};

11.盛最多水的容器

题目：

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

解析：

经典的双指针问题，面积实际上等于两个指针中较小的那一个值乘以两个指针间的距离

这里先从数组边界开始，每一次都移动较小的边界指针(因为只有最短的会影响到整体)，最后遍历返回最大的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
    let l = 0, r = height.length - 1, max = 0;
    while (l < r) {
        max = Math.max(max, (r - l) * Math.min(height[l], height[r]));
        if (height[l] <= height[r]) {
            ++l;
        } else {
            --r;
        }
    }
    return max;
};

17.电话号码的字母组合

题目：

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

解析：

回溯：本质上就是穷举，把所有的情况以n叉树的形式表示出来，可以用伪代码表示递归逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
void backtracking(递归深度，即树的高度) {
    //终止条件
    if (树是否递归完) {
        保存结果;
        return;
    }
    for (当前节点的子节点数量) {
        处理当前子节点;
        backtracking(下一层节点); // 递归
        回溯，撤销当前子节点;
    }
}

本题关键在于树的宽度是由每个数字对应的字母决定，树的深度由数字的数量决定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
    if (digits.length == 0) return [];
    let res = [], path = [];
    const map = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
    if (digits.length === 1) return map[digits].split("");
    const backtracking = (digits, length, index) => {
        if (path.length == length) {
            res.push(path.join(""));
            return;
        }
        for (const s of map[digits[index]]) {
            path.push(s);
            backtracking(digits, length, index + 1);
            path.pop(s);
        }
    }
    backtracking(digits, digits.length, 0)
    return res;

};

2580.统计将重叠区间合并成组的方案数

题目：

给你一个二维整数数组 ranges ，其中 ranges[i] = [starti, endi] 表示 starti 到 endi 之间（包括二者）的所有整数都包含在第 i 个区间中。
你需要将 ranges 分成 两个 组（可以为空），满足：
每个区间只属于一个组。
两个有 交集 的区间必须在 同一个 组内。
如果两个区间有至少 一个 公共整数，那么这两个区间是 有交集 的。
比方说，区间 [1, 3] 和 [2, 5] 有交集，因为 2 和 3 在两个区间中都被包含。
请你返回将 ranges 划分成两个组的 总方案数 。由于答案可能很大，将它对 109 + 7 取余 后返回。

解析：

合并区间的思路，一般是先把区间按照左边界排序，然后遍历区间，维护当前合并区间的最大右边界maxR。如果当前区间左边界l > maxR，则没有重叠，更新maxR为当前区间右边界r；反之则右重叠区域，把当前区间合并，再更新maxR

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[][]} ranges
 * @return {number}
 */
var countWays = function(ranges) {
    ranges.sort((a,b)=>a[0]-b[0]);
    let res=1,maxR=-1;
    for(const [l,r] of ranges){
        if(l>maxR){
            res=res*2%1_000_000_007;
        }
        maxR=Math.max(r,maxR);
    }
    return res;
};

435.无重叠区域

题目：

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

解析：

  1. 动态规划(超时)

总结一下动态规划的逻辑一般是倒推，先假定一种情况，然后再逆推要达到这种情况的条件，找到规律以后遍历即可

本题逻辑就是用fi表示以i区间为集合最后一个区间，不重叠的最大区间数。那么逆推条件，这个最大区间数应该是倒数第二个区间+1得到的，因为这里要求不重叠，所以倒数第二个区间不一定和最后一个区间相邻，应该寻找满足同时fj最大的。因此状态方程为

这里的时间复杂度达到了，所以必须优化

  1. 贪心

官方题解没太看懂，但是看评论区大佬解释理解了，可以代入情景今天有好几个活动，每个活动都可以用区间 [start,end]表示开始和结束的时间，请问你今天最多能参加几个活动呢？

正确逻辑就是照结束时间从早到晚排序，优先选择参加那些结束时间早的，因为这样可以留下更多的时间参加其余的活动。如果有多个结束时间相同的，我们选择开始时间晚的，因为这样也有助于参加更多的活动。然后再从前往后遍历一遍，把后面重叠的删去，这样保证了最后得到的一定是最大不重叠区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var eraseOverlapIntervals = function(intervals) {
    if (!intervals.length) {
        return 0;
    }

    intervals.sort((a, b) => a[1] - b[1]);

    const n = intervals.length;
    let right = intervals[0][1];
    let ans = 1;
    for (let i = 1; i < n; ++i) {
        if (intervals[i][0] >= right) {
            ++ans;
            right = intervals[i][1];
        }
    }
    return n - ans;
};

452.用最少数量的箭引爆气球

题目：

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数

解析：

再来一道重叠区间！逻辑是一样的气球尾的位置升序排列，然后以第一个气球尾作为右边界，依次遍历，只要遇到第一个气球头超过了当前右边界，那么说明后续要么都没跟第一个气球重叠，要么哪怕有重叠后面的箭也会引爆，这样只用一次遍历即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[][]} points
 * @return {number}
 */
var findMinArrowShots = function(points) {
    if (!points.length ) {
        return 0;
    }

    points.sort((a, b) => a[1] - b[1]);
    let pos = points[0][1]
    let ans = 1;
    for (let balloon of points) {
        if (balloon[0] > pos) {
            pos = balloon[1];
            ans++;
        }
    }
    return ans;
};

1997.访问完所有房间的第一天

题目：

你需要访问 n 个房间，房间从 0 到 n - 1 编号。同时，每一天都有一个日期编号，从 0 开始，依天数递增。你每天都会访问一个房间。
最开始的第 0 天，你访问 0 号房间。给你一个长度为 n 且 下标从 0 开始 的数组 nextVisit 。在接下来的几天中，你访问房间的 次序 将根据下面的 规则 决定：
假设某一天，你访问 i 号房间。
如果算上本次访问，访问 i 号房间的次数为 奇数 ，那么 第二天 需要访问 nextVisit[i] 所指定的房间，其中 0 <= nextVisit[i] <= i 。
如果算上本次访问，访问 i 号房间的次数为 偶数 ，那么 第二天 需要访问 (i + 1) mod n 号房间。
请返回你访问完所有房间的第一天的日期编号。题目数据保证总是存在这样的一天。由于答案可能很大，返回对 109 + 7 取余后的结果

解析：

动态规划，题目的意思是如果首次到达房间i，那么一定会回退到前面的房间nextVisit[i]，如果想到下一个房间只能是第二次访问，所以可以推测出到达i房间，[0,i)的房间已经被访问过偶数次

这题麻烦在提取哪一个量作为状态量，这里定义dp[i]是从房间0到第一次到达房间i所花费的天数，这个转换逻辑是

  • 从0第一次到i-1 dp[i−1] (隐藏条件[0,i-1)访问次数都是偶数)
  • 从i-1跳到nextVisit[i-1] 走1天
  • 从nextVisit[i-1]到i-1 dp[i-1]−dp[nextVisit[i]] ((nextVisit[i],i-1)访问次数都是偶数，所以这个区间的跳转情况跟第一次访问是一样的)
  • i-1到i 走1天

得到状态方程dp[i]=2*dp[i−1]−dp[nextVisit[i-1]]+2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} nextVisit
 * @return {number}
 */
var firstDayBeenInAllRooms = function(nextVisit) {
    const mod =1e9+7;
    const len=nextVisit.length;
    const dp=new Array(len).fill(0);
    for(let i=1;i<len;i++){
        //注意这里为了避免负数要+mod
        dp[i]=(2*dp[i-1]-dp[nextVisit[i-1]]+2+ mod)%mod;
    }
    return dp[len-1];
};

208.实现 Trie (前缀树)

题目：

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
请你实现 Trie 类：
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

解析：

简单解释前缀树就是多叉树，类似于把字符串纵向排列，每层子节点为26个，表示26字母，每个子节点又会对应下一层26个子节点，直到字符串所有字符遍历完，通常不会初始化所有的26个子节点，按照需求初始化

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

var Trie = function() {
    this.children={};
};

/** 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let node = this.children;
    for(const ch of word){
        if(!node[ch]){
            node[ch]={};
        }
        node=node[ch];
    }
    node.isEnd=true;
};

/** 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let node = this.children;
    for(const ch of word){
        if(!node[ch]){
            return false;
        }
        node=node[ch];
    }
    return node!==undefined&&node.isEnd!==undefined;
};

/** 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    let node = this.children;
    for(const ch of prefix){
        if(!node[ch]){
            return false;
        }
        node=node[ch];
    }
    return node!==undefined;
};

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */

649.Dota2参议院

题目：

Dota2 的世界里有两个阵营：Radiant（天辉）和 Dire（夜魇）
Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的 一 项：
禁止一名参议员的权利：参议员可以让另一位参议员在这一轮和随后的几轮中丧失 所有的权利 。
宣布胜利：如果参议员发现有权利投票的参议员都是 同一个阵营的 ，他可以宣布胜利并决定在游戏中的有关变化。
给你一个字符串 senate 代表每个参议员的阵营。字母 ‘R’ 和 ‘D’分别代表了 Radiant（天辉）和 Dire（夜魇）。然后，如果有 n 个参议员，给定字符串的大小将是 n。
以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。
假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 “Radiant” 或 “Dire” 。

解析：

贪心加循环队列，维护两个阵营记录了各自参议员顺序的队列，按照顺序，当前参议院一定会淘汰掉下一个对方参议员，那么被淘汰掉的踢出队列，没被淘汰的进入队列尾部准备下一轮循环，最后看哪个队列不为空，即为获胜方

这里注意获取字符串的每个字符序列可以用Array.from(string).entries()，from是转化为array，entries可以获取每一个元素和对应的索引，可以用for (const [index, element] of array.entries())获取

一个小坑，在JavaScript中循环退出数组用while (array.length)，而不用array！=null，因为会超时[]!=null

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} senate
 * @return {string}
 */
var predictPartyVictory = function(senate) {
    let radient=[],dire=[];
    const n = senate.length;

    for(const [index,ch] of Array.from(senate).entries()){
        if(ch=="R"){
            radient.push(index);
        }else{
            dire.push(index);
        }
    }

    while(radient.length&&dire.length){
        if(radient[0]<dire[0]){
            radient.push(radient[0]+n);
        }else{
            dire.push(dire[0]+n);
        }
        radient.shift();
        dire.shift();
    }
    return radient.length ? "Radiant" : "Dire";
};

2095.删除链表的中间节点

题目：

给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。
长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。
对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。

解析：

设置一个head前的哨兵指针，然后设置快慢指针，快的一次走两个，慢的走一个，快的走到头，慢的所指就是中间节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteMiddle(ListNode head) {
        ListNode pre = new ListNode(0, head);
        ListNode fp = pre.next;
        ListNode sp = pre;
        while (fp != null && fp.next != null) {
            fp = fp.next.next;
            sp = sp.next;
        }
        sp.next = sp.next.next;
        return pre.next;
    }
}

450.删除二叉搜索树中的节点

题目：

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点；
如果找到了，删除它。

解析：

二叉搜索树构建增删改算法没啥好说的，数据结构基本常识了，做一下纯当练手了

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
/**
 * 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
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function(root, key) {
    if(!root){
        return null;
    }
    if (root.val > key) {
        root.left = deleteNode(root.left, key);
        return root;
    }
    if (root.val < key) {
        root.right = deleteNode(root.right, key);
        return root;
    }
    if(root.val==key){
        if (!root.left && !root.right) {
            return null;
        }
        if (!root.right) {
            return root.left;
        }
        if (!root.left ) {
            return root.right;
        }
        let node=root.right;
        while(node.left){
            node=node.left;
        }
        root.right=deleteNode(root.right, node.val)
        node.right=root.right;
        node.left=root.left;
        return node;
    }
};

199.二叉树的右视图

题目：

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

解析：

  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
    30
    31
    32
    33
    34
        /**
     * Definition for a binary tree node.
    * public class TreeNode {
    *     int val;
    *     TreeNode left;
    *     TreeNode right;
    *     TreeNode() {}
    *     TreeNode(int val) { this.val = val; }
    *     TreeNode(int val, TreeNode left, TreeNode right) {
    *         this.val = val;
    *         this.left = left;
    *         this.right = right;
    *     }
    * }
    */
    class Solution {
        public List<Integer> rightSideView(TreeNode root) {
            List<Integer> ans = new ArrayList<>();
            if (root == null) return ans;
            Queue<TreeNode> q=new LinkedList<>();
            q.offer(root);
            int count;
            while(!q.isEmpty()){
                count=q.size();
                for(int i=0;i<count;i++){
                    TreeNode node=q.poll();
                    if(node.left!=null)q.offer(node.left);
                    if(node.right!=null)q.offer(node.right);
                    if(i==count-1)ans.add(node.val);
                }
            }
            return ans;
        }
    }

  2. dfs
    深度优先，ans数组会获取到二叉树汇总最长路径，因为后访问右子树，如果有的话每层最右边节点会覆盖ans原先位置节点，最终可以得到右视图

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
        public List<Integer> rightSideView(TreeNode root) {
            List<Integer> ans = new ArrayList<>();
            dfs(root,0,ans);
            return ans;
            
        }
        private void dfs(TreeNode node,int depth,List<Integer> ans){
            if(node==null)return;
            if(ans.size()<=depth){
                ans.add(node.val);
            }else{
                ans.set(depth, node.val);
            }
            dfs(node.left, depth + 1,ans);
            dfs(node.right, depth + 1,ans);
                
        }
    }

2952.需要添加的硬币的最小数量

题目：

给你一个下标从 0 开始的整数数组 coins，表示可用的硬币的面值，以及一个整数 target 。
如果存在某个 coins 的子序列总和为 x，那么整数 x 就是一个 可取得的金额 。
返回需要添加到数组中的 任意面值 硬币的 最小数量 ，使范围 [1, target] 内的每个整数都属于 可取得的金额 。
数组的 子序列 是通过删除原始数组的一些（可能不删除）元素而形成的新的 非空 数组，删除过程不会改变剩余元素的相对位置。

解析：

贪心
假设现在得到了区间 [0,x−1] 中的所有整数，如果此时遍历到整数 coins[i]，那么把 [0,x−1]中的每个整数都增加 coins[i]，我们就得到了区间 [coins[i],coins[i]+x−1]中的所有整数。

如果 coins[i]<=x，那么合并 [0,x−1] 和 [coins[i],coins[i]+x−1] 这两个区间，我们可以得到 [0,coins[i]+x−1] 中的所有整数。
如果 coins[i]>x，或者遍历完了 coins数组，这意味着我们无法得到 x，那么就一定要把 x加到数组中（加一个比 x还小的数字就没法得到更大的数，不够贪），这样就可以得到了 [x,2x−1]中的所有整数，再与 [0,x−1]合并，可以得到 [0,2x−1]中的所有整数。然后再考虑 coins[i] 和 2x 的大小关系，继续分类讨论。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} coins
 * @param {number} target
 * @return {number}
 */
var minimumAddedCoins = function(coins, target) {
    coins.sort((x,y)=>x-y);
    let ans=0,x=1,i=0;
    while(x<=target){
        if(i<coins.length&&coins[i]<=x){
            x+=coins[i++];
        }else{
            ans++;
            x*=2;
        }
    }
    return ans;
};

331.验证二叉树的前序序列化

题目：

序列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。

解析：

回忆一下前序中序后序遍历，前中后指的是根节点的位置

本题用栈来模拟遍历，判断是否是叶子节点就是看该节点是否有两个#子节点

因为是递归，判断当前是否递归完叶子结点就是通过查找到连续x,#,#，然后把这三个全部出栈，用#代替，这样父节点也可以模拟叶子结点，只要最后栈里只剩下#，那么就成功遍历完

参考他人画的动画理解

(好像消消乐)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {string} preorder
 * @return {boolean}
 */
var isValidSerialization = function(preorder) {
    let stack=[];
    const arr=preorder.split(",")
    for(const ch of arr){
        stack.push(ch);
        while(stack.length>=3&&stack[stack.length-1] =='#'&& stack[stack.length-2] == '#' && stack[stack.length-3] != '#'){
            stack.pop();
            stack.pop();
            stack.pop();
            stack.push("#");
        }
    }
    return stack.length==1&&stack.pop()=="#";
};

接算法笔记（三）~

算法学习笔记（二）
2024/03/07/算法学习笔记（二）/
作者
文景色 | Ella
发布于
2024-03-07 00:00
许可
 评论
评论插件加载失败
正在加载评论插件
  1. 前言
    1. 题库LeetCode75
      1. 238.除自身以外数组的乘积
      2. 206.反转链表进阶
      3. 1969.数组元素的最小非零乘积
      4. 338.比特位计数
      5. 322.零钱兑换
      6. 518.零钱兑换Ⅱ
      7. 443.压缩字符串
      8. 11.盛最多水的容器
      9. 17.电话号码的字母组合
      10. 2580.统计将重叠区间合并成组的方案数
      11. 435.无重叠区域
      12. 452.用最少数量的箭引爆气球
      13. 1997.访问完所有房间的第一天
      14. 208.实现 Trie (前缀树)
      15. 649.Dota2参议院
      16. 2095.删除链表的中间节点
      17. 450.删除二叉搜索树中的节点
      18. 199.二叉树的右视图
      19. 2952.需要添加的硬币的最小数量
      20. 331.验证二叉树的前序序列化
      21. 接算法笔记（三）~
  1. 前言
    1. 题库LeetCode75
      1. 238.除自身以外数组的乘积
      2. 206.反转链表进阶
      3. 1969.数组元素的最小非零乘积
      4. 338.比特位计数
      5. 322.零钱兑换
      6. 518.零钱兑换Ⅱ
      7. 443.压缩字符串
      8. 11.盛最多水的容器
      9. 17.电话号码的字母组合
      10. 2580.统计将重叠区间合并成组的方案数
      11. 435.无重叠区域
      12. 452.用最少数量的箭引爆气球
      13. 1997.访问完所有房间的第一天
      14. 208.实现 Trie (前缀树)
      15. 649.Dota2参议院
      16. 2095.删除链表的中间节点
      17. 450.删除二叉搜索树中的节点
      18. 199.二叉树的右视图
      19. 2952.需要添加的硬币的最小数量
      20. 331.验证二叉树的前序序列化
      21. 接算法笔记（三）~