shelterofly

目标

给你一个字符串 s ，它只包含三种字符 a, b 和 c 。

请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。

示例 1：

输入：s = "abcabc"
输出：10
解释：包含 a，b 和 c 各至少一次的子字符串为 "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" 和 "abc" (相同字符串算多次)。

示例 2：

输入：s = "aaacb"
输出：3
解释：包含 a，b 和 c 各至少一次的子字符串为 "aaacb", "aacb" 和 "acb" 。

示例 3：

输入：s = "abc"
输出：1

说明：

• 3 <= s.length <= 5 x 10^4
• s 只包含字符 a，b 和 c 。

思路

有一个字符串只包含三个字符 a b c，求这三个字符至少出现一次的子串个数。

直接的想法是计算这三个字符出现次数的前缀和，然后使用滑动窗口。使用前缀和来判断窗口内的子串是否满足条件，如果 [l, r] 满足条件，那么 [l, r ~ n - 1] 也满足条件。

判断字符是否至少出现一次可以不用前缀和，使用三个变量记录它们上次出现的下标，如果小于左端点则用 -1 标记。

代码

/**
 * @date 2026-06-30 9:14
 */
public class NumberOfSubstrings1358 {

    public int numberOfSubstrings(String s) {
        int n = s.length();
        int a = -1, b = -1, c = -1;
        int l = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'a') {
                a = i;
            } else if (s.charAt(i) == 'b') {
                b = i;
            } else {
                c = i;
            }
            while (a >= 0 && b >= 0 && c >= 0) {
                res += n - i;
                if (a <= l) {
                    a = -1;
                } else if (b <= l) {
                    b = -1;
                } else if (c <= l) {
                    c = -1;
                }
                l++;
            }
        }
        return res;
    }

}

性能

目标

给你一个正整数数组 arr 。请你对 arr 执行一些操作（也可以不进行任何操作），使得数组满足以下条件：

• arr 中 第一个 元素必须为 1 。
• 任意相邻两个元素的差的绝对值 小于等于 1 ，也就是说，对于任意的 1 <= i < arr.length （数组下标从 0 开始），都满足 abs(arr[i] - arr[i - 1]) <= 1 。abs(x) 为 x 的绝对值。

你可以执行以下 2 种操作任意次：

• 减小 arr 中任意元素的值，使其变为一个 更小的正整数 。
• 重新排列 arr 中的元素，你可以以任意顺序重新排列。

请你返回执行以上操作后，在满足前文所述的条件下，arr 中可能的 最大值 。

示例 1：

输入：arr = [2,2,1,2,1]
输出：2
解释：
我们可以重新排列 arr 得到 [1,2,2,2,1] ，该数组满足所有条件。
arr 中最大元素为 2 。

示例 2：

输入：arr = [100,1,1000]
输出：3
解释：
一个可行的方案如下：
1. 重新排列 arr 得到 [1,100,1000] 。
2. 将第二个元素减小为 2 。
3. 将第三个元素减小为 3 。
现在 arr = [1,2,3] ，满足所有条件。
arr 中最大元素为 3 。

示例 3：

输入：arr = [1,2,3,4,5]
输出：5
解释：数组已经满足所有条件，最大元素为 5 。

说明：

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^9

思路

有一个正整数数组 arr，可以将任意元素变成比它更小的正整数，也可以按任意顺序重新排列元素。需要将 arr 变成目标数组，使得第一个元素为 1，且相邻元素差的绝对值不超过 1。返回目标数组可能的最大值。

根据题目要求，第一个元素必须是 1，且相邻元素差的绝对值不超过 1，要使元素值变大只能 +1，且该元素只能由大于等于它的元素转化而来。

贪心策略，从小到大排序数组，遍历数组记录最大值，由于元素值都大于 0，都可以操作成 1，当元素值小于最大值时直接跳过，否则，将元素操作成最大值加一。越大的元素越晚操作，可以使最大值更大。

由于最大值不超过 n，可以将大于 n 的元素都视为 n，这样可以使用计数排序优化。

代码

/**
 * @date 2026-06-29 18:11
 */
public class MaximumElementAfterDecrementingAndRearranging1846 {

    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
        Arrays.sort(arr);
        int res = 0;
        for (int num : arr) {
            if (num <= res) {
                continue;
            }
            res++;
        }
        return res;
    }

}

性能

目标

夏日炎炎，小男孩 Tony 想买一些雪糕消消暑。

商店中新到 n 支雪糕，用长度为 n 的数组 costs 表示雪糕的定价，其中 costs[i] 表示第 i 支雪糕的现金价格。Tony 一共有 coins 现金可以用于消费，他想要买尽可能多的雪糕。

注意：Tony 可以按任意顺序购买雪糕。

给你价格数组 costs 和现金量 coins ，请你计算并返回 Tony 用 coins 现金能够买到的雪糕的 最大数量 。

你必须使用计数排序解决此问题。

示例 1：

输入：costs = [1,3,2,4,1], coins = 7
输出：4
解释：Tony 可以买下标为 0、1、2、4 的雪糕，总价为 1 + 3 + 2 + 1 = 7

示例 2：

输入：costs = [10,6,8,7,7,8], coins = 5
输出：0
解释：Tony 没有足够的钱买任何一支雪糕。

示例 3：

输入：costs = [1,6,3,1,2,5], coins = 20
输出：6
解释：Tony 可以买下所有的雪糕，总价为 1 + 6 + 3 + 1 + 2 + 5 = 18 。

说明：

• costs.length == n
• 1 <= n <= 10^5
• 1 <= costs[i] <= 10^5
• 1 <= coins <= 10^8

思路

costs[i] 表示第 i 支雪糕的数量，求使用现金 coins 所能购买雪糕的最大数量。

贪心策略：优先购买价格较低的雪糕。使用计数排序记录每种价格的雪糕数量，从小到大遍历价格，累加当前所能购买的雪糕数量，如果超过剩余金额直接返回。

代码

/**
 * @date 2026-06-22 9:27
 */
public class MaxIceCream1833 {

    public int maxIceCream_v1(int[] costs, int coins) {
        int max = 0;
        for (int cost : costs) {
            max = Math.max(max, cost);
        }
        int[] cnt = new int[max + 1];
        for (int cost : costs) {
            cnt[cost]++;
        }
        int res = 0;
        for (int i = 1; i < cnt.length; i++) {
            if (cnt[i] == 0) {
                continue;
            }
            if (coins < i) {
                return res;
            }
            int amount = Math.min(coins / i, cnt[i]);
            coins -= amount * i;
            res += amount;
        }
        return res;
    }

}

性能

目标

给你两个数 hour 和 minutes 。请你返回在时钟上，由给定时间的时针和分针组成的较小角的角度（60 单位制）。

示例 1：

输入：hour = 12, minutes = 30
输出：165

示例 2：

输入：hour = 3, minutes = 30
输出；75

示例 3：

输入：hour = 3, minutes = 15
输出：7.5

示例 4：

输入：hour = 4, minutes = 50
输出：155

示例 5：

输入：hour = 12, minutes = 0
输出：0

说明：

• 1 <= hour <= 12
• 0 <= minutes <= 59
• 与标准答案误差在 10^-5 以内的结果都被视为正确结果。

思路

计算时钟时针与分针的较小夹角。

问题的关键是时针转动的角度不能直接按 hour 来算，根据分针的指向有一定的偏移，偏移的角度是 minutes / 60 * 30，其中 30 是一个小时格子的角度。hour / 12 * 360 + minutes / 60 * 30 - minutes / 60 * 360 = 30 * hour - minutes * 5.5

代码

/**
 * @date 2026-06-18 9:17
 */
public class AngleClock1344 {

    public double angleClock(int hour, int minutes) {
        double res = Math.abs(30 * hour - minutes * 5.5);
        return Math.min(res, 360 - res);
    }
}

性能

目标

给你一个字符串 s，它由小写英文字母和特殊字符：*、# 和 % 组成。

请根据以下规则从左到右处理 s 中的字符，构造一个新的字符串 result：

• 如果字符是 小写 英文字母，则将其添加到 result 中。
• 字符 '*' 会 删除 result 中的最后一个字符（如果存在）。
• 字符 '#' 会 复制 当前的 result 并 追加 到其自身后面。
• 字符 '%' 会 反转 当前的 result。

在处理完 s 中的所有字符后，返回最终的字符串 result。

示例 1：

输入： s = "a#b%*"
输出： "ba"
解释：
i s[i] 操作 当前 result
0 'a' 添加 'a' "a"
1 '#' 复制 result "aa"
2 'b' 添加 'b' "aab"
3 '%' 反转 result "baa"
4 '*' 删除最后一个字符 "ba"
因此，最终的 result 是 "ba"。

示例 2：

输入： s = "z*#"
输出： ""
解释：
i s[i] 操作 当前 result
0 'z' 添加 'z' "z"
1 '*' 删除最后一个字符 ""
2 '#' 复制字符串 ""
因此，最终的 result 是 ""。

说明:

• 1 <= s.length <= 20
• s 只包含小写英文字母和特殊字符 *、# 和 %。

思路

根据规则从左到右处理字符串 s，如果时小写字母添加到结果 result，如果是 * 删除 result 的最后一个字符，如果是 # 将 result 追加到自身的后面，如果是 % 则反转当前的 result。

字符串长度最大为 20，可以暴力模拟。

代码

/**
 * @date 2025-07-14 9:15
 */
public class ProcessStrQ1 {

    public String processStr(String s) {
        StringBuilder sb = new StringBuilder();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            switch (c) {
                case '*':
                    if (sb.length() > 0) {
                        sb.deleteCharAt(sb.length() - 1);
                    }
                    break;
                case '#':
                    sb.append(sb);
                    break;
                case '%':
                    sb.reverse();
                    break;
                default:
                    sb.append(c);
            }
        }
        return sb.toString();
    }

}

性能

目标

给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。

长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。

对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。

示例 1：

输入：head = [1,3,4,7,1,2,6]
输出：[1,3,4,1,2,6]
解释：
上图表示给出的链表。节点的下标分别标注在每个节点的下方。
由于 n = 7 ，值为 7 的节点 3 是中间节点，用红色标注。
返回结果为移除节点后的新链表。 

示例 2：

输入：head = [1,2,3,4]
输出：[1,2,4]
解释：
上图表示给出的链表。
对于 n = 4 ，值为 3 的节点 2 是中间节点，用红色标注。

示例 3：

输入：head = [2,1]
输出：[2]
解释：
上图表示给出的链表。
对于 n = 2 ，值为 1 的节点 1 是中间节点，用红色标注。
值为 2 的节点 0 是移除节点 1 后剩下的唯一一个节点。

说明：

• 链表中节点的数目在范围 [1, 10^5] 内
• 1 <= Node.val <= 10^5

思路

删除链表的中间节点。

使用快慢指针，开始时都指向头节点，快指针每次走两步，慢指针走一步。当快指针指向最后一个节点或者 null 时，慢指针指向中间节点。因此需要在慢指针更新前将节点删除掉。

代码

/**
 * @date 2026-06-15 8:59
 */
public class DeleteMiddle2095 {

    public ListNode deleteMiddle(ListNode head) {
        if (head.next == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (true) {
            fast = fast.next.next;
            if (fast == null || fast.next == null) {
                slow.next = slow.next.next;
                break;
            }
            slow = slow.next;
        }
        return head;
    }

}

性能