周赛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 )