R语言 Zookeeper安装 VR全景图片 Filter Opencv webserver scroll linktosql ionic framework bootstrap管理系统模板 ios视频教程 matlab取绝对值 xshell搭建ss svn查看历史版本 python生成随机数 python中的map函数 java教材 java基础编程 javafloat java平台 java时间戳转换 路由器有辐射吗 小米5c拆机 字幕提取 pr时间轴 lrc软件 edquota 文字图片制作 兽之祝福 excel后缀 淘新闻下载 linux添加用户 x怎么截图 凯立德地图包下载 剑三小诺 在线转码 魔兽40m补丁 ps图层旋转 海思和麒麟哪个好 ps操控变形怎么用
当前位置: 首页 > 学习教程  > 编程语言

leetcode 95. Unique Binary Search Trees II、140. Word Break II(自顶向下解决问题)

2020/10/8 20:25:30 文章标签:

文章目录思考自顶向下解决问题的模式95. Unique Binary Search Trees题目链接题意思路140. Word Break II题目链接题意思路思考自顶向下解决问题的模式 95. Unique Binary Search Trees 题目链接 leetcode 95. Unique Binary Search Trees 题意 给定一个整数n,…

文章目录

        • 思考自顶向下解决问题的模式
        • 95. Unique Binary Search Trees
          • 题目链接
          • 题意
          • 思路
        • 140. Word Break II
          • 题目链接
          • 题意
          • 思路

思考自顶向下解决问题的模式

95. Unique Binary Search Trees

题目链接

leetcode 95. Unique Binary Search Trees

题意

给定一个整数n,输出把1到n所有值作为树结点的所有可能的二叉搜索树的组合。

思路

二叉搜索树的定义:左边结点的值 < 根节点的值 < 右边结点的值。那么根据根节点的不同,1到n的所有值尽可能作为根节点。这里我们不妨假设k(1<=k<=n)为某一颗二叉搜索树的根节点。那么左子树的根节点的可能值为[1,k-1],右子树的根节点的所有可能值为[k+1,n]。

难点在于怎么在[1,k-1],[k+1,n]继续遍历子树的所有左右子树,直接列举所有情况显然是不现实的,这时候我们采用自顶向下的思想,将[1,k-1],[k+1,n]的所有情况放在栈(存储子问题用到的临时变量)中,最后逐步合并所有可能的情况即可。

class Solution {
public:
    //分治算法
    vector<TreeNode*> generateTrees(int n){
        vector<TreeNode*> ans;
        if(n==0) return ans;
        
        return solve(1,n);
    }
    
    vector<TreeNode*> solve(int l,int r){
        vector<TreeNode*> ans;//通过栈区的临时变量存储左右根节点的信息
        if(l>r){
            ans.push_back(NULL);
            return ans;
        }
        
        for(int i=l;i<=r;i++){
            // TreeNode* root=new TreeNode(i);
            vector<TreeNode*> left=solve(l,i-1);
            vector<TreeNode*> right=solve(i+1,r);
            
            //自顶向下思考问题
            for(TreeNode * le: left){
                for(TreeNode *ri:right){
                    
                    TreeNode* root=new TreeNode(i);
                    
                    root->left=le;
                    root->right=ri;
                    
                    ans.push_back(root);//存储子问题的所有可能状态
                }
            }
                
        }
        
        return ans;
    }
    

140. Word Break II

题目链接

leetcode 140. Word Break II

题意

给定一个字典,判断一个字符串能被断句成多少种可能的情况

思路
  1. 首先利用一个set保存词典里面所有出现的词,这样在后续断句的时候能以O(1)的复杂度判断单词是否在词典中
  2. 然后就是断句,给定一个字符串s = “catsanddog”,给定词典 wordDict = [“cat”, “cats”, “and”, “sand”, “dog”],如何寻求所有可能的断句方式?我们可以采用类似上面一题的思想,将这个单词先分成左右两部分,比如将s分成"cat"和"sanddog",那么原问题就变成判断"cat"是否在词典wordDict中,以及"sanddog"的子字符串是否在词典中,这样依次类推下去。
  3. 对于本题还要采用记忆化搜索剪枝(用一个map存储一下已经遍历字符串的结果),避免右边部分字符串的子问题反复判断是否在词典中
class Solution {
public:
    //好题
    //学习自顶向下思考问题的模式
    
    //给定词库 给样例单词做分词
    //暴力O(N^2M)
    //如何高效判断单词的匹配是否正确
    //怎么确定分词位置?
    
    //与判断不同类型的二叉树的题 处理方法比较类似  有点自顶向下的思想
    //新建一个vector 然后从初始点一步步包括子问题
    
    unordered_map<string,vector<string>> ump;//记忆化搜索 剪枝
    
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        vector<string> ans;
        
        if(!s.size() || !wordDict.size()) return ans;
        
        set<string> S;
        
        for(string str:wordDict){
            if(!S.count(str)){
                S.insert(str);
            }
        }
        
        return solve(s,S);
    }
    
    bool Containr(set<string> S,string str){
        
        for(int i=1;i<=str.size();i++){
            string tmp=str.substr(0,i);
            if(S.count(tmp)) return true;
        }
        return false;
    }
    
    vector<string> solve(string s, set<string> S){
        //记忆化搜索
        if(ump.count(s)) return ump[s];
        
        vector<string> ans;//自顶向下,ans放在栈中,存放临时变量
        
        if(S.count(s)) ans.push_back(s);//全部包含 单独处理
        
        for(int i=1;i<s.size();i++){//长度
            
            string left=s.substr(0,i);
            string right=s.substr(i);
            
            if(S.count(left) && Containr(S,right) ){//左边包含 右边也有可能包含
                
                //子问题
                for(string r: solve(right,S)){//仅仅右边字符串 符合情况的所有字符串情况
                    ans.push_back(left+" "+r);
                }
            }
        }
        
        //存储已经找过的字符串
        ump[s]=ans;
        
        return ans;
    }
};

本题思路参考:https://leetcode.com/problems/word-break-ii/discuss/44179/Slightly-modified-DP-Java-solution


本文链接: http://www.dtmao.cc/news_show_250283.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?