请写出网站建设前期需要做的准备,局域网 手机网站建设,网页浏览器官方下载,提交网站收录文章目录 竞赛链接Q1#xff1a;6925. 故障键盘解法1——直接模拟解法2——双端队列 Q2#xff1a;6953. 判断是否能拆分数组#xff08;贪心#xff09;Q3#xff1a;2812. 找出最安全路径⭐解法1——多源BFS瓶颈路模型#xff1f;解法2——多源BFS 倒序枚举答案 并查… 文章目录 竞赛链接Q16925. 故障键盘解法1——直接模拟解法2——双端队列 Q26953. 判断是否能拆分数组贪心Q32812. 找出最安全路径⭐解法1——多源BFS瓶颈路模型解法2——多源BFS 倒序枚举答案 并查集TODO Q42813. 子序列最大优雅度⭐⭐⭐⭐⭐反悔贪心思路——反悔贪心代码相似题目列表LCP 30. 魔塔游戏堆贪心871. 最低加油次数堆贪心 成绩记录 竞赛链接
Q16925. 故障键盘
https://leetcode.cn/problems/faulty-keyboard/
提示 1 s.length 100 s 由小写英文字母组成 s[0] ! i
解法1——直接模拟
遇到 ‘i’ 翻转已有的字符串其它字符直接添加即可。
class Solution {public String finalString(String s) {StringBuilder ans new StringBuilder();for (char ch: s.toCharArray()) {if (ch ! i) ans.append(ch);else ans.reverse();}return ans.toString();}
}解法2——双端队列
用一个变量维护当前翻转了几次来决定新来的字符添加在开头还是结尾。
class Solution {public String finalString(String s) {int f 0;DequeCharacter dq new ArrayDeque();for (char ch: s.toCharArray()) {if (ch i) f;else {if (f % 2 0) dq.offerLast(ch);else dq.offerFirst(ch);}}StringBuilder ans new StringBuilder();for (char ch: dq) ans.append(ch);if (f % 2 1) ans.reverse();return ans.toString();}
}Q26953. 判断是否能拆分数组贪心
https://leetcode.cn/problems/check-if-it-is-possible-to-split-array/ 提示 1 n nums.length 100 1 nums[i] 100 1 m 200 class Solution {public boolean canSplitArray(ListInteger nums, int m) {int n nums.size();if (n 1 || n 2) return true;for (int i 0; i n - 1; i) {if (nums.get(i) nums.get(i 1) m) return true;}return false;}
}Q32812. 找出最安全路径⭐
https://leetcode.cn/problems/find-the-safest-path-in-a-grid/ 提示 1 grid.length n 400 grid[i].length n grid[i][j] 为 0 或 1 grid 至少存在一个小偷
解法1——多源BFS瓶颈路模型
第一遍 bfs 求出各个位置的安全系数。 第二遍 bfs将各个位置的安全系数更新为从终点开始的路径上的较小值。
class Solution {int[] dx new int[]{-1, 0, 1, 0}, dy new int[]{0, -1, 0, 1};public int maximumSafenessFactor(ListListInteger grid) {int n grid.size();if (grid.get(0).get(0) 1 || grid.get(n - 1).get(n - 1) 1) return 0;int[][] g new int[n][n], safe new int[n][n];Queueint[] q new LinkedList();// 第一遍多源bfs 求出各个位置的安全系数for (int i 0; i n; i) {for (int j 0; j n; j) {if (grid.get(i).get(j) 1) {g[i][j] 1;q.offer(new int[]{i, j});}}}while (!q.isEmpty()) {int sz q.size();for (int i 0; i sz; i) {int[] cur q.poll();int x cur[0], y cur[1];for (int k 0; k 4; k) {int nx x dx[k], ny y dy[k];if (nx 0 ny 0 nx n ny n g[nx][ny] 0) {q.offer(new int[]{nx, ny});g[nx][ny] g[x][y] 1;}}}}// 第二遍bfs 从终点出发求出各个路径的最小安全系数q.offer(new int[]{n - 1, n - 1});safe[n - 1][n - 1] g[n - 1][n - 1];while (!q.isEmpty()) {int[] cur q.poll();int x cur[0], y cur[1];for (int k 0; k 4; k) {int nx x dx[k], ny y dy[k];if (nx 0 ny 0 nx n ny n) {int nsafe Math.min(g[nx][ny], safe[x][y]);if (nsafe safe[nx][ny]) {safe[nx][ny] nsafe;q.offer(new int[]{nx, ny});}}}}return safe[0][0] - 1;}
}解法2——多源BFS 倒序枚举答案 并查集TODO
https://leetcode.cn/problems/find-the-safest-path-in-a-grid/solutions/2375565/jie-jin-on2-de-zuo-fa-duo-yuan-bfsdao-xu-r5um/
在这里插入代码片Q42813. 子序列最大优雅度⭐⭐⭐⭐⭐反悔贪心
https://leetcode.cn/problems/maximum-elegance-of-a-k-length-subsequence/ 提示 1 items.length n 10^5 items[i].length 2 items[i][0] profiti items[i][1] categoryi 1 profiti 10^9 1 categoryi n 1 k n
思路——反悔贪心
https://leetcode.cn/problems/maximum-elegance-of-a-k-length-subsequence/solutions/2375128/fan-hui-tan-xin-pythonjavacgo-by-endless-v2w1/
代码
核心的思想是x y^2枚举 y^2的值并使得 x 在该枚举值下的值最大就得到了该枚举值下的最大值。比较得到的所有的最大值就是最终结果了。
class Solution {public long findMaximumElegance(int[][] items, int k) {// 把利润从大到小排序Arrays.sort(items, (a, b) - b[0] - a[0]);long ans 0, totalProfit 0;SetInteger vis new HashSet();DequeInteger duplicate new ArrayDeque();for (int i 0; i items.length; i) {int profit items[i][0], category items[i][1];if (i k) {totalProfit profit;if (!vis.add(category)) {// 如果已经有这个类别了就把当前的放在栈顶duplicate.push(profit);}} else if (!duplicate.isEmpty() vis.add(category)) {// 如果当前栈不为空且当前种类没有出现过totalProfit profit - duplicate.pop(); // 修改利润}ans Math.max(ans, totalProfit (long) vis.size() * vis.size());}return ans;}
}相似题目列表
做完之后感觉这两个题目更相似一些但是和反悔贪心关系不是那么大。
LCP 30. 魔塔游戏堆贪心
https://leetcode.cn/problems/p0NxJO/description/ 提示 1 nums.length 10^5 -10^5 nums[i] 10^5
先检查是否有答案存在。
如果有答案存在就将已经枚举到的负值放入堆中每次 s 0 时就取出最小的那个负数移动到末尾即可。
class Solution {public int magicTower(int[] nums) {if (Arrays.stream(nums).sum() 0) return -1;int ans 0;// pq中存放目前遇到的负数PriorityQueueInteger pq new PriorityQueue();long s 1;for (int x: nums) {s x;if (x 0) pq.offer(x);while (s 0) {// 每次把最小的移动到最后面去s - pq.poll();ans;}}return ans;}
}871. 最低加油次数堆贪心
https://leetcode.cn/problems/minimum-number-of-refueling-stops/ 提示 1 target, startFuel 10^9 0 stations.length 500 1 positioni positioni1 target 1 fueli 10^9
用堆维护目前可以加的油但是先不加等到走不动了再一个个加。
class Solution {public int minRefuelStops(int target, int startFuel, int[][] stations) {if (startFuel target) return 0;Arrays.sort(stations, (x, y) - x[0] - y[0]); // 按照位置排序PriorityQueueInteger pq new PriorityQueueInteger((x, y) - y - x);int p startFuel, ans 0;for (int i 0; i stations.length; i) {while (p stations[i][0] !pq.isEmpty()) {p pq.poll();ans;}if (p stations[i][0]) break;if (p target) return ans;pq.offer(stations[i][1]);}while (p target !pq.isEmpty()) {p pq.poll();ans;}return p target? -1: ans;}
}成绩记录 T3 借助了一些些外力。 上小分。
