Day 27kotori 和氣球解題思路放置第一個位置有 n 種方法第二個位置就有 n-1 種第三個位置也有 n-1 種代碼實現(xiàn)importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt(),min.nextInt();longretn;for(inti2;im;i){retret*(n-1)%109;}System.out.println(ret);}}走迷宮解題思路參考腐爛的橘子使用 bfs 擴散方向當前坐標被誰先擴散誰就決定當前坐標的最小距離在擴散前先計算擴散坐標的最小距離擴散后標記該坐標為已擴散代碼實現(xiàn)importjava.util.*;importjava.io.*;publicclassMain{privatestaticReadinnewRead();publicstaticvoidmain(String[]args)throwsIOException{intnin.nextInt(),min.nextInt();intx0in.nextInt(),y0in.nextInt();intx1in.nextInt(),y1in.nextInt();char[][]gridsnewchar[n2][m2];for(inti1;in;i){Stringlinein.next();for(intj1;jm;j){grids[i][j]line.charAt(j-1);}}if(grids[x0][y0]*||grids[x1][y1]*){System.out.println(-1);return;}int[][]dnewint[][]{{-1,0},{1,0},{0,1},{0,-1}};boolean[][]checknewboolean[n2][m2];int[][]distancenewint[n2][m2];Queueint[]queuenewLinkedList();queue.offer(newint[]{x0,y0});// 起點距離為 0distance[x0][y0]0;check[x0][y0]true;while(!queue.isEmpty()){int[]pointqueue.poll();intcurxpoint[0],curypoint[1];// 枚舉四個方向for(int[]p:d){intxcurxp[0];intycuryp[1];// 注意棋盤邊界if(x1||xn||y1||ym)continue;if(check[x][y])continue;if(grids[x][y]*)continue;// 四個方向, 在入隊列前, 就可以算出其距離// 因為, 首先這個點能被擴散到, 其次, 這個點最先被誰擴散, 誰就決定其最小距離distance[x][y]distance[curx][cury]1;if(xx1yy1){System.out.println(distance[x][y]);return;}queue.offer(newint[]{x,y});// 標記為已擴散check[x][y]true;}}// 隊列為空, 都還沒計算出終點, 說明到達不了System.out.println(-1);}}classRead{StringTokenizerstnewStringTokenizer();BufferedReaderbfnewBufferedReader(newInputStreamReader(System.in));Stringnext()throwsIOException{if(!st.hasMoreTokens()){Stringlinebf.readLine();if(linenull)returnnull;stnewStringTokenizer(line);}returnst.nextToken();}intnextInt()throwsIOException{returnInteger.parseInt(next());}}主持人調(diào)度 (二)解題思路使用優(yōu)先級隊列存儲活動結(jié)束時間當前獲取的開始時間如果早于最早活動結(jié)束時間說明活動沖突新增加一個主持人如果不沖突就復用主持人然后把最早結(jié)束活動出隊列注意題目中的例子一定要使用Integer.compare(v1[0], v2[0])來避免比較過程計算溢出排序錯誤代碼實現(xiàn)importjava.util.*;publicclassSolution{publicintminmumNumberOfHost(intn,int[][]startEnd){// 當開始時間分別接近 Integer.MAX_VALUE 和 Integer.MIN_VALUE 時減法會發(fā)生整數(shù)溢出導致排序順序錯誤。并且兩個開始時間相等時原比較器仍返回 1也違反了比較器約定。Arrays.sort(startEnd,(v1,v2)-Integer.compare(v1[0],v2[0]));PriorityQueueIntegerqueuenewPriorityQueue();intcnt1;for(inti0;in;i){if(queue.isEmpty()){queue.offer(startEnd[i][1]);}else{intpequeue.peek();intnsstartEnd[i][0];if(nspe){cnt;}else{queue.poll();}queue.add(startEnd[i][1]);}}returncnt;}}