Day 18压缩字符串(一)解题思路遍历过程中前后字符相同计数器 1遍历到新字符重置计数器 (不用计数器也可以考虑使用双指针)单独处理字符串最后一种字符代码实现importjava.util.*;publicclassSolution{publicStringcompressString(Stringparam){StringBuildersbnewStringBuilder();intcnt1;char[]chsparam.toCharArray();if(chs.length1)returnparam;for(inti1;iparam.length();i){if(chs[i]chs[i-1]){cnt;}else{sb.append(chs[i-1]);if(cnt1)sb.append(cnt);cnt1;}if(iparam.length()-1){sb.append(chs[i]);if(cnt1)sb.append(cnt);}}returnsb.toString();}}chika 和蜜柑解题思路TopK 思想找到甜度最大的 k 个橘子构造小根堆甜度小的放上面甜度相同酸度大的放上面重点关注小根堆的构建以及数据计算可能溢出的问题使用 Long.compare(a, b)会比较 a, b 这两个 long 类型的值然后根据大小返回 -1, 0, 1避免 (a-b) 计算造成的溢出代码实现importjava.io.*;importjava.util.*;publicclassMain{privatestaticPrintWriteroutnewPrintWriter(newBufferedWriter(newOutputStreamWriter(System.out)));privatestaticReadinnewRead();publicstaticvoidmain(String[]args)throwsIOException{intnin.nextInt(),kin.nextInt();long[]anewlong[n];long[]bnewlong[n];for(inti0;in;i)a[i]in.nextLong();for(inti0;in;i)b[i]in.nextLong();// 关键: 构造器的初始化// 使用 Long.compare(x.vb, y.vb) 保证比较结果不溢出PriorityQueueNodequeuenewPriorityQueue((x,y)-{// 甜度小的在堆顶// 注意: 不能 x.vb y.vb 这样比较, 因为当 x.vb y.vb 时, 会导致去比较酸度, 导致甜度大的可能被放到堆顶// 只要甜度不同, 就比较, 将甜度小的放堆顶if(x.vb!y.vb)returnLong.compare(x.vb,y.vb);// 甜度相同, 酸度大的在堆顶returnLong.compare(y.va,x.va);});longsumA0,sumB0;for(inti0;in;i){intsizequeue.size();if(sizek){queue.offer(newNode(a[i],b[i]));sumAa[i];sumBb[i];continue;}else{Nodetopqueue.poll();if(top.vbb[i]||(top.vbb[i]a[i]top.va)){queue.offer(newNode(a[i],b[i]));sumA(a[i]-top.va);sumB(b[i]-top.vb);}else{queue.offer(top);}}}out.println(sumA sumB);out.close();}}classNode{longva;// 酸度longvb;// 甜度publicNode(longva,longvb){this.vava;this.vbvb;}}classRead{StringTokenizerstnewStringTokenizer();BufferedReaderbfnewBufferedReader(newInputStreamReader(System.in));Stringnext()throwsIOException{if(!st.hasMoreTokens()){Stringlinebf.readLine();if(linenull)returnline;stnewStringTokenizer(line);}returnst.nextToken();}intnextInt()throwsIOException{returnInteger.parseInt(next());}longnextLong()throwsIOException{returnLong.parseLong(next());}}01 背包 重点01 背包模板题1. 状态表示dp[i][j]表示从前 i 个物品中挑选总体积不超过 j 的情况下最大重量是多少。2. 状态转移方程根据「最后一步」的状况来分情况讨论i. 不选择第 i 个物品相当于就是去前 i - 1 个物品中挑选并且总体积不超过 j。此时dp[i][j] dp[i - 1][j]ii. 选择第 i 个物品那么我就只能去前i - 1个物品中挑选总体积不超过j - v[i]的物品。此时dp[i][j] dp[i - 1][j - v[i]] w[i]。但是这种状态不一定存在因此需要特判一下。综上状态转移方程为dp[i][j] max(dp[i - 1][j], dp[i - 1][j - v[i]] w[i])补充一句第二种情况需要满足j v[i]否则不能选第i个物品。代码实现importjava.util.*;publicclassSolution{publicintknapsack(intV,intn,int[][]vw){// 背包体积范围在 0~1000 内int[]dpnewint[1010];for(inti0;in;i){for(intjV;jvw[i][0];j--){dp[j]Math.max(dp[j],dp[j-vw[i][0]]vw[i][1]);}}returndp[V];}}
