北京网站建设龙鹏,网站一键生成,塘坑网站建设,做网站大家都找谁文章目录 771. 宝石与石头代码1——暴力代码2——位运算集合⭐#xff08;英文字母的long集合表示#xff09; 2208. 将数组和减半的最少操作次数#xff08;贪心 优先队列#xff09;2569. 更新数组后处理求和查询⭐⭐⭐⭐⭐#xff08;线段树#xff09;TODO2500. 删除… 文章目录 771. 宝石与石头代码1——暴力代码2——位运算集合⭐英文字母的long集合表示 2208. 将数组和减半的最少操作次数贪心 优先队列2569. 更新数组后处理求和查询⭐⭐⭐⭐⭐线段树TODO2500. 删除每行中的最大值排序2050. 并行课程 III解法1——优先队列记忆化搜索解法2——记忆化搜索 141. 环形链表快慢指针判断环形链表142. 环形链表 II找到入环的第一个节点 771. 宝石与石头
https://leetcode.cn/problems/jewels-and-stones/description/ 代码1——暴力
class Solution {public int numJewelsInStones(String jewels, String stones) {int ans 0;for (char ch: stones.toCharArray()) {if (jewels.indexOf(ch) ! -1) ans;}return ans;}
}代码2——位运算集合⭐英文字母的long集合表示
‘A’ ~ ‘Z’ 是 65 ~ 90 1000001~1011010 ‘a’ ~ ‘z’ 是 97 ~ 1121100001~1110000
63 的 二进制表示是111111
将上述范围变成了 1 ~ 26 和 33 ~ 58。
class Solution {public int numJewelsInStones(String jewels, String stones) {long mask 0;for (char ch: jewels.toCharArray()) mask | 1L (ch 63);int ans 0;for (char ch: stones.toCharArray()) {ans mask (ch 63) 1;}return ans;}
}2208. 将数组和减半的最少操作次数贪心 优先队列
https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/description/ 提示
1 nums.length 10^5 1 nums[i] 10^7
题目要求至少减少到原数组和的一半 需要的操作次数。
使用贪心策略每次对当前最大的元素减半。获得当前最大的元素可以使用堆。
class Solution {public int halveArray(int[] nums) {PriorityQueueDouble pq new PriorityQueueDouble((a, b) - b.compareTo(a));int ans 0;double sum 0, cur 0;for (int num: nums) {pq.offer((double)num);sum num;}while (cur sum / 2) {double v pq.poll();cur v / 2;pq.offer(v / 2);ans;}return ans;}
}2569. 更新数组后处理求和查询⭐⭐⭐⭐⭐线段树TODO
https://leetcode.cn/problems/handling-sum-queries-after-update/description/ 提示 1 nums1.length,nums2.length 10^5 nums1.length nums2.length 1 queries.length 10^5 queries[i].length 3 0 l r nums1.length - 1 0 p 10^6 0 nums1[i] 1 0 nums2[i] 10^9
文字题解https://leetcode.cn/problems/handling-sum-queries-after-update/solutions/2119436/xian-duan-shu-by-endlesscheng-vx80/ 视频题解https://www.bilibili.com/video/BV15D4y1G7ms/
在这里插入代码片2500. 删除每行中的最大值排序
https://leetcode.cn/problems/delete-greatest-value-in-each-row/description/ 提示
m grid.length n grid[i].length 1 m, n 50 1 grid[i][j] 100
排序之后我们可以按顺序找出每一行当前的最大值。
class Solution {public int deleteGreatestValue(int[][] grid) {int m grid.length, n grid[0].length, ans 0;for (int i 0; i m; i) {Arrays.sort(grid[i]);}for (int j n - 1; j 0; --j) {int mx 0;for (int i 0; i m; i) {mx Math.max(mx, grid[i][j]);}ans mx;}return ans;}
}2050. 并行课程 III
https://leetcode.cn/problems/parallel-courses-iii/description/ 解法1——优先队列记忆化搜索
class Solution {ListInteger[] g;int[] in;public int minimumTime(int n, int[][] relations, int[] time) {in new int[n 1];g new ArrayList[n 1];Arrays.setAll(g, e - new ArrayList());for (int[] r: relations) {g[r[0]].add(r[1]);in[r[1]];}int ans 0; // ans记录答案// 按照完成时间升序排序的优先队列PriorityQueueint[] pq new PriorityQueueint[]((a, b) - a[1] - b[1]);for (int i 1; i n; i) {if (in[i] 0) {pq.offer(new int[]{i, time[i - 1]});}}while (!pq.isEmpty()) {int[] cur pq.poll();ans cur[1];for (int y: g[cur[0]]) {if (--in[y] 0) {pq.offer(new int[]{y, ans time[y - 1]});}}}return ans;}
}解法2——记忆化搜索
class Solution {public int minimumTime(int n, int[][] relations, int[] time) {int mx 0;ListInteger[] prev new List[n 1];Arrays.setAll(prev, e - new ArrayList());for (int[] relation : relations) {int x relation[0], y relation[1];prev[y].add(x);}MapInteger, Integer memo new HashMapInteger, Integer();for (int i 1; i n; i) {mx Math.max(mx, dp(i, time, prev, memo));}return mx;}public int dp(int i, int[] time, ListInteger[] prev, MapInteger, Integer memo) {if (!memo.containsKey(i)) {int cur 0;for (int p : prev[i]) {cur Math.max(cur, dp(p, time, prev, memo));}cur time[i - 1];memo.put(i, cur);}return memo.get(i);}
}141. 环形链表快慢指针判断环形链表
https://leetcode.cn/problems/linked-list-cycle/ public class Solution {public boolean hasCycle(ListNode head) {ListNode slow head, fast head;while (fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;if (slow fast) return true;}return false;}
}142. 环形链表 II找到入环的第一个节点
https://leetcode.cn/problems/linked-list-cycle-ii/description/ 提示
链表中节点的数目范围在范围 [0, 10^4] 内 -10^5 Node.val 10^5 pos 的值为 -1 或者链表中的一个有效索引
解析
public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow head, fast head;while (fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;if (slow fast) {ListNode t head;while (t ! slow) {t t.next;slow slow.next;}return t;}}return null;}
}
