【LeetCode每日一题合集】2023.10.9-2023.10.15（贪心⭐位运算的应用：只出现一次的数字）

文章目录

2578. 最小和分割（贪心）
2731. 移动机器人（脑筋急转弯+排序统计）
2512. 奖励最顶尖的 K 名学生（哈希表+排序）（练习Java语法）
- 代码风格1
- 代码风格2
2562. 找出数组的串联值（简单模拟）
- 写法1——模拟
- 写法2——String、Integer 的 API
1488. 避免洪水泛滥⭐
- 解法1——贪心+优先队列
- 解法2——贪心+二分查找
- - 补充：TreeSet的ceiling()和floor()
136. 只出现一次的数字（异或的应用）
137. 只出现一次的数字 II⭐（位运算）
- 解法1——依次确定二进制的每一位
- 解法2——数字电路设计🚹

2578. 最小和分割（贪心）

https://leetcode.cn/problems/split-with-minimum-sum/?envType=daily-question&envId=2023-10-09

在这里插入图片描述

分给两个数字，两个数字的位数越接近越好。
除此之外，数字越大就放在越靠后的位置即可。

class Solution {public int splitNum(int num) {List<Integer> ls = new ArrayList<>();while (num != 0) {ls.add(num % 10);num /= 10;}Collections.sort(ls);int n = ls.size(), ans = 0;for (int i = 0, t = 1; i < n; ++i) {ans += ls.get(n - 1 - i) * t;if (i % 2 == 1) t *= 10;}return ans;}
}

2731. 移动机器人（脑筋急转弯+排序统计）

https://leetcode.cn/problems/movement-of-robots/description/?envType=daily-question&envId=2023-10-10

在这里插入图片描述

提示：

2 <= nums.length <= 10^5
-2 * 10^9 <= nums[i] <= 2 * 10^9
0 <= d <= 10^9
nums.length == s.length
s 只包含 'L' 和 'R' 。
nums[i] 互不相同。

两个机器人相碰之后可以认为是相互代替了对方。

class Solution {public int sumDistance(int[] nums, String s, int d) {final int MOD = (int)1e9 + 7;int n = nums.length;long[] p = new long[n];for (int i = 0; i < n; ++i) {if (s.charAt(i) == 'L') p[i] = nums[i] - d;else p[i] = nums[i] + d;}Arrays.sort(p);long ans = 0, sum = 0;for (int i = 1; i < n; ++i) {long x = p[i] - p[i - 1];sum = (sum + x * i) % MOD;ans = (ans + sum) % MOD;}return (int)ans;}
}

2512. 奖励最顶尖的 K 名学生（哈希表+排序）（练习Java语法）

https://leetcode.cn/problems/reward-top-k-students/description/?envType=daily-question&envId=2023-10-11

在这里插入图片描述

代码风格1

class Solution {public List<Integer> topStudents(String[] positive_feedback, String[] negative_feedback, String[] report, int[] student_id, int k) {Map<String, Integer> words = new HashMap<>();for (String word: positive_feedback) words.put(word, 3);for (String word: negative_feedback) words.put(word, -1);int n = report.length;int[] scores = new int[n];int[][] stus = new int[n][2];for (int i = 0; i < n; ++i) {int s = 0;for (String w: report[i].split(" ")) s += words.getOrDefault(w, 0);stus[i] = new int[]{s, student_id[i]};}Arrays.sort(stus, (a, b) -> {return a[0] != b[0]? b[0] - a[0]: a[1] - b[1];});List<Integer> ans = new ArrayList<>();for (int i = 0; i < k; ++i) ans.add(stus[i][1]);return ans;}
}

代码风格2

class Solution {Set<String> pos, neg;public List<Integer> topStudents(String[] positive_feedback, String[] negative_feedback, String[] report, int[] student_id, int k) {int n = student_id.length;pos = new HashSet<>(Arrays.stream(positive_feedback).collect(Collectors.toSet()));neg = new HashSet<>(Arrays.stream(negative_feedback).collect(Collectors.toSet()));List<Integer> ans = new ArrayList<>();Map<Integer, Integer> s = new HashMap<>();      // 计算分数for (int i = 0; i < n; ++i) {s.merge(student_id[i], cp(report[i]), Integer::sum);}List<Integer> sId = Arrays.stream(student_id).boxed().collect(Collectors.toList());Collections.sort(sId, (x, y) -> {int a = s.getOrDefault(x, 0), b = s.getOrDefault(y, 0);if (a != b) return b - a;return x - y;});for (int i = 0; i < k; ++i) ans.add(sId.get(i));return ans;}public int cp(String r) {String[] ws = r.split(" ");int res = 0;for (String w: ws) {if (pos.contains(w)) res += 3;else if (neg.contains(w)) res -= 1;}return res;}
}

2562. 找出数组的串联值（简单模拟）

https://leetcode.cn/problems/find-the-array-concatenation-value/description/?envType=daily-question&envId=2023-10-12

在这里插入图片描述

提示：
1 <= nums.length <= 1000
1 <= nums[i] <= 10^4

写法1——模拟

class Solution {public long findTheArrayConcVal(int[] nums) {long ans = 0;for (int l = 0, r = nums.length - 1; l <= r; ++l, --r) {if (l != r) {ans += op(nums[l], nums[r]);} else {ans += nums[l];}}return ans;}public int op(int a, int b) {int t = b;while (t != 0) {a *= 10;t /= 10;}return a + b;}
}

写法2——String、Integer 的 API

class Solution {public long findTheArrayConcVal(int[] nums) {long ans = 0;for (int i = 0, j = nums.length - 1; i <= j; i++, j--) {if (i != j) {ans += Integer.parseInt(Integer.toString(nums[i]) + Integer.toString(nums[j]));} else {ans += nums[i];}}return ans;}
}

1488. 避免洪水泛滥⭐

https://leetcode.cn/problems/avoid-flood-in-the-city/description/?envType=daily-question&envId=2023-10-13

在这里插入图片描述

提示：

1 <= rains.length <= 10^5
0 <= rains[i] <= 10^9

解法1——贪心+优先队列

https://leetcode.cn/problems/avoid-flood-in-the-city/solutions/303095/tan-xin-you-xian-dui-lie-he-xin-si-lu-yi-ju-hua-by/?envType=daily-question&envId=2023-10-13

每当一个湖泊下雨时，将其下一个下雨的下标存入优先队列中。
这样当可以排水时，可以O(1)取出下一个最需要排水的湖泊。

class Solution {public int[] avoidFlood(int[] rains) {int n = rains.length;int[] ans = new int[n];Set<Integer> s = new HashSet<>();                   // 存储已经有水的湖泊Map<Integer, Deque<Integer>> m = new HashMap<>();   // 湖编号=>下雨日期双端队列for (int i = 0; i < n; ++i) {int r = rains[i];if (r > 0) {if (!m.containsKey(r)) m.put(r, new ArrayDeque<Integer>());m.get(r).offerLast(i);}}PriorityQueue<Integer> pq = new PriorityQueue<>();  // 优先队列，下一个最需要被排水的湖泊编号for (int i = 0; i < n; ++i) {if (rains[i] > 0) {if (s.contains(rains[i])) {return new int[]{};     // 已经有水了，不能避免} else {ans[i] = -1;s.add(rains[i]);        m.get(rains[i]).pollFirst();if (!m.get(rains[i]).isEmpty()) pq.offer(m.get(rains[i]).peekFirst());}} else {if (pq.isEmpty()) ans[i] = 1;else {int idx = pq.poll();ans[i] = rains[idx];s.remove(rains[idx]);}}}return ans;}
}

解法2——贪心+二分查找

https://leetcode.cn/problems/avoid-flood-in-the-city/solutions/2472026/bi-mian-hong-shui-fan-lan-by-leetcode-so-n5c9/?envType=daily-question&envId=2023-10-13
我们总是在最早的晴天日子中进行抽干操作，以最大程度地避免洪水的发生。

class Solution {public int[] avoidFlood(int[] rains) {int n = rains.length;TreeSet<Integer> st = new TreeSet<>();      // 记录可用日期int[] ans = new int[n];Arrays.fill(ans, 1);Map<Integer, Integer> last = new HashMap<>();// 记录各个湖泊上一个下雨的下标for (int i = 0; i < n; ++i) {if (rains[i] == 0) st.add(i);else {ans[i] = -1;if (last.containsKey(rains[i])) {Integer idx = st.ceiling(last.get(rains[i]));   // 二分查找到最早可用排水的日期if (idx == null) return new int[0];ans[idx] = rains[i];st.remove(idx);}last.put(rains[i], i);}}return ans;}
}

二分查找可以使用 TreeSet 的 ceiling() 方法来实现。

补充：TreeSet的ceiling()和floor()

TreeSet 是 Java 中的一个基于红黑树实现的有序集合类，它提供了一些用于查找元素的方法，包括 ceiling() 和 floor() 方法。这两个方法用于查找与指定元素最接近的元素，但有一些差异。

ceiling(E e) 方法：
ceiling(E e) 方法返回集合中大于等于指定元素 e 的最小元素，或者如果不存在这样的元素，则返回 null。
如果存在等于 e 的元素，它也会返回这个元素。

floor(E e) 方法：
floor(E e) 方法返回集合中小于等于指定元素 e 的最大元素，或者如果不存在这样的元素，则返回 null。
如果存在等于 e 的元素，它也会返回这个元素。

136. 只出现一次的数字（异或的应用）

https://leetcode.cn/problems/single-number/description/?envType=daily-question&envId=2023-10-14
在这里插入图片描述

提示：
1 <= nums.length <= 3 * 10^4
-3 * 104 <= nums[i] <= 3 * 10^4
除了某个元素只出现一次以外，其余每个元素均出现两次。

class Solution {public int singleNumber(int[] nums) {int ans = 0;for (int num: nums) ans ^= num;return ans;}
}

137. 只出现一次的数字 II⭐（位运算）

https://leetcode.cn/problems/single-number-ii/description/?envType=daily-question&envId=2023-10-15

在这里插入图片描述

解法1——依次确定二进制的每一位

在这里插入图片描述

class Solution {public int singleNumber(int[] nums) {int ans = 0;for (int i = 0; i < 32; ++i) {						// 枚举每一位int total = 0;for (int x: nums) total += ((x >> i) & 1);		// 枚举每个数字if (total % 3 == 1) ans |= 1 << i; }return ans;}
}