周赛327总结
飞快过了第一题第二题后，卡在了第三题（想太简单了，后来思路正确，但是代码一直有小bug），看了眼第四题题目太长了，然后还是继续死磕第三题，第四题模拟也不是我能做出来的模拟，真滴难
正整数和负整数的最大计数【LC6283】
Given an array nums sorted in non-decreasing order, return the maximum between the number of positive integers and the number of negative integers.
- In other words, if the number of positive integers in nums is pos and the number of negative integers is neg, then return the maximum of pos and neg.
Note that 0 is neither positive nor negative.
模拟
- 思路：简单模拟
。由于数组是递增的，因此可以统计负数个数neg和0个数zero，正数个数即为长度n−neg−zero，返回较大值即可
- 实现
class Solution { public int maximumCount(int[] nums) { int neg = 0, zero = 0, n = nums.length; for (int num : nums){ if (num < 0){ neg++; }else if (num == 0){ zero++; }else{ break; } } return Math.max(neg, n - neg - zero); } }
。复杂度
- 时间复杂度：O ( n )
- 空间复杂度：O ( 1 )
二分查找
- 思路：二分查找0
。负数数量为0的左边界，正数数量为n-0的右边界，因此可以二分查找0的左边界和右边界、
- 实现
class Solution { public int maximumCount(int[] nums) { return Math.max(binarySearch(nums, 0),nums.length - binarySearch(nums, 1)); } public int binarySearch(int[] nums, int t){ int l = 0, r = nums.length - 1; while(l <= r){ int mid = (l + r) / 2; if (nums[mid] < t){ l = mid + 1; }else{ r = mid - 1; } } return l; } }
。复杂度
- 时间复杂度：O ( l o g n )
- 空间复杂度：O ( 1 )
执行 K 次操作后的最大分数【LC6285】
You are given a 0-indexed integer array nums and an integer k. You have a starting score of 0.
In one operation:
1.choose an index i such that 0 <= i < nums.length,
2.increase your score by nums[i], and
3.replace nums[i] with ceil(nums[i] / 3).
Return the maximum possible score you can attain after applying exactly k operations.
The ceiling function ceil(val) is the least integer greater than or equal to val.
- 思路：贪心
。局部最优：每次操作获得的分数最大->每次获得的分数为数组中的最大值
。全局最优：执行K次操作后获得的分数最大
- 实现：使用大顶堆存放数组中的元素，每次弹出堆顶max，然后将⌈nums[i]/3)⌉放入堆中，执行k次，累加堆顶元素返回即可
class Solution { public long maxKelements(int[] nums, int k) { PriorityQueue<Integer> pq = new PriorityQueue<Integer>((o1, o2) -> (o2 - o1)); for (int num : nums){ pq.add(num); } long res = 0L; for (int i = 0; i < k; i++){ int max = pq.poll(); res += max; int add = max % 3 == 0 ? 0 : 1; pq.add(max / 3 + add); } return res; } }
。复杂度
- 时间复杂度：O ( n + k l o g n )
- 空间复杂度：O ( n )
使字符串总不同字符的数目相等【LC6284】
给你两个下标从 0 开始的字符串 word1 和 word2 。
一次 移动 由以下两个步骤组成：
- 选中两个下标 i 和 j ，分别满足 0 <= i < word1.length 和 0 <= j < word2.length ，
- 交换 word1[i] 和 word2[j] 。
如果可以通过 恰好一次 移动，使 word1 和 word2 中不同字符的数目相等，则返回 true ；否则，返回 false 。
- 思路：哈希表
。使用哈希表记录两个字符串出现的字符及其次数
。如果初始时，两个字符串中字符种类差值大于2，那么不可能通过一次操作，使不同字符的数目相同，返回false；反之，枚举移动操作。
。遍历哈希表，枚举移动操作：如果某次移动能够使两个字符串中不同字符的数目相等，则返回true；反之，返回false
- 将字符串word1的字符c1与字符串word2的字符c2交换
- 需要根据字符在本字符集的出现次数判断是否需要将字符种类减1
- 并判断字符是否在另一个字符集出现过，如果没有，那么将字符种类加1
- 最后将交换后两个字符串字符种类进行比较，如果相等，返回true；如果不相等，则继续枚举
注意：由于只需要获得交换后的字符种类数目即可，不需要真的对哈希表进行操作。但是如果交换的字符相同时进行以上操作，由于哈希表仍是原字符串的哈希表，会得到错误答案，因此当交换的字符相同时，字符种类不变，直接比较原始种类即可。
- 实现
class Solution { public boolean isItPossible(String word1, String word2) { int m = word1.length(), n = word2.length(); Map<Character, Integer> count1 = new HashMap<>(); Map<Character, Integer> count2 = new HashMap<>(); for (char c : word1.toCharArray()){ count1.put(c, count1.getOrDefault(c, 0) + 1); } for (char c : word2.toCharArray()){ count2.put(c, count2.getOrDefault(c, 0) + 1); } // 统计w1和w2中的字母种类a b int a = count1.size(), b = count2.size(); // |a-b| > 2 false if ( Math.abs(a - b) > 2){ return false; } for (var node1 : count1.entrySet()){ char c1 = node1.getKey(); int v1 = node1.getValue(); for (var node2 : count2.entrySet()){ int a1 = a, b1 = b; char c2 = node2.getKey(); int v2 = node2.getValue(); if (c1 != c2){ if (v1 == 1){ a1--; } if (v2 == 1){ b1--; } if (!count1.containsKey(c2)){ a1++; } if (!count2.containsKey(c1)){ b1++; } if (a1 == b1){ return true; } } } } return false; } }
。复杂度
- 时间复杂度：O(n+m+∣∑∣ 2 )，∣ ∑ ∣为字符集的大小，本题中均为小写字母，因此∣ ∑ ∣ = 26
- 空间复杂度：O ( ∣ ∑ ∣ )
过桥的时间【LC6306】
共有 k 位工人计划将 n 个箱子从旧仓库移动到新仓库。给你两个整数 n 和 k，以及一个二维整数数组 time ，数组的大小为 k x 4 ，其中 time[i] = [leftToRighti, pickOldi, rightToLefti, putNewi] 。
一条河将两座仓库分隔，只能通过一座桥通行。旧仓库位于河的右岸，新仓库在河的左岸。开始时，所有 k 位工人都在桥的左侧等待。为了移动这些箱子，第 i 位工人（下标从 0 开始）可以：
- 从左岸（新仓库）跨过桥到右岸（旧仓库），用时 leftToRighti 分钟。
- 从旧仓库选择一个箱子，并返回到桥边，用时 pickOldi 分钟。不同工人可以同时搬起所选的箱子。
- 从右岸（旧仓库）跨过桥到左岸（新仓库），用时 rightToLefti 分钟。
- 将箱子放入新仓库，并返回到桥边，用时 putNewi 分钟。不同工人可以同时放下所选的箱子。
如果满足下面任一条件，则认为工人 i 的 效率低于 工人 j ：
- leftToRighti + rightToLefti > leftToRightj + rightToLeftj
- leftToRighti + rightToLefti == leftToRightj + rightToLeftj 且 i > j
工人通过桥时需要遵循以下规则：
- 如果工人 x 到达桥边时，工人 y 正在过桥，那么工人 x 需要在桥边等待。
- 如果没有正在过桥的工人，那么在桥右边等待的工人可以先过桥。如果同时有多个工人在右边等待，那么 效率最低 的工人会先过桥。
- 如果没有正在过桥的工人，且桥右边也没有在等待的工人，同时旧仓库还剩下至少一个箱子需要搬运，此时在桥左边的工人可以过桥。如果同时有多个工人在左边等待，那么 效率最低 的工人会先过桥。
所有 n 个盒子都需要放入新仓库，请你返回最后一个搬运箱子的工人 到达河左岸 的时间。
- 思路：使用四个堆存放工人的下标和完成事件或者到达桥的时间，然后根据要求过桥、搬运箱子，放回最后一个搬运箱子的工人到达河左岸的时间
。首先将time数组排序，排序后下标越大，效率越低，优先级越高
。使用四个堆存放工人的下标和完成事件或者到达桥的时间
- workL：新仓库正在放箱的工人【在当前时间之前的所有工人均以完成事件，因此根据时间从小到大排序】
- waitL：新仓库等待过桥的工人【低效率的先过桥，根据下标从大到小排序】【到达对岸的时间非必须，辅助作用】
- workR：旧仓库正在拿箱的工人【在当前时间之前的所有工人均以完成事件，因此根据时间从小到大排序】
- waitLR：旧仓库等待过桥的工人【低效率的先过桥，根据下标从大到小排序】
。使用变量cur记录当前的时间，初始时，所有工人位于新仓库，因此将所有节点放入waitL
。然后模拟整个流程，计算n个工人从旧仓库到达新仓库，并选择箱子的时间
- 将workL和workR中所有完成工作的工人，放入排队列表
- 选择右岸效率最低的工人过桥，若无，再选择左岸效率最低的工人过桥：时间cur移动至其到达对岸的时间节点，并更新其完成工作的时间，最后将其放入工作列表
- 若两个排队列表均为空，说明工人都在working，那么选择最快完成工作的工人，让他排队过桥
。最后，计算所有工人回到左岸的时间，返回最终时间即可
- 分析可知，此时waitR一定没有元素【因为退出循环的条件是有n个员工到达右岸，如果waitR中有元素的话，n 一定不为0，因此最后一个员工到达右岸时，waitR一定没有元素】，而workR一定有元素，其他两个堆是否有元素不影响结果，因此将workR中工作的所有员工依次出队，若当前时间在其完成工作的时间之前，那么需要更新当前时间为其完成工作的时间，然后将当前时间更新为其到达左岸的时间，最后返回cur【堆中根据完成时间从小到大排序，而每次只能过桥一个员工，因此可得最终时间】
- 实现
class Solution { public int findCrossingTime(int n, int k, int[][] time) { // 预处理 排序，下标越大，效率越低 Arrays.sort(time, (o1, o2) -> (o1[0] + o1[2] - o2[0] - o2[2])); PriorityQueue<int[]> workL = new PriorityQueue<int[]>((o1, o2) -> (o1[1] - o2[1])); PriorityQueue<int[]> waitL = new PriorityQueue<int[]>((o1, o2) -> (o2[0] - o1[0])); PriorityQueue<int[]> workR = new PriorityQueue<int[]>((o1, o2) -> (o1[1] - o2[1])); PriorityQueue<int[]> waitR = new PriorityQueue<int[]>((o1, o2) -> (o2[0] - o1[0])); for (int i = k - 1; i >= 0; i--){ waitL.add(new int[]{i, time[i][0]}); } int cur = 0; // 在过桥的时候其他人可以选择箱子和放下箱子 while (n > 0){ // 将新仓库完成放箱子的工人放入排队列表 while (!workL.isEmpty() && workL.peek()[1] <= cur){ int[] done = workL.poll(); waitL.add(done); } // 将旧仓库完成拿箱子的工人放入排队列表 while (!workR.isEmpty() && workR.peek()[1] <= cur){ int[] done = workR.poll(); waitR.add(done); } // 旧仓库的工人优先过桥 if (!waitR.isEmpty()){ int[] poll = waitR.poll(); cur += time[poll[0]][2]; poll[1] = cur + time[poll[0]][3];// 放完箱的时间 workL.add(poll); }else if (!waitL.isEmpty()){ int[] poll = waitL.poll(); cur += time[poll[0]][0]; poll[1] = cur + time[poll[0]][1]; // 拿好箱的时间 workR.add(poll); n--; }else if (workL.isEmpty()){// 工人都在working cur = workR.peek()[1]; }else if (workR.isEmpty()){ cur = workL.peek()[1]; }else{ cur = Math.min(workL.peek()[1], workR.peek()[1]); } } // 最后waitR一定没有元素，workR一定有元素，其他两个堆是否有元素不影响结果，因此将工作的员工依次出队，更新过桥时间，返回即可 while (!workR.isEmpty()){ int[] poll = workR.poll(); cur = Math.max(poll[1], cur) + time[poll[0]][2]; } // while (!workR.isEmpty() || !waitR.isEmpty()){ // // 如果员工都在working 那么将时间后移 // if (waitR.isEmpty()){ // cur = Math.max(cur, workR.peek()[1]); // } // // 将旧仓库完成拿箱子的工人放入排队列表 // while (!workR.isEmpty() && workR.peek()[1] <= cur){ // int[] done = workR.poll(); // waitR.add(done); // } // int[] poll = waitR.poll(); // cur += time[poll[0]][2]; // } return cur; } }
。复杂度
- 时间复杂度：O ( n + l o g k )
- 空间复杂度：O ( k )
