1. 二分查找算法

int left_bound(int[] nums, int target) {int left = 0, right = nums.length - 1;// 搜索區間為 [left, right]while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {// 搜索區間變為 [mid+1, right]left = mid + 1;} else if (nums[mid] > target) {// 搜索區間變為 [left, mid-1]right = mid - 1;} else if (nums[mid] == target) {// 收縮右側邊界right = mid - 1;}}// 判斷 target 是否存在于 nums 中// 如果越界，target 肯定不存在，返回 -1if (left < 0 || left >= nums.length) {return -1;}// 判斷一下 nums[left] 是不是 targetreturn nums[left] == target ? left : -1;
}

3. 滑動窗口算法

上下是對稱的

/* 滑動窗口算法框架 */
void slidingWindow(String s) {// 用合適的數據結構記錄窗口中的數據HashMap<Character, Integer> window = new HashMap<>();int left = 0, right = 0;while (right < s.length()) {// c 是將移入窗口的字符char c = s.charAt(right);window.put(c, window.getOrDefault(c, 0) + 1);// 增大窗口right++;// 進行窗口內數據的一系列更新.../*** debug 輸出的位置 ***/// 注意在最終的解法代碼中不要 print// 因為 IO 操作很耗時，可能導致超時System.out.printf("window: [%d, %d)\n", left, right);/********************/// 判斷左側窗口是否要收縮while (left < right && window needs shrink) {// d 是將移出窗口的字符char d = s.charAt(left);window.put(d, window.get(d) - 1);// 縮小窗口left++;// 進行窗口內數據的一系列更新...}}
}

4. 二叉樹的層序遍歷

// 輸入一棵二叉樹的根節點，層序遍歷這棵二叉樹
void levelTraverse(TreeNode root) {if (root == null) return;Queue<TreeNode> q = new LinkedList<>();q.offer(root);// 從上到下遍歷二叉樹的每一層while (!q.isEmpty()) {int sz = q.size();// 從左到右遍歷每一層的每個節點for (int i = 0; i < sz; i++) {TreeNode cur = q.poll();// 將下一層節點放入隊列if (cur.left != null) {q.offer(cur.left);}if (cur.right != null) {q.offer(cur.right);}}}
}

5. 動態規劃算法

以最小硬幣數為例
class Solution {int[] memo;int coinChange(int[] coins, int amount) {memo = new int[amount + 1];// 備忘錄初始化為一個不會被取到的特殊值，代表還未被計算Arrays.fill(memo, -666);return dp(coins, amount);}int dp(int[] coins, int amount) {if (amount == 0) return 0;if (amount < 0) return -1;// 查備忘錄，防止重復計算if (memo[amount] != -666)return memo[amount];int res = Integer.MAX_VALUE;for (int coin : coins) {// 計算子問題的結果int subProblem = dp(coins, amount - coin);// 子問題無解則跳過if (subProblem == -1) continue;// 在子問題中選擇最優解，然后加一res = Math.min(res, subProblem + 1);}// 把計算結果存入備忘錄memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;return memo[amount];}
}

6. Nsum問題

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);return nSum(nums,4,0,target);}public List<List<Integer>> nSum(int[] nums, int n, int start , long target){List<List<Integer>> result = new ArrayList<>();if(n==2){int left = start;int right = nums.length -1 ;while(left<right){int leftValue = nums[left];int rightValue = nums[right];int sum = leftValue + rightValue;if(sum==target){List<Integer> collect = new ArrayList<>();collect.add(leftValue);collect.add(rightValue);result.add(collect);    while(left<right&&nums[left]==leftValue) left++;while(left<right&&nums[right]==rightValue) right--;       }else if( sum > target){right--;while(left<right&&nums[right]==rightValue) right--;  }else{left++;while(left<right&&nums[left]==leftValue) left++;}}}else{for(int i = start;i<nums.length;i++){List<List<Integer>> temp = nSum(nums,n-1,i+1,target-nums[i]);for(List<Integer> list : temp){list.add(nums[i]);result.add(list);}while(i<nums.length-1&&nums[i]==nums[i+1]) i++;}}return result;}}