【笔试强训】Week5：空调遥控， kotor和气球，走迷宫，主持人调度II，体操队形，二叉树的最大路径和，排序子序列，消减整数

文章目录1. 空调遥控题目描述解题思路解法一滑动窗口解法二二分查找代码实现2. kotori和气球题目描述解题思路代码实现3. 走迷宫题目描述解题思路代码实现4. 主持人调度II题目描述解题思路代码实现5. 体操队形题目描述解题思路代码实现6. 二叉树的最大路径和题目描述解题思路代码实现7. 排序子序列题目描述解题思路代码实现8. 消减整数题目描述解题思路代码实现1. 空调遥控空调遥控题目描述解题思路解法一滑动窗口时间复杂度O(n * lonn) O(n)把数组排序维护一个窗口保证max-min2p统计窗口长度返回最大值解法二二分查找时间复杂度O(n * lonn) O(n * lonn)把数组排序枚举每一个温度通过二分查找分别找到arr[i]-parr[i]p对应的下标计算这个区间内人数总和返回最大值即可代码实现importjava.util.*;importjava.io.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息publicclassMain{staticReadinnewRead();staticPrintWriteroutnewPrintWriter(newBufferedWriter(newOutputStreamWriter(System.out)));publicstaticvoidmain(String[]args)throwsIOException{intnin.nextInt();intpin.nextInt();long[]arrnewlong[n];for(inti0;in;i)arr[i]in.nextLong();Arrays.sort(arr);intleft0;intright0;intret0;while(rightn){while(leftright(arr[right]-arr[left])2*p)left;retMath.max(right-left1,ret);right;}System.out.println(ret);out.close();}}classRead{StringTokenizerstnewStringTokenizer();BufferedReaderbfnewBufferedReader(newInputStreamReader(System.in));Stringnext()throwsIOException{while(!st.hasMoreTokens()){stnewStringTokenizer(bf.readLine());}returnst.nextToken();}intnextInt()throwsIOException{returnInteger.parseInt(next());}longnextLong()throwsIOException{returnLong.parseLong(next());}}2. kotori和气球kotori和气球题目描述解题思路排列组合第一个位置n种选择其余位置n-1种选择代码实现importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt();intmin.nextInt();intansn;for(inti1;im;i){ansans*(n-1)%109;}System.out.println(ans);}}3. 走迷宫走迷宫题目描述解题思路最短路径 --》 BFS注意下标从1开始字符串要先前置一个“ ” 再填写到grid中代码实现importjava.util.*;importjava.io.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息publicclassMain{staticReadinnewRead();publicstaticvoidmain(String[]args)throwsIOException{intnin.nextInt();intmin.nextInt();intxsin.nextInt();intysin.nextInt();intxtin.nextInt();intytin.nextInt();int[]dx{0,0,1,-1};int[]dy{1,-1,0,0};if(xsxtysyt){System.out.println(0);return;}boolean[][]checknewboolean[n1][m1];char[][]gridnewchar[n1][m1];for(inti1;in;i){Stringstrin.next();str str;grid[i]str.toCharArray();}intans0;Queueint[]queuenewLinkedList();queue.add(newint[]{xs,ys});check[xs][ys]true;while(!queue.isEmpty()){ans;intsizequeue.size();for(inti0;isize;i){int[]topqueue.poll();for(intk0;k4;k){intxdx[k]top[0];intydy[k]top[1];if(x0xny0ym!check[x][y]grid[x][y].){if(xxtyyt){System.out.println(ans);return;}queue.add(newint[]{x,y});check[x][y]true;}}}}System.out.println(-1);}}classRead{StringTokenizerstnewStringTokenizer();BufferedReaderbfnewBufferedReader(newInputStreamReader(System.in));Stringnext()throwsIOException{while(!st.hasMoreTokens()){stnewStringTokenizer(bf.readLine());}returnst.nextToken();}intnextInt()throwsIOException{returnInteger.parseInt(next());}longnextLong()throwsIOException{returnLong.parseLong(next());}}4. 主持人调度II主持人调度II题目描述解题思路把所有数组按照第一个元素排序创建一个列表表示已分配的数组。放入第一个数组接着遍历数组如果可以与已分配的数组时间错开就可以继续排在后面。如果与所有已分配的数组都重合就再添加一个子列表结果就是列表的长度优化子列表中不需要存放放已分配好的数组的右端点的最大值每次遍历列表时间复杂度太高可以把列表设置成小根堆每次与堆顶元素比较即可代码实现publicintminmumNumberOfHost(intn,int[][]startEnd){// write code hereArrays.sort(startEnd,(a,b)-Integer.compare(a[0],b[0]));PriorityQueueIntegerheapnewPriorityQueue();heap.add(startEnd[0][1]);for(inti1;in;i){inttopheap.peek();if(startEnd[i][0]top){heap.poll();heap.add(startEnd[i][1]);}elseheap.add(startEnd[i][1]);}returnheap.size();}5. 体操队形体操队形题目描述解题思路DFS 枚举通过决策树来枚举所有情况剪枝不合法的情况通过vis数组记录每个数字是否被使用过以下面为例2要求排在1前面当1已经排队2还没排队所有情况都不可能成立所以1先排队的情况都要剪枝。代码实现importjava.util.*;publicclassMain{staticboolean[]vis;staticint[]arr;staticintn0;staticintret0;publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);nin.nextInt();arrnewint[n1];visnewboolean[n1];for(inti1;in;i){arr[i]in.nextInt();}dfs(1);System.out.println(ret);}staticvoiddfs(intpos){if(posn1){ret;return;}for(inti1;in;i){if(!vis[i](arr[i]i||!vis[arr[i]])){vis[i]true;dfs(pos1);vis[i]false;}}}}6. 二叉树的最大路径和二叉树的最大路径和题目描述解题思路树形dp DFS在某个子树上整合的信息经过根节点的最大路径和左子树返回以左孩子为根节点的最大单链路径和如果最大和是负数可以直接舍弃left Math.max(0,dfs(root.left))右子树返回以右孩子为根节点的最大单链路径和因为最终的统计如果要包含根节点所以左右子树的路径必须是单链再拼接上根节点才能得到以经过根节点的最大路径和。每次得到的路径和中取最大值是最终的结果.代码实现importjava.util.*;publicclassSolution{intret-1010;publicintmaxPathSum(TreeNoderoot){// write code heredfs(root);returnret;}intdfs(TreeNoderoot){if(rootnull)return0;intleftMath.max(0,dfs(root.left));intrightMath.max(0,dfs(root.right));retMath.max(ret,leftrightroot.val);returnMath.max(left,right)root.val;}}7. 排序子序列排序子序列题目描述解题思路贪心模拟定义一个指针先判断当前是上升或者下降如果是上升就让指针一直向后移动到波峰下降同理指针不再移动时统计结果。如果当前阶段是水平只移动指针不统计结果让这段水平区域与后面上升或下降的部分连到一起代码实现importjava.util.*;importjava.io.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息publicclassMain{publicstaticvoidmain(String[]args)throwsIOException{ReadinnewRead();intnin.nextInt();int[]arrnewint[n];for(inti0;in;i){arr[i]in.nextInt();}intret0;inti0;while(in){if(in-1){ret;break;}if(arr[i]arr[i1]){while(in-1arr[i]arr[i1])i;ret;}elseif(arr[i]arr[i1]){while(in-1arr[i]arr[i1])i;ret;}else{while(in-1arr[i]arr[i1])i;}i;}System.out.println(ret);}}classRead{StringTokenizerstnewStringTokenizer();BufferedReaderbfnewBufferedReader(newInputStreamReader(System.in));Stringnext()throwsIOException{while(!st.hasMoreTokens()){stnewStringTokenizer(bf.readLine());}returnst.nextToken();}intnextInt()throwsIOException{returnInteger.parseInt(next());}longnextLong()throwsIOException{returnLong.parseLong(next());}}8. 消减整数消减整数题目描述解题思路贪心每次尽可能减去之前数的两倍假设x-a得到y如果y%2a0说明y可以一直-2a得到0否则就-a代码实现importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);inttin.nextInt();while(t0){inthin.nextInt();h-1;inta1;intans1;while(h0){if(h%(2*a)0){h-2*a;a*2;}elseh-a;ans;}System.out.println(ans);t--;}}}