复习算法总结

本文主要是介绍复习算法总结，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、二分法 找到数组中第一个数， 和最后一个数。  

关键点： 找第一个数-> 那么小于target的都可以舍弃 ，   找最后一个数， 大于target的都可以舍弃

当left = mid 时，  要加1， int mid = left + (right - left + 1)/2 ;

private int findFirstPosition(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
// 小于一定不是解
if (nums[mid] < target) {
// 下一轮搜索区间是 [mid + 1..right]
left = mid + 1;
} else {
// nums[mid] >= target，下一轮搜索区间是 [left..mid]
right = mid;
}
}

// 退出循环以后不能确定 nums[left] 是否等于 target，因此需要再判断一次
if (nums[left] == target) {
return left;
}
return -1;
}

private int findLastPosition(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (nums[mid] > target) {
// 下一轮搜索区间是 [left..mid - 1]
right = mid - 1;
} else {
// 下一轮搜索区间是 [mid..right]
left = mid;
}
}
// 主程序先执行 findFirstPosition，能执行到 findLastPosition 说明数组中一定存在等于 target 的元素，因此这里不用判断 nums[left] 是否等于 target
return left;
}

二、下一个排列

算法： 找到最会一个升序，最小值坐标， 之后的位置找到最后一个大于它的坐标， 交换位置， 最小值之后进行升序排序

核心代码

int j = nums.length - 1;
while (j >= 0 && nums[i] >= nums[j]) {
j--;
}

从后向前找， 找到大于nums[i]的最后一个数。

三、 二分法搜索旋转数组

核心：  多了一步判断mid在左还是右，     先取确定的值，不确定的直接舍弃。

int lo = 0, hi = nums.length - 1, mid = 0;
while (lo <= hi) {
mid = lo + (hi - lo) / 2;
if (nums[mid] == target) {
return mid;
}
// 先根据 nums[mid] 与 nums[lo] 的关系判断 mid 是在左段还是右段
if (nums[mid] >= nums[lo]) {
// 再判断 target 是在 mid 的左边还是右边，从而调整左右边界 lo 和 hi
if (target >= nums[lo] && target < nums[mid]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
} else {
if (target > nums[mid] && target <= nums[hi]) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
return -1;

四、 二分法找到插入位置

核心： right = length 可能查到最后。 找大于等于， 那么小于直接舍弃区间

public int searchInsert(int[] nums, int target) {
int len = nums.length;
int left = 0;
int right = len;
// 在区间 nums[left..right] 里查找第 1 个大于等于 target 的元素的下标
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target){
// 下一轮搜索的区间是 [mid + 1..right]
left = mid + 1;
} else {
// 下一轮搜索的区间是 [left..mid]
right = mid;
}
}
return left;
}

五、组合之合2

核心： 如何去重， 下一次坐标从i+1开始。    Deque<Integer> path = new ArrayDeque<>(len);  使用addFirst 和removeLast来进行回溯。

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
int len = candidates.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}

// 关键步骤
Arrays.sort(candidates);

Deque<Integer> path = new ArrayDeque<>(len);
dfs(candidates, len, 0, target, path, res);
return res;
}

/**
* @param candidates 候选数组
* @param len 冗余变量
* @param begin 从候选数组的 begin 位置开始搜索
* @param target 表示剩余，这个值一开始等于 target，基于题目中说明的"所有数字（包括目标数）都是正整数"这个条件
* @param path 从根结点到叶子结点的路径
* @param res
*/
private void dfs(int[] candidates, int len, int begin, int target, Deque<Integer> path, List<List<Integer>> res) {
if (target == 0) {
res.add(new ArrayList<>(path));
return;
}
for (int i = begin; i < len; i++) {
// 大剪枝：减去 candidates[i] 小于 0，减去后面的 candidates[i + 1]、candidates[i + 2] 肯定也小于 0，因此用 break
if (target - candidates[i] < 0) {
break;
}

// 小剪枝：同一层相同数值的结点，从第 2 个开始，候选数更少，结果一定发生重复，因此跳过，用 continue
if (i > begin && candidates[i] == candidates[i - 1]) {
continue;
}

path.addLast(candidates[i]);
// 调试语句 ①
// System.out.println("递归之前 => " + path + "，剩余 = " + (target - candidates[i]));

// 因为元素不可以重复使用，这里递归传递下去的是 i + 1 而不是 i
dfs(candidates, len, i + 1, target - candidates[i], path, res);

path.removeLast();
// 调试语句 ②
// System.out.println("递归之后 => " + path + "，剩余 = " + (target - candidates[i]));
}

}

六、跳跃游戏

核心： 定义几个关键变量， 从头开始遍历数组，不断更新这几个变量。  每个位置的最大距离不断更新

每次i== end时,   先跳出一步，如果i不能等于end， 也就是end >= length-1, 那么step就是最终跳跃的结果。

public int jump(int[] nums) {
int length = nums.length;
int end = 0;
int maxPosition = 0;
int steps = 0;
for (int i = 0; i < length - 1; i++) {
maxPosition = Math.max(maxPosition, i + nums[i]);
if (i == end) {
end = maxPosition;
steps++;
}
}
return steps;
}

七、全排列1，   不包含重复元素

核心：考虑i是从i开始 还是i+1开始， 显然这两种都有问题， 需要从0开始，但是从0开始需要有一个变量记录，现在都有哪些元素使用了，

public List<List<Integer>> permute(int[] nums) {
int len = nums.length;
// 使用一个动态数组保存所有可能的全排列
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}

boolean[] used = new boolean[len];
Deque<Integer> path = new ArrayDeque<>(len);

dfs(nums, len, 0, path, used, res);
return res;
}

private void dfs(int[] nums, int len, int depth,
Deque<Integer> path, boolean[] used,
List<List<Integer>> res) {
if (depth == len) {
res.add(new ArrayList<>(path));
return;
}

for (int i = 0; i < len; i++) {
if (!used[i]) {
path.addLast(nums[i]);
used[i] = true;

System.out.println(" 递归之前 => " + path);
dfs(nums, len, depth + 1, path, used, res);

used[i] = false;
path.removeLast();
System.out.println("递归之后 => " + path);
}
}
}

八、全排列2

核心： 可以包含重复元素， 需要减枝：   当前层， 前面的没有使用， 现在的也不允许使用。

if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}

// 回溯使用这个

Deque<Integer> path = new ArrayDeque<>(len);

public List<List<Integer>> permuteUnique(int[] nums) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}

// 排序（升序或者降序都可以），排序是剪枝的前提
Arrays.sort(nums);

boolean[] used = new boolean[len];
// 使用 Deque 是 Java 官方 Stack 类的建议
Deque<Integer> path = new ArrayDeque<>(len);
dfs(nums, len, 0, used, path, res);
return res;
}

private void dfs(int[] nums, int len, int depth, boolean[] used, Deque<Integer> path, List<List<Integer>> res) {
if (depth == len) {
res.add(new ArrayList<>(path));
return;
}

for (int i = 0; i < len; ++i) {
if (used[i]) {
continue;
}

// 剪枝条件：i > 0 是为了保证 nums[i - 1] 有意义
// 写 !used[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}

path.addLast(nums[i]);
used[i] = true;

dfs(nums, len, depth + 1, used, path, res);
// 回溯部分的代码，和 dfs 之前的代码是对称的
used[i] = false;
path.removeLast();
}
}

这篇关于复习算法总结的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！