Java刷题 leetcode
- 或值至少为 K 的最短子数组 II
中等
相关标签
相关企业
提示
给你一个 非负 整数数组 nums 和一个整数 k 。
如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。
请你返回 nums 中 最短特别非空
子数组
的长度，如果特别子数组不存在，那么返回 -1 。
示例 1：
输入：nums = [1,2,3], k = 2
输出：1
解释：
子数组 [3] 的按位 OR 值为 3 ，所以我们返回 1 。
示例 2：
输入：nums = [2,1,8], k = 10
输出：3
解释：
子数组 [2,1,8] 的按位 OR 值为 11 ，所以我们返回 3 。
示例 3：
输入：nums = [1,2], k = 0
输出：1
解释：
子数组 [1] 的按位 OR 值为 1 ，所以我们返回 1 。
提示：
1 <= nums.length <= 2 * 105
0 <= nums[i] <= 109
0 <= k <= 109
class Solution {
public int minimumSubarrayLength(int[] nums, int k) {
// 初始化结果为整数最大值，用于存储满足条件的最短子数组的长度
int ans = Integer.MAX_VALUE;
// 遍历数组 nums
for (int i = 0; i < nums.length; i++) {
// 获取当前元素
int x = nums[i];
// 如果当前元素大于等于 k，直接返回 1，因为单个元素构成的子数组长度为 1
if (x >= k) {
return 1;
}
// 内层循环，从当前元素的前一个元素开始向左遍历
for (int j = i - 1; j >= 0 && (nums[j] | x)!= nums[j]; j--) {
// 将当前元素 x 的位信息添加到 nums[j] 中，通过按位或操作
nums[j] |= x;
// 如果更新后的 nums[j] 大于等于 k，计算子数组长度并更新最小长度
if (nums[j] >= k) {
ans = Math.min(ans, i - j + 1);
}
}
}
// 如果 ans 仍为整数最大值，说明没有找到满足条件的子数组，返回 -1；否则返回最小长度
return ans == Integer.MAX_VALUE? -1 : ans;
}
}- 判断矩阵是否满足条件
简单
相关标签
相关企业
提示
给你一个大小为 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[0].length; ++j) {
if (i + 1 < grid.length && grid[i][j] != grid[i + 1][j]) {
return false;
}
if (j + 1 < grid[0].length && grid[i][j] == grid[i][j + 1]) {
return false;
}
}
}
return true;
}
}
- 分割字符频率相等的最少子字符串
中等
相关标签
相关企业
提示
给你一个字符串 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) {
// 将字符串 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) {
// 当 i 小于 0 时，表示已经处理完整个字符串，返回 0
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;
// 从当前位置 i 向前遍历
for (int j = i; j >= 0; j--) {
// 如果字符 s[j] 的计数从 0 变为 1，则 k 加 1，表示不同字符的数量加 1
k += cnt[s[j] - 'a']++ == 0? 1 : 0;
// 更新字符出现次数的最大值
maxCnt = Math.max(maxCnt, cnt[s[j] - 'a']);
// 检查是否满足划分条件：子串长度等于不同字符数量乘以最大出现次数
if (i - j + 1 == k * maxCnt) {
// 递归调用 dfs 计算子串左边部分的最小划分数量，并加 1 表示当前划分
res = Math.min(res, dfs(j - 1, s, memo) + 1);
}
}
// 将计算结果存储在备忘录中
memo[i] = res;
return res;
}
}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 <= 20001 <= employees[i].id <= 2000- 所有的
employees[i].id互不相同。 -100 <= employees[i].importance <= 100- 一名员工最多有一名直接领导，并可能有多名下属。
employees[i].subordinates中的 ID 都有效。
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class Solution {
// 存储员工 ID 到员工对象的映射
Map<Integer, Employee> map = new HashMap<Integer, Employee>();
public int getImportance(List<Employee> employees, int id) {
// 将员工列表中的员工对象添加到 map 中，以员工 ID 为键
for (Employee employee : employees) {
map.put(employee.id, employee);
}
// 从指定的员工 ID 开始进行深度优先搜索
return dfs(id);
}
public int dfs(int id) {
// 根据员工 ID 获取对应的员工对象
Employee employee = map.get(id);
// 获取该员工的重要性
int total = employee.importance;
// 获取该员工的下属员工 ID 列表
List<Integer> subordinates = employee.subordinates;
// 遍历下属员工
for (int subId : subordinates) {
// 递归计算下属员工的重要性，并累加到 total 中
total += dfs(subId);
}
return total;
}
}