算法与数据结构①：二分法、动态规划、快速排序、回溯、二叉树遍历

两种边界条件的模板
两次比较：比较次数最小的二分法，查找区间[lo,hi)，条件是lo < hi，返回值是不大于target的最大秩
请注意，区间缩小至2时，lo必等于mi。
只要nums[mi]= =target，lo移动到目标值的右边，最终nums[lo]必然是数组中大于target的第一个元素（若末尾是target，lo会到nums.length），- -lo是<=target的最大秩

class Solution {
public:
    	int searchInsert(vector& nums, int target) {
        int lo = 0, hi = nums.length; /注意这里搜索区间是[lo,hi)，如果搜索数组
        while(lo < hi) { /判断条件注意
            int mi = lo + hi >> 1; / >>的优先级低于+
            if(nums[mi] <= target){
				lo = mi + 1;
			}else{
				hi = mi;
			}
        }
      	return --lo; 
      	/ lo是大于target的最小秩， --lo是不大于target的最大秩
    }
}

查找区间[lo,hi)，条件是lo < hi，返回值是不小于target的最小秩
====因为循环退出前，mi总是在hi的左侧，当mi= = target时将hi移动到mi可以不断逼近第一个>=target
的元素，返回值是>=target的最小秩）

class Solution {
public:
	int searchInsert(vector& nums, int target) {
        int lo = 0, hi = nums.length; /注意这里搜索区间是[lo,hi)，如果搜索数组
        while(lo < hi) { /判断条件注意
            int mid = lo + hi >> 1; / >>的优先级低于+
            if(nums[mid] < target){
            	lo = mi + 1;
            }else{
            	hi = mi;
            }
        }
      	return hi; 
      	/ hi是 >= target的最小秩
    }
}

三次比较：查找区间[lo,hi]，条件是lo <= hi

class Solution {
    public int searchInsert(vector& nums, int target) {
        int left = 0, right = nums.length - 1; /注意查找区间是[lo,hi]
        while(left <= right) { // 注意
            int mid = (left + right) / 2; // 注意
            if(nums[mid] == target) { // 注意
                // 相关逻辑
            } else if(nums[mid] < target) {
                left = mid + 1; // 注意
            } else {
                right = mid - 1; // 注意
            }
        }
        // 相关返回值
        return 0;
    }
}

动态规划视频详解
动态规划（Dynamic Programming，DP）=记忆化搜索(Recursion with memoization)
对于递归：带备忘录(memo)的递归=递归树的剪枝(Pruning)
核心通过哈希表记忆降低复杂度=用空间换时间

第一种写法
void quicksort(vector& nums, int begin, int end){
	if(begin >= end) return;
	int i = begin, j = end;
	int temp = nums[begin];
	while(i < j){
		while(i < j && nums[j] >= temp) 
			j--; 
		nums[i] = nums[j];
		while(i < j && nums[i] <= temp)
			i++;
		nums[j] = nums[i];
	}
	nums[i] = temp;
	quicksort(nums, begin, i-1);
	quicksort(nums, i+1, end);

第二种写法
void quicksort(vector& nums, int begin, int end){
	if(begin >= end) return;
	int i = begin, j = end;
	while(i < j){
		while(i < j && nums[j] >= nums[begin]) j--;
		while(i < j && nums[i] <= nums[begin]) i++;
		swap(nums[i], nums[j]);
	}
	swap(nums[i], nums[begin]);
	quicksort(nums, begin, i-1);
	quicksort(nums, i+1, end);

快速排序详解

回溯法模板
leetcode46-全排列

void backtracking(参数){
	if(终止条件){
		收集结果;
		return;
	}
	for(遍历集合元素){
		处理节点;
		递归函数;
		回溯操作;
		}

二叉树三种遍历数组的特点
先序遍历数组：【根节点 | 左子树 | 右子树】
中序遍历数组：【左子树 | 根节点 | 右子树】
后序遍历数组：【左子树 | 右子树 | 根节点】