经典上机算法

一些常见的面试算法模板，如动态规划、二分。。。

二分

简例示意

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
1
2
3

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

代码实现：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + r >> 1; 
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if(nums[l] == target) return l;
        else return -1;
    }
};

易错点

1.边界问题

参考博客彻底解决二分查找出现的死循环、边界问题
错误示例一

2.死循环

左区间成立，右区间不成立时r - l等于1时，mid始终为l，也就是check(mid)永为true，造成死循环。
错误示例一

3.答案不是mid

一个例子

• 初始时，l = 1, r = 4。
• 第一次循环：m = 3，check(3) 返回 true，更新 l = 3。
• 第二次循环：m = 4，check(4) 返回 false，更新 r = 3。
• 第三次循环：l = 3, r = 3，循环终止。

模板代码

情况一：左区间不成立，右区间成立

void bSearch(int l, int r){
	while(l < r){
		int mid = l + r >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	return l;
}

情况二：左区间成立，右区间不成立

void bSearch_2(int l, int r){
	while(l < r){
		// 加1的是因为当r - l等于1时，mid始终为l，也就是check(mid)永为true，造成死循环。
		int mid = l + r + 1 >> 1; 
		if(check(mid)) l = mid; 
		else r = mid - 1;
	}
	return l;
}

动态规划

树