🌟欢迎来到 我的博客 —— 探索技术的无限可能！
26.员工的重要性
题目链接：690. 员工的重要性
你有一个保存员工信息的数据结构，它包含了员工唯一的 id ，重要度和直系下属的 id 。
给定一个员工数组 employees，其中：
employees[i].id 是第 i 个员工的 ID。
employees[i].importance 是第 i 个员工的重要度。
employees[i].subordinates 是第 i 名员工的直接下属的 ID 列表。
给定一个整数 id 表示一个员工的 ID，返回这个员工和他所有下属的重要度的 总和。
示例 1：
输入：employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1
输出：11
解释： 员工 1 自身的重要度是 5 ，他有两个直系下属 2 和 3 ，而且 2 和 3 的重要度均为 3 。因此员工 1 的总重要度是 5
- 3 + 3 = 11 。
示例 2：
输入：employees = [[1,2,[5]],[5,-3,[]]], id = 5
输出：-3
解释：员工 5 的重要度为 -3 并且没有直接下属。 因此，员工 5 的总重要度为 -3。
提示：
1 <= employees.length <= 2000
1 <= employees[i].id <= 2000
所有的 employees[i].id 互不相同。
-100 <= employees[i].importance <= 100
一名员工最多有一名直接领导，并可能有多名下属。
employees[i].subordinates 中的 ID 都有效。
题解：
方法：哈希表
/* // Definition for Employee. class Employee { public int id; public int importance; public List<Integer> subordinates; }; */ class Solution { public int getImportance(List<Employee> employees, int id) { Map<Integer, Employee> employeeMap = new HashMap<>(employees.size()); for (Employee e : employees) { employeeMap.put(e.id, e); } return dfs(employeeMap, id); } private int dfs(Map<Integer, Employee> employeeMap, int id) { Employee e = employeeMap.get(id); int res = e.importance; for (int subId : e.subordinates) { res += dfs(employeeMap, subId); } return res; } }
27.找出唯一性数组的中位数
题目链接：3134. 找出唯一性数组的中位数
给你一个整数数组 nums 。数组 nums 的 唯一性数组 是一个按元素从小到大排序的数组，包含了 nums 的所有非空
子数组
中不同元素的个数。
换句话说，这是由所有 0 <= i <= j < nums.length 的 distinct(nums[i…j]) 组成的递增数组。
其中，distinct(nums[i…j]) 表示从下标 i 到下标 j 的子数组中不同元素的数量。
返回 nums 唯一性数组 的 中位数 。
注意，数组的 中位数 定义为有序数组的中间元素。如果有两个中间元素，则取值较小的那个。
示例 1：
输入：nums = [1,2,3]
输出：1
解释：
nums 的唯一性数组为 [distinct(nums[0…0]), distinct(nums[1…1]),
distinct(nums[2…2]), distinct(nums[0…1]), distinct(nums[1…2]),
distinct(nums[0…2])]，即 [1, 1, 1, 2, 2, 3] 。唯一性数组的中位数为 1 ，因此答案是 1 。
示例 2：
输入：nums = [3,4,3,4,5]
输出：2
解释：
nums 的唯一性数组为 [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3] 。唯一性数组的中位数为
2 ，因此答案是 2 。
示例 3：
输入：nums = [4,3,5,4]
输出：2
解释：
nums 的唯一性数组为 [1, 1, 1, 1, 2, 2, 2, 3, 3, 3] 。唯一性数组的中位数为 2 ，因此答案是 2 。
提示：
1 <= nums.length <= 105
1 <= nums[i] <= 105
题解：
方法：二分
class Solution { public int medianOfUniquenessArray(int[] nums) { int n = nums.length; long k = ((long) n * (n + 1) / 2 + 1) / 2; int left = 0; int right = n; while (left + 1 < right) { int mid = (left + right) / 2; if (check(nums, mid, k)) { right = mid; } else { left = mid; } } return right; } private boolean check(int[] nums, int upper, long k) { long cnt = 0; int l = 0; HashMap<Integer, Integer> freq = new HashMap<>(); for (int r = 0; r < nums.length; r++) { freq.merge(nums[r], 1, Integer::sum); // 移入右端点 while (freq.size() > upper) { // 窗口内元素过多 int out = nums[l++]; if (freq.merge(out, -1, Integer::sum) == 0) { // 移出左端点 freq.remove(out); } } cnt += r - l + 1; // 右端点固定为 r 时，有 r-l+1 个合法左端点 if (cnt >= k) { return true; } } return false; } }
28.分割字符频率相等的最少子字符串
给你一个字符串 s ，你需要将它分割成一个或者更多的 平衡 子字符串。比方说，s == “ababcc” 那么 (“abab”, “c”, “c”) ，(“ab”, “abc”, “c”) 和 (“ababcc”) 都是合法分割，但是 (“a”, “bab”, “cc”) ，(“aba”, “bc”, “c”) 和 (“ab”, “abcc”) 不是，不平衡的子字符串用粗体表示。
请你返回 s 最少 能分割成多少个平衡子字符串。
注意：一个 平衡 字符串指的是字符串中所有字符出现的次数都相同。
示例 1：
输入：s = “fabccddg”
输出：3
解释：
我们可以将 s 分割成 3 个子字符串：("fab, “ccdd”, “g”) 或者 (“fabc”, “cd”, “dg”) 。
示例 2：
输入：s = “abababaccddb”
输出：2
解释：
我们可以将 s 分割成 2 个子字符串：(“abab”, “abaccddb”) 。
提示：
1 <= s.length <= 1000
s 只包含小写英文字母。
题解：
方法：记忆化搜索
class Solution { public int minimumSubstringsInPartition(String S) { char[] s = S.toCharArray(); int n = s.length; int[] memo = new int[n]; return dfs(n - 1, s, memo); } private int dfs(int i, char[] s, int[] memo) { if (i < 0) { return 0; } if (memo[i] > 0) { // 之前计算过 return memo[i]; } int res = Integer.MAX_VALUE; int[] cnt = new int[26]; int k = 0, maxCnt = 0; for (int j = i; j >= 0; j--) { k += cnt[s[j] - 'a']++ == 0 ? 1 : 0; maxCnt = Math.max(maxCnt, cnt[s[j] - 'a']); if (i - j + 1 == k * maxCnt) { res = Math.min(res, dfs(j - 1, s, memo) + 1); } } memo[i] = res; // 记忆化 return res; } }
29.判断矩阵是否满足条件
题目链接：3142. 判断矩阵是否满足条件
给你一个大小为 m x n 的二维矩阵 grid 。你需要判断每一个格子 grid[i][j] 是否满足：
如果它下面的格子存在，那么它需要等于它下面的格子，也就是 grid[i][j] == grid[i + 1][j] 。
如果它右边的格子存在，那么它需要不等于它右边的格子，也就是 grid[i][j] != grid[i][j + 1] 。
如果 所有 格子都满足以上条件，那么返回 true ，否则返回 false 。
示例 1：
输入：grid = [[1,0,2],[1,0,2]]
输出：true
解释：
网格图中所有格子都符合条件。
示例 2：
输入：grid = [[1,1,1],[0,0,0]]
输出：false
解释：
同一行中的格子值都相等。
示例 3：
输入：grid = [[1],[2],[3]]
输出：false
解释：
同一列中的格子值不相等。
提示：
1 <= n, m <= 10
0 <= grid[i][j] <= 9
题解：
class Solution { public boolean satisfiesConditions(int[][] grid) { for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[i].length; j++) { if (j > 0 && grid[i][j] == grid[i][j - 1] || i > 0 && grid[i][j] != grid[i - 1][j]) { return false; } } } return true; } }
30.所有数对中数位差之和
题目链接：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 <= 105
1 <= nums[i] < 109
nums 中的整数都有相同的数位长度。
题解：
方法：拆位法
class Solution { public long sumDigitDifferences(int[] nums) { long ans = 0; int[][] cnt = new int[Integer.toString(nums[0]).length()][10]; for (int k = 0; k < nums.length; k++) { int x = nums[k]; for (int i = 0; x > 0; x /= 10, i++) { ans += k - cnt[i][x % 10]++; } } return ans; } }
31.构造相同颜色的正方形
题目链接：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’ 。
题解：
方法：遍历
class Solution { public boolean canMakeSquare(char[][] grid) { return check(grid, 0, 0) || check(grid, 0, 1) || check(grid, 1, 0) || check(grid, 1, 1); } private boolean check(char[][] grid, int i, int j) { int[] cnt = new int[2]; cnt[grid[i][j] & 1]++; cnt[grid[i][j + 1] & 1]++; cnt[grid[i + 1][j] & 1]++; cnt[grid[i + 1][j + 1] & 1]++; return cnt[0] != 2; } }
2024.9
1.在既定时间做作业的学生人数
题目链接：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
题解：
方法：遍历
class Solution { public int busyStudent(int[] startTime, int[] endTime, int queryTime) { int ans = 0; for (int i = 0; i < startTime.length; i++) { if (startTime[i] <= queryTime && queryTime <= endTime[i]) { ans++; } } return ans; } }
