【笔试强训】Week1：点击消除，数组中两个字符串的最小距离，dd爱框框，腐烂的苹果，大数乘法

文章目录IO优化1. 点击消除AB5题目描述解题思路代码实现2. 数组中两个字符串的最小距离题目描述解题思路代码实现3. dd爱框框题目描述解题思路代码实现4. 除2题目描述解题思路代码实现5. 腐烂的苹果NC398题目描述解题思路代码实现6. 大数乘法NC 10题目描述解题思路代码实现IO优化Scanner和System.out需要频繁刷新缓冲区当数据量很大时即使解题思路是对的也可能导致超时。需要自定义快速读入。importjava.util.*;importjava.io.*;publicclassMain{publicstaticPrintWriteroutnewPrintWriter(newBufferedWriter(newOutputStreamWriter(System.out)));publicstaticReadinnewRead();publicstaticvoidmain(String[]args){//codeout.close();}}publicclassRead{StringTokenizerstnewStringTokenizer();BufferedReaderbfnewBufferedReader(newInputStreamReader(System.in));Stringnext()throwsIOException{while((!st.hasMoreTokens())){stnewStringTokenizer(bf.readLine());}returnst.nextToken();}StringnextLine()throwsIOException{returnbf.readLine();}intnextInt()throwsIOException{returnInteger.parseInt(next());}longnextLong()throwsIOException{returnLong.parseLong(next());}doublenextDouble()throwsIOException{returnDouble.parseDouble(next());}}1. 点击消除AB5点击消除题目描述解题思路如果利用栈来实现需要先把所有字符出栈再逆序可以借助StringBuilder模拟栈结构进行尾插和尾删最终剩余的就是结果。代码实现importjava.util.*;publicclassMain1{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);char[]arrin.nextLine().toCharArray();StringBuildersbnewStringBuilder();inti0;while(iarr.length){if(sb.isEmpty())sb.append(arr[i]);else{chartmpsb.charAt(sb.length()-1);if(tmparr[i])sb.deleteCharAt(sb.length()-1);elsesb.append(arr[i]);}i;}if(sb.isEmpty())System.out.println(0);elseSystem.out.println(sb.toString());}}2. 数组中两个字符串的最小距离数组中两个字符串的最小距离题目描述解题思路动态规划从左向右遍历dp[i]表示在左边另一个字符串的最近距离。定义两个指针prev1prev2分别记录两个指定字符串最近一次出现的下标.注意对于Scanner在nextInt()/next()之后紧接着用nextLine()读取整行时需要加in.nextLine();来清换行。对于自定义的高速IO不需要特殊操作代码实现importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt();Stringstr1in.next();Stringstr2in.next();String[]strsnewString[n];for(inti0;in;i)strs[i]in.next();intprev1-1;intprev2-1;intansInteger.MAX_VALUE;for(inti0;in;i){if(strs[i].equals(str1)){if(prev2!-1)ansMath.min(ans,i-prev2);prev1i;}if(strs[i].equals(str2)){if(prev1!-1)ansMath.min(ans,i-prev1);prev2i;}}if(prev1-1||prev2-1)System.out.println(-1);elseSystem.out.println(ans);}}3. dd爱框框dd爱框框题目描述解题思路滑动窗口进窗口判断是否符合条件 同时更新结果出窗口代码实现importjava.util.*;importjava.io.*;publicclassMain{staticReadinnewRead();staticPrintWriteroutnewPrintWriter(newBufferedWriter(newOutputStreamWriter(System.out)));publicstaticvoidmain(String[]args)throwsIOException{intnin.nextInt();intxin.nextInt();int[]arrnewint[n1];for(inti1;in;i){arr[i]in.nextInt();}intl1;intr1;intlenInteger.MAX_VALUE;intansl0;intansr0;intsum0;while(rn){sumarr[r];while(sumx){if(r-l1len){lenr-l1;ansll;ansrr;}sum-arr[l];}r;}out.println(ansl ansr);out.close();}}classRead{StringTokenizerstnewStringTokenizer();BufferedReaderbfnewBufferedReader(newInputStreamReader(System.in));Stringnext()throwsIOException{while(!st.hasMoreTokens()){stnewStringTokenizer(bf.readLine());}returnst.nextToken();}StringnextLine()throwsIOException{returnbf.readLine();}intnextInt()throwsIOException{returnInteger.parseInt(next());}longnextLong()throwsIOException{returnLong.parseLong(next());}doublenextDouble()throwsIOException{returnDouble.parseDouble(next());}}4. 除2除2题目描述解题思路贪心堆利用大根堆每次取出最大的偶数砍半如果还是偶数则放入堆中代码实现importjava.util.*;importjava.io.*;publicclassMain{staticReadinnewRead();staticPrintWriteroutnewPrintWriter(newBufferedWriter(newOutputStreamWriter(System.out)));publicstaticvoidmain(String[]args)throwsIOException{intnin.nextInt();intkin.nextInt();long[]arrnewlong[n];longsum0;PriorityQueueLongheapnewPriorityQueueLong((a,b)-Long.compare(b,a));for(inti0;in;i){arr[i]in.nextLong();sumarr[i];if(arr[i]%20){heap.offer(arr[i]);}}while(k0!heap.isEmpty()){longtmpheap.poll();tmp/2;sum-tmp;if(tmp%20)heap.offer(tmp);k--;}out.println(sum);out.close();}}classRead{StringTokenizerstnewStringTokenizer();BufferedReaderbfnewBufferedReader(newInputStreamReader(System.in));Stringnext()throwsIOException{while(!st.hasMoreTokens()){stnewStringTokenizer(bf.readLine());}returnst.nextToken();}StringnextLine()throwsIOException{returnbf.readLine();}intnextInt()throwsIOException{returnInteger.parseInt(next());}longnextLong()throwsIOException{returnLong.parseLong(next());}doublenextDouble()throwsIOException{returnDouble.parseDouble(next());}}5. 腐烂的苹果NC398腐烂的苹果题目描述解题思路多源BFS最短路径与常规的最短路径不同对于多源BFS来说最后一个节点也会向外扫描多记一步最终结果应该-1代码实现importjava.util.*;publicclassSolution{/** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * * param grid int整型ArrayListArrayList * return int整型 */publicintrotApple(ArrayListArrayListInteger_grid){// write code hereintret0;intm_grid.size();intn_grid.get(0).size();int[][]gridnewint[m][n];Queueint[]queuenewLinkedList();int[]dx{0,0,1,-1};int[]dy{1,-1,0,0};for(inti0;im;i)for(intj0;jn;j)grid[i][j]_grid.get(i).get(j);for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]2){queue.offer(newint[]{i,j});}}}while(!queue.isEmpty()){ret;intszqueue.size();for(inti0;isz;i){int[]topqueue.poll();intiitop[0];intjjtop[1];for(intk0;k4;k){intxiidx[k];intyjjdy[k];if(x0xmy0yngrid[x][y]1){grid[x][y]2;queue.offer(newint[]{x,y});}}}}for(inti0;im;i){for(intj0;jn;j)if(grid[i][j]1)return-1;}returnret-1;}}6. 大数乘法NC 10大数乘法题目描述解题思路模拟无进位相加先将两个字符串从个位开始逐位相乘把每一位的乘积累加到结果数组的对应位置 第i位 × 第j位结果落在ij位再从低位到高位统一处理进位生成逆序的结果字符串最后反转字符串得到最终的乘积结果。代码实现importjava.util.*;publicclassSolution{/** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * * param s string字符串 第一个整数 * param t string字符串 第二个整数 * return string字符串 */publicStringsolve(Strings,Stringt){// write code hereif(s.equals(0)||t.equals(0))return0;StringBuilderretnewStringBuilder();char[]sss.toCharArray();char[]ttt.toCharArray();intmss.length;intntt.length;int[]arrnewint[mn-1];for(inti0;im;i){for(intj0;jn;j){intn1ss[m-1-i]-0;intn2tt[n-1-j]-0;arr[ij]n1*n2;}}intr0;intk0;while(kmn-1||r!0){if(kmn-1)rarr[k];ret.append(r%10);r/10;}returnret.reverse().toString();}}