算法笔记

leetcode

美丽塔 2865

给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。

你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。

如果以下条件满足，我们称这些塔是 美丽 的：

  1. 1 <= heights[i] <= maxHeights[i]
  2. heights 是一个 山脉 数组。

如果存在下标 i 满足以下条件，那么我们称数组 heights 是一个 山脉 数组：

  • 对于所有 0 < j <= i ，都有 heights[j - 1] <= heights[j]
  • 对于所有 i <= k < n - 1 ，都有 heights[k + 1] <= heights[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
31
32
33
34
class Solution {
    public long maximumSumOfHeights(List<Integer> maxHeights) {
        long max = 0L;
        int n = maxHeights.size();
        long []prefix = new long[n];
        long []afterfix = new long[n];
        Deque<Integer> stack1 = new ArrayDeque<Integer>();
        Deque<Integer> stack2 = new ArrayDeque<Integer>();
        for(int i = 0;i<n;i++){
            while(!stack1.isEmpty() && maxHeights.get(i) < maxHeights.get(stack1.peek())){
                stack1.pop();
            }
            if(stack1.isEmpty()){
                prefix[i] = (long) (i + 1) * maxHeights.get(i);
            }else{
                prefix[i] = prefix[stack1.peek()] + (long)(i - stack1.peek()) * maxHeights.get(i);
            }
            stack1.push(i);
        }
        for(int i = n-1;i>=0;i--){
            while(!stack2.isEmpty() && maxHeights.get(i) < maxHeights.get(stack2.peek())){
                stack2.pop();
            }
            if(stack2.isEmpty()){
                afterfix[i] = (long) (n - i) * maxHeights.get(i);
            }else{
                afterfix[i] = afterfix[stack2.peek()] + (long)(stack2.peek() - i) * maxHeights.get(i);
            }
            stack2.push(i);
            max = Math.max(max, prefix[i] + afterfix[i] - maxHeights.get(i));
        }
        return max;
    }
}

滑动窗口最大值 239

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

单调队列，具体请看单调队列 滑动窗口最大值【基础算法精讲 27】

维护一个双向队列，从队尾插入新的数据时保证队列的递增性质或递减性质，如果出现矛盾，则不断从队尾剔除数据，直到满足条件，最终从队尾插入新的数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        Deque<Integer> q = new ArrayDeque<>(); // 双端队列
        for (int i = 0; i < n; i++) {
            // 1. 入
            while (!q.isEmpty() && nums[q.getLast()] <= nums[i]) {
                q.removeLast(); // 维护 q 的单调性
            }
            q.addLast(i); // 入队
            // 2. 出
            if (i - q.getFirst() >= k) { // 队首已经离开窗口了
                q.removeFirst();
            }
            // 3. 记录答案
            if (i >= k - 1) {
                // 由于队首到队尾单调递减，所以窗口最大值就是队首
                ans[i - k + 1] = nums[q.getFirst()];
            }
        }
        return ans;
    }
}

计算二进制的1的数量

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

请你用整数形式返回 nums 中的特定元素之 和 ，这些特定元素满足：其对应下标的二进制表示中恰存在 k 个置位。

整数的二进制表示中的 1 就是这个整数的 置位 。

例如，21 的二进制表示为 10101 ，其中有 3 个置位。

API：Integer.bitCount()

1
2
3
4
5
6
7
8
private int position(int num){
    int ans = 0;
    while(num>0){
        ans += num & 1;
        num = num >> 1;
    }
    return ans;
}

最大合金数 2861

单调性二分查找

假设你是一家合金制造公司的老板，你的公司使用多种金属来制造合金。现在共有 n 种不同类型的金属可以使用，并且你可以使用 k 台机器来制造合金。每台机器都需要特定数量的每种金属来创建合金。

对于第 i 台机器而言，创建合金需要 composition[i][j] 份 j 类型金属。最初，你拥有 stock[i] 份 i 类型金属，而每购入一份 i 类型金属需要花费 cost[i] 的金钱。

给你整数 n、k、budget，下标从 1 开始的二维数组 composition，两个下标从 1 开始的数组 stock 和 cost，请你在预算不超过 budget 金钱的前提下，最大化 公司制造合金的数量。

所有合金都需要由同一台机器制造。

返回公司可以制造的最大合金数。

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,0], cost = [1,2,3]
输出：2
解释：最优的方法是使用第 1 台机器来制造合金。
要想制造 2 份合金，我们需要购买：
- 2 份第 1 类金属。
- 2 份第 2 类金属。
- 2 份第 3 类金属。
总共需要 2 * 1 + 2 * 2 + 2 * 3 = 12 的金钱，小于等于预算 15 。
注意，我们最开始时候没有任何一类金属，所以必须买齐所有需要的金属。
可以证明在示例条件下最多可以制造 2 份合金。

题解

假设要制造 num 份合金，由于 num 越小，花费的钱越少，num 越多，花费的钱越多，有单调性，可以二分。

对于第 j 类金属：

  • 如果 composition[i][j] * num <= stock[j]，那么无需购买额外的金属。
  • 如果 composition[i][j] * num > stock[j]，那么需要购买额外的金属，花费为 (composition[i][j] * num - stock[j]) * cost[j]。

遍历每类金属，计算总花费。如果总花费超过 budget，则无法制造 num 份合金，否则可以制造。

最后讨论下二分的上下界：

  • 二分上界：粗略计算一下，假设 composition[i][j] 和 cost[j] 都是 1，此时可以制造最多的合金，个数为 min(stock) + budget。
  • 二分下界：可以设为 1。更巧妙的做法是，设当前答案为 ans，那么可以初始化二分下界为 ans + 1，因为算出小于等于 ans 的值是没有意义的，不会让 ans 变大。如果这台机器无法制造出至少 ans + 1 份合金，那么二分循环结束后的结果为 ans，不影响答案。

答案：引用自灵茶山艾府

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
// 全部转成 int[] 数组，效率比 List<Integer> 更高
class Solution {
    public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> Stock, List<Integer> Cost) {
        int ans = 0;
        int mx = Collections.min(Stock) + budget;
        int[] stock = Stock.stream().mapToInt(i -> i).toArray();
        int[] cost = Cost.stream().mapToInt(i -> i).toArray();
        for (List<Integer> Comp : composition) {
            int[] comp = Comp.stream().mapToInt(i -> i).toArray();
            int left = ans, right = mx + 1;
            while (left + 1 < right) { // 开区间写法
                int mid = left + (right - left) / 2;
                boolean ok = true;
                long money = 0;
                for (int i = 0; i < n; i++) {
                    if (stock[i] < (long) comp[i] * mid) {
                        money += ((long) comp[i] * mid - stock[i]) * cost[i];
                        if (money > budget) {
                            ok = false;
                            break;
                        }
                    }
                }
                if (ok) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
            ans = left;
        }
        return ans;
    }
}

分割回文串 131

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

1
2
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

Code

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
class Solution {
    private int n;
    private boolean[] check;
    private List<Integer> cutPoint;
    private List<List<String>> ans;
    public List<List<String>> partition(String s) {
        n = s.length();
        check = new boolean[n+1];
        cutPoint = new ArrayList<>();
        ans = new ArrayList<>();
        cutPoint.add(0);
        dfs(0,s);
        return ans;
    }
   public static boolean isPalindrome(String str)
    {
        int left = 0,right = str.length()-1;
        while(left < right){
            if(str.charAt(left) != str.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }


    public void dfs(int r,String s){
        if(r == n){
            List<String> temp = new ArrayList<>();
            for(int i = 0; i < cutPoint.size(); i++){
                if(i == cutPoint.size() - 1) continue;
                temp.add(s.substring(cutPoint.get(i),cutPoint.get(i+1)));
            }
            ans.add(temp);
            return;
        }
        for(int j = r+1; j <= n; j++){
            if(isPalindrome(s.substring(r,j)) && !check[j]){
                cutPoint.add(j);
                check[j] = true;
                dfs(j,s);
                cutPoint.remove(cutPoint.size()-1);
                check[j] = false;
                continue;
            }
        }
    }
}

水壶问题 365

有两个水壶，容量分别为 jug1Capacity 和 jug2Capacity 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 targetCapacity 升。

如果可以得到 targetCapacity 升水，最后请用以上水壶中的一或两个来盛放取得的 targetCapacity 升水。

你可以：

  • 装满任意一个水壶
  • 清空任意一个水壶
  • 从一个水壶向另外一个水壶倒水，直到装满或者倒空

题解

状态队列/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
37
38
class Solution {
    public boolean canMeasureWater(int x, int y, int z) {
        Deque<int[]> stack = new LinkedList<int[]>();
        stack.push(new int[]{0, 0});
        Set<Long> seen = new HashSet<Long>();
        while (!stack.isEmpty()) {
            if (seen.contains(hash(stack.peek()))) {
                stack.pop();
                continue;
            }
            seen.add(hash(stack.peek()));
            
            int[] state = stack.pop();
            int remain_x = state[0], remain_y = state[1];
            if (remain_x == z || remain_y == z || remain_x + remain_y == z) {
                return true;
            }
            // 把 X 壶灌满。
            stack.push(new int[]{x, remain_y});
            // 把 Y 壶灌满。
            stack.push(new int[]{remain_x, y});
            // 把 X 壶倒空。
            stack.push(new int[]{0, remain_y});
            // 把 Y 壶倒空。
            stack.push(new int[]{remain_x, 0});
            // 把 X 壶的水灌进 Y 壶，直至灌满或倒空。
            stack.push(new int[]{remain_x - Math.min(remain_x, y - remain_y), remain_y + Math.min(remain_x, y - remain_y)});
            // 把 Y 壶的水灌进 X 壶，直至灌满或倒空。
            stack.push(new int[]{remain_x + Math.min(remain_y, x - remain_x), remain_y - Math.min(remain_y, x - remain_x)});
        }
        return false;
    }

    public long hash(int[] state) {
        return (long) state[0] * 1000001 + state[1];
    }
}

数学解法

贝祖定理

只要满足 z ≤ x+y 且这样的 a, b 存在，那么我们的目标就是可以达成的。这是因为：

  • 若 a ≥ 0, b ≥ 0，那么显然可以达成目标。

  • 若 a < 0，那么可以进行以下操作：

    1. 往 y 壶倒水；
    2. 把 y 壶的水倒入 x 壶；
    3. 如果 y 壶不为空，那么 x 壶肯定是满的，把 x 壶倒空，然后再把 y 壶的水倒入 x 壶。

    重复以上操作直至某一步时 x 壶进行了 a 次倒空操作，y 壶进行了 b 次倒水操作。

  • 若 b < 0，方法同上，x 与 y 互换。

而贝祖定理告诉我们，ax+by=z 有解当且仅当 z 是 x, y 的最大公约数的倍数。因此我们只需要找到 x, y 的最大公约数并判断 z 是否是它的倍数即可。

求最大公约数即可

自由之路 514

514. 自由之路 - 力扣（LeetCode）

动态规划

给定一个字符串 ring ，表示刻在外环上的编码；给定另一个字符串 key ，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。

  1. 您可以将 ring 顺时针或逆时针旋转 一个位置 ，计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 key[i] 。
  2. 如果字符 key[i] 已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步。按完之后，您可以开始拼写 key 的下一个字符（下一阶段）, 直至完成所有拼写。

题解

记忆化搜索，memo数组存储

dp设置为，dp(i,j)为此时位于第i位置上，去搜索第j个字符所在位置

使循环数组所有元素相等的最少秒数 2808

给你一个下标从 0 开始长度为 n 的数组 nums 。

每一秒，你可以对数组执行以下操作：

  • 对于范围在 [0, n - 1] 内的每一个下标 i ，将 nums[i] 替换成 nums[i] ，nums[(i - 1 + n) % n] 或者 nums[(i + 1) % n] 三者之一。

注意，所有元素会被同时替换。

请你返回将数组 nums 中所有元素变成相等元素所需要的 最少 秒数。

API

computeIfAbsent 是 Java 中 Map 接口的一个方法，它用于在 Map 中根据指定的键（key）来获取对应的值（value）。如果该键不存在于 Map 中，computeIfAbsent 方法会使用指定的函数来计算一个默认值，并将该默认值存入 Map 中，然后返回该默认值。如果该键已经存在于 Map 中，则不会计算默认值，而是直接返回已存在的值。

数字游戏 LCP 24

小扣在秋日市集入口处发现了一个数字游戏。主办方共有 N 个计数器，计数器编号为 0 ~ N-1。每个计数器上分别显示了一个数字，小扣按计数器编号升序将所显示的数字记于数组 nums。每个计数器上有两个按钮，分别可以实现将显示数字加一或减一。小扣每一次操作可以选择一个计数器，按下加一或减一按钮。

主办方请小扣回答出一个长度为 N 的数组，第 i 个元素(0 <= i < N)表示将 0~i 号计数器 初始 所示数字操作成满足所有条件 nums[a]+1 == nums[a+1],(0 <= a < i) 的最小操作数。回答正确方可进入秋日市集。

由于答案可能很大，请将每个最小操作数对 1,000,000,007 取余。

动态维护中位数

当处理前缀数组 nums 的每个前缀时，我们需要按照提示 2 中的公式计算最小距离和。这个问题的解法类似于 295. 数据流的中位数，我们可以使用两个堆来维护前 k 个数中，nums[i] - i 较小的一半和较大的一半，从而动态维护提示 2 中的「左半之和」以及「右半之和」。

具体来说，我们使用一个大根堆 left 维护较小的一半，其元素和为 leftSum；用一个小根堆 right 维护较大的一半，其元素和为 rightSum。在遍历 nums[i] 时，设 b = nums[i] - i，我们可以按以下方式进行分类讨论：

  1. 如果前缀长度是奇数，此时 left 和 right 的大小相等，我们首先将 b 插入 left，然后弹出 left 的堆顶元素，将其加到 right 中。这个操作可以保证，无论 b 是大是小，此时 right 的堆顶元素就是中位数 x。此时，最小距离和为 rightSum - x - leftSum。
  2. 如果前缀长度是偶数，此时 left 比 right 少一个元素，我们首先将 b 插入 right，然后弹出 right 的堆顶元素，将其加到 left 中。此时，最小距离和为 rightSum - leftSum。

这种方法能够动态地维护中位数以及左半之和和右半之和，并根据前缀长度的奇偶来进行不同的操作，以计算最小距离和。

107 二叉树层序遍历

自底向上的层序遍历

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

简单dp

你需要访问 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 取余后的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int firstDayBeenInAllRooms(vector<int>& nextVisit) {
        int n = nextVisit.size();
        const int MOD = 1000000007;
        long long dp[100005][2] = {0};
        // 处于xx状态时花了多少天
        dp[0][0] = 0;
        dp[0][1] = 1;
        dp[1][0] = 2;
        for(int i = 1;i<n;i++){
            dp[i][0] = (dp[i-1][1] + 1 ) % MOD;
            dp[i][1] = (dp[i][0] + dp[i][0] - dp[nextVisit[i]][0] + 1) % MOD;
        }
        int ans = dp[n-1][0] % MOD;
        return ans >= 0 ? ans : ans + MOD;
    }
};

luogu

P1044 栈

栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。

栈有两种最重要的操作，即 pop（从栈顶弹出一个元素）和 push（将一个元素进栈）。

栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。

卡特兰数