标签： 模拟

目标

给你一个下标从 0 开始的二维整数数组 dimensions。

对于所有下标 i (0 <= i < dimensions.length)，dimensions[i][0] 表示矩形 i 的长度，而 dimensions[i][1] 表示矩形 i 的宽度。

返回对角线最 长 的矩形的 面积 。如果存在多个对角线长度相同的矩形，返回面积最 大 的矩形的面积。

示例 1：

输入：dimensions = [[9,3],[8,6]]
输出：48
解释：
下标 = 0，长度 = 9，宽度 = 3。对角线长度 = sqrt(9 * 9 + 3 * 3) = sqrt(90) ≈ 9.487。
下标 = 1，长度 = 8，宽度 = 6。对角线长度 = sqrt(8 * 8 + 6 * 6) = sqrt(100) = 10。
因此，下标为 1 的矩形对角线更长，所以返回面积 = 8 * 6 = 48。

示例 2：

输入：dimensions = [[3,4],[4,3]]
输出：12
解释：两个矩形的对角线长度相同，为 5，所以最大面积 = 12。

说明：

• 1 <= dimensions.length <= 100
• dimensions[i].length == 2
• 1 <= dimensions[i][0], dimensions[i][1] <= 100

思路

依题意模拟即可。

代码

/**
 * @date 2025-08-26 8:45
 */
public class AreaOfMaxDiagonal3000 {

    /**
     * 网友题解
     */
    class Solution {
        public int areaOfMaxDiagonal(int[][] dimensions) {
            int ans = 0, maxL = 0;
            for (int[] d : dimensions) {
                int x = d[0], y = d[1];
                int l = x * x + y * y;
                if (l > maxL || l == maxL && x * y > ans) {
                    maxL = l;
                    ans = x * y;
                }
            }
            return ans;
        }
    }

    /**
     * 执行通过
     */
    public int areaOfMaxDiagonal(int[][] dimensions) {
        int res = 0;
        int diagonal = 0;
        for (int[] dimension : dimensions) {
            int length = dimension[0];
            int width = dimension[1];
            int cur = length * length + width * width;
            if (diagonal < cur) {
                res = length * width;
                // 出错点：不要忘记更新 diagonal
                diagonal = cur;
            } else if (diagonal == cur) {
                // 出错点：对角线相等需要分开处理，取面积的最大值
                res = Math.max(res, length * width);
            }
        }
        return res;
    }

}

性能

目标

给你一个仅由数字 6 和 9 组成的正整数 num。

你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成 6 。

请返回你可以得到的最大数字。

示例 1：

输入：num = 9669
输出：9969
解释：
改变第一位数字可以得到 6669 。
改变第二位数字可以得到 9969 。
改变第三位数字可以得到 9699 。
改变第四位数字可以得到 9666 。
其中最大的数字是 9969 。

示例 2：

输入：num = 9996
输出：9999
解释：将最后一位从 6 变到 9，其结果 9999 是最大的数。

示例 3：

输入：num = 9999
输出：9999
解释：无需改变就已经是最大的数字了。

说明：

• 1 <= num <= 10^4
• num 每一位上的数字都是 6 或者 9 。

思路

有一个由 6 和 9 组成的数字，可以最多将一个 6 变成 9，返回可以得到的最大数字。

将左边第一个 6 变为 9 得到的数字最大。

代码

/**
 * @date 2025-08-16 17:09
 */
public class Maximum69Number1323 {

    public int maximum69Number(int num) {
        int l = String.valueOf(num).length();
        int pow10 = (int) Math.pow(10, l - 1);
        int n = num;
        while (pow10 > 0) {
            if (n / pow10 == 6) {
                return num + 3 * pow10;
            }
            n -= 9 * pow10;
            pow10 /= 10;
        }
        return num;
    }

}

性能

目标

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

给你一个字符串 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};
    }

}

性能