Day 13牛牛冲钻五模拟如果进入胜场对胜场进行计数达到 3后续的胜场 k 星如果进入败场计数清零importjava.util.*;importjava.io.*;publicclassMain{privatestaticPrintWriteroutnewPrintWriter(newBufferedWriter(newOutputStreamWriter(System.out)));privatestaticReadinnewRead();publicstaticvoidmain(String[]args)throwsIOException{inttin.nextInt();for(inti0;it;i){intnin.nextInt(),kin.nextInt();Stringstrin.next();intret0,cnt0;for(intj0;jstr.length();j){charchstr.charAt(j);if(chL){ret--;cnt0;}elseif(chW){cnt;retcnt3?k:1;}}out.println(ret);}out.close();}}classRead{StringTokenizerstnewStringTokenizer();BufferedReaderbfnewBufferedReader(newInputStreamReader(System.in));Stringnext()throwsIOException{if(!st.hasMoreTokens()){stnewStringTokenizer(bf.readLine());}returnst.nextToken();}intnextInt()throwsIOException{returnInteger.parseInt(next());}StringnextLine()throwsIOException{returnbf.readLine();}}最长无重复子数组滑动窗口要细心一点importjava.util.*;publicclassSolution{publicintmaxLength(int[]arr){int[]hashnewint[100000];intret0;for(intl0,r0;rarr.length;r){hash[arr[r]];while(hash[arr[r]]1){hash[arr[l]]--;l;}retMath.max(ret,r-l1);}returnret;}}重排字符串贪心 重排序贪心哪种字符的剩余个数最多那么这种字符就最危险优先处理核心步骤使用大根堆维护剩余字符以及字符的个数每次都处理优先拿个数最多的字符拼接到新的字符串因为个数最多意味着最危险堆顶元素和新字符串最后一个字符相同再拿个数最多的元素也就是说每次可能需要出堆一到两个元素出堆后维护剩余个数再重新入堆剪枝当出现次数最多的字符超过字符总个数的一半注定无法拼接为预期字符串当堆顶元素出堆和新字符串末尾字符相同但是堆已空没有其他字符那再放就一定相邻相同importjava.util.*;publicclassMain{staticclassNode{charch;intcount;Node(charch,intcount){this.chch;this.countcount;}}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intnsc.nextInt();Stringssc.next();int[]cntnewint[26];for(charc:s.toCharArray()){cnt[c-a];}intmaxCount0;for(intx:cnt){maxCountMath.max(maxCount,x);}if(maxCount(n1)/2){System.out.println(no);return;}PriorityQueueNodepqnewPriorityQueue((a,b)-b.count-a.count);for(inti0;i26;i){if(cnt[i]0){pq.offer(newNode((char)(ai),cnt[i]));}}StringBuilderansnewStringBuilder();while(!pq.isEmpty()){Nodefirstpq.poll();if(ans.length()0||ans.charAt(ans.length()-1)!first.ch){ans.append(first.ch);first.count--;if(first.count0){pq.offer(first);}}else{Nodesecondpq.poll();ans.append(second.ch);second.count--;if(second.count0){pq.offer(second);}pq.offer(first);}}System.out.println(yes);System.out.println(ans.toString());}}补充优先级队列大小堆 堆排序思想可以把它总结成三块PriorityQueue 比较器规则、和堆排序思想的关系、时间复杂度。1. PriorityQueue 为什么能变成大根堆Java 的PriorityQueue默认是小根堆也就是“优先级小”的元素先出来。比较器(a, b) - 返回值规则是返回值 0a 排在 b 前面 返回值 0a 和 b 优先级相同 返回值 0b 排在 a 前面如果写(a, b) - a.count - b.count表示count小的优先出来是小根堆。如果写(a, b) - b.count - a.count表示count大的优先出来是大根堆。更推荐写成(a, b) - Integer.compare(b.count, a.count)这样可以避免整数相减溢出。虽然这道题count 10^5不会溢出但养成这个习惯更好。2. 和堆排序思想的关系堆排序的核心思想是每次从堆中取出当前最大值或最小值如果是大根堆堆顶永远是当前最大元素 每次取出堆顶就得到了当前剩余元素中的最大值 不断取出就能得到一个降序序列例如有这些次数a: 2 b: 2 c: 3大根堆里堆顶先是c: 3取出c后次数减一再放回c: 2 a: 2 b: 2下次再取当前次数最多的字符。这道题不是纯排序而是借用了堆排序的思想始终拿当前剩余次数最多的字符但它多了一个限制不能和上一个字符相同所以如果堆顶字符和上一个相同就临时取第二大的字符来放。也就是说堆排序每次取最大值 本题贪心每次尽量取最大值但要避开相邻重复3. 时间复杂度假设字符串长度是n字符种类是k。这题只有小写字母所以k 26每个字符最多会被取出、修改、再放回若干次。每次堆操作的复杂度是O(log k)总共处理n个字符所以整体复杂度是O(n log k)因为k 26所以O(n log 26)而log 26是常数因此可以近似看成O(n)空间复杂度O(k)因为堆里最多放 26 种字符再加上计数数组cnt[26]。所以空间复杂度是O(26) O(1)如果算输出字符串StringBuilder它需要存放长度为n的答案那么总空间是O(n)一句话总结PriorityQueue 通过比较器决定谁优先出队。 (a, b) - b.count - a.count 会让 count 大的排在前面所以实现大根堆。 本题借用了堆排序“每次取当前最大值”的思想但要额外判断不能和上一个字符相同。 时间复杂度 O(n log 26)近似 O(n)。