标签： 模拟

目标

一个字符串如果没有 三个连续 相同字符，那么它就是一个 好字符串 。

给你一个字符串 s ，请你从 s 删除 最少 的字符，使它变成一个 好字符串 。

请你返回删除后的字符串。题目数据保证答案总是 唯一的 。

示例 1：

输入：s = "leeetcode"
输出："leetcode"
解释：
从第一组 'e' 里面删除一个 'e' ，得到 "leetcode" 。
没有连续三个相同字符，所以返回 "leetcode" 。

示例 2：

输入：s = "aaabaaaa"
输出："aabaa"
解释：
从第一组 'a' 里面删除一个 'a' ，得到 "aabaaaa" 。
从第二组 'a' 里面删除两个 'a' ，得到 "aabaa" 。
没有连续三个相同字符，所以返回 "aabaa" 。

示例 3：

输入：s = "aab"
输出："aab"
解释：没有连续三个相同字符，所以返回 "aab" 。

说明：

• 1 <= s.length <= 10^5
• s 只包含小写英文字母。

思路

定义 好字符串 是不包含连续三个相同字符的字符串，给定一个字符串，删掉最少的字符使之变为好字符串。

记录连续重复字符个数，不同则重置，如果达到三个则跳过。

代码

/**
 * @date 2025-07-21 8:40
 */
public class MakeFancyString1957 {

    public String makeFancyString_v1(String s) {
        int n = s.length();
        char prev = ' ';
        int cnt = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (prev == c) {
                if (cnt < 2) {
                    cnt++;
                    sb.append(c);
                }
            } else {
                sb.append(c);
                prev = c;
                cnt = 1;
            }
        }
        return sb.toString();
    }

}

性能

目标

Alice 和 Bob 正在玩一个游戏。最初，Alice 有一个字符串 word = "a"。

给定一个正整数 k。

现在 Bob 会要求 Alice 执行以下操作 无限次 :

• 将 word 中的每个字符 更改 为英文字母表中的 下一个 字符来生成一个新字符串，并将其 追加 到原始的 word。

例如，对 "c" 进行操作生成 "cd"，对 "zb" 进行操作生成 "zbac"。

在执行足够多的操作后， word 中 至少 存在 k 个字符，此时返回 word 中第 k 个字符的值。

注意，在操作中字符 'z' 可以变成 'a'。

示例 1:

输入：k = 5
输出："b"
解释：
最初，word = "a"。需要进行三次操作:
生成的字符串是 "b"，word 变为 "ab"。
生成的字符串是 "bc"，word 变为 "abbc"。
生成的字符串是 "bccd"，word 变为 "abbcbccd"。

示例 2:

输入：k = 10
输出："c"

说明：

• 1 <= k <= 500

思路

开始的时候有一个字符 a，可以反复执行以下操作：将现有的所有字母替换为它在字母表中的下一个字母（z 的下一个字母为 a），拼接到当前字符后面。返回第 k 个字母。

暴力模拟操作过程。

代码

/**
 * @date 2025-07-03 8:48
 */
public class KthCharacter3304 {

    public char kthCharacter(int k) {
        StringBuilder sb = new StringBuilder();
        sb.append('a');
        while (sb.length() < k) {
            String s = sb.toString();
            int length = s.length();
            for (int i = 0; i < length; i++) {
                char c = (char) ('a' + (s.charAt(i) - 'a' + 1) % 26);
                sb.append(c);
            }
        }
        return sb.toString().charAt(k - 1);
    }

}

性能

目标

字符串 s 可以按下述步骤划分为若干长度为 k 的组：

• 第一组由字符串中的前 k 个字符组成，第二组由接下来的 k 个字符串组成，依此类推。每个字符都能够成为 某一个 组的一部分。
• 对于最后一组，如果字符串剩下的字符 不足 k 个，需使用字符 fill 来补全这一组字符。

注意，在去除最后一个组的填充字符 fill（如果存在的话）并按顺序连接所有的组后，所得到的字符串应该是 s 。

给你一个字符串 s ，以及每组的长度 k 和一个用于填充的字符 fill ，按上述步骤处理之后，返回一个字符串数组，该数组表示 s 分组后 每个组的组成情况。

示例 1：

输入：s = "abcdefghi", k = 3, fill = "x"
输出：["abc","def","ghi"]
解释：
前 3 个字符是 "abc" ，形成第一组。
接下来 3 个字符是 "def" ，形成第二组。
最后 3 个字符是 "ghi" ，形成第三组。
由于所有组都可以由字符串中的字符完全填充，所以不需要使用填充字符。
因此，形成 3 组，分别是 "abc"、"def" 和 "ghi" 。

示例 2：

输入：s = "abcdefghij", k = 3, fill = "x"
输出：["abc","def","ghi","jxx"]
解释：
与前一个例子类似，形成前三组 "abc"、"def" 和 "ghi" 。
对于最后一组，字符串中仅剩下字符 'j' 可以用。为了补全这一组，使用填充字符 'x' 两次。
因此，形成 4 组，分别是 "abc"、"def"、"ghi" 和 "jxx" 。

说明：

• 1 <= s.length <= 100
• s 仅由小写英文字母组成
• 1 <= k <= 100
• fill 是一个小写英文字母

思路

将字符串划分为长度为 k 的组，如果长度不足则使用 fill 补全。

代码

/**
 * @date 2025-06-22 12:16
 */
public class DivideString2138 {

    public String[] divideString(String s, int k, char fill) {
        int n = s.length();
        String[] res = new String[n / k + (n % k == 0 ? 0 : 1)];
        char[] chars = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (i != 0 && i % k == 0) {
                res[j++] = sb.toString();
                sb = new StringBuilder();
            }
            sb.append(chars[i]);
        }
        int cnt = k - sb.length();
        while (cnt > 0) {
            sb.append(fill);
            cnt--;
        }
        if (j == res.length - 1) {
            res[j] = sb.toString();
        }
        return res;
    }

}

性能

目标

给你一个整数数组 nums，你需要确保数组中的元素 互不相同 。为此，你可以执行以下操作任意次：

• 从数组的开头移除 3 个元素。如果数组中元素少于 3 个，则移除所有剩余元素。

注意：空数组也视作为数组元素互不相同。返回使数组元素互不相同所需的 最少操作次数 。

示例 1：

输入： nums = [1,2,3,4,2,3,3,5,7]
输出： 2
解释：
第一次操作：移除前 3 个元素，数组变为 [4, 2, 3, 3, 5, 7]。
第二次操作：再次移除前 3 个元素，数组变为 [3, 5, 7]，此时数组中的元素互不相同。
因此，答案是 2。

示例 2：

输入： nums = [4,5,6,4,4]
输出： 2
解释：
第一次操作：移除前 3 个元素，数组变为 [4, 4]。
第二次操作：移除所有剩余元素，数组变为空。
因此，答案是 2。

示例 3：

输入： nums = [6,7,8,9]
输出： 0
解释：
数组中的元素已经互不相同，因此不需要进行任何操作，答案是 0。

说明：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

思路

每次操作可以删除数组前三个元素，求使数组元素互不相同所需要的最小操作次数。

最直接的想法是记录数组中每个元素的出现次数，同时记录重复元素的个数，然后模拟删除操作，如果将某个元素的出现次数减为 1，那么将重复元素个数减 1，直到重复元素个数为 0，返回操作次数。

网友题解使用逆向思维，倒序遍历数组，直到遇到第一个重复的元素，由于操作是从头开始的，因此一定要删除该重复元素。假如下标是 i，那么需要操作 ⌈(i + 1)/3⌉ = i/3 + 1 次。

对于整数 a >= 0, b > 0，有 ⌈a/b⌉ = ⌊(a + b - 1)/b⌋，将 a = qb + r 带入分析即可。或者直接写 ⌊a/b⌋ + a % b > 0 ? 1 : 0。

正向考虑稍微有点复杂，需要找到重复数字前一个下标中的最大下标。

代码

/**
 * @date 2025-04-08 8:43
 */
public class MinimumOperations3396 {

    public int minimumOperations_v1(int[] nums) {
        int[] index = new int[101];
        Set<Integer> set = new HashSet<>();
        Arrays.fill(index, -1);
        int maxIndex = -1;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (set.contains(num)) {
                maxIndex = Math.max(maxIndex, index[num]);
            }
            set.add(num);
            index[num] = i;
        }
        if (maxIndex == -1) {
            return 0;
        } else {
            return maxIndex / 3 + 1;
        }
    }

    public int minimumOperations(int[] nums) {
        int[] cnt = new int[101];
        Queue<Integer> q = new ArrayDeque<>();
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            q.offer(num);
            if (++cnt[num] > 1) {
                set.add(num);
            }
        }
        if (set.size() == 0) {
            return 0;
        }
        int sameCnt = set.size();
        int res = 0;
        while (!q.isEmpty()) {
            res++;
            for (int i = 0; !q.isEmpty() && i < 3; i++) {
                if (--cnt[q.poll()] == 1) {
                    sameCnt--;
                }
            }
            if (sameCnt == 0) {
                break;
            }
        }
        return res;
    }

}

性能

目标

给你一个 正 整数 n 。

用 even 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的偶数下标的个数。

用 odd 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的奇数下标的个数。

返回整数数组 answer ，其中 answer = [even, odd] 。

示例 1：

输入：n = 17
输出：[2,0]
解释：17 的二进制形式是 10001 。 
下标 0 和 下标 4 对应的值为 1 。 
共有 2 个偶数下标，0 个奇数下标。

示例 2：

输入：n = 2
输出：[0,1]
解释：2 的二进制形式是 10 。 
下标 1 对应的值为 1 。 
共有 0 个偶数下标，1 个奇数下标。

说明：

• 1 <= n <= 1000

思路

返回正整数 n 偶数比特位与奇数比特位为 1 的个数。

可以遍历 n 的 bit 位进行统计，也可以使用掩码调用库函数统计。

代码

/**
 * @date 2025-02-20 8:39
 */
public class EvenOddBit2595 {

    public int[] evenOddBit_v2(int n) {
        // 提取偶数位 0101
        int even = n & 0x55555555;
        // 提取奇数位 1010
        int odd = n & 0xAAAAAAAA;
        return new int[]{Integer.bitCount(even), Integer.bitCount(odd)};
    }

    public int[] evenOddBit_v1(int n) {
        int even = 0;
        int odd = 0;
        while (n > 0) {
            even += n & 1;
            n >>= 1;
            odd += n & 1;
            n >>= 1;
        }
        return new int[]{even, odd};
    }

}

性能

目标

给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。

完成所有替换操作后，请你返回这个数组。

示例 1：

输入：arr = [17,18,5,4,6,1]
输出：[18,6,6,6,1,-1]
解释：
- 下标 0 的元素 --> 右侧最大元素是下标 1 的元素 (18)
- 下标 1 的元素 --> 右侧最大元素是下标 4 的元素 (6)
- 下标 2 的元素 --> 右侧最大元素是下标 4 的元素 (6)
- 下标 3 的元素 --> 右侧最大元素是下标 4 的元素 (6)
- 下标 4 的元素 --> 右侧最大元素是下标 5 的元素 (1)
- 下标 5 的元素 --> 右侧没有其他元素，替换为 -1

示例 2：

输入：arr = [400]
输出：[-1]
解释：下标 0 的元素右侧没有其他元素。

说明：

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

思路

将数组中的元素替换为其后面元素的最大值。

最大值不算当前元素，因此在将后面元素最大值赋值给当前元素时会丢失当前元素，导致前面元素的最大值丢失。而如果先将当前元素与后续元素最大值进行更新，最大值就就包含了当前元素。因此需要临时变量保存当前元素值，再用临时变量更新最大值。

代码

/**
 * @date 2025-02-16 17:28
 */
public class ReplaceElements1299 {

    public int[] replaceElements(int[] arr) {
        int n = arr.length;
        int max = -1;
        for (int i = n - 1; i >= 0; i--) {
            int tmp = arr[i];
            arr[i] = max;
            max = Math.max(tmp, max);
        }
        return arr;
    }
}

性能

目标

给你一个字符串 num ，表示一个大整数。如果一个整数满足下述所有条件，则认为该整数是一个 优质整数 ：

• 该整数是 num 的一个长度为 3 的 子字符串 。
• 该整数由唯一一个数字重复 3 次组成。

以字符串形式返回 最大的优质整数 。如果不存在满足要求的整数，则返回一个空字符串 "" 。

注意：

• 子字符串 是字符串中的一个连续字符序列。
• num 或优质整数中可能存在 前导零 。

示例 1：

输入：num = "6777133339"
输出："777"
解释：num 中存在两个优质整数："777" 和 "333" 。
"777" 是最大的那个，所以返回 "777" 。

示例 2：

输入：num = "2300019"
输出："000"
解释："000" 是唯一一个优质整数。

示例 3：

输入：num = "42352338"
输出：""
解释：不存在长度为 3 且仅由一个唯一数字组成的整数。因此，不存在优质整数。

说明：

• 3 <= num.length <= 1000
• num 仅由数字（0 - 9）组成

思路

判断字符串中是否存在 三个连续相同的数字，如果有多个返回数字最大的那个。

可以使用一个变量记录连续相同的字符个数，如果不同就重置 cnt 为 1。

代码

/**
 * @date 2025-01-08 8:48
 */
public class LargestGoodInteger2264 {

    public String largestGoodInteger(String num) {
        char c = 0;
        int n = num.length();
        int cnt = 1;
        for (int i = 1; i < n; i++) {
            if (num.charAt(i) == num.charAt(i - 1)) {
                cnt++;
            } else {
                cnt = 1;
                continue;
            }
            if (cnt == 3 && c < num.charAt(i)) {
                c = num.charAt(i);
            }
        }
        return c > 0 ? new String(new char[]{c, c, c}) : "";
    }

}

性能