刷題小記：
主要偏向扎實編碼基礎的考察，但貌似近些年題目難度有所提高，僅供參考。
卡碼網136.獲取連通的相鄰節點列表（卡碼網136.獲取連通的相鄰節點列表）
題目分析：
題目描述：
存在N個轉發節點，每個轉發節點有自己唯一的標識TB且每個節點有M個端口，節點間通過端口通訊。現在將這些端口劃分為多個通訊平面，通過VLAN隔離：
- 如果兩個端口的VLAN ID相同，則說明位于同個VLAN，處于連通狀態。
- 如果兩個端口的VLAN ID不同，則說明位于不同VLAN，彼此不連通。
現在給出節點A的端口數以及每個端口的VLAN ID，以及節點A相鄰的其他節點及其端口信息，求所有與節點A連通的相鄰節點的標識符列表（按從小到大的順序輸出）。
輸入描述：
輸入的第一行：包含M + 1個用空格隔開的數，第一個數表示A有M個端口，后M個數分別表示這M個端口的VLAN ID。
輸入的第二行：包含一個整數N，表示有N個與A相鄰的節點，取值為[0, 4000)
輸入的第三行開始有N行數據，每一行：第一個數表示節點x的標識符，第二個數表示它的端口數m_x，然后有m_x個數表示每個端口所屬的VLAN ID。
其中，標識符TB的的取值范圍達到long型。
輸出描述：
第一行：與節點A連通的相鄰節點的個數。
第二行：升序排列的這些連通節點的標識符TB
解題思路：
關鍵點是處理好輸入，尤其是TB需要用long型存儲。
遍歷每個相鄰節點的端口數，只要有端口的VLAN ID與節點A的端口的VLAN ID相同（即contains），那么該節點就與節點A連通。
import java.util.*;
class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);while(in.hasNext()) {int M = in.nextInt();List<Integer> portA = new ArrayList<>();for(int i = 0; i < M; i++) {portA.add(in.nextInt());}int N = in.nextInt();long[] TB = new long[N];List<List<Integer>> ports = new ArrayList<>();for(int i = 0; i < N; i++) {List<Integer> port_i = new ArrayList<>();TB[i] = in.nextLong();int m = in.nextInt();for(int j = 0; j < m; j++) {port_i.add(in.nextInt());}ports.add(new ArrayList<>(port_i));}List<Long> resList = new ArrayList<>();for(int i = 0; i < N; i++) {List<Integer> port_i = ports.get(i);for(int port : port_i) {if(portA.contains(port)) {resList.add(TB[i]);break;}}}Collections.sort(resList);System.out.println(resList.size());for(int i = 0; i < resList.size(); i++) {if(i != 0) System.out.print(" ");System.out.print(resList.get(i));}}}
}卡碼網137.字符串處理器（卡碼網137.字符串處理器）
題目分析：
設計一個帶游標的字符處理器，實現如下功能：
- 插入：在游標處添加文本，其對應操作是insert str：insert表示插入操作命令關鍵字（區分大小寫），str表示待操作的字符串，該操作執行后將str拼接到右表當前位置，且游標移動到str的右邊。
- 刪除：在游標處刪除文本，其對應操作是delete len：delete表示刪除命令關鍵字，len是一個整數，表示刪除游標左邊字符串的長度，如果len大于游標所在處左側字符串的長度 或者 len是負數，那么操作非法，不做任何處理。
- 移動：將游標左右移動，其對應操作是move cnt：move表示移動命令關鍵字，cnt是一個整數，表示游標移動次數，如果cnt為負數表示向左移動cnt次，如果cnt為正數表示向右移動cnt次，如果為0則不移動，如果超過字符串左右邊界則認為輸入命名非法，不做任何處理。
- 復制：將游標左邊字符串復制并插入到游標的右邊，且游標位置不變（如果游標右邊有字符，復制插入到游標和原有字符中間），對應操作為copy：copy表示復制操作命令關鍵字。
輸入描述：
支持輸入多行，每行包含一個操作命令，當輸入end（區分大小寫）表示操作停止。
首次執行時字符串處理器內部字符串為空，游標位置索引為0，此時字符串處理器序列化結果為"|"。
輸出描述：
當前字符串處理器的序列化結果，游標用"|"表示。
import java.util.*;
class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);StrOperator strOperator = new StrOperator();while(in.hasNext()) {String[] op = in.nextLine().split(" ");switch(op[0]) {case "insert":strOperator.insert(op[1]);break;case "delete":strOperator.delete(Integer.parseInt(op[1]));break;case "move":strOperator.move(Integer.parseInt(op[1]));break;case "copy":strOperator.copy();break;case "end":strOperator.end();break;default:break;}}in.close();}
}
class StrOperator {int cur;int length;StringBuilder sb;StrOperator() {this.cur = 0;this.length = 0;this.sb = new StringBuilder();}void insert(String str) {sb.insert(cur, str);cur += str.length();length += str.length();}void delete(int len) {if(cur >= len && len >= 0) {sb.delete(cur - len, cur);cur -= len;length -= len;}}void move(int cnt) {if(cur + cnt < 0 || cur + cnt > length) {return;}else {cur += cnt;}}void copy() {String str = sb.substring(0, cur);sb.insert(cur, str);length += str.length();}void end() {if(length == 0) {System.out.println("|");} else {sb.insert(cur, "|");System.out.println(sb.toString());}}
}卡碼網138.消息傳輸（卡碼網138.消息傳輸）
題目分析：
題目描述：
給定m×n（1<= m, n <= 1000)的網格地圖grid中，分布著一些信號塔。
每個單元格可以有以下三種狀態：
- 值0表示空地，無法傳遞信號
- 值1表示信號塔A，收到消息后，在1ms后將信號發送給上下左右四個方向的信號塔；
- 值2表示信號塔B，2ms后完成信號發送
給定一個坐標(j, k)，輸入保證該處一定有信號塔。現求網格地圖中所有信號塔收到信號的最短時間，單位為ms，如果有信號塔無法收到信號，則返回-1。
注意：以信號塔A為例，在它收到信號后，經過1ms將信號發送至上下左右四個方向的一格處，信號塔B同理。
輸入描述：
第一行：網格的列數n
第二行：網格的行數m
第三行：給定坐標(j, k)
接下來的m行，每行n個用空格隔開的整數，表示單元格狀態。
輸出描述：
輸出返回網格地圖中所有信號塔都已收到信號的最小時間，如果無法實現，返回-1。
解題思路：
用一個大小與grid相同的time數組，初始化全部元素為-1，用于記錄信號塔接收到信號的最短時間。
本題顯然適用廣度優先搜索遍歷，當一個點接收到信號時，有4種可能性：
- 該點為空地，忽略
- 該點是信號塔，第一次接收信號，更新time并將其添入que
- 該點是信號塔，不是第一次接收信號，該次訪問時間不小于time，忽略
- 該點是信號塔，不是第一次接收信號，該次訪問時間小于time，更新time并將其添入que
最終遍歷time數組，在確認全部信號塔的接收時間不為-1的情況下，所得到的最大值就是至少需要的時間。
import java.util.*;class Main{private static int[][] dir={{1,0},{-1,0},{0,1},{0,-1}};public static void main (String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();int startx = in.nextInt(), starty = in.nextInt();int[][] time=new int[m][n];int[][] grid=new int[m][n];for(int[] t:time){Arrays.fill(t,-1);}in.nextLine();for(int i = 0; i < m; i++){String s = in.nextLine();String[] t=s.split(" ");for(int j = 0; j < n; j++){grid[i][j]=Integer.valueOf(t[j]);}}bfs(grid, time, startx, starty);int ans = 0;boolean valid = true;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] > 0) {if(time[i][j] == -1) {valid = false;break;}ans=Math.max(ans,time[i][j]);}}if(!valid) break;}if(valid) System.out.println(ans);else System.out.println(-1);}private static void bfs(int[][] grid, int[][] time, int startx, int starty) {Deque<int[]> que = new ArrayDeque<>();time[startx][starty] = 0;que.offer(new int[]{startx, starty});while (!que.isEmpty()) {int[] towerIndex = que.poll();int x = towerIndex[0], y = towerIndex[1];for (int[] d : dir) {int nextx = x + d[0];int nexty = y + d[1];if (nextx >= 0 && nextx < grid.length && nexty >= 0 && nexty < grid[0].length && grid[nextx][nexty] > 0) {int newtime = time[x][y] + grid[x][y];if (time[nextx][nexty] == -1 || newtime < time[nextx][nexty]) {time[nextx][nexty] = newtime;que.offer(new int[]{nextx, nexty});}}}}}
}
