文章目录

1604. 警告一小时内使用相同员工卡大于等于三次的人 M1605. 给定行和列的和求可行矩阵 M1606. 找到处理最多请求的服务器 H1610. 可见点的最大数目 H1611. 使整数变为 0 的最少操作次数 H 总结第36场双周赛和第209场周赛。一共5道题。

---

1604. 警告一小时内使用相同员工卡大于等于三次的人 M

主要是好久不用python了。这里因为用到排序，所以写一下python的。如果使用java的话可以用一个hashmap维护，键是人名，值是一个list然会对list进行排序。

顺便说一下java的排序：

int[]: Araays.sort(nums)List: Collections.sort(nums) class Solution: def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]: ## 如果使用java的话可以用一个hashmap维护，键是人名，值是一个list然会对list进行排序。 nums = [] for i in range(len(keyName)): cur = [] cur.append(keyName[i]) time = keyTime[i] cur.append(int(time[0:2])*60+int(time[3:5])) nums.append(cur) ## 好久不太用lambda表达式了，这里人名先进行排序，然后对相同人名的时间在进行排序。 nums.sort(key = lambda x:(x[0],x[1])) ans = set() for i in range(len(nums)-2): cur = nums[i][0] if (nums[i+2][0] == cur and 0<nums[i+2][1]-nums[i][1]<=60): ans.add(cur) res = sorted(list(ans)) return res

---

1605. 给定行和列的和求可行矩阵 M

没有想到可以用贪心的方法解决。基本思路是首先我们在当前位置填写上能填写的最大值， 能填写是指的行列两维需要的值，显然是min。

class Solution { public int[][] restoreMatrix(int[] rowSum, int[] colSum) { int n = rowSum.length; int m = colSum.length; int[][] ans = new int[n][m]; for (int i = 0; i < n ; i++){ for (int j = 0; j<m; j++){ int min = Math.min(rowSum[i], colSum[j]); ans[i][j] = min; rowSum[i] -= min; colSum[j] -= min; } } return ans; } }

---

1606. 找到处理最多请求的服务器 H

很好的一道题目，用到了优先队列和有序集合的数据结构。优先队列用于存储所有节点完成的时间。有序集合用于存储节点。我们每次循环索引值，可以对应得到时间。然后判断优先队列队头的元素与当前时间的关系，如果节点已经完成任务就弹出，并且加入队列。再选择节点完成任务时候，有序集合可以保证整个过程的时间复杂度是$O(lgN)$。

有序集合TreeSet

添加元素：set.add()得到头/尾元素：set.first(), set.last()删除索引值对应的元素：set.remove(index)得到大于等于当前值的最小元素：set.ceiling(num)得到小于等于当前值的最大元素：set.floor(num)单纯的小于或者大于 set.lower(num), set.higher(num) 如果找不到是返回null的，但是要注意用Integer进行接受才可以判断。 class Solution { public List<Integer> busiestServers(int k, int[] arrival, int[] load) { // lambda表达式的优先队列 PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[1]-o2[1]); TreeSet<Integer> set = new TreeSet<>(); int n = arrival.length; int[] count = new int[k]; for (int i = 0; i <k; i++) set.add(i); for (int i = 0; i<n; i++){ while (!pq.isEmpty() && pq.peek()[1]<=arrival[i]){ int cur = pq.poll()[0]; set.add(cur); } if (set.isEmpty())continue; else { // 注意这里必须是integer ，这样后面才能进行null的判断 // ceiling Integer num = set.ceiling(i%k); if (num == null) num = set.first(); count[num]++; pq.offer(new int[]{num, arrival[i]+load[i]}); set.remove(num); } } //System.out.println(Arrays.toString(count)); List<Integer> ans = new ArrayList<>(); int max = 0; for (int i = 0; i<k; i++){ if (count[i]>max){ ans.clear(); ans.add(i); max = count[i]; } else if (count[i] == max) ans.add(i); } return ans; } }

---

1610. 可见点的最大数目 H

一道没有做出来的数学题，虽然可以想到思路式双指针的方法，但是没想想好实现。这里有一个很关键的细节在于，我们在旋转的时候需要考虑多转一圈。感谢leetcode的 @lemon 同学的图例。

class Solution { public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) { List<Double> list = new ArrayList<>(); int x = location.get(0); int y = location.get(1); int same = 0; for (List<Integer> point:points){ int dx = x - point.get(0); int dy = y - point.get(1); if (dx == 0 && dy == 0){ // 就是自己本身 same++; continue; } double ang = Math.atan2(dx, dy); //得到是弧度 list.add(ang); list.add(ang + 2 * Math.PI); } Collections.sort(list); //System.out.println(list); int left = 0; int right = 0; int res = 0; int ans = same; double maxangle = angle * Math.PI / 180.0; // 这里需要注意，角度转换为弧度 while (right<list.size()){ if (list.get(right)-list.get(left)<=maxangle) { res++; right++; }else { ans = Math.max(ans, res+same); res--; left++; } } return ans; } }

---

1611. 使整数变为 0 的最少操作次数 H

看到这类问题真的就是自己写写画画尝试找规律。可以发现问题的核心在于两个连续的11和其余都是0的情况。这些特殊点转换到全0的次数是2的n次幂。然后我们需要找到任意点转换到特殊点的路径，不难发现其实是由特殊点组合起来的。

class Solution { public int minimumOneBitOperations(int n) { //这个api还是不错的，很值得学习 String num = Integer.toBinaryString(n); int m = num.length(); int ans = 0; int cur = 0; for (int i = m-1; i>=0; i--){ if ((n>>i & 1) == 1){ ans += (1<<i); if (i == 0) cur = 1; else cur = (1<<i) + (1<<(i-1)); n ^= cur; } } return ans; } }