数据结构第八章-搜索

岛屿数量

#medium 200. 岛屿数量 - 力扣（LeetCode）用一个二维数组代表一张地图，这张地图有字符0和字符1组成，其中0代表水域，1代表小岛土地，小岛1被水0包围，当小岛土地1在水平和垂直方向相连接，认为是同一块土地，求这张地图中小岛的数量示例

示例 1：
输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：
输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

方法1 DFS

代码实现

    void DFS(std::vector<std::vector<int> > &mark,

    std::vector<std::vector<char> > &grid,int x,int y

    ){

        mark[x][y] = 1;//标记已经搜寻的位置

        static const int dx[] = {-1,1,0,0};//方向数组

        static const int dy[] = {0,0,-1,1};

        for(int i = 0;i<4;i++){

            int newx = x + dx[i];//移动搜索点

            int newy = y + dy[i];

            if(newx <0||newx>=mark.size()||newy<0||newy>=mark[newx].size()){//超过数组边界时

            continue;//忽略掉这个点，跳过本次循环

            }

            if(grid[newx][newy]=='1'&&mark[newx][newy]==0){//当该点没有被探索过而且该点为陆地

                DFS(mark,grid,newx,newy);

            }

        }

    }

方法2 ：BFS

代码实现

    void BFS(std::vector<std::vector<int> > &mark,

    std::vector<std::vector<char> >& grid,int x,int y

    ){

        mark[x][y] = 1;//标记已经搜寻的位置

        static const int dx[] = {-1,1,0,0};//方向数组

        static const int dy[] = {0,0,-1,1};

        std::queue<std::pair<int,int> > Q;//宽度优先搜索队列

        Q.push(std::make_pair(x,y));//把x,y push进入队列

        mark[x][y] = 1;//标记

        while(!Q.empty()){

            x = Q.front().first;//取出队列头部元素进行访问

            y = Q.front().second;

            Q.pop();

            for(int i = 0;i<4;i++){

                int newx = x+dx[i];

                int newy = y+dy[i];

                if(newx<0||newx>=mark.size()||newy<0||newy>=mark[newx].size()){//忽略越过地图边界的位置

                    continue;

                }

                if(mark[newx][newy]==0&&grid[newx][newy]=='1'){//如果当前位置没有探索，而且为陆地

                    Q.push(std::make_pair(newx,newy));

                    mark[newx][newy] = 1;//做标记

  
  

                }

            }

        }

    }

整体算法思路

探索几次就有几个分离的陆地 解决方法如下

    int numIslands(vector<vector<char>>& grid) {

        int island_num = 0;

        std::vector<std::vector<int> > mark;

        for(int i = 0;i<grid.size();i++){//初始化mark数组

            mark.push_back(std::vector<int>());//后面加的括号是初始化为空向量的意思，（）是初始化的内容

            for(int j = 0;j < grid[i].size();j++){

                mark[i].push_back(0);//初始化mark数组为0

            }

        }

        for(int i = 0;i<grid.size();i++){//遍历整个地图

            for(int j = 0;j < grid[i].size();j++){

                if(mark[i][j] == 0&&grid[i][j] == '1'){

                    DFS(mark,grid,i,j);//搜索这座岛屿,BFS和DFS都行

                    island_num++;//增加岛屿计数器

                }

            }

        }

        return island_num;

    }

词语阶梯

#hard 127. 单词接龙 - 力扣（LeetCode）已知两个单词（起始单词与结束单词）一个单词词典 ，根据转换规则计算从起始单词到结束单词的最短转换步数 转换规则

在转换时，只能转换单词中的1个字符
转换得到的新单词，必须存储在单词字典里面如果转换不了就返回0 示例

示例 1：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例 2：
输入：**beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：**0
解释：**endWord "cog" 不在字典中，所以无法进行转换。

算法思路 图的表示与构造 [[第五章：二叉树与图#图的两种表示方法|邻接表]] 代码实现如下

        /*构造无向图*/

    bool connect(const std::string &word1,const std:: string &word2){//判断两个字符串是不是只差了1个字符

        int cnt = 0;//记录word1和word2不相等的字数

        for(int i = 0;i<word1.length();i++){

            if(word1[i] != word2[i]){

                cnt ++;

            }

        }

        return cnt == 1;

    }

    void construct_graph(std::string &beginWord,

    std::vector<std::string> &wordList,

    std::map<std::string,std::vector<std::string> > &graph){

        wordList.push_back(beginWord);//wordList 没有beginword

        for(int i = 0;i<wordList.size();i++){//初始化map指向空向量

            graph[wordList[i]] = std::vector<std::string>();

        }

        for(int i  = 0; i<wordList.size();i++){

            for(int j = i+1;j<wordList.size();j++){//只需要遍历i后面的的字符串就行，从0开始算会多算很对

                if(connect(wordList[i],wordList[j])){

                    graph[wordList[i]].push_back(wordList[j]);//构造无向图，双向链接

                    graph[wordList[j]].push_back(wordList[i]);

                }

            }

        }

    }

图的宽度遍历 代码实现如下

 /*宽搜代码*/

    int BFS_graph(std::string &beginWord,std::string &endWord,std::map<std::string,std::vector<std::string> >&graph){

        std::queue<std::pair<std::string,int> > Q;//搜索队列<顶点，步数>

        std::set<std::string> visit;//记录已经访问的顶点

        Q.push(std::make_pair(beginWord,1));//添加起始点，起始点步数为1

        visit.insert(beginWord);

        while(!Q.empty()){//队列不空继续搜索

            std::string node = Q.front().first;//取出头节点和步数

            int step = Q.front().second;

            Q.pop();//完成访问弹出队列

            if(node == endWord){//找到终点直接返回步数

                return step;

            }

            const std::vector<std::string> &neighbors = graph[node];//取出node的全部临界点

            for(int i = 0;i<neighbors.size();i++){

                if(visit.find(neighbors[i]) == visit.end()){//如果相邻节点还没有添加到队列

                    Q.push(std::make_pair(neighbors[i],step+1));//添加到队列里面并标记已经访问

                    visit.insert(neighbors[i]);

                }

            }

        }

        return 0;

    }

总代码

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {

        std::map<std::string,std::vector<std::string> > graph;

        construct_graph(beginWord,wordList,graph);

        return BFS_graph(beginWord,endWord,graph);
    }

不算很难，还算不上是hard难度 ~~下一题让你开开眼~~

词语阶梯plus

#hard 126. 单词接龙 II - 力扣（LeetCode）上一道题的plus版本挺难的转换规则与上一道题一样但是除了返回最短步数之外，还需要返回最短步数对应的所有路径

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
解释：存在 2 种最短的转换序列：
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：[]
解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。

BFS算法

#未完成 记录路径的宽搜 记录所有push进去的节点，通过前移front指针来表示pop 多条路径的保存 遍历搜索路径 代码解决如下

class Solution {
public:
    struct Qitem{//图的结构
        std::string node;//当前搜索节点
        int parent_node;//前驱节点在队列里面的位置
        int step ;//到达当前节点的步数
        Qitem(std::string node, int parent_node,int step):node(node),parent_node(parent_node),step(step){
        }
    };
    /*遍历搜索路径输出结果*/
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        std::map<std::string,std::vector<std::string> > graph;
        construct_graph(beginWord,wordList,graph);
        std::vector<Qitem> Q;//利用vector实现队列
        std::vector<int> end_word_pos;
        BFS_graph(beginWord,endWord,graph,end_word_pos,Q);//遍历生成end_word_pos
        std::vector<std::vector<std::string> >result;//最终结果
        //遍历路径输出结果
        for(int i = 0 ;i<end_word_pos.size();i++){
            int pos = end_word_pos[i];
            std::vector<std::string> path;//从endword到beginword将路径上的节点push进入path
            while(pos!= -1){
                path.push_back(Q[pos].node);
                pos = Q[pos].parent_node;
            }
            result.push_back(std::vector<std::string>());
            for(int j = path.size()-1;j>=0;j--){
                result[i].push_back(path[j]);
            }
        }
        return result;

    }
    /*BFS代码*/
    void BFS_graph(std::string &beginWord,std::string &endWord,std::map<std::string,std::vector<std::string> > &graph,
    std::vector<int> &end_word_pos,//终点所在队列的位置下标
    std::vector<Qitem>&Q){//vector实现的队列
        std::map<std::string,int> visit;//<单词，步数>
        int min_step = 0;//到达endWord的最小步数
        Q.push_back(Qitem(beginWord,-1,1));//起始单词的前驱为-1
        visit[beginWord] = 1;//标记起始单词步数为1
        int front = 0;//队列头指针front,指向vector表示的队列头部
        while(front != Q.size()){//当front指向vector的尾部，即Q.size()，的时候队列为空
            const std::string &node = Q[front].node;
            int step = Q[front].step;//取出队列头元素
            if(min_step!= 0 && step > min_step){//所有路径全部搜索完,step>min_step的时候，代表所有到达终点的路径都搜索完成
                break;
            }
            if(node == endWord){
                min_step= step;//当搜索到结果的时候，记录到达终点的最小步数
                end_word_pos.push_back(front);
            }
            /*访问图*/
            const std::vector<std::string>  &neighbors = graph[node];
            for(int i = 0; i <neighbors.size();i++){
                if(visit.find(neighbors[i])==visit.end()||visit[neighbors[i]] == step + 1){//节点没有被访问，或者是另一条最短的路径，visit[neibors[i]] == step+1 相当于储存最后一个节点的最后一个到达的方式
                    Q.push_back(Qitem(neighbors[i],front,step+1));//节点的前驱实际上的当前的队头元素
                    visit[neighbors[i]] = step + 1 ;//标记到达邻接点neighbors[i]的最小步数
                }
            }
            front++;//用front指针的前移来表示pop
        }


    }

//由于wordlist里面有可能有beginword，直接将beginword push进入wordlist会出现重复结果
/*建图和连接*/
    void construct_graph(std::string&beginWord,std::vector<std::string>&wordList,std::map<std::string,std::vector<std::string> > &graph){
        int has_begin_word = 0;
        for(int i = 0;i<wordList.size();i++){//排除beginword重复出现的情况
            if(wordList[i] == beginWord){
                has_begin_word = 1;
            }
            graph[wordList[i]] = std::vector<std::string>();
        }
        for(int i = 0;i<wordList.size();i++){
            for(int j =i +1 ; j<wordList.size();j++){
                if(connect(wordList[i],wordList[j])){
                    graph[wordList[i]].push_back(wordList[j]);//双向链接
                    graph[wordList[j]].push_back(wordList[i]);
                }
            }
            if(has_begin_word == 0&&connect(beginWord,wordList[i]) ){//如果里面没有beginword，在表里面查找能够与beginword连接的单词
                    graph[beginWord].push_back(wordList[i]);
            }
            
        }
    }
    bool connect(const std::string &word1,const std:: string &word2){//判断两个字符串是不是只差了1个字符
        int cnt = 0;//记录word1和word2不相等的字数
        for(int i = 0;i<word1.length();i++){
            if(word1[i] != word2[i]){
                cnt ++;
            }
        }
        return cnt == 1;
    }
};

然而会超时 ~~byd都tm什么鸡掰测试用例啊，去tm酒吧点tmd2500碗炒饭是吧~~ 时间复杂度我算不出来反正就是超时，~~就是建图的时候构建了多余的边啦，BFS的时候处理的数据比较多啦，之类的~~ 双向BFS没准可以 BFS+DFS也可以

BFS+DFS

#完成这里采用liweiwei的方法在广度优先遍历的时候，我们需要记录：从当前的单词 currWord 只变化了一个字符以后，且又在单词字典中的单词 nextWord 之间的单向关系（虽然实际上无向图，但是广度优先遍历是有方向的，我们解决这个问题可以只看成有向图），记为 from，它是一个映射关系：键是单词，值是广度优先遍历的时候从哪些单词可以遍历到「键」所表示的单词，使用哈希表来保存。广度搜索时候同一层的节点如有边连接，不可以记录下来，所以要有一个steps来记录单词在第几层因为BFS是按照层次进行遍历，所以建立完图形之后保留的路径必然是最短路径我们用BFS隐式的建立邻接表（不保存同层的连接）以给的示例为例利用BFS建立的邻接表如下

from = {
    {"cog", {"dog", "log"}},
    {"dog", {"dot"}},
    {"dot", {"hot"}},
    {"hot", {"hit"}},
    {"log", {"lot"}},
    {"lot", {"hot"}}
};

这个算法利用BFS来建图，由于是分层建图，所以相对来说要处理的数据量变少，而且减少了多余边的处理 代码实现如下

class Solution {

public:

    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {

        vector<vector<string>> res;

        // 因为需要快速判断扩展出的单词是否在 wordList 里，因此需要将 wordList 存入哈希表，这里命名为「字典」

        unordered_set<string> dict(wordList.begin(), wordList.end());

        // 特殊用例判断

        if (!dict.count(endWord)) return res;

        // 因为从 beginWord 开始扩展，因此 dict 里一定不可以有 beginWord

        dict.erase(beginWord);

  

        // 第 1 步：广度优先遍历构建图

        // 为了避免记录不需要的边，我们需要记录扩展出的单词是在第几次扩展的时候得到的，key：单词，value：在广度优先遍历的第几层

        // steps 记录了已经访问过的 word 集合，同时记录了在第几层访问到

        unordered_map<string, int> steps{{beginWord, 0}};

        // 记录了单词是从哪些单词扩展而来，key：单词，value：单词列表，这些单词可以变换到 key ，它们是一对多关系，dfs 的时候会用到

        unordered_map<string, vector<string>> from;

        bool found = bfs(beginWord, endWord, dict, steps, from);

        // 第 2 步：深度优先遍历找到所有解，从 endWord 恢复到 beginWord ，所以每次尝试操作 path 列表的头部

        if (found) {

            vector<string> path{endWord};

            dfs(from, path, beginWord, endWord, res);

        }

        return res;

    }

  

private:

    bool bfs(string beginWord, string endWord, unordered_set<string>& dict,

             unordered_map<string, int>& steps, unordered_map<string, vector<string>>& from) {

        int wordLen = beginWord.size();

        int step = 0;//定义到该点的步数

        bool found = false;//初始化found

        queue<string> q{{beginWord}};//定义bfs队列

        while (!q.empty()) {

            step++;//步数前移

            for (int size = q.size(); size > 0; size--) {//遍历当前层的所有节点

                string currWord = q.front(); q.pop();//访问当前队列头节点

                for (int i = 0; i < wordLen; i++) {//遍历当前单词的所有字符

                    string newWord = currWord;

                    for (char ch = 'a'; ch <= 'z'; ch++) {

                        //将每一位替换成26个小写英文字母

                        newWord[i] = ch;//对字符进行替换

                        if (steps.count(newWord) && steps[newWord] == step)//更新已经访问过单词的信息，连接这个单词的新后驱，一个节点被多个节点访问的情况，如果steps里面存在当前的元素，并且该键值对等于当前的步数，就把currentword加入到from里面，BTW，C++里面对map进行访问的话会自动插入一个新map导致错误结果

                            from[newWord].push_back(currWord);//存储该单词的前驱节点

                        if (!dict.count(newWord)) continue;//如果没有在dict里面查找到newword，那么说明不在wordlist里面

                        dict.erase(newWord);//在dict里面删除newword，标记这个单词已经被访问过了

                        //dict和steps承担已经访问的功能

                        q.push(newWord);//将这个新词添加到bfs队列里面（newword是currentword的后续）

                        //维护from,steps,found的定义

                        from[newWord].push_back(currWord);//将新单词的前趋和后趋连接

                        steps[newWord] = step;//把该点步数和该点连接

                        if (newWord == endWord) found = true;//注意：由于有多条路径到达endword 找到后不能立即退出，设置found = true即可

                    }

                }

            }

            if (found) break;

        }

        return found;

    }

  

    void dfs(unordered_map<string, vector<string>>& from, vector<string>& path,

             string beginWord, string cur, vector<vector<string>>& res) {

        if (cur == beginWord) {//当前访问单词是否为beginword，如果是，当前结果push到res里面并返回

            res.push_back(vector<string>(path.rbegin(), path.rend()));//rbegin和rend是反向迭代器，最后res的结果和path的路径相反

            return;

        }

        for (const string& precursor : from[cur]) {//遍历from[cur]里面的所有单词,即cur的所有前驱

            path.push_back(precursor);//把前驱push进入路径中

            dfs(from, path, beginWord, precursor, res);//对该前驱进行递归，直到找到beginword

            path.pop_back();//回溯的时候删掉该层单词

        }

    }

};

关于

    if (steps.count(newWord) && steps[newWord] == step)
            from[newWord].push_back(currWord);

存在的意义

在后续操作中，我们利用dict来进行标定已访问的操作，然而这种情况导致了有些同一个层次有多个前驱的节点无法正常工作，所以我们在if (!dict.count(newWord)) con tinue; 之前加入对steps的判定，如果这个单词在steps里面能被找到（说明该词在/曾经在dict里面出现过）；该层次的步数与上一次遍历的步数一样（说明该前驱是另一条最短路径）

关于本题还可以对双向BFS进行处理，这里不过多赘述~~我不会~~

火柴棍摆正方形

#medium 473. 火柴拼正方形 - 力扣（LeetCode）本题和[[第四章：递归，回溯和分治#求子集|求子集]] 的方法很像，只不过复杂一点已知一个数组，保存了n个（n<=15)个火柴棍，问可否使用n个火柴棍摆成一个正方形

示例

示例1：
输入: matchsticks = [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形，每边两根火柴。

示例 2:
输入: matchsticks = [3,3,3,3,4]
输出: false
解释: 不能用所有火柴拼成一个正方形。

回溯算法

无优化的深度搜索

如图会超时

优化与剪枝

从大到小排序，可以减少摆法，因为必须要把这个大的火柴棍摆在不同的边上

解决方法如下

class Solution {

public:

    bool makesquare(vector<int>& matchsticks) {

        if(matchsticks.size()<4){

            return false;//数量小于4的时候返回假

        }

        int sum = 0;

        for(int i = 0;i<matchsticks.size();i++){//累加求和

            sum+=matchsticks[i];

            }

        if(sum % 4){//当和有余数返回假

            return false;

        }

        std::sort(matchsticks.rbegin(),matchsticks.rend());//从大到小排序，额外传入cmp也可以

        int bucket[4] = {0};

        return generate(0,matchsticks,sum/4,bucket);

    }

private:

    bool generate(int i,std::vector<int>&matchsticks,int target,int bucket[]){

        if(i>=matchsticks.size()){//当已经把matchstick完全遍历完

            return bucket[0] == target && bucket[1] == target && bucket[2] == target && bucket[3] == target;//判断4条边是否全部正确

        }

        for(int j = 0;j<4 ;j++){//遍历4个桶

            if(bucket[j]+matchsticks[i] > target){//当该桶再加入火柴棍会导致超过target的时候跳过本次循环

                continue;

            }

            bucket[j]+=matchsticks[i];//放进桶里

            if(generate(i+1,matchsticks,target,bucket)){//进行后续递归，找到的时候返回true

                return true;

            }

            bucket[j]-= matchsticks[i];//回溯

        }

        return false;//如果前面没有搜索到true的话就意味着没搜到

    }

};

位运算法

实际上就是暴力枚举所有子集利用位运算法求子集和代表值的方法参考[[第四章：递归，回溯和分治#求子集#方法二：位运算法|位运算法]]

class Solution {

public:

    bool makesquare(vector<int>& matchsticks) {

        if(matchsticks.size()<4){

            return false;

        }

        int sum = 0;

        for(int i =0;i<matchsticks.size();i++){

            sum += matchsticks[i];

        }

        if(sum%4){

            return false;

        }

        int target = sum/4;

        sort(matchsticks.rbegin(),matchsticks.rend());

        std::vector<int> ok_subset;//满足条件的一条边的集合

        std::vector<int> ok_half;//满足条件两条边的集合

        int all = 1<<matchsticks.size();//求出所有子集

        for(int i =0;i<all;i++){

            int sum = 0;

            for(int j = 0;j<matchsticks.size();j++){

                if(i&(1<<j)){//当i&(1<<j)为真的时候说明第j个元素出现在子集里面

                    sum += matchsticks[j];//计算当时这条边的和

                }

            }

            if(sum == target){//如果这条边的和与target相等，push进入ok_subset

                ok_subset.push_back(i);

            }

        }

        for(int i =0;i<ok_subset.size();i++){//两两进行比较

            for(int j = i+1;j<ok_subset.size();j++){

                if((ok_subset[i]&ok_subset[j])==0){//二者进行与运算等于0说明两个集合没有交集，说明两个ok_subset是没有重合元素的，可以绑定成一个ok_half

                    ok_half.push_back(ok_subset[i]|ok_subset[j]);//绑定push进vector

                }

            }

        }

        for(int i = 0;i < ok_half.size();i++){//同理对ok_half进行捆绑

            for(int j = i+1;j<ok_half.size();j++){

                if((ok_half[i]&ok_half[j])==0){

                    return true;//如果可以实现捆绑说明能构成正方体

  

                }

            }

        }

        return false;

  

    }

};

看看就好，暴力枚举不可取不用看了，会超时

状态压缩动态规划

参考[[第九章：动态规划]] 这个思路是官方的思路，现在列举在下面

计算所有火柴的总长度 $totalLen$，如果$totalLen$ 不是 4 的倍数，那么不可能拼成正方形，返回 false。当 $totalLen$ 是 4 的倍数时，每条边的边长为 $len=totalLen/4$。我们给正方形的四条边进行编号，分别为 1,2,3 和 4。按照编号顺序依次将火柴放入正方形的四条边，只有前一条边被放满后，才能将火柴放入后一条边。

用状态 s 记录哪些火柴已经被放入（s 的第 k 位为 1 表示第 k 根火柴已经被放入），$dp[s]$ 表示正方形未放满的边的当前长度，计算如下：

当 $s=0$ 时，没有火柴被放入，因此 $dp[0]=0$。
当 $s≠0$ 时，如果去掉它的第 k 根火柴得到的状态 s_1 满足 $dp[s_1]≥0$ 且 $dp[s_1]+matchsticks[k]≤len$，那么 $dp[s]=(dp[s_1]+matchsticks[k]) mod len$（因为放满前一条边后，我们开始放后一条边，此时未放满的边的长度为 0，所以需要对 len 取余）；否则 $dp[s]=-1$，表示状态 s 对应的火柴集合不可能按上述规则放入正方形的边。

令 $s_{all}$ 表示所有火柴都已经被放入时的状态，如果 $dp[s_{all}]=0$ 成立，那么可以拼成正方形，否则不可以拼成正方形。 代码实现如下

class Solution {
public:
    bool makesquare(vector<int>& matchsticks) {
        // 计算所有火柴棒的总长度
        int totalLen = accumulate(matchsticks.begin(), matchsticks.end(), 0);
        // 判断总长度是否能被4整除
        if (totalLen % 4 != 0) {
            return false;
        }
        // 计算正方形每条边的长度
        int len = totalLen / 4, n = matchsticks.size();
        // 初始化动态规划数组
        vector<int> dp(1 << n, -1);
        dp[0] = 0;
        // 遍历所有状态
        for (int s = 1; s < (1 << n); s++) {
            // 遍历所有火柴棒
            for (int k = 0; k < n; k++) {
                // 判断第k根火柴棒是否已经使用
                if ((s & (1 << k)) == 0) {
                    continue;
                }
                // 计算不使用第k根火柴棒的状态
                int s1 = s & ~(1 << k);
                // 状态转移方程
                if (dp[s1] >= 0 && dp[s1] + matchsticks[k] <= len) {
                    dp[s] = (dp[s1] + matchsticks[k]) % len;
                    break;
                }
            }
        }
        // 返回结果
        return dp[(1 << n) - 1] == 0;
    }
};

收集雨水

#hard 407. 接雨水 II - 力扣（LeetCode）本题的青春版：42. 接雨水 - 力扣（LeetCode）

已知一个m*n的二维数组，数组储存正整数，代表一个个单元的高度（立方体），将这些立方体想象成水槽，问，如果下雨这些立方体会有多少积水示例一

示例一：
输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
输出: 4
解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。

示例二

示例二：
输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
输出: 10

算法思路 想象水流从外层往里层流 case1: case2: 示例： 结构体的stl优先级队列

    struct Qitem{

       int x;

       int y;

       int h;

       Qitem(int x,int y, int h):x(x),y(y),h(h){  

       }

   };

   struct cmp{

       bool operator()(const Qitem &a,const Qitem &b){

           return a.h>b.h;

       }

   }

   int main(){

       std::priority_queue<Qitem,std::vector<Qitem>,cmp>Q;
       return 0;

   }

代码解决如下

class Solution {

    struct Qitem{//节点结构

        int x;

        int y;

        int h;

        Qitem(int x,int y, int h):x(x),y(y),h(h){  

        }

    };

    struct cmp{

        bool operator()(const Qitem &a,const Qitem &b){

            return a.h>b.h;

        }

    };

public:

    int trapRainWater(vector<vector<int>>& heightMap) {

        std::priority_queue<Qitem,std::vector<Qitem>,cmp> Q;//定义高度的优先级队列

        if(heightMap.size()<3||heightMap[0].size()<3){

            return 0; //无法积水

        }

        /*初始化优先级队列，即把周围所有的点都push进队列*/

        int row = heightMap.size();

        int column = heightMap[0].size();

        std::vector<std::vector<int> > mark;

        for(int i = 0;i<row;i++){

            mark.push_back(std::vector<int>());

            for(int j = 0;j<column;j++){

                mark[i].push_back(0);

            }

        }

        for(int i = 0;i<row;i++){

            Q.push(Qitem(i,0,heightMap[i][0]));//第一列

            mark[i][0] = 1;

            Q.push(Qitem(i,column -1 ,heightMap[i][column-1]));//最后一列

            mark[i][column - 1] = 1;

        }

        for(int i = 1 ;i<column;i++){

            Q.push(Qitem(0,i,heightMap[0][i]));//第一行

            mark[0][i] = 1;

            Q.push(Qitem(row -1 ,i,heightMap[row-1][i]));//最后一行

            mark[row - 1][i] = 1;

        }

        /*搜索代码*/

        static const int dx[] = {-1,1,0,0};

        static const int dy[]={0,0,-1,1};//方向数组

        int result = 0;//最终积水量

        while(!Q.empty()){

            int x = Q.top().x;

            int y = Q.top().y;

            int h = Q.top().h;

            Q.pop();//取出队列头部信息

            for(int i =0;i<4;i++){

                int newx = x+dx[i];//四个方向

                int newy = y+dy[i];

                if(newx <0||newx>=row||newy<0||newy>=column||mark[newx][newy]){

                    continue;//当新拓展的点超出边界或者已经加入队列

                }

                if(h>heightMap[newx][newy]){//如果当前的点高于拓展点

                    result +=h - heightMap[newx][newy];

                    heightMap[newx][newy] = h;

                }

                Q.push(Qitem(newx,newy,heightMap[newx][newy]));

                mark[newx][newy] =1 ;

            }

  
  

        }

        return result;

  
  
  

    }

};