算法模版，今天开始背
- 二分查找算法
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;
}- 滑动窗口算法
上下是对称的
/* 滑动窗口算法框架 */
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++;// 进行窗口内数据的一系列更新...}}
}
- 二叉树的层序遍历
// 输入一棵二叉树的根节点，层序遍历这棵二叉树
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);}}}
}
- 动态规划算法
以最小硬币数为例
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];}
}
- 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;}}