leetcode-神策数据周赛、1337-矩阵中战斗力最弱的k行 ｜8月更文挑战
站长
· 阅读数 16
leetcode-神策数据周赛、1337-矩阵中战斗力最弱的k行
[博客链接]
[题目描述]
- 给你一个大小为 m * n 的矩阵 mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。
- 请你返回矩阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。
- 如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。
- 军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。 示例 1：
- 输入：mat = [[1,1,0,0,0], [1,1,1,1,0], [1,0,0,0,0], [1,1,0,0,0], [1,1,1,1,1]],
- k = 3
- 输出：[2,0,3]
- 解释：
- 每行中的军人数目：
- 行 0 -> 2
- 行 1 -> 4
- 行 2 -> 1
- 行 3 -> 2
- 行 4 -> 5
- 从最弱到最强对这些行排序后得到 [2,0,3,1,4] 示例 2：
- 输入：mat = [[1,0,0,0], [1,1,1,1], [1,0,0,0], [1,0,0,0]],
- k = 2
- 输出：[0,2]
- 解释：
- 每行中的军人数目：
- 行 0 -> 1
- 行 1 -> 4
- 行 2 -> 1
- 行 3 -> 1
- 从最弱到最强对这些行排序后得到 [0,2,3,1] 提示：
- m == mat.length
- n == mat[i].length
- 2 <= n, m <= 100
- 1 <= k <= m
- matrix[i][j] 不是 0 就是 1
- Related Topics 数组 二分查找 矩阵 排序 堆（优先队列）
- 👍 70 👎 0
[题目链接]
[github地址]
[思路介绍]
思路一：暴力法+hash+优先队列
- 暴力法扫描所有单行数组，求战斗力和
- 然后通过treemap做排序
- 再通过优先队列对优先队列做弹出
- 给固定长度K的数组进行赋值
public int[] kWeakestRows(int[][] mat, int k) {
Map<Integer, PriorityQueue<Integer>> map = new TreeMap<>((a, b) -> a - b);
for (int i = 0; i < mat.length; i++) {
int j = 0, temp = 0;
while (j < mat[i].length && mat[i][j++] == 1) {
temp++;
}
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
priorityQueue = map.getOrDefault(temp, priorityQueue);
priorityQueue.add(i);
map.put(temp, priorityQueue);
}
int[] res = new int[k];
int i = 0;
for (int key : map.keySet()
) {
while (i < k && !map.get(key).isEmpty()) {
res[i++] = map.get(key).poll();
}
}
return res;
}
时间复杂度O(m*n)
思路二：二分查找+优先队列
- 根据数组排列情况，可以通过二分计算战斗力值
- 同时根据优先队列的大小控制输出数组
- 然后返回结果
//思路二：二分+优先队列
//根据数组排列情况，可以通过二分计算战斗力值
//同时根据优先队列的大小控制输出数组
//然后返回结果
Map<Integer, Integer> map = new HashMap<>();
public int[] kWeakestRows(int[][] mat, int k) {
int[] res = new int[k];
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
if (map.getOrDefault(o2, 0).equals(map.getOrDefault(o1, 0))) {
return o2 - o1;
}
return map.getOrDefault(o2, 0) - map.getOrDefault(o1, 0);
}
});
for (int i = 0; i < mat.length; i++) {
int value = getValue(mat[i]);
map.put(i, value);
if (priorityQueue.size() < k) {
priorityQueue.add(i);
} else {
if (map.get(priorityQueue.peek()) > value) {
priorityQueue.poll();
priorityQueue.add(i);
}
}
}
for (int i = k - 1; i >= 0; i--) {
res[i] = priorityQueue.poll();
}
return res;
}
private int getValue(int[] mat) {
int l = 0, r = mat.length - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (mat[mid] >= 1) l = mid;
else r = mid - 1;
}
return mat[r] > 0 ? r + 1 : r;
}
时间复杂度O(m(lgn+lgk)
神策数据周赛
Q1 是否是三除数
给你一个整数 n 。如果 n 恰好有三个正除数 ，返回 true ；否则，返回 false 。
如果存在整数 k ，满足 n = k * m ，那么整数 m 就是 n 的一个 除数 。
示例 1：
输入：n = 2
输出：false
解释：2 只有两个除数：1 和 2 。
示例 2：
输入：n = 4
输出：true
解释：4 有三个除数：1、2 和 4 。
提示：
1 <= n <= 104
思路一：数学分析
- 也就是说他只能包含一个因数，因为1 和 n本身是一定满足的
class Solution {
public boolean isThree(int n) {
if(n <= 2){
return false;
}
boolean flag =false;
for(int i = 2; i <n ; i++){
if(n%i==0){
if(flag){return false;}
flag = true;
}
}
return flag;
}
}
时间复杂度O(n)
Q2 最长连续工作周数
给你 n 个项目，编号从 0 到 n - 1 。同时给你一个整数数组 milestones ，其中每个 milestones[i] 表示第 i 个项目中的阶段任务数量。
你可以按下面两个规则参与项目中的工作：
每周，你将会完成 某一个 项目中的 恰好一个 阶段任务。你每周都 必须 工作。
在 连续的 两周中，你 不能 参与并完成同一个项目中的两个阶段任务。
一旦所有项目中的全部阶段任务都完成，或者仅剩余一个阶段任务都会导致你违反上面的规则，那么你将 停止工作 。注意，由于这些条件的限制，你可能无法完成所有阶段任务。
返回在不违反上面规则的情况下你 最多 能工作多少周。
示例 1：
输入：milestones = [1,2,3]
输出：6
解释：一种可能的情形是：
••••- 第 1 周，你参与并完成项目 0 中的一个阶段任务。
- 第 2 周，你参与并完成项目 2 中的一个阶段任务。
- 第 3 周，你参与并完成项目 1 中的一个阶段任务。
- 第 4 周，你参与并完成项目 2 中的一个阶段任务。
- 第 5 周，你参与并完成项目 1 中的一个阶段任务。
- 第 6 周，你参与并完成项目 2 中的一个阶段任务。
总周数是 6 。
示例 2：
输入：milestones = [5,2,1]
输出：7
解释：一种可能的情形是：
- 第 1 周，你参与并完成项目 0 中的一个阶段任务。
- 第 2 周，你参与并完成项目 1 中的一个阶段任务。
- 第 3 周，你参与并完成项目 0 中的一个阶段任务。
- 第 4 周，你参与并完成项目 1 中的一个阶段任务。
- 第 5 周，你参与并完成项目 0 中的一个阶段任务。
- 第 6 周，你参与并完成项目 2 中的一个阶段任务。
- 第 7 周，你参与并完成项目 0 中的一个阶段任务。
总周数是 7 。
注意，你不能在第 8 周参与完成项目 0 中的最后一个阶段任务，因为这会违反规则。
因此，项目 0 中会有一个阶段任务维持未完成状态。
提示：
n == milestones.length
1 <= n <= 105
1 <= milestones[i] <= 109
思路一：贪心法
-
最大解如果可以满足情况，那么其余任务一定都可以满足
-
如果最大解不满足情况，则是总和-最大解*2+1
-
这道题的贪心我没想到怎么证明
public long numberOfWeeks(int[] milestones) {
int max = milestones[0];
long sum = 0L;
for (int i = 0; i < milestones.length; i++) {
sum += milestones[i];
max = Math.max(max, milestones[i]);
}
long remain = sum - max;
return Math.min(sum, 2 * remain + 1);
}
时间复杂度O(n)
Q3 满足所需苹果的最小周长
给你一个用无限二维网格表示的花园，每一个 整数坐标处都有一棵苹果树。整数坐标 (i, j) 处的苹果树有 |i| + |j| 个苹果。
你将会买下正中心坐标是 (0, 0) 的一块 正方形土地 ，且每条边都与两条坐标轴之一平行。
给你一个整数 neededApples ，请你返回土地的 最小周长 ，使得 至少 有 neededApples 个苹果在土地 里面或者边缘上。
|x| 的值定义为：
如果 x >= 0 ，那么值为 x
如果 x < 0 ，那么值为 -x
示例 1：
输入：neededApples = 1
输出：8
解释：边长长度为 1 的正方形不包含任何苹果。
但是边长为 2 的正方形包含 12 个苹果（如上图所示）。
周长为 2 * 4 = 8 。
示例 2：
输入：neededApples = 13
输出：16
示例 3：
输入：neededApples = 1000000000
输出：5040
提示：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-garden-perimeter-to-collect-enough-apples
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路一：数学公式+二分
- 可以很容易的求得总苹果树的数量公示
- apples = 2 * i * (i + 1) * (2 * i + 1);
//思路一：二分等会儿写吧 先写暴力
/*public long minimumPerimeter(long neededApples) {
for (long i = 0; i < Integer.MAX_VALUE; i++) {
long apples = 2 * i * (i + 1) * (2 * i + 1);
if (apples >= neededApples) {
return i * 8L;
}
}
return 0;
}*/
//思路二：二分
public long minimumPerimeter(long neededApples) {
int l = 0, r = Integer.MAX_VALUE;
while (l < r) {
int mid = (l + r )/2;
long apples = 2 * mid * (mid + 1) * (2 * mid + 1);
if (apples > neededApples) {
r = mid - 1;
} else {
l = mid;
}
}
return r;
}
时间复杂度暴力O(n), 二分O(lgn)
转载自:https://juejin.cn/post/6991321271120166948