这是本节的多页打印视图。
点击此处打印.
返回本页常规视图.
Algorithm
算法
可以跟着 Carl 刷, 地址 。
个人认为算法最难的有：
回溯
一般可以解决如下几种问题：
- 组合问题： 在N个数里面按照规则找出K个数的集合
- 切割问题： 一个字符串按照规则有几种切割方式
- 子集问题： N个数的集合里有多少符合条件的子集
- 排列问题： N个数按一定规则全排列，有几种排列方式
- 棋盘问题： N皇后，数独等
解题有固定模板，按照模板往下写。
贪心
贪心的本质是选择每一个阶段的局部最优，从而达到全局最优。
贪心算法没有固定套路模板，最好的策略就是举反例，如果想不到，就试一试贪心。
解决问题就是常识性推导加上举反例。
一般解题的4个步骤：
- 将问题分解成若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
动态规划
Dynamic Programming，简称 DP 。如果某一问题有很多重叠子问题，使用动态规划是最有效的。
动态规划中每一个状态一定是由上一个状态推导出来的，这一点区别于贪心，贪心没有状态推导，而是从局部直接选出最优的。
解决的问题：
- 常见的基础问题，如斐波那契数，爬楼梯，不同路径等
- 背包问题
- 打家劫舍
- 股票问题
- 子序列问题
1.1 - 二分查找
二分查找
二分查找
1.给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
力扣链接-704题-二分查找
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
思路：
二分查找，注意边界问题，使用左闭右开或者左闭右闭。
在while寻找中每次的边界处理都要根据区间的定义操作。
我习惯使用 左闭右闭 区间的思路。
public int search(int[] nums, int target) {
if (nums == null || nums[0] > target || nums[nums.length - 1] < target) {
return -1;
}
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
2.给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
力扣链接-35题-搜索插入位置
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
思路：
方法一：
直接遍历判断，变量index赋值为-1，
如果小于target，记录index，如果等于直接返回，如果大于target直接退出循环。
public int searchInsert(int[] nums, int target) {
if (nums == null) {
return -1;
}
int index = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] < target) {
index = i;
} else if (nums[i] == target) {
return i;
} else {
break;
}
}
return index == -1 ? 0 : index + 1;
}
方法二：
二分查找，采用左闭右闭区间。
public int searchInsert(int[] nums, int target) {
if (nums == null) {
return -1;
}
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
3.在排序数组中查找元素的第一个和最后一个位置
leetcode-34题
public int[] searchRange(int[] nums, int target) {
if (nums == null || nums.length == 0 || nums[0] > target || nums[nums.length - 1] < target) {
return new int[]{-1, -1};
}
int left = 0;
int right = nums.length - 1;
int start = -1, end = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
if (left == right) {
return new int[]{mid, mid};
} else {
for (int i = mid; i >= left; i--) {
if (nums[i] == target) {
start = i;
}
}
for (int i = mid; i <= right; i++) {
if (nums[i] == target) {
end = i;
}
}
return new int[]{start, end};
}
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return new int[]{-1, -1};
}
1.2 - 移除元素
移除元素
移除元素
27.移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
思路：
可以使用暴力的双层循环解决，外层循环查找是否等于val值，相等时内层for循环为数值向后移动。
另一种方法是使用一层for循环，使用双指针。
- 右指针指向当前将要处理的元素
- 左指针left指向下一个将要赋值的位置
- 如果右指针指向的元素不等于val，一定是数组的一个元素，我们就将右指针指向的元素复制
到左指针位置，然后将左右指针同时右移
- 如果右指针指向的元素等于val，那么不能在输出的数组里，这时候左指针不动，右指针向右移动一位
public int removeElement(int[] nums, int val) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
3 - 回溯
回溯算法
模板：
- 函数模板返回值和参数
返回值是void
参数一般不确定，可以先写逻辑，然后需要参数再填
- 终止条件
一般是到了叶子结点，也就是满足条件的一条答案，把这个答案存起来，并结束本层递归。
if(终止条件){
存放结果;
return;
}
- 遍历过程
一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成树的深度。
for(选择：本层集合元素(树中节点孩子的数量就是集合的大小)){
处理节点；
backtracking(路径，选择列表)//递归
回溯，撤销处理结果
}
for循环可以理解是横向遍历，backtracking是纵向遍历。
分析完过程，整个框架如下：
void backtracking(参数){
if(终止条件){
存放结果;
return;
}
for(选择：本层集合元素(树中节点孩子的数量就是集合的大小)){
处理节点；
backtracking(路径，选择列表);//递归
回溯，撤销处理结果
}
}