🌟欢迎来到 我的博客 —— 探索技术的无限可能！
29.棒球比赛
题目链接：682. 棒球比赛
你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。
比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：
整数 x - 表示本回合新获得分数 x
“+” - 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。
“D” - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。
“C” - 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。
请你返回记录中所有得分的总和。
示例 1：
输入：ops = [“5”,“2”,“C”,“D”,“+”]
输出：30
解释：
“5” - 记录加 5 ，记录现在是 [5]
“2” - 记录加 2 ，记录现在是 [5, 2]
“C” - 使前一次得分的记录无效并将其移除，记录现在是 [5].
“D” - 记录加 2 * 5 = 10 ，记录现在是 [5, 10].
“+” - 记录加 5 + 10 = 15 ，记录现在是 [5, 10, 15].
所有得分的总和 5 + 10 + 15 = 30
示例 2：
输入：ops = [“5”,“-2”,“4”,“C”,“D”,“9”,“+”,“+”]
输出：27
解释：
“5” - 记录加 5 ，记录现在是 [5]
“-2” - 记录加 -2 ，记录现在是 [5, -2]
“4” - 记录加 4 ，记录现在是 [5, -2, 4]
“C” - 使前一次得分的记录无效并将其移除，记录现在是 [5, -2]
“D” - 记录加 2 * -2 = -4 ，记录现在是 [5, -2, -4]
“9” - 记录加 9 ，记录现在是 [5, -2, -4, 9]
“+” - 记录加 -4 + 9 = 5 ，记录现在是 [5, -2, -4, 9, 5]
“+” - 记录加 9 + 5 = 14 ，记录现在是 [5, -2, -4, 9, 5, 14]
所有得分的总和 5 + -2 + -4 + 9 + 5 + 14 = 27
示例 3：
输入：ops = [“1”]
输出：1
提示：
1 <= ops.length <= 1000
ops[i] 为 “C”、“D”、“+”，或者一个表示整数的字符串。整数范围是 [-3 * 104, 3 * 104]
对于 “+” 操作，题目数据保证记录此操作时前面总是存在两个有效的分数
对于 “C” 和 “D” 操作，题目数据保证记录此操作时前面总是存在一个有效的分数
题解：
方法：模拟
class Solution { public int calPoints(String[] operations) { List<Integer> st = new ArrayList<>(); for (String op : operations) { switch (op.charAt(0)) { case '+': st.add(st.get(st.size() - 2) + st.get(st.size() - 1)); break; case 'D': st.add(st.get(st.size() - 1) * 2); break; case 'C': st.remove(st.size() - 1); break; default: st.add(Integer.parseInt(op)); } } int sum = 0; for (int x : st) { sum += x; } return sum; } }
30.双模幂运算
题目链接：2961. 双模幂运算
给你一个下标从 0 开始的二维数组 variables ，其中 variables[i] = [ai, bi, ci, mi]，以及一个整数 target 。
如果满足以下公式，则下标 i 是 好下标：
0 <= i < variables.length
((aibi % 10)ci) % mi == target
返回一个由 好下标 组成的数组，顺序不限 。
示例 1：
输入：variables = [[2,3,3,10],[3,3,3,1],[6,1,1,4]], target = 2
输出：[0,2]
解释：对于 variables 数组中的每个下标 i ：
- 对于下标 0 ，variables[0] = [2,3,3,10] ，(23 % 10)3 % 10 = 2 。
- 对于下标 1 ，variables[1] = [3,3,3,1] ，(33 % 10)3 % 1 = 0 。
- 对于下标 2 ，variables[2] = [6,1,1,4] ，(61 % 10)1 % 4 = 2 。
因此，返回 [0,2] 作为答案。
示例 2：
输入：variables = [[39,3,1000,1000]], target = 17
输出：[]
解释：对于 variables 数组中的每个下标 i ：
- 对于下标 0 ，variables[0] = [39,3,1000,1000] ，(393 % 10)1000 % 1000 = 1
。因此，返回 [] 作为答案。
提示：
1 <= variables.length <= 100
variables[i] == [ai, bi, ci, mi]
1 <= ai, bi, ci, mi <= 103
0 <= target <= 103
题解：
方法：快速幂取模
class Solution { public List<Integer> getGoodIndices(int[][] variables, int target) { List<Integer> ans = new ArrayList<>(); for (int i = 0; i < variables.length; i++) { int[] v = variables[i]; if (pow(pow(v[0], v[1], 10), v[2], v[3]) == target) { ans.add(i); } } return ans; } // 本题 mod 很小，即使平方也不会超过 int 范围，所以不需要用 long private int pow(int x, int n, int mod) { int res = 1; while (n > 0) { if (n % 2 > 0) { res = res * x % mod; } x = x * x % mod; n /= 2; } return res; } }
31.覆盖所有点的最少矩形数目
题目链接：3111. 覆盖所有点的最少矩形数目
给你一个二维整数数组 point ，其中 points[i] = [xi, yi] 表示二维平面内的一个点。同时给你一个整数 w 。你需要用矩形 覆盖所有 点。
每个矩形的左下角在某个点 (x1, 0) 处，且右上角在某个点 (x2, y2) 处，其中 x1 <= x2 且 y2 >= 0 ，同时对于每个矩形都 必须 满足 x2 - x1 <= w 。
如果一个点在矩形内或者在边上，我们说这个点被矩形覆盖了。
请你在确保每个点都 至少 被一个矩形覆盖的前提下，最少 需要多少个矩形。
注意：一个点可以被多个矩形覆盖。
示例 1：
输入：points = [[2,1],[1,0],[1,4],[1,8],[3,5],[4,6]], w = 1
输出：2
解释：
上图展示了一种可行的矩形放置方案：
一个矩形的左下角在 (1, 0) ，右上角在 (2, 8) 。
一个矩形的左下角在 (3, 0) ，右上角在 (4, 8) 。
示例 2：
输入：points = [[0,0],[1,1],[2,2],[3,3],[4,4],[5,5],[6,6]], w = 2
输出：3
解释：
上图展示了一种可行的矩形放置方案：
一个矩形的左下角在 (0, 0) ，右上角在 (2, 2) 。
一个矩形的左下角在 (3, 0) ，右上角在 (5, 5) 。
一个矩形的左下角在 (6, 0) ，右上角在 (6, 6) 。
示例 3：
输入：points = [[2,3],[1,2]], w = 0
输出：2
解释：
上图展示了一种可行的矩形放置方案：
一个矩形的左下角在 (1, 0) ，右上角在 (1, 2) 。
一个矩形的左下角在 (2, 0) ，右上角在 (2, 3) 。
提示：
1 <= points.length <= 105
points[i].length == 2
0 <= xi == points[i][0] <= 109
0 <= yi == points[i][1] <= 109
0 <= w <= 109
所有点坐标 (xi, yi) 互不相同。
题解：
方法：贪心 + 排序
class Solution { public int minRectanglesToCoverPoints(int[][] points, int w) { Arrays.sort(points, (a, b) -> a[0] - b[0]); int ans = 0, x1 = -1; for (int[] p : points) { int x = p[0]; if (x > x1) { ++ans; x1 = x + w; } } return ans; } }
2024.8
1.心算挑战
题目链接：LCP 40. 心算挑战
「力扣挑战赛」心算项目的挑战比赛中，要求选手从 N 张卡牌中选出 cnt 张卡牌，若这 cnt 张卡牌数字总和为偶数，则选手成绩「有效」且得分为 cnt 张卡牌数字总和。 给定数组 cards 和 cnt，其中 cards[i] 表示第 i 张卡牌上的数字。 请帮参赛选手计算最大的有效得分。若不存在获取有效得分的卡牌方案，则返回 0。
示例 1：
输入：cards = [1,2,8,9], cnt = 3
输出：18
解释：选择数字为 1、8、9 的这三张卡牌，此时可获得最大的有效得分 1+8+9=18。
示例 2：
输入：cards = [3,3,1], cnt = 1
输出：0
解释：不存在获取有效得分的卡牌方案。
提示：
1 <= cnt <= cards.length <= 10^5
1 <= cards[i] <= 1000
题解：
方法：排序+贪心
class Solution { public int maxmiumScore(int[] cards, int cnt) { Arrays.sort(cards); int n = cards.length; int s = 0; for (int i = n - cnt; i < n; i++) { s += cards[i]; // 最大的 cnt 个数之和 } if (s % 2 == 0) { // s 是偶数 return s; } int x = cards[n - cnt]; int ans = replacedSum(cards, cnt, s, x); // 替换 x for (int i = n - cnt + 1; i < n; i++) { if (cards[i] % 2 != x % 2) { // 找到一个最小的奇偶性和 x 不同的数 ans = Math.max(ans, replacedSum(cards, cnt, s, cards[i])); // 替换 break; } } return ans; } private int replacedSum(int[] cards, int cnt, int s, int x) { for (int i = cards.length - cnt - 1; i >= 0; i--) { if (cards[i] % 2 != x % 2) { // 找到一个最大的奇偶性和 x 不同的数 return s - x + cards[i]; // 用 cards[i] 替换 s } } return 0; } }
2.直角三角形
题目链接：3128. 直角三角形
给你一个二维 boolean 矩阵 grid 。
请你返回使用 grid 中的 3 个元素可以构建的 直角三角形 数目，且满足 3 个元素值 都 为 1 。
注意：
如果 grid 中 3 个元素满足：一个元素与另一个元素在 同一行，同时与第三个元素在 同一列 ，那么这 3 个元素称为一个 直角三角形 。这 3 个元素互相之间不需要相邻。
示例 1：
输入：grid = [[0,1,0],[0,1,1],[0,1,0]]
输出：2
解释：
有 2 个直角三角形。
示例 2：
输入：grid = [[1,0,0,0],[0,1,0,1],[1,0,0,0]]
输出：0
解释：
没有直角三角形。
示例 3：
输入：grid = [[1,0,1],[1,0,0],[1,0,0]]
输出：2
解释：
有两个直角三角形。
提示：
1 <= grid.length <= 1000
1 <= grid[i].length <= 1000
0 <= grid[i][j] <= 1
题解：
方法：枚举
class Solution { public long numberOfRightTriangles(int[][] grid) { int m = grid.length, n = grid[0].length; int[] rows = new int[m]; int[] cols = new int[n]; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { rows[i] += grid[i][j]; cols[j] += grid[i][j]; } } long ans = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == 1) { ans += (rows[i] - 1) * (cols[j] - 1); } } } return ans; } }
3.正方形中的最多点数
题目链接：3143. 正方形中的最多点数
给你一个二维数组 points 和一个字符串 s ，其中 points[i] 表示第 i 个点的坐标，s[i] 表示第 i 个点的 标签 。
如果一个正方形的中心在 (0, 0) ，所有边都平行于坐标轴，且正方形内 不 存在标签相同的两个点，那么我们称这个正方形是 合法 的。
请你返回 合法 正方形中可以包含的 最多 点数。
注意：
如果一个点位于正方形的边上或者在边以内，则认为该点位于正方形内。
正方形的边长可以为零。
示例 1：
输入：points = [[2,2],[-1,-2],[-4,4],[-3,1],[3,-3]], s = “abdca”
输出：2
解释：
边长为 4 的正方形包含两个点 points[0] 和 points[1] 。
示例 2：
输入：points = [[1,1],[-2,-2],[-2,2]], s = “abb”
输出：1
解释：
边长为 2 的正方形包含 1 个点 points[0] 。
示例 3：
输入：points = [[1,1],[-1,-1],[2,-2]], s = “ccd”
输出：0
解释：
任何正方形都无法只包含 points[0] 和 points[1] 中的一个点，所以合法正方形中都不包含任何点。
提示：
1 <= s.length, points.length <= 105
points[i].length == 2
-109 <= points[i][0], points[i][1] <= 109
s.length == points.length
points 中的点坐标互不相同。
s 只包含小写英文字母。
题解：
方法：哈希表 + 排序
class Solution { public int maxPointsInsideSquare(int[][] points, String s) { TreeMap<Integer, List<Integer>> g = new TreeMap<>(); for (int i = 0; i < points.length; ++i) { int x = points[i][0], y = points[i][1]; int key = Math.max(Math.abs(x), Math.abs(y)); g.computeIfAbsent(key, k -> new ArrayList<>()).add(i); } boolean[] vis = new boolean[26]; int ans = 0; for (var idx : g.values()) { for (int i : idx) { int j = s.charAt(i) - 'a'; if (vis[j]) { return ans; } vis[j] = true; } ans += idx.size(); } return ans; } }
4.另一棵树的子树
题目链接：572. 另一棵树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例 1：
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true
示例 2：
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false
提示：
root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-104 <= root.val <= 104
-104 <= subRoot.val <= 104
题解：
方法：暴力
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isSubtree(TreeNode root, TreeNode subRoot) { if (root == null) { return false; } return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot); } // 100. 相同的树 private boolean isSameTree(TreeNode p, TreeNode q) { if (p == null || q == null) { return p == q; // 必须都是 null } return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } }
