作者： admin

目标

Alice 把 n 个气球排列在一根绳子上。给你一个下标从 0 开始的字符串 colors ，其中 colors[i] 是第 i 个气球的颜色。

Alice 想要把绳子装扮成 五颜六色的 ，且她不希望两个连续的气球涂着相同的颜色，所以她喊来 Bob 帮忙。Bob 可以从绳子上移除一些气球使绳子变成 彩色 。给你一个 下标从 0 开始 的整数数组 neededTime ，其中 neededTime[i] 是 Bob 从绳子上移除第 i 个气球需要的时间（以秒为单位）。

返回 Bob 使绳子变成 彩色 需要的 最少时间 。

示例 1：

输入：colors = "abaac", neededTime = [1,2,3,4,5]
输出：3
解释：在上图中，'a' 是蓝色，'b' 是红色且 'c' 是绿色。
Bob 可以移除下标 2 的蓝色气球。这将花费 3 秒。
移除后，不存在两个连续的气球涂着相同的颜色。总时间 = 3 。

示例 2：

输入：colors = "abc", neededTime = [1,2,3]
输出：0
解释：绳子已经是彩色的，Bob 不需要从绳子上移除任何气球。

示例 3：

输入：colors = "aabaa", neededTime = [1,2,3,4,1]
输出：2
解释：Bob 会移除下标 0 和下标 4 处的气球。这两个气球各需要 1 秒来移除。
移除后，不存在两个连续的气球涂着相同的颜色。总时间 = 1 + 1 = 2 。

说明：

• n == colors.length == neededTime.length
• 1 <= n <= 10^5
• 1 <= neededTime[i] <= 10^4
• colors 仅由小写英文字母组成

思路

水平的绳子上绑着一排气球，现在要使相邻的气球颜色不同，需要解开一些气球，解开每个气球的时间为 neededTime[i] 求所需的最短时间。

将相邻的颜色相同的气球放入堆中，仅保留耗时最大的即可。

代码

/**
 * @date 2025-11-03 8:56
 */
public class MinCost1578 {

    public int minCost(String colors, int[] neededTime) {
        int n = neededTime.length;
        int i = 0;
        int res = 0;
        while (i < n) {
            int max = i;
            int sum = 0;
            char c = colors.charAt(i);
            while (i < n && c == colors.charAt(i)) {
                if (neededTime[i] > neededTime[max]) {
                    max = i;
                }
                sum += neededTime[i++];
            }
            res += sum - neededTime[max];
        }
        return res;
    }

}

性能

目标

给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后，返回修改后的链表的头节点。

示例 1：

输入： nums = [1,2,3], head = [1,2,3,4,5]
输出： [4,5]
解释：
移除数值为 1, 2 和 3 的节点。

示例 2：

输入： nums = [1], head = [1,2,1,2,1,2]
输出： [2,2,2]
解释：
移除数值为 1 的节点。

示例 3：

输入： nums = [5], head = [1,2,3,4]
输出： [1,2,3,4]
解释：
链表中不存在值为 5 的节点。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5
• nums 中的所有元素都是唯一的。
• 链表中的节点数在 [1, 10^5] 的范围内。
• 1 <= Node.val <= 10^5
• 输入保证链表中至少有一个值没有在 nums 中出现过。

思路

依题意模拟即可，删除链表中的指定节点。

代码

/**
 * @date 2025-11-03 13:55
 */
public class ModifiedList3217 {

    public ListNode modifiedList_v1(int[] nums, ListNode head) {
        Set<Integer> set = new HashSet<>(nums.length, 1);
        for (int num : nums) {
            set.add(num);
        }
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;
        while (head != null) {
            if (set.contains(head.val)) {
                prev.next = head.next;
            } else {
                prev = head;
            }
            head = head.next;
        }
        return dummy.next;
    }

}

/**
 * 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; }
 * }
 */

性能

目标

银行内部的防盗安全装置已经激活。给你一个下标从 0 开始的二进制字符串数组 bank ，表示银行的平面图，这是一个大小为 m x n 的二维矩阵。 bank[i] 表示第 i 行的设备分布，由若干 '0' 和若干 '1' 组成。'0' 表示单元格是空的，而 '1' 表示单元格有一个安全设备。

对任意两个安全设备而言，如果同时 满足下面两个条件，则二者之间存在 一个 激光束：

• 两个设备位于两个 不同行 ：r1 和 r2 ，其中 r1 < r2 。
• 满足 r1 < i < r2 的 所有 行 i ，都 没有安全设备 。

激光束是独立的，也就是说，一个激光束既不会干扰另一个激光束，也不会与另一个激光束合并成一束。

返回银行中激光束的总数量。

示例 1：

输入：bank = ["011001","000000","010100","001000"]
输出：8
解释：在下面每组设备对之间，存在一条激光束。总共是 8 条激光束：
 * bank[0][1] -- bank[2][1]
 * bank[0][1] -- bank[2][3]
 * bank[0][2] -- bank[2][1]
 * bank[0][2] -- bank[2][3]
 * bank[0][5] -- bank[2][1]
 * bank[0][5] -- bank[2][3]
 * bank[2][1] -- bank[3][2]
 * bank[2][3] -- bank[3][2]
注意，第 0 行和第 3 行上的设备之间不存在激光束。
这是因为第 2 行存在安全设备，这不满足第 2 个条件。

示例 2：

输入：bank = ["000","111","000"]
输出：0
解释：不存在两个位于不同行的设备

提示：

• m == bank.length
• n == bank[i].length
• 1 <= m, n <= 500
• bank[i][j] 为 '0' 或 '1'

思路

跳过中间的空行，将相邻的非空行上的装置数量相乘。

代码

/**
 * @date 2025-10-27 10:34
 */
public class NumberOfBeams2125 {

    public int numberOfBeams(String[] bank) {
        int prev = 0, cur = 0;
        int res = 0;
        for (String b : bank) {
            for (char c : b.toCharArray()) {
                if (c == '1') {
                    cur++;
                }
            }
            if (cur == 0) {
                continue;
            }
            res += cur * prev;
            prev = cur;
            cur = 0;
        }
        return res;
    }

}

性能

目标

你的任务是为一个很受欢迎的银行设计一款程序，以自动化执行所有传入的交易（转账，存款和取款）。银行共有 n 个账户，编号从 1 到 n 。每个账号的初始余额存储在一个下标从 0 开始的整数数组 balance 中，其中第 (i + 1) 个账户的初始余额是 balance[i] 。

请你执行所有 有效的 交易。如果满足下面全部条件，则交易 有效 ：

• 指定的账户数量在 1 和 n 之间，且
• 取款或者转账需要的钱的总数 小于或者等于 账户余额。

实现 Bank 类：

• Bank(long[] balance) 使用下标从 0 开始的整数数组 balance 初始化该对象。
• boolean transfer(int account1, int account2, long money) 从编号为 account1 的账户向编号为 account2 的账户转帐 money 美元。如果交易成功，返回 true ，否则，返回 false 。
• boolean deposit(int account, long money) 向编号为 account 的账户存款 money 美元。如果交易成功，返回 true ；否则，返回 false 。
• boolean withdraw(int account, long money) 从编号为 account 的账户取款 money 美元。如果交易成功，返回 true ；否则，返回 false 。

示例：

输入：
["Bank", "withdraw", "transfer", "deposit", "transfer", "withdraw"]
[[[10, 100, 20, 50, 30]], [3, 10], [5, 1, 20], [5, 20], [3, 4, 15], [10, 50]]
输出：
[null, true, true, true, false, false]

解释：
Bank bank = new Bank([10, 100, 20, 50, 30]);
bank.withdraw(3, 10);    // 返回 true ，账户 3 的余额是 $20 ，所以可以取款 $10 。
                         // 账户 3 余额为 $20 - $10 = $10 。
bank.transfer(5, 1, 20); // 返回 true ，账户 5 的余额是 $30 ，所以可以转账 $20 。
                         // 账户 5 的余额为 $30 - $20 = $10 ，账户 1 的余额为 $10 + $20 = $30 。
bank.deposit(5, 20);     // 返回 true ，可以向账户 5 存款 $20 。
                         // 账户 5 的余额为 $10 + $20 = $30 。
bank.transfer(3, 4, 15); // 返回 false ，账户 3 的当前余额是 $10 。
                         // 所以无法转账 $15 。
bank.withdraw(10, 50);   // 返回 false ，交易无效，因为账户 10 并不存在。

说明：

• n == balance.length
• 1 <= n, account, account1, account2 <= 10^5
• 0 <= balance[i], money <= 10^12
• transfer, deposit, withdraw 三个函数，每个 最多调用 10^4 次

思路

依题意模拟即可。

代码

class Bank {

    private long[] balance;

    public Bank(long[] balance) {
        this.balance = balance;
    }

    public boolean transfer(int account1, int account2, long money) {
        if (account1 > balance.length || account2 > balance.length || balance[account1 - 1] < money){
            return false;
        }
        balance[account1 - 1] -= money;
        balance[account2 - 1] += money;
        return true;
    }

    public boolean deposit(int account, long money) {
        if (account > balance.length){
            return false;
        }
        balance[account - 1] += money;
        return true;
    }

    public boolean withdraw(int account, long money) {
        if (account > balance.length || balance[account - 1] < money ){
            return false;
        }
        balance[account - 1] -= money;
        return true;
    }
}

/**
 * Your Bank object will be instantiated and called as such:
 * Bank obj = new Bank(balance);
 * boolean param_1 = obj.transfer(account1,account2,money);
 * boolean param_2 = obj.deposit(account,money);
 * boolean param_3 = obj.withdraw(account,money);
 */

性能

目标

如果整数 x 满足：对于每个数位 d ，这个数位 恰好 在 x 中出现 d 次。那么整数 x 就是一个 数值平衡数 。

给你一个整数 n ，请你返回 严格大于 n 的 最小数值平衡数 。

示例 1：

输入：n = 1
输出：22
解释：
22 是一个数值平衡数，因为：
- 数字 2 出现 2 次 
这也是严格大于 1 的最小数值平衡数。

示例 2：

输入：n = 1000
输出：1333
解释：
1333 是一个数值平衡数，因为：
- 数字 1 出现 1 次。
- 数字 3 出现 3 次。 
这也是严格大于 1000 的最小数值平衡数。
注意，1022 不能作为本输入的答案，因为数字 0 的出现次数超过了 0 。

示例 3：

输入：n = 3000
输出：3133
解释：
3133 是一个数值平衡数，因为：
- 数字 1 出现 1 次。
- 数字 3 出现 3 次。 
这也是严格大于 3000 的最小数值平衡数。

说明：

• 0 <= n <= 10^6

思路

定义平衡数中每一位上数字的出现次数 cnt[d] = d，判断大于 n 的最小平衡数。

回溯构造 10^7 范围内的所有平衡数，然后二分查找。

官网题解是枚举所有大于 n 的整数，判断是否是平衡数，也可以预处理 (n, 1224444] 范围内的所有平衡数，然后二分查找。

代码

/**
 * @date 2025-10-24 9:12
 */
public class NextBeautifulNumber2048 {

    public int nextBeautifulNumber(int n) {
        return set.higher(n);
    }

    private static final TreeSet<Integer> set = new TreeSet<>();

    static {
        int[] cnt = new int[7];
        Arrays.setAll(cnt, i -> i);
        dfs(0, 0, 7, cnt);
    }

    public static void dfs(int cur, int l, int length, int[] cnt) {
        if (l > length + 1) {
            return;
        }
        boolean balance = true;
        for (int i = 1; i < cnt.length; i++) {
            if (cnt[i] != i && cnt[i] != 0) {
                balance = false;
                break;
            }
        }
        if (balance) {
            set.add(cur);
        }
        for (int i = 1; i < cnt.length; i++) {
            if (cnt[i] == 0) {
                continue;
            }
            cnt[i]--;
            dfs(cur * 10 + i, l + 1, length, cnt);
            cnt[i]++;
        }
    }

}

性能