括號匹配

public static boolean isValid(String s) {// 創建一個棧用于存儲左括號Stack<Character> stack = new Stack<>();// 遍歷字符串中的每個字符for (char c : s.toCharArray()) {if (c == '(' || c == '[' || c == '{') {// 如果是左括號，將其壓入棧中stack.push(c);} else {if (stack.isEmpty()) {// 如果棧為空，說明沒有匹配的左括號，返回 falsereturn false;}// 彈出棧頂元素char top = stack.pop();if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {// 如果右括號與棧頂的左括號不匹配，返回 falsereturn false;}}}// 如果棧為空，說明所有括號都匹配，返回 truereturn stack.isEmpty();}

子數組最大和

/*** 計算子數組的最大和* @param nums 整數數組* @return 子數組的最大和*/public static int maxSubArray(int[] nums) {// 當前子數組的最大和int currentMax = nums[0];// 全局子數組的最大和int globalMax = nums[0];// 從數組的第二個元素開始遍歷for (int i = 1; i < nums.length; i++) {// 更新當前子數組的最大和currentMax = Math.max(nums[i], currentMax + nums[i]);// 更新全局子數組的最大和globalMax = Math.max(globalMax, currentMax);}return globalMax;}

循環升序數組最小值

public class FindMinInRotatedSortedArray {// 此方法用于在循環升序數組中查找最小值public static int findMin(int[] nums) {// 初始化左指針，指向數組起始位置int left = 0;// 初始化右指針，指向數組末尾位置int right = nums.length - 1;// 當左指針小于右指針時，繼續循環查找while (left < right) {// 計算中間位置，使用 left + (right - left) / 2 避免整數溢出int mid = left + (right - left) / 2;// 如果中間元素大于右邊界元素，說明最小值在 mid 右側if (nums[mid] > nums[right]) {// 更新左指針到 mid + 1 位置left = mid + 1;} else {// 否則，最小值在 mid 或 mid 左側，更新右指針到 mid 位置right = mid;}}// 當 left 和 right 相遇時，該位置的元素即為最小值return nums[left];}public static void main(String[] args) {// 定義一個示例循環升序數組int[] nums = {3, 4, 5, 1, 2};// 調用 findMin 方法查找最小值并打印結果System.out.println("數組中的最小值是: " + findMin(nums));}
}    

字符串解碼

class Solution {// 該方法用于對輸入的編碼字符串進行解碼public String decodeString(String s) {// 用于存儲重復次數的棧Stack<Integer> countStack = new Stack<>();// 用于存儲待拼接的字符串的棧Stack<String> stringStack = new Stack<>();// 用于構建當前正在處理的字符串StringBuilder currentString = new StringBuilder();// 用于記錄當前的重復次數int k = 0;// 遍歷輸入字符串中的每一個字符for (char c : s.toCharArray()) {// 如果當前字符是數字if (Character.isDigit(c)) {// 更新重復次數 k，考慮到多位數的情況k = k * 10 + (c - '0');// 如果當前字符是左括號 [} else if (c == '[') {// 將當前的重復次數 k 壓入 countStack 棧中countStack.push(k);// 將當前已經構建好的字符串壓入 stringStack 棧中stringStack.push(currentString.toString());// 清空 currentString，準備處理括號內的字符串currentString = new StringBuilder();// 重置重復次數 k 為 0k = 0;// 如果當前字符是右括號 ]} else if (c == ']') {// 從 stringStack 棧中彈出上一個字符串StringBuilder decodeString = new StringBuilder(stringStack.pop());// 從 countStack 棧中彈出重復次數int count = countStack.pop();// 根據重復次數，將當前括號內的字符串添加到 decodeString 后面for (int i = 0; i < count; i++) {decodeString.append(currentString);}// 更新 currentString 為 decodeStringcurrentString = decodeString;// 如果當前字符是普通字符} else {// 將該字符添加到 currentString 后面currentString.append(c);}}// 返回最終解碼后的字符串return currentString.toString();}
}

合并區間

class Solution {public static int[][] merge(int[][] intervals) {// 如果輸入數組為空或者長度為 0，直接返回空數組if (intervals == null || intervals.length == 0) {return new int[0][0];}// 按照區間的起始位置進行排序Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));// 用于存儲合并后的區間List<int[]> merged = new ArrayList<>();// 取第一個區間作為初始的合并區間int[] current = intervals[0];// 遍歷剩余的區間for (int i = 1; i < intervals.length; i++) {int[] interval = intervals[i];// 如果當前區間的結束位置大于等于下一個區間的起始位置，說明有重疊if (current[1] >= interval[0]) {// 更新當前區間的結束位置為兩個區間結束位置的最大值current[1] = Math.max(current[1], interval[1]);} else {// 沒有重疊，將當前區間加入到合并列表中merged.add(current);// 更新當前區間為下一個區間current = interval;}}// 將最后一個合并的區間加入到列表中merged.add(current);// 將列表轉換為二維數組并返回return merged.toArray(new int[merged.size()][]);}
}

合并兩個有序數組

假設有兩個有序數組?nums1?和?nums2，要將?nums2?合并到?nums1?中，使?nums1?成為一個有序數組。nums1?的長度足以容納?nums2?的元素。

class Solution {// 該方法用于將 nums2 合并到 nums1 中，使 nums1 成為一個有序數組public void merge(int[] nums1, int m, int[] nums2, int n) {// p1 指向 nums1 中有效元素的最后一個位置int p1 = m - 1;// p2 指向 nums2 中最后一個元素的位置int p2 = n - 1;// p 指向合并后數組的最后一個位置int p = m + n - 1;// 當 p1 和 p2 都未越界時，進行比較和賦值操作while (p1 >= 0 && p2 >= 0) {// 如果 nums1[p1] 大于 nums2[p2]if (nums1[p1] > nums2[p2]) {// 將 nums1[p1] 放到合并后數組的 p 位置nums1[p] = nums1[p1];// p1 指針左移一位p1--;} else {// 否則將 nums2[p2] 放到合并后數組的 p 位置nums1[p] = nums2[p2];// p2 指針左移一位p2--;}// p 指針左移一位p--;}// 如果 nums2 中還有剩余元素，將其依次放入 nums1 中while (p2 >= 0) {nums1[p] = nums2[p2];p2--;p--;}}
}    

合并K個有序數組

import java.util.PriorityQueue;class Solution {// 該方法用于合并多個有序數組public int[] mergeKArrays(int[][] arrays) {// 如果輸入的數組為空或者長度為 0，直接返回一個空數組if (arrays == null || arrays.length == 0) {return new int[0];}// 創建一個最小堆，用于存儲每個數組的當前最小值PriorityQueue<Node> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);// 計算所有數組的總長度int totalLength = 0;// 遍歷每個數組for (int i = 0; i < arrays.length; i++) {// 如果當前數組不為空if (arrays[i].length > 0) {// 將當前數組的第一個元素及其所在數組的索引和位置信息封裝成 Node 放入最小堆中minHeap.offer(new Node(arrays[i][0], i, 0));// 累加當前數組的長度到總長度中totalLength += arrays[i].length;}}// 創建一個用于存儲合并后結果的數組int[] result = new int[totalLength];// 結果數組的索引int index = 0;// 當最小堆不為空時，繼續合并操作while (!minHeap.isEmpty()) {// 從最小堆中取出當前最小值對應的 NodeNode node = minHeap.poll();// 將該最小值放入結果數組中result[index++] = node.val;// 如果該元素所在數組還有剩余元素if (node.col + 1 < arrays[node.row].length) {// 將該數組的下一個元素及其位置信息封裝成 Node 放入最小堆中minHeap.offer(new Node(arrays[node.row][node.col + 1], node.row, node.col + 1));}}// 返回合并后的結果數組return result;}// 自定義 Node 類，用于存儲元素的值、所在數組的索引和元素在數組中的位置static class Node {int val;int row;int col;// 構造函數，用于初始化 Node 對象Node(int val, int row, int col) {this.val = val;this.row = row;this.col = col;}}
}