admin – 第 27 页 – shelterofly

目标

给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

说明：

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 已按非递减顺序排序

进阶：

请你设计时间复杂度为 O(n) 的算法解决本问题

思路

有一个非递减顺序排列的数组（数组中存在负数），求其各元素平方组成的数组，要求也按非递减顺序排列。

将负数的绝对值压入栈中直到遇到正数，然后比较当前正数与栈顶元素的大小，取其最小值计算平方即可。这里使用了指针模拟栈的操作。

代码


/**
 * @date 2024-09-08 20:40
 */
public class SortedSquares977 {

    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int top = -1;
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) {
                nums[i] = - nums[i];
                top++;
            } else {
                while (top >= 0 && nums[i] >= nums[top]) {
                    res[j++] = nums[top] * nums[top];
                    top--;
                }
                res[j++] = nums[i] * nums[i];
            }
        }
        // 如果没有正数，循环中的else分支不会执行，这里判断一下
        while (top >= 0) {
            res[j++] = nums[top] * nums[top];
            top--;
        }
        return res;
    }

}

性能

目标

给你一个整数数组 nums 和一个非负整数 k 。如果一个整数序列 seq 满足在范围下标范围 [0, seq.length - 2] 中存在不超过 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为好序列。

请你返回 nums 中好子序列的最长长度

示例 1：

输入：nums = [1,2,1,1,3], k = 2
输出：4
解释：
最长好子序列为 [1,2,1,1,3] 。

示例 2：

输入：nums = [1,2,3,4,5,1], k = 0
输出：2
解释：
最长好子序列为 [1,2,3,4,5,1] 。

说明：

1 <= nums.length <= 5 * 10^3
1 <= nums[i] <= 10^9
0 <= k <= min(50, nums.length)

思路

这个和昨天的题类似，只不过数据范围变了。

// todo

代码

性能

目标

请你返回 nums 中好 子序列 的最长长度

示例 1：

输入：nums = [1,2,1,1,3], k = 2
输出：4
解释：
最长好子序列为 [1,2,1,1] 。

示例 2：

输入：nums = [1,2,3,4,5,1], k = 0
输出：2
解释：
最长好子序列为 [1,1] 。

说明：

1 <= nums.length <= 500
1 <= nums[i] <= 10^9
0 <= k <= min(nums.length, 25)

提示：

The absolute values in nums don’t really matter. So we can remap the set of values to the range [0, n - 1].
Let dp[i][j] be the length of the longest subsequence till index j with at most i positions such that seq[i] != seq[i + 1].
For each value x from left to right, update dp[i][x] = max(dp[i][x] + 1, dp[i - 1][y] + 1), where y != x.

思路

求整数数组 nums 的子序列，要求子序列中最多存在 k 个下标 i 满足 seq[i] != seq[i + 1]，即至多 k 对相邻元素不同。

只要选出了子序列，那么相邻元素不同的对数就已经确定。

记忆化搜索超时了 // todo

代码

性能

目标

给你一个字符串 s 。

你的任务是重复以下操作删除所有数字字符：

删除第一个数字字符以及它左边最近的非数字字符。

请你返回删除所有数字字符以后剩下的字符串。

示例 1：

输入：s = "abc"
输出："abc"
解释：
字符串中没有数字。

示例 2：

输入：s = "cb34"
输出：""
解释：
一开始，我们对 s[2] 执行操作，s 变为 "c4" 。
然后对 s[1] 执行操作，s 变为 "" 。

说明：

1 <= s.length <= 100
s 只包含小写英文字母和数字字符。
输入保证所有数字都可以按以上操作被删除。

思路

删除给定字符串中的数字字符，每次删除操作需要同步删除该字符左侧最后一个非数字字符。

遍历的过程中使用栈保存非数字字符，遇到数字字符就弹栈，然后返回栈底到栈顶的字符即可。

知识点：

ArrayDeque 双端队列的特性取决于如何放入数据

                start
         last           first
offer       4 3 2 1
push              1 2 3 4

offer是向左添加数据
push是向右添加数据
poll/pop/remove 默认从右向左取数据
如果api中带last，例如pollLast、removeLast则是从左向右取，first则相反

代码


/**
 * @date 2024-09-05 8:47
 */
public class ClearDigits3174 {

    public String clearDigits(String s) {
        int n = s.length();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c > '9' || c < '0') {
                sb.append(c);
            } else {
                sb.deleteCharAt(sb.length() - 1);
            }
        }
        return sb.toString();
    }

}

性能

目标

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，其中 n 是班级中学生的总数。班主任希望能够在让所有学生保持开心的情况下选出一组学生：

如果能够满足下述两个条件之一，则认为第 i 位学生将会保持开心：

这位学生被选中，并且被选中的学生人数严格大于 nums[i] 。
这位学生没有被选中，并且被选中的学生人数严格小于 nums[i] 。

返回能够满足让所有学生保持开心的分组方法的数目。

示例 1：

输入：nums = [1,1]
输出：2
解释：
有两种可行的方法：
班主任没有选中学生。
班主任选中所有学生形成一组。 
如果班主任仅选中一个学生来完成分组，那么两个学生都无法保持开心。因此，仅存在两种可行的方法。

示例 2：

输入：nums = [6,0,3,3,6,7,2,7]
输出：3
解释：
存在三种可行的方法：
班主任选中下标为 1 的学生形成一组。
班主任选中下标为 1、2、3、6 的学生形成一组。
班主任选中所有学生形成一组。

说明：

1 <= nums.length <= 10^5
0 <= nums[i] < nums.length

思路

从数组中选择一组元素，使之满足该组元素个数严格大于组中所有元素值并且严格小于未被选择的元素值，求满足条件的所有选择数。

注意到元素值不超过数组长度，可以先统计各元素值的出现次数 cnt[i]，然后遍历 cnt。

这道题的关键是要意识到：值相同的元素要么同时被选，要么同时不被选。因为选择的元素个数 sum 应该大于所有选择的元素值，小于所有未选择的元素值，一个元素不可能既小于 sum 又大于 sum。题目的本质是将学生成两组（被选择的和未被选择的），选择的标准是根据所选人数动态变化的，水平相同的学生要么都选，要么都不选，要一碗水端平，这就是题目名想要表达的处世哲学吧。

当 cnt[0] == 0 时，说明所有元素都大于0，因此可以一个都不选。
当 cnt[i] != 0 时，如果我们想要选择这些元素值为i的学生，需要满足选择后的学生总数 sum 大于 i，并且 cnt[i+1] ~ cnt[sum] 应该都为0，否则就存在小于 sum 但是未被选的学生了。

官网题解使用的是排序，满足 sorted[i - 1] < i && i < sorted[i] 时累加计数。不过排序的复杂度是O(nlogn)，其实我们的计数数组也是有序的，算是计数排序吧，时间复杂度为O(n)。

代码


/**
 * @date 2024-09-04 10:29
 */
public class CountWays2860 {
    public int countWays(List<Integer> nums) {
        int n = nums.size();
        int[] cnt = new int[n];
        for (Integer num : nums) {
            cnt[num]++;
        }
        int[] prefix = new int[n];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + cnt[i];
        }
        int res = cnt[0] > 0 ? 0 : 1;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += cnt[i];
            if (sum > i && cnt[i] != 0 && prefix[Math.min(n - 1, sum)] == prefix[i]) {
                res++;
            }
        }
        return res;
    }
}

性能

目标

给你一个下标从 0 开始的整数数组 nums ，它表示一个班级中所有学生在一次考试中的成绩。老师想选出一部分同学组成一个非空小组，且这个小组的实力值最大，如果这个小组里的学生下标为 i0, i1, i2, ... , ik ，那么这个小组的实力值定义为 nums[i0] * nums[i1] * nums[i2] * ... * nums[ik] 。

请你返回老师创建的小组能得到的最大实力值为多少。

示例 1：

输入：nums = [3,-1,-5,2,5,-9]
输出：1350
解释：一种构成最大实力值小组的方案是选择下标为 [0,2,3,4,5] 的学生。实力值为 3 * (-5) * 2 * 5 * (-9) = 1350 ，这是可以得到的最大实力值。

示例 2：

输入：nums = [-4,-5,-4]
输出：20
解释：选择下标为 [0, 1] 的学生。得到的实力值为 20 。我们没法得到更大的实力值。

说明：

1 <= nums.length <= 13
-9 <= nums[i] <= 9

思路

有一个存在负数的数组，求它的非空子序列使得子序列的乘积最大。

首先，要选择所有正数，不能选零（除非全是零），负数必须成对的选（可以使用栈来保存）。可以将数组从小到大排序，从后向前取所有大于零的值，然后再从前向后取，判断栈是否为空，为空入栈，非空出栈，直到零。特别需要注意的是初值的设置需要分情况讨论，如果全是零或者至多一个负数，直接返回零。如果至少有一个正数，则初值设为1。如果全是负数，初值设为第一个元素，之所以不设为1是因为如果只有一个负数，那么就应该取这个值，如果设为1后面再配对的话就不对了，所以需要特殊处理成对匹配的情况。

代码


/**
 * @date 2024-09-03 8:57
 */
public class MaxStrength2708 {

    public long maxStrength(int[] nums) {
        long res = 1L;
        Arrays.sort(nums);
        int n = nums.length;
        int i = n - 1;
        for (; i >= 0; i--) {
            if (nums[i] > 0) {
                res *= nums[i];
            } else if (nums[i] < 0) {
                // 跳过0，使i指向最后一个负数
                break;
            }
        }
        int j = 0;
        boolean flag = true;
        // 至多一个负数，其余全是0，返回0。
        if (i <= 0 && nums[n - 1] == 0) {
            return 0L;
        } else if (i == n - 1) {
            // 如果全是负数
            res = nums[0];
            flag = false;
            j = 1;
        }
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for (; j <= i; j++) {
            if (nums[j] < 0) {
                if (stack.isEmpty() && flag) {
                    stack.push(nums[j]);
                } else {
                    if (!flag) {
                        res *= nums[j];
                    } else {
                        res *= stack.pop() * nums[j];
                    }
                    flag = true;
                }
            }
        }
        return res;
    }

}

性能

2024.考试的最大困扰度

目标

一位老师正在出一场由 n 道判断题构成的考试，每道题的答案为 true （用 'T' 表示）或者 false （用 'F' 表示）。老师想增加学生对自己做出答案的不确定性，方法是最大化有连续相同结果的题数。（也就是连续出现 true 或者连续出现 false）。

给你一个字符串 answerKey ，其中 answerKey[i] 是第 i 个问题的正确结果。除此以外，还给你一个整数 k ，表示你能进行以下操作的最多次数：

每次操作中，将问题的正确答案改为 'T' 或者 'F' （也就是将 answerKey[i] 改为 'T' 或者 'F' ）。

请你返回在不超过 k 次操作的情况下，最大连续 'T' 或者 'F' 的数目。

示例 1：

输入：answerKey = "TTFF", k = 2
输出：4
解释：我们可以将两个 'F' 都变为 'T' ，得到 answerKey = "TTTT" 。
总共有四个连续的 'T' 。

示例 2：

输入：answerKey = "TFFT", k = 1
输出：3
解释：我们可以将最前面的 'T' 换成 'F' ，得到 answerKey = "FFFT" 。
或者，我们可以将第二个 'T' 换成 'F' ，得到 answerKey = "TFFF" 。
两种情况下，都有三个连续的 'F' 。

示例 3：

输入：answerKey = "TTFTTFTT", k = 1
输出：5
解释：我们可以将第一个 'F' 换成 'T' ，得到 answerKey = "TTTTTFTT" 。
或者我们可以将第二个 'F' 换成 'T' ，得到 answerKey = "TTFTTTTT" 。
两种情况下，都有五个连续的 'T' 。

说明：

n == answerKey.length
1 <= n <= 5 * 10^4
answerKey[i] 要么是 'T' ，要么是 'F'
1 <= k <= n

思路

有一个字符串 answerKey 由 T 或 F 组成, 允许我们执行 k 次操作，每次操作可以将字符串中的 T 改为 F 或者 F 改为 T。问 T 或 F 可能的最大连续个数。

这道题没有做出来，想着使用动态规划去做，但是没有找到合适的状态定义。比如 dp[i][j][k] 表示 [0,i] 以 T 或 F 结尾剩余操作次数 k 时的最大连续个数。2 x 10^8 的存储空间肯定不行。

题解说是滑动窗口、或者前缀和 + 二分查找，也有使用动态规划的。

这道题的难点在于想明白这 k 次操作必须统一，要么全部从 T 改为 F，要么全部从 F 改为 T，才能使连续个数最大。因为如果 T 的连续个数最多，并且存在将 T 改为 F 的操作，那么我们总可以撤回该操作，并将一个 F 改为 T（如果存在的话，如果不存在说明全是T，撤销操作也会加一）使得连续个数至少加一。

网友题解中的动态规划是这样定义的 dp[i] 表示 [0,i] 中以 answerKey[i] 结尾的连续后缀个数。这里的前提就是遇到不连续的统一从 T 改为 F 或者从 F 改为 T 使之连续，如果超过了可操作的次数，需要撤回最早的操作，使得当前后缀连续。后缀连续个数可以用当前下标减去最早进行操作的下标计算得到（使用链表保存操作的下标，获取链表head记录的下标后将其删，再将当前下标加入链表末尾）。在计算dp过程中记录其最大值即为最大连续个数。如果对这个动态规划进行存储优化，那就是滑动窗口。

寻找一个窗口，使得窗口内的 T 或者 F 个数小于等于 k，并且使 F 或者 T 的个数最大。滑动窗口的套路一般是枚举右边界，如果条件不满足，更新左边界直到条件满足。

二分的做法本质也是滑动窗口，枚举左边界，二分查找能够到达的最远右边界。

代码


/**
 * @date 2024-09-02 16:55
 */
public class MaxConsecutiveAnswers2024 {

    /**
     * 前缀和 + 二分查找
     * 其实本质也是滑动窗口，枚举左边界，二分查找最远的右边界
     * O(nlogn) 62ms
     */
    public int maxConsecutiveAnswers_v1(String answerKey, int k) {
        int n = answerKey.length();
        int[] prefix = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            if (answerKey.charAt(i - 1) == 'T') {
                prefix[i] = prefix[i - 1] + 1;
            } else {
                prefix[i] = prefix[i - 1];
            }
        }
        int res = 0;
        for (int i = 1; i <= n; i++) {
            int l = i, r = n;
            int mid = l + (r - l) / 2;
            while (l <= r) {
                int num = mid - i + 1;
                int cnt = prefix[mid] - prefix[i - 1];
                if (num - cnt <= k || cnt <= k) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
                mid = l + (r - l) / 2;
            }
            res = Math.max(res, r - i + 1);
        }
        return res;
    }

    /**
     * 滑动窗口 O(n)
     * 21ms
     */
    public int maxConsecutiveAnswers(String answerKey, int k) {
        return Math.max(process(answerKey, k, 'T'), process(answerKey, k, 'F'));
    }

    public int process(String answerKey, int k, char turnTo) {
        int n = answerKey.length();
        int res = 0;
        List<Integer> optsIndex = new LinkedList<>();
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (answerKey.charAt(i) != turnTo) {
                if (k > 0) {
                    k--;
                    optsIndex.add(i);
                    cnt++;
                } else {
                    cnt = i - optsIndex.remove(0);
                    optsIndex.add(i);
                }
            } else {
                cnt++;
            }
            res = Math.max(res, cnt);
        }
        return res;
    }

}

性能

1450.在既定时间做作业的学生人数

目标

给你两个整数数组 startTime（开始时间）和 endTime（结束时间），并指定一个整数 queryTime 作为查询时间。

已知，第 i 名学生在 startTime[i] 时开始写作业并于 endTime[i] 时完成作业。

请返回在查询时间 queryTime 时正在做作业的学生人数。形式上，返回能够使 queryTime 处于区间 [startTime[i], endTime[i]]（含）的学生人数。

示例 1：

输入：startTime = [1,2,3], endTime = [3,2,7], queryTime = 4
输出：1
解释：一共有 3 名学生。
第一名学生在时间 1 开始写作业，并于时间 3 完成作业，在时间 4 没有处于做作业的状态。
第二名学生在时间 2 开始写作业，并于时间 2 完成作业，在时间 4 没有处于做作业的状态。
第三名学生在时间 3 开始写作业，预计于时间 7 完成作业，这是是唯一一名在时间 4 时正在做作业的学生。

示例 2：

输入：startTime = [4], endTime = [4], queryTime = 4
输出：1
解释：在查询时间只有一名学生在做作业。

示例 3：

输入：startTime = [4], endTime = [4], queryTime = 5
输出：0

示例 4：

输入：startTime = [1,1,1,1], endTime = [1,3,2,4], queryTime = 7
输出：0

示例 5：

输入：startTime = [9,8,7,6,5,4,3,2,1], endTime = [10,10,10,10,10,10,10,10,10], queryTime = 5
输出：5

说明：

startTime.length == endTime.length
1 <= startTime.length <= 100
1 <= startTime[i] <= endTime[i] <= 1000
1 <= queryTime <= 1000

思路

当满足 startTime[i] <= queryTime && endTime[i] >= queryTime 时计数即可。

当 queryTime 是一个数组时，可以使用差分数组或者二分查找来解，具体参考官网题解。

代码


/**
 * @date 2024-09-01 14:35
 */
public class BusyStudent1450 {

    public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
        int n = startTime.length;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (startTime[i] <= queryTime && endTime[i] >= queryTime) {
                res++;
            }
        }
        return res;
    }
}

性能

3127.构造相同颜色的正方形

目标

给你一个二维 3 x 3 的矩阵 grid ，每个格子都是一个字符，要么是 'B' ，要么是 'W' 。字符 'W' 表示白色，字符 'B' 表示黑色。

你的任务是改变至多一个格子的颜色，使得矩阵中存在一个 2 x 2 颜色完全相同的正方形。

如果可以得到一个相同颜色的 2 x 2 正方形，那么返回 true ，否则返回 false 。

示例 1：

输入：grid = [["B","W","B"],["B","W","W"],["B","W","B"]]
输出：true
解释：
修改 grid[0][2] 的颜色，可以满足要求。

示例 2：

输入：grid = [["B","W","B"],["W","B","W"],["B","W","B"]]
输出：false
解释：
只改变一个格子颜色无法满足要求。

示例 3：

输入：grid = [["B","W","B"],["B","W","W"],["B","W","W"]]
输出：true
解释：
grid 已经包含一个 2 x 2 颜色相同的正方形了。

说明：

grid.length == 3
grid[i].length == 3
grid[i][j] 要么是 'W' ，要么是 'B' 。

思路

有一个 3 x 3 矩阵，每一个格子有黑白两色，分别用 B W 表示。问能否修改至多一个格子的颜色使矩阵中存在一个 2 x 2 的纯色（颜色相同）矩阵。

可能的 2 x 2 矩阵只有4个，它们有一个公共格子，以它为中心向左上、右上、左下、右下方向判断即可。可以分情况讨论，修改颜色的格子是中间的格子，那么要求其余的三个格子颜色相同。否则，其余格子与中间格子颜色不同的个数最多只能有一个。综上，与中心格子不同的颜色数只能为0、1、3，只需判断不等于2即可。

代码

/**
 * @date 2024-08-31 21:28
 */
public class CanMakeSquare3127 {
    static private final int[][][] directions = new int[][][]
    {
            {{-1, 0}, {-1, -1}, {0, -1}},
            {{1, 0}, {1, -1}, {0, -1}},
            {{-1, 0}, {-1, 1}, {0, 1}},
            {{1, 0}, {1, 1}, {0, 1}}
    };

    public boolean canMakeSquare(char[][] grid) {
        char mid = grid[1][1];
        for (int[][] direction : directions) {
            int cnt = 0;
            for (int[] cor : direction) {
                if (mid != grid[1 + cor[0]][1 + cor[1]]) {
                    cnt++;
                }
            }
            if (cnt != 2) {
                return true;
            }
        }
        return false;
    }

}

性能

3153.所有数对中数位不同之和

目标

你有一个数组 nums ，它只包含正整数，所有正整数的数位长度都相同。

两个整数的数位不同指的是两个整数相同位置上不同数字的数目。

请你返回 nums 中所有整数对里，数位不同之和。

示例 1：

输入：nums = [13,23,12]
输出：4
解释：
计算过程如下：
- 13 和 23 的数位不同为 1 。
- 13 和 12 的数位不同为 1 。
- 23 和 12 的数位不同为 2 。
所以所有整数数对的数位不同之和为 1 + 1 + 2 = 4 。

示例 2：

输入：nums = [10,10,10,10]
输出：0
解释：
数组中所有整数都相同，所以所有整数数对的数位不同之和为 0 。

说明：

2 <= nums.length <= 10^5
1 <= nums[i] < 10^9
nums 中的整数都有相同的数位长度。

思路

有一个数组其元素的数位长度相同，针对数组中所有可能的数对组合（即任选两个元素），比较其数位不同的个数并累加求和。

C(n,2) = n(n-1)/2 时间复杂度为 O(n^2)，再加上数位比较，暴力枚举会超时。

考虑到所有元素的数位 digitLength 相同，那么可以统计所有元素该位上数字出现次数，时间复杂度为 O(digitLength*n)。然后逐数位比较，即在 0~9 之间组合，组合数等于对应数位数字出现次数的乘积。外层数位循环最大为10（可以忽略掉出现次数为0的），内层 0~9 组合数最多(10*9/2)，总循环次数最大450，没有增大数据规模。

代码


/**
 * @date 2024-08-30 9:33
 */
public class SumDigitDifferences3153 {

    public long sumDigitDifferences(int[] nums) {
        int n = nums.length;
        int first = nums[0];
        int digitsLength = 0;
        while (first > 0) {
            digitsLength++;
            first /= 10;
        }
        int[][] cnt = new int[digitsLength][10];
        for (int i = 0; i < n; i++) {
            int d = 0;
            int num = nums[i];
            while (num > 0) {
                cnt[d++][num % 10]++;
                num /= 10;
            }
        }
        long res = 0L;
        for (int[] digit : cnt) {
            for (int i = 0; i < 10; i++) {
                if (digit[i] == 0) {
                    continue;
                }
                for (int j = i + 1; j < 10; j++) {
                    res += (long) digit[i] * digit[j];
                }
            }
        }
        return res;
    }

}

2025 年 5 月
一	二	三	四	五	六	日
			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