- 二分查找算法
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 肯定不存在,返回 -1
if (left < 0 || left >= nums.length) {
return -1;
}
// 判断一下 nums[left] 是不是 target
return nums[left] == target ? left : -1;
}
- 滑动窗口算法
上下是对称的文章来源地址https://www.toymoban.com/news/detail-646759.html
/* 滑动窗口算法框架 */
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;
}
}
文章来源:https://www.toymoban.com/news/detail-646759.html
到了这里,关于算法模版,今天开始背的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!