Day 37旋转字符串字符串旋转的关键性质是如果B是A的旋转结果那么B一定是A A的子串。例如A youzan A A youzanyouzan B zanyou因此可以这样写publicclassSolution{publicbooleansolve(StringA,StringB){if(Anull||Bnull){returnfalse;}if(A.length()!B.length()){returnfalse;}return(AA).contains(B);}}如果题目严格要求时间复杂度为O(n)可以使用 KMP避免依赖String.contains()的具体实现publicclassSolution{publicbooleansolve(StringA,StringB){if(Anull||Bnull||A.length()!B.length()){returnfalse;}StringtextAA;returnkmpContains(text,B);}privatebooleankmpContains(Stringtext,Stringpattern){int[]nextbuildNext(pattern);inti0;intj0;while(itext.length()){if(text.charAt(i)pattern.charAt(j)){i;j;if(jpattern.length()){returntrue;}}elseif(j0){jnext[j-1];}else{i;}}returnfalse;}privateint[]buildNext(Stringpattern){int[]nextnewint[pattern.length()];intj0;for(inti1;ipattern.length();i){while(j0pattern.charAt(i)!pattern.charAt(j)){jnext[j-1];}if(pattern.charAt(i)pattern.charAt(j)){j;}next[i]j;}returnnext;}}这个版本的复杂度是时间复杂度O(n) 空间复杂度O(n)其中n是字符串长度。合并k个已排序的链表解题思路使用小跟堆每次取堆顶元素作为下一个链表连接的节点代码实现importjava.util.*;/* * public class ListNode { * int val; * ListNode next null; * public ListNode(int val) { * this.val val; * } * } */publicclassSolution{publicListNodemergeKLists(ArrayListListNodelists){PriorityQueueListNodequeuenewPriorityQueue((v1,v2)-{returnInteger.compare(v1.val,v2.val);});for(ListNoden:lists){if(n!null)queue.add(n);}ListNodedummynewListNode(0);ListNodecurdummy;while(!queue.isEmpty()){ListNodenodequeue.poll();if(node.next!null)queue.add(node.next);cur.nextnode;curcur.next;}returndummy.next;}}滑雪解题思路记忆化搜索为什么不用 visit 去重因为每次严格走更低的区域不会走重复代码实现// 矩阵中的数字表示滑雪场各个区域的高度// 可以从任意区域出发滑向相邻且高度严格更低的区域// 求最长滑道的长度importjava.io.*;importjava.util.*;publicclassMain{// 输出对象privatestaticfinalPrintWriteroutnewPrintWriter(newBufferedWriter(newOutputStreamWriter(System.out)));// 输入对象privatestaticfinalReadinnewRead();// 四个移动方向上、下、左、右privatestaticfinalint[][]dirs{{-1,0},{1,0},{0,-1},{0,1}};// 高度矩阵privatestaticint[][]grid;// 记忆化数组// dp[i][j] 表示从位置 (i, j) 出发的最长滑道长度privatestaticint[][]dp;privatestaticintn;privatestaticintm;// 全局最大滑道长度privatestaticintret0;publicstaticvoidmain(String[]args)throwsIOException{nin.nextInt();min.nextInt();gridnewint[n][m];dpnewint[n][m];// 读取矩阵for(inti0;in;i){for(intj0;jm;j){grid[i][j]in.nextInt();}}// 尝试从每个位置出发for(inti0;in;i){for(intj0;jm;j){retMath.max(ret,dfs(i,j));}}out.println(ret);out.flush();}/** * 计算从 (i, j) 出发的最长滑道长度 */privatestaticintdfs(inti,intj){// 如果已经计算过直接返回结果if(dp[i][j]!0){returndp[i][j];}// 至少包含当前位置因此初始长度为 1intlongest1;// 尝试向四个方向移动for(int[]dir:dirs){intxidir[0];intyjdir[1];// 目标位置必须在矩阵内// 并且目标位置的高度严格低于当前位置if(check(x,y)grid[x][y]grid[i][j]){longestMath.max(longest,1dfs(x,y));}}// 保存当前位置的计算结果dp[i][j]longest;returnlongest;}/** * 判断坐标是否在矩阵范围内 */privatestaticbooleancheck(inti,intj){returni0inj0jm;}}/** * 快速输入类 */classRead{privatefinalStringTokenizerstnewStringTokenizer();privatefinalBufferedReaderbfnewBufferedReader(newInputStreamReader(System.in));privateStringTokenizertokenizerst;Stringnext()throwsIOException{while(!tokenizer.hasMoreTokens()){Stringlinebf.readLine();if(linenull){returnnull;}tokenizernewStringTokenizer(line);}returntokenizer.nextToken();}intnextInt()throwsIOException{returnInteger.parseInt(next());}}
