目錄

庫存管理II

翻轉對

合并K個升序鏈表

存在重復元素II

字符串相乘

字符串解碼

在每個樹行中找最大值

數據流的中位數

被包圍的區域

為高爾夫比賽砍樹

庫存管理II

LCR 159. 庫存管理 III - 力扣（LeetCode）

解法一：先進行排序，接著返回要的個數即可

class Solution {public int[] inventoryManagement(int[] stock, int cnt) {Arrays.sort(stock);int[] ret = new int[cnt];for(int i = 0; i < cnt; i++){ret[i] = stock[i];}return ret;}
}

解法二：維護一個優先級隊列，由于是要最小值，所以建最小堆，把元素都加入堆之后，前cnt個即可

class Solution {public int[] inventoryManagement(int[] stock, int cnt) {if(cnt==0)return new int[0]; //特殊情況處理Queue<Integer> q = new PriorityQueue<>(cnt);int[] ret = new int[cnt];for(int i = 0; i < stock.length; i++){q.offer(stock[i]);}for(int i = 0; i < cnt; i++) ret[i] = q.poll();return ret;}
}

翻轉對

493. 翻轉對 - 力扣（LeetCode）

要找的是這樣一對數，其中前面的數大于后面數字的兩倍。這個問題的解決思路與尋找逆序對有相似之處，都是利用歸并排序的思想。在逆序對的計算中，我們可以在合并數組的過程中同時計算逆序對的個數；而在這個問題中，必須先計算翻轉對的個數。
?
在計算翻轉對個數時，可以采用歸并的降序和升序兩種方式。其核心思想和逆序對是一致的，需要特別注意的是，判斷條件不能簡單地按照題目要求，直接判斷一個數是否比后一個數的兩倍大，因為這樣在計算過程中可能會發生溢出。因此，我們改為比較當前數的二分之一是否比后一個數大，如果出現溢出情況，則直接終止循環，因為此時前一個數肯定不可能比溢出后的數更大。
?
降序情況：
在降序排列的過程中，當滿足當前數的二分之一大于后一個數，或者右區間端點越界時，就退出循環。如果是右區間端點越界，直接終止循環即可，因為這意味著后面不存在比當前數的二分之一更大的數了；如果沒有越界，則更新翻轉對的個數，并移動右區間的指針。
?
升序情況：
在升序排列的過程中，當滿足當前數的二分之一大于后一個數，或者左區間端點越界時，就退出循環。若左區間端點越界，直接結束循環，因為這表明在當前左區間之后不存在比當前數的二分之一更小的數（由于是升序，左區間后面的數只會更大）。若沒有越界，則更新翻轉對的個數，并移動左區間的指針。

降序排序：

class Solution {public int reversePairs(int[] nums) {int len = nums.length;int[] tmp = new int[len];return _merge(nums,tmp,0,len-1);}public int _merge(int[] nums, int[] tmp, int left, int right){if(left >= right) return 0 ;// 遞歸終止條件：區間只有一個元素或無元素int mid = left + (right-left) / 2; //計算中間值int ret = 0;// 當前區間的逆序對計數// 1. 遞歸處理左半部分和右半部分ret += _merge(nums,tmp,left,mid);ret += _merge(nums,tmp,mid+1,right);// 2. 統計重要逆序對（nums[i] > 2*nums[j]）int begin1 = left,begin2 = mid+1;while(begin1 <= mid){// 移動右指針，直到找到 nums[begin1] > 2*nums[begin2]// 使用 nums[begin1]/2.0 比較避免乘法溢出while(begin2<=right && nums[begin1] / 2.0<= nums[begin2]) {begin2++;}// 如果右指針越界，說明左半部分剩余元素都不滿足條件 直接break即可if(begin2>right) {break;}begin1++;ret += right-begin2 + 1; //更新翻轉對個數}// 3. 合并兩個已排序的子數組（降序排序）begin1 = left;begin2 = mid+1;int index = left;while(begin1<=mid && begin2<=right){tmp[index++] = nums[begin1]<=nums[begin2]?nums[begin2++]:nums[begin1++];}// 處理剩余元素while (begin1<=mid)  tmp[index++] = nums[begin1++];while (begin2<=right)  tmp[index++] = nums[begin2++];for(int i = left; i <= right; i++){nums[i] = tmp[i];}return ret;}
}

升序：

        while(begin2 <= right){// 移動左指針，直到找到 nums[begin1] > 2*nums[begin2]// 使用 nums[begin1]/2.0 比較避免乘法溢出while(begin1<=mid && nums[begin1] / 2.0<= nums[begin2]) {begin1++;}// 如果左指針越界， 直接break即可if(begin1>mid) {break;}begin2++;ret += mid-begin1 + 1; //更新翻轉對個數}// 3. 合并兩個已排序的子數組（降序排序）begin1 = left;begin2 = mid+1;int index = left;while(begin1<=mid && begin2<=right){tmp[index++] = nums[begin1]<=nums[begin2]?nums[begin1++]:nums[begin2++];}

合并K個升序鏈表

23. 合并 K 個升序鏈表 - 力扣（LeetCode）

解法一：借助數據結構堆來實現。具體而言，使用最小堆，基于優先級隊列來構建這個堆結構。在此創建優先級隊列時要自定義比較器，通過它能夠依據特定規則對堆中的元素進行排序。
為了簡化對邊界情況的處理，引入一個虛擬頭結點。這樣一來，在后續的操作中，就無需針對特殊情況編寫額外的邏輯。同時，創建一個尾指針方便在鏈表尾部插入新節點。
算法的執行流程如下：首先，遍歷給定的每一個鏈表。在遍歷每個鏈表時，針對鏈表中的每一個節點，將其加入到優先級隊列中。需要特別注意的是，由于鏈表可能存在環，因此在遍歷過程中，必須斷開每個節點的 ?next??指針，以避免出現無限循環的問題。
當所有節點都加入到優先級隊列后，開始從隊列中取出元素。每次取出堆頂元素，將其連接到尾指針所指向節點的后面，然后更新尾指針，使其指向新添加的節點。重復這一過程，直到優先級隊列為空。

最終，返回虛擬頭結點的下一個節點，該節點即為經過處理后的鏈表的頭節點。

class Solution {public ListNode mergeKLists(ListNode[] lists) {// 1. 創建最小堆優先隊列，按節點的val值升序排序Queue<ListNode> queue = new PriorityQueue<>((o1,o2) -> o1.val-o2.val);// 2. 創建虛擬頭節點和尾指針，用于構建結果鏈表ListNode ret = new ListNode();ListNode end = ret;// 3. 遍歷所有鏈表，將節點加入優先隊列for(ListNode head : lists){  // head是每個鏈表的頭節點//拿到每一個鏈表while(head != null){ListNode next = head.next;// 斷開當前節點的next指針，避免鏈表成環head.next = null;queue.offer(head); // 將當前節點加入優先隊列head = next; //更新節點}}// 4. 從優先隊列中取出最小節點，構建結果鏈表while(!queue.isEmpty()){// 取出堆頂元素，也就是當前最小節點end.next = queue.poll(); // 將節點鏈接到結果鏈表的尾部end = end.next;}// 5. 返回結果鏈表的頭節點（跳過虛擬頭節點）return ret.next;}
}

2.也可以先將每個鏈表的頭節點加入優先級隊列（不需要提前遍歷整個鏈表，需要過濾空鏈表），接著遍歷優先級隊列，依次取出節點最小值，加入到結果鏈表中，如果此時節點還有后繼節點咋加入到優先級隊列中，直到優先級隊列為空。

class Solution {public ListNode mergeKLists(ListNode[] lists) {// 1. 創建最小堆優先隊列，按節點的val值升序排序Queue<ListNode> queue = new PriorityQueue<>((o1,o2) -> o1.val-o2.val);// 2. 創建虛擬頭節點和尾指針，用于構建結果鏈表ListNode ret = new ListNode();ListNode end = ret;// 3. 遍歷所有鏈表，將每個鏈表頭節點加入優先隊列// 這里只需要加入每個鏈表的頭節點，不需要遍歷整個鏈表for(ListNode head : lists){ if(head!=null)queue.offer(head); // 將非空鏈表的頭節點加入優先隊列}// 4. 從優先隊列中取出最小節點，構建結果鏈表while(!queue.isEmpty()){ListNode t = queue.poll();end.next = t;end = t;// 如果取出的節點還有后續節點，將后續節點加入優先隊列if(t.next!=null)queue.offer(t.next);}// 5. 返回結果鏈表的頭節點（跳過虛擬頭節點）return ret.next;}
}

解法二：歸并思想

運用歸并思想處理鏈表。其核心思路是將鏈表持續二分，把復雜問題拆解為規模更小的子問題。
?在拆分過程中，當子問題里僅包含一個鏈表時，直接返回該鏈表；若子問題中沒有鏈表，就返回?null?。當子問題包含兩個鏈表時，執行鏈表合并操作，將這兩個鏈表有序整合。隨后，把合并后的鏈表作為結果，用于上一層的歸并操作。持續這一過程，直至完成對整個鏈表的歸并處理。

class Solution {public ListNode mergeKLists(ListNode[] lists) {// 調用分治合并方法，初始范圍為整個數組return merge(lists,0,lists.length-1);}public ListNode merge(ListNode[] lists, int left, int right){if(left > right) return null;// 遞歸終止條件2：范圍內只有一個鏈表，直接返回if(left == right) return lists[left];int mid = left + (right - left) / 2;// 遞歸合并左半部分鏈表ListNode node1 = merge(lists, left, mid);// 遞歸合并右半部分鏈表ListNode node2 = merge(lists, mid+1, right);//合并兩個已排序的鏈表ListNode ret = new ListNode(); // 創建虛擬頭節點（簡化邊界條件處理）ListNode tmp = ret;while(node1!=null && node2 !=null){if(node1.val <node2.val){tmp.next = node1;tmp = tmp.next;node1 = node1.next;}else {tmp.next = node2;tmp = tmp.next;node2 = node2.next;          }}tmp.next = node1==null ? node2 : node1;return ret.next;}
}

存在重復元素II

219. 存在重復元素 II - 力扣（LeetCode）

借助哈希表解決這一問題，哈希表的每個元素由兩部分構成：一是數組中的元素本身，二是該元素在數組中的下標。
遍歷整個數組時，每次先檢查哈希表中是否已經存在當前元素。若存在，取出其下標，并與當前元素下標進行運算，判斷是否滿足設定條件。一旦滿足，立即返回?true?。倘若不滿足，或者哈希表中不存在該元素，就將當前元素及其下標更新到哈希表中。這是由于題目要求?i - j?的絕對值小于等于?k?，即需要找到距離當前元素最近的重復元素，因此用當前元素的下標覆蓋哈希表中原有的下標。當遍歷完整個數組后，若仍未找到符合條件的元素，說明不存在這樣的一對元素，直接返回?false?。

class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {Map<Integer,Integer> hash = new HashMap<>();int len = nums.length;for(int i = 0; i < len; i++){//如果元素存在則取出下標和當前下標進行運算 判斷是否<=keyif(hash.containsKey(nums[i])){if(Math.abs(hash.get(nums[i])-i) <=k) {return true;} }//不存在或者條件不成立則更新hash表中該元素的下標hash.put(nums[i],i);}return false;}
}

字符串相乘

43. 字符串相乘 - 力扣（LeetCode）

該題只能直接模擬豎式乘法，主要步驟就是先無進位相乘，然后處理進位，最后處理前導零（當元結果為全0時，只需返回一個零）；

豎式乘法運算過程中，首先需要一個數組來存放無進位相乘的結果。由于兩個長度分別為 m 和 n 的數字相乘，結果的最大長度為 m + n - 1。因此，創建一個大小為 m + n - 1 的數組。這是因為當兩個數字最高位相乘時，產生的結果處于結果數字的最高位開始的位置，而后續的計算會涉及到當前數字除最高位以外的低位部分。

字符串預處理：為了方便從最低位開始計算，將輸入的兩個字符串進行翻轉，然后將它們轉換為字符數組。這樣，在后續計算中，可以像實際豎式乘法一樣，從最低位開始逐位相乘。

將兩個字符串先翻轉，方便先從最低為進行計算，接著轉換成char數組

雙重循環模擬豎式乘法

1. 外層循環遍歷第一個數的每一位
2. 內層循環遍歷第二個數的每一位
3. 將每一位相乘的結果累加到數組的對應位置（i+j）

• 例如：計算123×456時，3×6的結果放在add[0]（）這就是要翻轉的原因，翻轉之后可以直接從前向后一次遍歷從低位到高位），2×5的結果放在add[1]等

處理進位

1. 循環處理直到所有數字處理完畢且沒有進位
2. 每次取出當前位的值加上進位值
3. 取個位數加入結果字符串
4. 計算新的進位值

• 例如：某位計算得到15，則保留5，進位1

處理前導零

1. 由于結果是逆序的，實際處理的是最高位的零
2. 刪除多余的前導零，但要保留最后一個零（即結果本身就是0的情況）

• 例如：處理"000"變為"0"

由于之前對字符串進行了翻轉，最后需要將結果數組逆序，轉換為字符串形式并返回。

class Solution {public String multiply(String num1, String num2) {// 兩個數相乘的最大位數是m+n-1（不考慮進位時）int m = num1.length(), n=num2.length();int[] add = new int[m+n-1];  // 用于創建int數組存放無進位相乘的結果// 翻轉字符串，方便從低位開始計算char[] tmp1 = new StringBuilder(num1).reverse().toString().toCharArray();char[] tmp2 = new StringBuilder(num2).reverse().toString().toCharArray();// 進行無進位相乘// 模擬豎式乘法，將每一位相乘的結果存入對應的位置for(int i=0; i<m; i++){for(int j = 0; j < n; j++){add[i+j] += (tmp1[i] - '0') * (tmp2[j] - '0');}}int cut = 0, t = 0; // cut是數組索引，t是進位值// 當還有未處理的數字或還有進位時繼續循環StringBuilder ret = new StringBuilder();while(cut < add.length || t!=0){// 如果還有未處理的數字，加到進位中if(cut < add.length){t+=add[cut++];}// 取個位數加入結果ret.append((char)(t%10 + '0'));t /= 10; // 計算新的進位}// 處理前導零// 當前結果處于逆序狀態，所以實際處理的是最高位的零// 但要保留最后一個零（即結果本身就是0的情況）while(ret.length() > 1 && ret.charAt(ret.length()-1) == '0'){ret.deleteCharAt(ret.length()-1);}return ret.reverse().toString();}
}

字符串解碼

394. 字符串解碼 - 力扣（LeetCode）

本題采用雙棧策略，通過一個數字棧存儲重復次數，一個字符棧處理目標字符串。遍歷給定字符串前，需先向字符棧中壓入一個空字符串。這是因為后續處理過程中，完成處理的字符串會拼接到棧頂元素上，若棧頂無元素，程序就會報錯 。在遍歷字符串的過程中，依據當前字符的類型，可分為以下四種情況進行處理：

1. 當前字符為 “[”：向字符棧中壓入一個空字符串，用于拼接該括號內的所有字符。
2. 當前字符為 “]”：表明括號內的字符已全部就緒，可以進行處理。此時，從數字棧和字符棧分別彈出棧頂元素。數字棧的棧頂元素決定了字符棧棧頂字符串需拼接的次數。完成當前字符串的拼接后，將結果拼接到字符棧的新棧頂元素上。
3. 當前字符為數字：由于數字可能包含多位，需通過循環讀取并將其壓入數字棧。
4. 當前字符為普通字符：直接將其拼接到字符棧的棧頂元素上。若該字符位于括號內，前面步驟已在“[”位置壓入空字符串，字符會拼接到該空字符串上；若不在括號內，字符則直接拼接到棧頂已有元素上。

當字符串遍歷結束，字符棧的棧頂元素即為完成編碼后的字符串。

class Solution {public String decodeString(String s) {// 使用雙棧分別存儲數字和字符串Deque<Integer> nums = new ArrayDeque<>(); // 數字棧，保存重復次數Deque<String> sQue=  new ArrayDeque<>();  // 字符串棧，保存待處理的字符串sQue.push(""); // 初始化棧，壓入空字符串避免空指針for(int i = 0; i < s.length(); i++){char ch = s.charAt(i);if(ch == '['){sQue.push(""); // 遇到左括號：壓入新字符串，準備處理括號內的內容}else if(ch == ']'){// 遇到右括號：1. 彈出棧頂字符串（括號內的內容）String s1 = sQue.pop();// 2. 彈出重復次數Integer t = nums.pop();// 3. 構建重復后的字符串StringBuilder tmp = new StringBuilder();for(int j = 0; j < t; j++){tmp.append(s1);}// 4. 將結果拼接到上層字符串sQue.push(sQue.pop() + tmp.toString());} else if(ch >= '0' && ch <= '9'){// 處理數字（可能多位）：int num = 0;// 循環讀取連續的數字字符while(s.charAt(i) >= '0' && s.charAt(i) <='9'){num = num*10 + (s.charAt(i++) - '0');}i--;  // 回退一步，因為外層循環會i++nums.push(num);} else {// 處理字母：直接拼接到當前棧頂字符串sQue.push(sQue.pop() + ch);}}   return sQue.pop();}
}

在每個樹行中找最大值

515. 在每個樹行中找最大值 - 力扣（LeetCode）

本題是對一棵二叉樹進行處理，通過層序遍歷的方式來解決。層序遍歷，就是按照從上到下、從左到右的順序，一層一層地訪問二叉樹的節點。在遍歷的過程中，需要找出每一層節點值的最大值，并將這些最大值依次加入到返回鏈表中。
?
特別要注意的是，程序必須能夠處理空樹的情況。當輸入的二叉樹為空時，由于樹中不存在任何節點，所以返回的鏈表為空。
?
具體實施過程中，借助隊列這一數據結構實現層序遍歷。首先，將二叉樹的根節點入隊。在隊列不為空的情況下，獲取當前隊列的長度，這個長度代表了當前層的節點數量。然后，遍歷當前層的所有節點，在遍歷過程中，更新當前層的最大值，并將節點的左右子節點（如果存在）加入隊列。遍歷完當前層后，將求得的最大值加入到返回鏈表中。如此反復，直至隊列為空，完成整棵二叉樹的層序遍歷，得到符合要求的返回鏈表。

class Solution {public List<Integer> largestValues(TreeNode root) {List<Integer> ret = new LinkedList<>(); if(root == null) return ret; // 處理空樹情況// 使用隊列實現BFS層序遍歷Queue<TreeNode> q = new LinkedList<>();q.offer(root); // 根節點入隊while(!q.isEmpty()){// 當前層的節點數量int size = q.size();// 初始化當前層最大值（設置為最小整數值）int max = Integer.MIN_VALUE;// 遍歷當前層所有節點for(int i = 0; i < size; i++){TreeNode node = q.poll(); // 取出隊首節點max = Math.max(max, node.val); // 更新最大值//將不為空的子節點加入隊列，以便下一次遍歷if(node.left != null) q.offer(node.left);if(node.right != null) q.offer(node.right);} // 記錄當前層最大值到結果列表ret.add(max);}return ret;}
}

數據流的中位數

295. 數據流的中位數 - 力扣（LeetCode）

本題通過構建最大堆和最小堆，解決該題。算法使用兩個堆實現：一個最大堆?left?，用于維護數據集中較小的一半元素；一個最小堆?right?，用于維護數據集中較大的一半元素。
?
插入新元素時，需保證兩個堆的長度差不超過1。?left?堆的堆頂元素是較小一半元素中的最大值，?right?堆的堆頂元素是較大一半元素中的最小值。當兩個堆的長度相等時，中位數是兩個堆頂元素的平均值；當兩個堆的長度不等時，中位數是?left?堆的堆頂元素，因為?left?堆的長度始終大于或等于?right?堆。
?
插入操作的具體邏輯
?
1.?當?left?和?right?堆的長度相等時：

• 如果插入的元素小于或等于?left?堆的堆頂元素，或?left?堆為空，直接將元素插入?left?堆。因為?left?堆負責存儲較小的元素。
• 如果插入的元素大于?left?堆的堆頂元素，將其插入?right?堆。為了維持?left?堆的長度大于或等于?right?堆的要求，需要將?right?堆的堆頂元素取出，插入到?left?堆中。這樣操作后，?left?堆依然存儲小于或等于中位數的元素，?right?堆存儲大于中位數的元素。

2.?當?left?和?right?堆的長度不相等時：

• 如果插入的元素小于?left?堆的堆頂元素，將其插入?left?堆。為了滿足既定規則，需將?left?堆的堆頂元素取出，插入到?right?堆中。
• 如果插入的元素大于或等于?left?堆的堆頂元素，直接將其插入?right?堆。

class MedianFinder {//核心思想：用最大堆存較小一半數，最小堆存較大一半數Queue<Integer> left; // 最大堆（堆頂是左側最大值）Queue<Integer> right;// 最小堆（堆頂是右側最小值）int m = 0,n = 0;public MedianFinder() {left = new PriorityQueue<>((a,b)-> b-a); //最大堆right = new PriorityQueue<>(); //最小堆}public void addNum(int num) {// 情況1：左右堆大小相等（平衡狀態）if(left.size() == right.size()){/* 插入策略：如果左堆為空 或 數字<=左堆最大值 則直接插入到左堆否則先插入右堆，為了保持平衡再將右堆最小值移到左堆保證插入后左堆比右堆多1個元素 */if(left.size()==0 || num <= left.peek()){left.offer(num);} else {right.offer(num);left.offer(right.poll()); // 平衡操作}} else {// 情況2：左堆比右堆多1個元素（非平衡狀態）/* 插入策略：如果數字<=左堆最大值，為了保持平衡插入左堆后，將左堆最大值移到右堆否則直接插入右堆，保證插入后兩堆大小相等 */if( num <= left.peek()){left.offer(num);right.offer(left.poll()); // 平衡操作} else {right.offer(num);}}}public double findMedian() {// 情況1：兩堆大小相等則取兩個堆頂平均值 左堆多1個元素 ，左堆頂即中位數if(left.size() == right.size()){return (left.peek() + right.peek()) / 2.0;} else {return left.peek();}}
}

被包圍的區域

該問題旨在將所有被 `X` 完全包圍的 `O` 轉換為 `X`，而與邊界相連的 `O` 則保持不變。一種可行的方法是對每個 `O` 執行廣度優先搜索（BFS）。然而，在BFS遍歷過程中，如果將遇到的 `O` 直接修改為 `X`，當此次BFS遍歷到邊界時，意味著此前修改的所有元素并不符合轉換要求，此時就需要將它們改回。因此，需要借助一個數組來記錄每次BFS修改過的元素，所以使用正難則反思想

解法一：
與其逐個尋找被包圍的 `O`，不如先對所有與邊界相連的 `O` 及其連通區域進行標記。如此一來，剩余未被標記的 `O` 即為需要轉換的對象，直接將其改為 `X` 即可。

實現步驟

• 邊界'O'入隊與標記：對棋盤的四條邊進行掃描，將邊界上出現的 `O` 加入隊列，并同時進行標記。
• BFS標記相連'O*：以這些邊界上的 `O` 作為起點，執行BFS，以此標記所有與之相連的內部 `O`。
• 轉換未標記'O'：最后對內部區域進行遍歷，將其中未被標記的 `O` 替換為 `X`。

注意事項
1. 全面的邊界檢查：必須對棋盤的四條邊進行完整檢查，確保所有邊界上的 `O` 都被正確處理。
2. BFS的越界控制：在執行BFS時，要嚴格確保搜索過程不會越界訪問棋盤之外的區域。
3. 僅處理內部區域：在最終處理階段，只需針對內部區域進行操作，邊界部分應保持原狀，不做任何改動。?

class Solution {// 定義四個方向的位移數組：右、左、上、下int[] dx = new int[]{0, 0, -1, 1};int[] dy = new int[]{1, -1, 0, 0};public void solve(char[][] board) {// 獲取棋盤的行數和列數int m = board.length, n = board[0].length;// 創建訪問標記數組，記錄哪些'O'是與邊界相連的boolean[][] vis = new boolean[m][n];// 使用隊列進行BFS遍歷Queue<int[]> q = new LinkedList<>();// 處理第一列和最后一列for(int i = 0; i < m; i++) {// 第一列的'O'if(board[i][0] == 'O') {q.offer(new int[]{i, 0});  // 加入隊列vis[i][0] = true;          // 標記為已訪問}// 最后一列的'O'if(board[i][n-1] == 'O') {q.offer(new int[]{i, n-1}); // 加入隊列vis[i][n-1] = true;         // 標記為已訪問}}// 處理第一行和最后一行for(int i = 0; i < n; i++) {// 第一行的'O'if(board[0][i] == 'O') {q.offer(new int[]{0, i});   // 加入隊列vis[0][i] = true;           // 標記為已訪問}// 最后一行的'O'if(board[m-1][i] == 'O') {q.offer(new int[]{m-1, i}); // 加入隊列vis[m-1][i] = true;         // 標記為已訪問}}// 開始BFS遍歷所有與邊界相連的'O'while(!q.isEmpty()) {int[] t = q.poll();  // 取出隊列中的坐標int a = t[0], b = t[1];// 檢查四個方向for(int i = 0; i < 4; i++) {int x = a + dx[i];  // 計算新坐標xint y = b + dy[i];  // 計算新坐標y// 檢查新坐標是否在棋盤內、未被訪問過且是'O'if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && board[x][y] == 'O') {q.offer(new int[]{x, y});  // 加入隊列vis[x][y] = true;          // 標記為已訪問}}}// 遍歷棋盤內部區域（不包括邊界）for(int i = 1; i < m-1; i++) {for(int j = 1; j < n-1; j++) {// 如果該位置的'O'未被標記（即不與邊界相連）if(!vis[i][j] && board[i][j] == 'O') {board[i][j] = 'X';  // 將其改為'X'}}}}
}

解法二：

采用逆向思維，不是直接尋找被包圍的'O'，而是先將所有與邊界相連的'O'轉換成'.處理完之后，遍歷整個數組，如果是'O'則直接改成'X'，并還原'.'轉換成‘O'；
執行步驟：

邊界處理階段：掃描四條邊界，對每個邊界'O'執行BFS
標記階段：BFS會擴散標記所有相連的'O'為'.'
轉換階段：遍歷整個棋盤，將未被標記的'O'轉為'X'，被標記的'.'恢復為'O'

class Solution {// 定義四個方向的位移數組：右、左、上、下int[] dx = new int[]{0, 0, -1, 1};int[] dy = new int[]{1, -1, 0, 0};int m, n;  // 棋盤的行數和列數，定義為成員變量避免重復計算public void solve(char[][] board) {// 邊界檢查：如果棋盤為空或大小為0，直接返回if (board == null || board.length == 0) return;// 初始化棋盤的行數和列數m = board.length; n = board[0].length;for (int i = 0; i < m; i++) {// 檢查第一列的每個元素是否為'O'if (board[i][0] == 'O') {bfs(board, i, 0);  // 執行BFS標記所有相連的'O'}// 檢查最后一列的每個元素是否為'O'if (board[i][n-1] == 'O') {bfs(board, i, n-1);  // 執行BFS標記所有相連的'O'}}for (int i = 0; i < n; i++) {// 檢查第一行的每個元素是否為'O'if (board[0][i] == 'O') {bfs(board, 0, i);  // 執行BFS標記所有相連的'O'}// 檢查最后一行的每個元素是否為'O'if (board[m-1][i] == 'O') {bfs(board, m-1, i);  // 執行BFS標記所有相連的'O'}}// 3. 遍歷整個棋盤，進行最終轉換for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {// 將未被標記的'O'（不與邊界相連的）轉換為'X'if (board[i][j] == 'O') {board[i][j] = 'X'; }// 將被標記為'.'的'O'（與邊界相連的）恢復為'O'if (board[i][j] == '.') {board[i][j] = 'O';}}}}void bfs(char[][] board, int i, int j) {// 使用隊列實現BFSQueue<int[]> q = new LinkedList<>();// 將起始點加入隊列q.offer(new int[]{i, j});// 將起始點標記為'.'（表示與邊界相連的'O'）board[i][j] = '.';while (!q.isEmpty()) {// 取出隊列中的當前坐標int[] t = q.poll();int a = t[0], b = t[1];// 檢查四個方向for (int k = 0; k < 4; k++) {// 計算新坐標int x = a + dx[k];int y = b + dy[k];// 檢查新坐標是否有效且為未被標記的'O'if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {// 將新坐標加入隊列q.offer(new int[]{x, y});// 標記為'.'表示與邊界相連board[x][y] = '.';}}}}
}

為高爾夫比賽砍樹

675. 為高爾夫比賽砍樹 - 力扣（LeetCode）

該題和迷宮問題比較像，只不過迷宮問題是尋找一個出口（最短路徑），而這里需要尋找多條最短路徑，所以就可以按照迷宮問題那時候的解法BFS解決該題：
1. 收集樹木
第一步，需要對整個森林網格進行全面的遍歷，找出所有代表樹木的單元格（也就是值大于 1 的位置）。這一步就像是在地圖上標記出所有的目標點，為后續的行動做好準備。可以使用一個列表來存儲這些樹木的信息，列表中的每個元素是一個包含樹木位置（行和列坐標）。
2. 排序樹木
在收集到所有樹木的信息后，對這些樹木進行排序。排序的依據是樹木的高度，要確保樹木按照高度從小到大的順序排列。這樣做的目的是為了保證后續的砍伐行動是按照正確的順序進行的（題目要求必須要低到高砍樹）。

在確定了樹木的砍伐順序后，需要計算從當前位置到下一棵樹的最短路徑步數。這里和迷宮問題采用思想廣度優先搜索（BFS）算法來實現。BFS 是一種非常適合用于尋找最短路徑的算法，因為它會逐層擴展搜索范圍，確保找到的路徑是最短的。

• 使用隊列實現：BFS 算法使用隊列來實現。將起始點加入隊列，并開始進行搜索。每次從隊列中取出一個節點，然后將其相鄰的四個方向的節點加入隊列，繼續進行搜索。
• 維護訪問標記數組：為了避免重復訪問同一個單元格，需要維護一個訪問標記數組。這個數組的大小與森林網格相同，初始時所有元素都標記為未訪問。每當我們訪問一個單元格時，就將對應的標記數組元素標記為已訪問。
• 分層處理計算步數：在 BFS 搜索過程中，采用分層處理的方式來計算步數。每一層的節點代表著從起始點出發經過相同步數能夠到達的節點。當找到目標樹時，當前的層數就是從起始點到目標樹的最短路徑步數。
• 遇到目標點立即返回：一旦在搜索過程中遇到目標樹，就立即返回當前的步數，因為 BFS 保證了找到的路徑是最短的，如果遍歷完隊列還沒有找到則返回-1。

4. 累加步數
在計算出從當前位置到下一棵樹的最短路徑步數后，將這個步數累加到總步數中。然后，將當前位置更新為下一棵樹的位置，繼續進行下一輪的搜索，直到所有的樹木都被砍伐完。

class Solution {// 定義四個方向的位移數組：右、左、下、上int[] dx = new int[]{0, 0, 1, -1};int[] dy = new int[]{1, -1, 0, 0};int m, n; // 森林的行數和列數public int cutOffTree(List<List<Integer>> forest) {m = forest.size(); n = forest.get(0).size();// 1. 收集所有需要砍的樹（值大于1的位置）List<int[]> trees = new ArrayList<>();for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(forest.get(i).get(j) > 1) {trees.add(new int[]{i, j}); // 保存樹的坐標}}}// 2. 按照樹的高度從小到大排序（題目要求按高度順序砍樹）Collections.sort(trees, (a, b) -> forest.get(a[0]).get(a[1]) - forest.get(b[0]).get(b[1]));// 3. 按順序砍樹，計算總步數int ret = 0;int dx = 0, dy = 0; // 起始位置（從(0,0)開始）for(int[] tree : trees) {int x = tree[0];int y = tree[1];// 計算從當前位置到目標樹的最短步數int steps = bfs(forest, dx, dy, x, y);if(steps == -1) { // 如果無法到達該樹return -1;}ret += steps; // 累加步數dx = x; dy = y;    // 更新當前位置為剛砍掉的樹的位置}    return ret;}int bfs(List<List<Integer>> forest, int bx, int by, int x, int y) {// 如果起點就是目標點，步數為0if(bx == x && by == y) return 0;Queue<int[]> queue = new LinkedList<>(); // BFS隊列boolean[][] vis = new boolean[m][n]; // 訪問標記數組queue.offer(new int[]{bx, by}); // 起點入隊vis[bx][by] = true;         // 標記起點已訪問int steps = 0; // 記錄步數while(!queue.isEmpty()) {int size = queue.size(); // 當前層的節點數steps++; // 每處理一層，步數加1while(size-- != 0) { // 處理當前層的所有節點int[] t = queue.poll();int a = t[0], b = t[1];// 檢查四個方向for(int i = 0; i < 4; i++) {int newX = a + dx[i];int newY = b + dy[i];// 檢查新坐標是否有效  // 未訪問過if(newX>=0 && newX<m && newY>=0 && newY<n && forest.get(newX).get(newY)!= 0  && !vis[newX][newY]) { // 如果到達目標點，返回當前步數if(x == newX && y == newY) {return steps;}// 否則加入隊列繼續搜索queue.offer(new int[]{newX, newY});vis[newX][newY] = true;}}}}// 隊列為空仍未找到目標點，返回-1return -1;}
}