labuladong算法

思维

二维数组旋转

https://labuladong.gitee.io/algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/er-wei-shu-150fb/

• 顺时针旋转：\对角线翻转，再水平翻转
• 逆时针旋转：/对角线翻转，再水平翻转。

二叉树

动归/DFS/回溯算法都可以看做二叉树问题的扩展，只是它们的关注点不同：

• 动态规划算法属于分解问题的思路，它的关注点在整棵「子树」。
• 回溯算法属于遍历的思路，它的关注点在节点间的「树枝」。
• DFS 算法属于遍历的思路，它的关注点在单个「节点」。

Code

回溯算法

组合子集用start，额外传参i+1
排列用used，不用额外传参

1. 形式一、元素无重不可复选，即 nums 中的元素都是唯一的，每个元素最多只能被使用一次，backtrack 核心代码如下：

void backtrack(vector<int>& nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.size(); i++) {
        // 做选择
        track.push_back(nums[i]);
        // 注意参数
        backtrack(nums, i + 1);
        // 撤销选择
        track.pop_back();
    }
}

void backtrack(vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++) {
        // 剪枝逻辑
        if (used[i]) {
            continue;
        }
        // 做选择
        used[i] = true;
        track.push_back(nums[i]);
        backtrack(nums);
        // 撤销选择
        track.pop_back();
        used[i] = false;
    }
}

2. 元素可重不可复选，即 nums 中的元素可以存在重复，每个元素最多只能被使用一次，其关键在于排序和剪枝，backtrack 核心代码如下：

sort(nums.begin(), nums.end());

/* 组合/子集问题回溯算法框架 */
void backtrack(vector<int>& nums, int start) {
    //回溯算法标准框架
    for (int i = start; i < nums.size(); i++) {
        // 剪枝逻辑，跳过值相同的相邻树枝
        if (i > start && nums[i] == nums[i - 1]) {
            continue;
        }
        // 做选择
        track.push_back(nums[i]);
        // 注意参数
        backtrack(nums, i + 1);
        // 撤销选择
        track.pop_back();
    }
}

sort(nums.begin(), nums.end());

/* 排列问题回溯算法框架 */
void backtrack(vector<int>& nums, vector<bool>& used) {
    for (int i = 0; i < nums.size(); i++) {
        // 剪枝逻辑
        if (used[i]) {
            continue;
        }
        // 剪枝逻辑，固定相同的元素在排列中的相对位置
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            continue;
        }
        // 做选择
        used[i] = true;
        track.push_back(nums[i]);

        backtrack(nums, used);
        // 撤销选择
        track.pop_back();
        used[i] = false;
    }
}

3. 元素无重可复选，即 nums 中的元素都是唯一的，每个元素可以被使用若干次，只要删掉去重逻辑即可，backtrack 核心代码如下：

/* 组合/子集问题回溯算法框架 */
void backtrack(vector<int>& nums, int start, vector<int>& track) {
    // 回溯算法标准框架
    for (int i = start; i < nums.size(); i++) {
        // 做选择
        track.push_back(nums[i]);
        // 注意参数
        backtrack(nums, i+1, track);
        // 撤销选择
        track.pop_back();
    }
}


/* 排列问题回溯算法框架 */
void backtrack(vector<int>& nums, vector<int>& track) {
    if (track.size() == nums.size()) {
        // 输出结果
        // ...
        return;
    }
    for (int i = 0; i < nums.size(); i++) {
        // 排除不合法的选择
        if (find(track.begin(), track.end(), nums[i]) != track.end()) {
            continue;
        }
        // 做选择
        track.push_back(nums[i]);
        backtrack(nums, track);
        // 撤销选择
        track.pop_back();
    }
}

BFS

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    queue<Node> q; // 核心数据结构
    unordered_set<Node> visited; // 避免走回头路
    
    q.push(start); // 将起点加入队列
    visited.insert(start);
    int step = 0; // 记录扩散的步数

    while (!q.empty()) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.front();
            q.pop();
            /* 划重点：这里判断是否到达终点 */
            if (cur == target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj()) {
                if (visited.count(x) == 0) {
                    q.push(x);
                    visited.insert(x);
                }
            }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}

二分法模板

前面代码完全一致，只有后面三行代码不同。

//基础二分查找
int binary_search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1; 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}

//查找左边界
int left_bound(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定左侧边界
            right = mid - 1; // 因退出循环条件时，right+1=left,所以假如只有一个值符合，那么最后的left正好是这个索引，即答案。
        }
    }
    // 判断 target 是否存在于 nums 中
    // 此时 target 比所有数都大，返回 -1
    // 
    if (left == nums.size()) return -1;
    // 判断一下 nums[left] 是不是 target
    return nums[left] == target ? left : -1;
}

//查找右边界
int right_bound(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定右侧边界
            left = mid + 1;
        }
    }
    // 此时 left - 1 索引越界
    if (right ==-1) return -1;
    // 判断一下 nums[left] 是不是 target
    return nums[right] == target ? right : -1;
}

滑动窗口模板

bool checkInclusion(string s1, string s2) {//s1为子串
        unordered_map<char, int> need,window;
        for(char ch : s1) need[ch]++;
        int left=0,right=0;
        int valid=0; 
        vector<int> rt;

        while(right<s2.size()){
            char cur=s2[right];
            right++;
            if(need.count(cur)){ //属于子串字符
                window[cur]++;
                if(window[cur]==need[cur]) valid++; 
            }

            //如果窗口不定长，建议用while，有时候if会出错
            
            //窗口定长
            while(right-left>=s1.size()){
                if(valid==need.size()){
                    return true;
                }

                char d=s2[left];
                left++;
                if(need.count(d)){//属于子串字符
                    if(window[d]==need[d]) valid--;
                    window[d]--;
                }
            }
        }
        return false;