【题解】—— LeetCode一周小结36

简介: LeetCode每日一道一周小结36

🌟欢迎来到 我的博客 —— 探索技术的无限可能!

🌟博客的简介(文章目录)


【题解】—— 每日一道题目栏


上接:【题解】—— LeetCode一周小结35

2.考试的最大困扰度

题目链接: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 * 104

answerKey[i] 要么是 ‘T’ ,要么是 ‘F’

1 <= k <= n

题解:

方法:滑动窗口

       

class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        char[] s = answerKey.toCharArray();
        int ans = 0;
        int left = 0;
        int[] cnt = new int[2];
        for (int right = 0; right < s.length; right++) {
            cnt[s[right] >> 1 & 1]++;
            while (cnt[0] > k && cnt[1] > k) {
                cnt[s[left++] >> 1 & 1]--;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

3.一个小组的最大实力值

题目链接:2708. 一个小组的最大实力值

给你一个下标从 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

题解:

方法:动态规划

       

class Solution {
    public long maxStrength(int[] nums) {
        long mn = nums[0];
        long mx = mn;
        for (int i = 1; i < nums.length; i++) {
            long x = nums[i];
            long tmp = mn;
            mn = Math.min(Math.min(mn, x), Math.min(mn * x, mx * x));
            mx = Math.max(Math.max(mx, x), Math.max(tmp * x, mx * x));
        }
        return mx;
    }
}

4.让所有学生保持开心的分组方法数

题目链接:2860. 让所有学生保持开心的分组方法数

给你一个下标从 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 <= 105

0 <= nums[i] < nums.length

题解:

方法:排序

       

class Solution {
    public int countWays(List<Integer> nums) {
        int[] a = nums.stream().mapToInt(i -> i).toArray();
        Arrays.sort(a);
        int ans = a[0] > 0 ? 1 : 0; // 一个学生都不选
        for (int i = 1; i < a.length; i++) {
            if (a[i - 1] < i && i < a[i]) {
                ans++;
            }
        }
        return ans + 1; // 一定可以都选
    }
}

5.清除数字

题目链接:3174. 清除数字

给你一个字符串 s 。

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

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

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

示例 1:

输入:s = “abc”

输出:“abc”

解释:

字符串中没有数字。

示例 2:

输入:s = “cb34”

输出:“”

解释:

一开始,我们对 s[2] 执行操作,s 变为 “c4” 。

然后对 s[1] 执行操作,s 变为 “” 。

提示:

1 <= s.length <= 100

s 只包含小写英文字母和数字字符。

输入保证所有数字都可以按以上操作被删除。

题解:

方法:

       

class Solution {
    public String clearDigits(String s) {
        StringBuilder st = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                st.deleteCharAt(st.length() - 1);
            } else {
                st.append(c);
            }
        }
        return st.toString();
    }
}

6.求出最长好子序列 I

题目链接:3176. 求出最长好子序列 I

给你一个整数数组 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 <= 500

1 <= nums[i] <= 109

0 <= k <= min(nums.length, 25)

题解:

方法:动态规划

       

class Solution {
    public int maximumLength(int[] nums, int k) {
        int n = nums.length;
        int[][] f = new int[n][k + 1];
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int h = 0; h <= k; ++h) {
                for (int j = 0; j < i; ++j) {
                    if (nums[i] == nums[j]) {
                        f[i][h] = Math.max(f[i][h], f[j][h]);
                    } else if (h > 0) {
                        f[i][h] = Math.max(f[i][h], f[j][h - 1]);
                    }
                }
                ++f[i][h];
            }
            ans = Math.max(ans, f[i][k]);
        }
        return ans;
    }
}

7.求出最长好子序列 II

题目链接:3177. 求出最长好子序列 II

给你一个整数数组 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 * 103

1 <= nums[i] <= 109

0 <= k <= min(50, nums.length)

题解:

方法:哈希表 动态规划

       

class Solution {
    public int maximumLength(int[] nums, int k) {
        Map<Integer, int[]> fs = new HashMap<>();
        int[][] records = new int[k + 1][3];
        for (int x : nums) {
            int[] f = fs.computeIfAbsent(x, i -> new int[k + 1]);
            for (int j = k; j >= 0; j--) {
                f[j]++;
                if (j > 0) {
                    int mx = records[j - 1][0], mx2 = records[j - 1][1], num = records[j - 1][2];
                    f[j] = Math.max(f[j], (x != num ? mx : mx2) + 1);
                }
                // records[j] 维护 fs[.][j] 的 mx, mx2, num
                int v = f[j];
                int[] p = records[j];
                if (v > p[0]) {
                    if (x != p[2]) {
                        p[2] = x;
                        p[1] = p[0];
                    }
                    p[0] = v;
                } else if (x != p[2] && v > p[1]) {
                    p[1] = v;
                }
            }
        }
        return records[k][0];
    }
}

8.有序数组的平方

题目链接:977. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 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 <= 104

-104 <= nums[i] <= 104

nums 已按 非递减顺序 排序

进阶:

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

题解:

方法:双指针

       

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        int i = 0;
        int j = n - 1;
        for (int p = n - 1; p >= 0; p--) {
            int x = nums[i] * nums[i];
            int y = nums[j] * nums[j];
            if (x > y) {
                ans[p] = x;
                i++;
            } else {
                ans[p] = y;
                j--;
            }
        }
        return ans;
    }
}

下接:【题解】—— LeetCode一周小结37


相关文章
|
19天前
|
人工智能 BI
|
2月前
|
Perl
|
3月前
|
测试技术 索引
|
5月前
|
存储 测试技术 索引
|
5月前
|
机器学习/深度学习 测试技术 C++
【题解】—— LeetCode一周小结14
【题解】—— LeetCode一周小结14
|
5月前
|
存储 人工智能 算法
【题解】—— LeetCode一周小结11
【题解】—— LeetCode一周小结11