【LeetCode每日一题合集】2023.7.24-2023.7.30

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 ~ 112（1100001~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) {PriorityQueue<Double> pq = new PriorityQueue<Double>((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 {List<Integer>[] 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记录答案// 按照完成时间升序排序的优先队列PriorityQueue<int[]> pq = new PriorityQueue<int[]>((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;List<Integer>[] 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);}Map<Integer, Integer> memo = new HashMap<Integer, 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, List<Integer>[] prev, Map<Integer, 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;}
}