天天看点
返回

力扣K神图解算法数据结构解析04

力扣K神图解算法数据结构点这里

四、搜索与回溯算法

  1. DFS，本质是递归
    • 递推参数
    • 终止条件
    • 递推工作
    • 回溯
  2. BFS，本质是队列 
    queue<int> que;
que.push(第一个参数);

while(!que.empty())
{	
    auto tmp = que.front();
    que.pop();
    if(终止条件) continue;
    //进行递推工作
	que.push(新的参数);
}
  3. 树的递归调用
    • 某函数既然可以递归调用root，那么也一定可以调用root->left和root->right，有时候只需要把任务分解成三部分即可，root节点，递归调用root->left，递归调用root->right
    • 树的遍历方式总体分为两类，DFS和BFS
      1. DFS，前序，中序，后序，其中中序是递增序列
      2. BFS，层序
  4. 剑指12，矩阵中的路径 
    //时间O(mn3^k)，空间O(k)
//标准dfs+剪枝，值得学习
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) 
    {
        //每个位置都要作为起点尝试一次
        for(int i=0;i<board.size();++i)
        {
            for(int j=0;j<board[0].size();++j)
            {
                if(dfs(i,j,0,board,word)) return true;
            }
        }
        return false;
    }

private:
 
    bool dfs(int i,int j,int k,vector<vector<char>>& board, string &word)
    {
        //如果越界或者字符不匹配
        if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size() 
        || board[i][j] != word[k]) return false;
        //执行到这步默认字符匹配，且是最后一个字符
        if(k == word.size()-1) return true;
        //递推工作，修改值
        board[i][j] = '\0';
        //如果有一条路径成功就返回
        auto res = dfs(i,j+1,k+1,board,word) || dfs(i,j-1,k+1,board,word) || 
                   dfs(i+1,j,k+1,board,word) || dfs(i-1,j,k+1,board,word);
        //回溯，恢复原状
        board[i][j] = word[k];
        //返回，很重要
        return res;
    }
};
  5. 剑指13，机器人的运动范围 
    //时间O(mn)，空间O(mn)
//标准dfs+剪枝，使用二维数组记录已访问过的位置
//注意，从左上到右下，只需关注右和下两个方向
class Solution {
public:
    int movingCount(int m, int n, int k) 
    {   
        vector<vector<int>> vec(m,vector<int>(n));
        return dfs(m,n,k,0,0,vec);
    }

private:
    int dfs(int m, int n, int k,int i, int j, vector<vector<int>> &vec)
    {   
        //如果越界，数位之和大于k，已访问过
        if(i >= m || j >= n || digitSum(i)+digitSum(j) > k || vec[i][j]) return 0;
        //标记
        vec[i][j] = 1;
        //递推
        return 1 + dfs(m,n,k,i,j+1,vec) + dfs(m,n,k,i+1,j,vec);
    }
    //数位之和
    int digitSum(int num)
    {
        int res = 0;
        int x;
        while(num)
        {
            x = num % 10;
            num /= 10;
            res += x;
        }
        return res;
    }
};


//时间O(mn)，空间O(mn)
//标准bfs+剪枝，使用二维数组记录已访问过的位置
//熟记bfs套路
class Solution {
public:
    int movingCount(int m, int n, int k) 
    {
        queue<pair<int,int>> que;
        que.push({0,0});
        int res = 0;
        vector<vector<int>> vec(m,vector<int>(n));

        while(!que.empty())
        {
            auto temp = que.front();
            que.pop();
            if(temp.first >= m || temp.second >= n || 							 			digitSum(temp.first)+digitSum(temp.second) > k ||
            vec[temp.first][temp.second]) continue;
            ++res;
            vec[temp.first][temp.second] = 1;
            que.push({temp.first,temp.second+1});
            que.push({temp.first+1,temp.second});
        }
        return res;
    }
    
private:
	//数位之和
    int digitSum(int num)
    {
        int res = 0;
        int x;
        while(num)
        {
            x = num % 10;
            num /= 10;
            res += x;
        }
        return res;
    }
};
  6. 剑指26，树的子结构 
    //时间O(mn)，空间O(m)
//总共分为两步，
//第一步，先序遍历node1,因为node2可能是node1中以任意节点开始的，isSubStructure
//第二步，查询以node1为根节点的树和以node2为根节点的树是否一致，dfs
class Solution {
public:
    bool isSubStructure(TreeNode* node1, TreeNode* node2) 
    {
        if(!node1 || !node2) return false;
        return dfs(node1,node2) || 
        isSubStructure(node1->left,node2) || 
        isSubStructure(node1->right,node2);
    }
private:
    bool dfs(TreeNode* node1, TreeNode* node2)
    {
        if(!node1 && node2 || 
        (node1 && node2 && node1->val != node2->val)) return false;
        if(!node1 && !node2 || node1 && !node2) return true;
        return dfs(node1->left,node2->left) && 
               dfs(node1->right,node2->right);
    }
};
  7. 剑指27，二叉树的镜像 
    //时间O(n)，空间O(n)
//无论是写在一个函数中，还是再使用一个recur函数都是可以的
//首先要明白这整个函数是干嘛的，调用它的左子树，右子树会起到什么样的效果
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) 
    {
        if(!root) return nullptr;
        auto p = root->right;
        root->right = mirrorTree(root->left);
        root->left = mirrorTree(p);
        return root;
    }
};
  8. 剑指28， 对称的二叉树 
    //时间O(n)，空间O(n)
//recur函数好难想出来
class Solution {
public:
    bool isSymmetric(TreeNode* root) 
    {
        if(!root) return true;
        return recur(root->left,root->right);
    }
private:
    //该函数用来判断以root1和root2为根节点的两棵子树是否对称
    bool recur(TreeNode* root1,TreeNode* root2)
    {
        if(!root1 && !root2) return true;
        if(!root1 && root2 || root1 && !root2 ||
        root1->val != root2->val) return false;
        return recur(root1->left,root2->right) &&
               recur(root1->right,root2->left);
    }
};
  9. 剑指32，从上到下打印二叉树1 
    //时间O(n)，空间O(n)
//bfs基础题目
class Solution {
public:
    vector<int> levelOrder(TreeNode* root) 
    {
        if(!root) return {};
        vector<int> res;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty())
        {
            auto p = que.front();
            que.pop();
            if(!p) continue;
            res.push_back(p->val);
            que.push(p->left);
            que.push(p->right);
        }
        return res;
    }
};
  10. 剑指32，从上到下打印二叉树2 
//时间O(n)，空间O(n)
//基于上一题目，需要加上循环控制，有几个细节需要注意下
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>> res;
        if(!root) return res;
        queue<TreeNode*> que;
        que.push(root);

        while(!que.empty())
        {
            int num = que.size();
            vector<int> vec;
            for(int i=0;i<num;++i)
            {
                auto p = que.front();
                que.pop();
                if(!p) continue;
                vec.push_back(p->val);
                que.push(p->left);
                que.push(p->right);
            }    
            if(!vec.empty()) res.push_back(vec);
        }
        return res;
    }
};
  1. 剑指32，从上到下打印二叉树3 
    //时间O(n)，空间O(n)
//使用flag标志奇偶层即可，唯一不足是需要reverse
//进一步简化可以将奇偶层分开，不需要reverse
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>> res;
        if(!root) return res;
        queue<TreeNode*> que;
        que.push(root);
        int flag = 0;

        while(!que.empty())
        {
            ++flag;
            int num = que.size();
            vector<int> vec;
            for(int i=0;i<num;++i)
            {
                auto p = que.front();
                que.pop();
                if(!p) continue;
                vec.push_back(p->val);
                que.push(p->left);
                que.push(p->right);
            }    
            if(!vec.empty()) 
            {
                if(flag % 2 == 0) reverse(vec.begin(),vec.end());
                res.push_back(vec);
            }
        }
        return res;
    }
};
  2. 剑指34，二叉树中和为某一值的路径 
    //时间O(n)，空间O(n)
//标准dfs，虽然知道每一步顺序大概是什么，但总是因为一些细节出问题
//需要好好思考下，基础还是不够扎实
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int target) 
    {
        dfs(root,target);
        return res;
    }
private:
    vector<vector<int>> res;
    //为什么vec用全局变量而不用函数传参？因为就算是一条真的路径最后也会进行回溯
    //调用pop_back，所以一个全局变量足矣
    vector<int> vec;
    void dfs(TreeNode* root, int target)
    {
        //终止条件没有想的那么复杂
        if(!root) return;
        vec.push_back(root->val);
        //更新target，就算为负也无妨，
        target -= root->val;
        //添加路径
        if(!target && !root->left && !root->right)
        {
            res.push_back(vec);
        }
        //先序遍历
        dfs(root->left,target);
        dfs(root->right,target);
        //回溯，很重要，target不需要回溯
        vec.pop_back();
    }
};
  3. 剑指36，二叉搜索树与双向链表 
    //时间O(n)，空间O(n)
//牢记，中序遍历是升序排列，无非是在中序遍历的基础上增加了其他东西
//三个关键点
//1.中序遍历是升序排列
//2.构建pre和cur的双向指向
//3.对于头尾节点，特殊关照
//以下是中序遍历标准格式
void recur(Node* root) 
{
	if(!root) return;
    recur(root->left);
    cout<<root->val<<endl;
    recur(root->right);
}
/************************************************************************************/
class Solution {
public:
    Node* treeToDoublyList(Node* root) 
    {
        if(!root) return nullptr;
        //pre初始化
        pre = nullptr;
        //中序遍历，构建双向链表
        recur(root);
        //加上头尾，构建双向循环链表
        //pre最后会指向尾节点
        head->left = pre;
        pre->right = head;
        //返回头指针
        return head;
    }

private:
    Node* pre;
    Node* head;
    void recur(Node* cur) 
    {
        //终止条件
        if(!cur) return;
        //中序遍历，升序排列
        recur(cur->left);
        //根据pre指针判断head
        if(!pre) head = cur;
        else if(pre) 
        {
            //构建双向指向
            pre->right = cur;
            cur->left = pre;
        }
        //更新pre，cur无需更新，其会随着recur函数调用自动更新
        pre = cur;
        recur(cur->right);
    }
};
  4. 剑指37，序列化二叉树 
    //时间O(n)，空间O(n)，这两个函数时间复杂度和空间复杂度均为O(n)，O(n)
//序列化和反序列化均使用层序遍历，所以说，层序遍历才是YYDS
//序列化的关键点
//1.层序遍历所有节点，将其值放在string中，其中null也要加入string中
//2.注意返回值string的格式，逗号分割，

//反序列化的关键点
//1.将string转成vector<string>，便于下一步查找左右子树的val，如果改接口，可省略此步骤
//2.层序遍历建立整棵树，不断构建当前节点和其左子树和右子树的关系，该入队就入队
//3.如何根据当前节点找到左子树节点和右子树节点的值很关键，重点是变量i的理解，i是非null节点的索引，根据k神所讲，left=2(m-n)+1,right=2(m-n)+2,这里无需求m-n，直接用i代替，i=m-n，另外，k神，YYDS
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) 
    {
        //root为空直接返回，不加中括号，否则下面还要处理，无意义
        if(!root) return "";
        string s;
        queue<TreeNode*> que;
        //层序遍历基本操作
        que.push(root);
        while(!que.empty())
        {
            TreeNode* p = que.front();
            que.pop();
            //如果节点为null，不再push左右子节点，将null加入字符串
            if(!p) s.append("null,");
            else
            {
                //节点非null，push左右子节点，将null加入字符串
                //使用逗号分割，空格也可以，下面统一处理
                s.append(to_string(p->val));
                s.append(",");
                que.push(p->left);
                que.push(p->right);
            }
        }
        return s;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string s) 
    {
        //如果s为空，直接返回nullptr
        if(s.empty()) return nullptr;
        //很重要，将string用逗号分隔开，放进vector<string>里面
        //便于下一步查找，其实这一步可以省略，不过需要改两个函数
        //的参数，serialize的返回值，deserialize的形参，
        //改为vector<string>类型的，会方便很多
        vector<string> res = spilit(s,',');
        
        //new root节点
        TreeNode* root = new TreeNode(stoi(res[0]));
        queue<TreeNode*> que;
        que.push(root);
        //i表示所有非null节点的序号，k神讲过
        //i=m-n，因此，left=2(m-n)+1,可以简化成left=2i+1
        int i = 0;
        //层序遍历基本操作
        while(!que.empty())
        {
            TreeNode* p = que.front();
            que.pop();

            //左子树
            //判断左子树是否为空，否的话，new节点，入队
            if(res[2*i+1] == "null") 
            {
                p->left = nullptr;
            }
            else{
                p->left = new TreeNode(stoi(res[2*i+1]));
                que.push(p->left);
            }

            //右子树
            //判断右子树是否为空，否的话，new节点，入队
            if(res[2*i+2] == "null") 
            {
                p->right = nullptr;
            }
            else{
                p->right = new TreeNode(stoi(res[2*i+2]));
                que.push(p->right);
            } 
            //i是连续的，因此每过一个非null节点就+1
            ++i;
        }
        return root;
    }
private:
    //spilit
    //将字符串函数，字符串函数中用symbol隔开各个元素，中各个元素
    //装进vector<string>中，因为没找到相关库函数，只能自己实现
    //使用双指针
    vector<string> spilit(string s,char symbol)
    {
        if(s.empty()) return {};
        vector<string> res;
        int i = 0;
        int j = 0;
        while(i < s.size())
        {
            while(j < s.size() && s[j] != symbol) ++j;
            res.push_back(s.substr(i,j-i));
            ++j;
            i=j;
        }
        return res;
    }
};
  5. 剑指38，字符串的排列 
    //时间复杂度和空间复杂度挺麻烦的
//这个题是真的草，标准的dfs
//有几点需要注意
//1.通过swap来实现数据的固定，x为固定位置，swap(s[x],s[i]);i属于[x,s.size()-1]
//2.去重第一必须想到哈希表
//3.递归即固定下一个位置
//4.勿忘回溯，很重要
class Solution {
public:
    vector<string> permutation(string s) 
    {
        dfs(s,0);
        return res;
    }
private:
    vector<string> res;
    void dfs(string s,int x)
    {
        //终止条件，所有位都已固定，0 - s.size()-1
        if(x == s.size()-1)
        {
            res.push_back(s);
            return;
        }
        //哈希表去重
        unordered_set<int> ss;
        //将固定位之后的数据(包括固定位)都依次放到固定位上
        for(int i=x;i<s.size();++i)
        {
            //如果重复就跳过
            if(ss.find(s[i]) != ss.end()) continue;
            //插入哈希表
            ss.insert(s[i]);
            //通过交换来实现固定数据
            swap(s[i],s[x]); 
            //递推，固定下一位
            dfs(s,x+1);
            //回溯
            swap(s[i],s[x]);
        }
    }
};
  6. 剑指54，二叉搜索树的第K大节点 
    //时间O(n)，空间O(n)
//牢记一点，二叉搜索树中序遍历为递增序列，中序遍历倒叙为递减序列
//因此，其为找中序遍历倒叙的第k个节点
class Solution {
public:
    int kthLargest(TreeNode* root, int k) 
    {
        recur(root,k);
        return res;
    }
private:
    int cnt = 0;
    int res;
    void recur(TreeNode* root, int k) 
    {   
        if(!root) return;
        recur(root->right,k);
        ++cnt;
        if(cnt == k)
        {
            res = root->val;
            return;
        }
        recur(root->left,k);
    }
};
  7. 剑指55，二叉树的深度 
    //时间O(n)，空间O(n)
//可以使用dfs/bfs
class Solution {
public:
    int maxDepth(TreeNode* root) 
    {
        if(!root) return 0;
        return 1 + max(maxDepth(root->left),maxDepth(root->right));
    }
};
  8. 剑指55，平衡二叉树 
    //时间O(nlogn)，空间O(n)
//此方法最容易想到，先序遍历+判断深度，从顶至底
class Solution {
public:
    bool isBalanced(TreeNode* root) 
    {
        if(!root) return true;
        bool tmp = abs(recur(root->left)-recur(root->right)) <= 1 ? true : false;
        return tmp && isBalanced(root->left) && isBalanced(root->right);
    }
private:
    int recur(TreeNode* root) 
    {
        if(!root) return 0;
        return 1+max(recur(root->left),recur(root->right));
    }
};
  9. 剑指64，1+2+…+n 
    //时间O(n)，空间O(n)
//首先必须是递归，因此n+sumNums(n-1)必不可少
//其次是&&的应用
//最后终止条件判断
//这题真草啊
class Solution {
public:
    int sumNums(int n) 
    {
        n && (n += sumNums(n-1));
        return n;
    }
};
  10. 剑指68，二叉搜索树的最近公共祖先 
    //时间O(n)，空间O(1)
//此题使用二分法最为简单，只要将p,q分开即可得到最近公共祖先
//那么我们利用二叉搜索树的特点，左子树小于根节点，右子树大于根节点，不断进行二分
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        //p,q必存在，因此必然能找到最近公共祖先
        while(true)
        {
            //其实是不断进行二分的过程
            //如果p,q在root左边
            if(root->val > p->val && root->val > q->val)
            {
                root = root->left;
            }
            //如果p,q在root右边
            else if(root->val < p->val && root->val < q->val)
            {
                root = root->right;
            }
            //二分成功，得到最近公共祖先
           	//p,q分异两侧，或p,q之一是root
            else break;
        }
        return root;    
    }
};


//时间O(n)，空间O(n)
//递归，分为三种情况,p,q都在左子树中，p,q都在右子树中，其他(即root为最近公共祖先)
//首先明确函数传入root会得出什么样的结果
//然后传入root->left，root->right分别会得出什么样的结果
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        if(root->val > p->val && root->val > q->val)
        {
            return lowestCommonAncestor(root->left,p,q);
        }
        else if(root->val < p->val && root->val < q->val)
        {
            return lowestCommonAncestor(root->right,p,q);
        }
        else return root;
    }
};
  11. 剑指68，二叉树的最近公共祖先 
    //时间O(n)，空间O(n)
//先序遍历进行递归+四种情况分类讨论
class Solution {
public:
    TreeNode* lowestCommonAncestor
    (TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        if(!root) return nullptr;
        //如果恰好是p,q，直接返回，返回值给了上一级left/right
        if(root == p || root == q) return root;
        //先序遍历
        auto left = lowestCommonAncestor(root->left,p,q);
        auto right = lowestCommonAncestor(root->right,p,q);.
        //四种情况分类讨论
        if(!left && !right) return nullptr;
        else if(left && right) return root;
        else if(left && !right) return left;
        else if(!left && right) return right;
        return nullptr;
    }
};
图解算法数据结构 数据结构 算法 力扣 剑指offer
上一篇: jdbc 中execute、executeQuery和executeUpdate之间的区别 （转载）
下一篇: 可单例开发、典型的教科书式的mvc构架----springmvc----day02（五）

继续阅读