leetcode算法题解(Java版)-16-动态规划(单词包含问题)-阿里云开发者社区

开发者社区> kissjz> 正文

leetcode算法题解(Java版)-16-动态规划(单词包含问题)

简介: 碰到二叉树的问题,差不多就是深搜、广搜,递归那方面想想了,当然如果要考虑一下空间、时间,还需要进行剪枝和压缩处理。这题比较简单:判断两个树是否相等,可以递归的判断子树是否相等,最后找到边界条件就是是否都为空,都不为空时节点里面的值是否相等。
+关注继续查看

一、递归

题目描述

Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

思路

  • 碰到二叉树的问题,差不多就是深搜、广搜,递归那方面想想了,当然如果要考虑一下空间、时间,还需要进行剪枝和压缩处理。这题比较简单:判断两个树是否相等,可以递归的判断子树是否相等,最后找到边界条件就是是否都为空,都不为空时节点里面的值是否相等。

代码

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null){
           return true;
        }
        else if(p==null||q==null){
            return false;
        }
        else if(q.val!=p.val){
            return false;
        }
        else{
            return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
        }
    }
}

二、动态规划

题目描述

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s ="leetcode",
dict =["leet", "code"].
Return true because"leetcode"can be segmented as"leet code".

思路

  • dp的题目,写了几道了。核心无非就是确定dp数组和状态转移方程。这几道题都有明显的特点,那就是dp数组记录的就是所求的答案,所以答案一般都是dp[s.length()]这种形式的。
  • 有了上面的总结,再来看着道题目。要求一串字母是否可以由所给的字典中的单词拼出来,要求返回布尔型。那好,也同时提示我们了dp数组就是记录它的子串是否能满足要求,类型是布尔型:dp[i]表示的是s[0,i-1]这个子串能否满足要求。
  • dp[i]=dp[j]&&s[j,i]是否在字典中(0<=j<=i-1)

代码

import java.util.Set;

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        if(s==null||s.length()==0||dict==null||dict.size()==0){
            return false;
        }
        boolean [] dp = new boolean [s.length()+2];
        dp[0] = true;
        
        for(int i=1;i<=s.length();i++){
            for(int j=i-1;j>=0;j--){//从尾部扫描单词
                if(dp[j]==true&&dict.contains(s.substring(j,i))){
                    dp[i]=true;
                    break;
                }
                else{
                    dp[i]=false;
                }
            }
        }
        return dp[s.length()];
    }
}

三、深搜

题目描述

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s ="catsanddog",
dict =["cat", "cats", "and", "sand", "dog"].
A solution is["cats and dog", "cat sand dog"].

思路

  • 题目是上一道题的加强版,为了考察动态规划。感觉有点复杂,没想出来怎么在上一道的基础上改进。
  • 深搜可以解决问题!直接看代码了

代码

import java.util.ArrayList;
import java.util.Set;

public class Solution {
    public ArrayList<String> res = new ArrayList<>();
    public ArrayList<String> wordBreak(String s, Set<String> dict) {
         dfs(s,s.length(),dict,"");
        return res;
    }
    public void dfs(String s,int index,Set<String> dict,String temp){
        if(index==0){
            if(temp.length()>0){
                res.add(temp.substring(0,temp.length()-1));//如果写成res.add(temp)则末尾会多一个空格,小细节
            }
        }
        for(int i=index-1;i>=0;i--){
            if(dict.contains(s.substring(i,index))){
                dfs(s,i,dict,s.substring(i,index)+" "+temp);
            }
        }
    }
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
JAVA常见算法题(二十四)
package com.xiaowu.demo; //一个5位数,判断它是不是回文数。即12321是回文数,个位与万位相同,十位与千位相同。 public class Demo24 { public static void main(String[] args) { f2...
567 0
[leetcode/lintcode 题解]大厂算法面试高频题: 序列化和反序列N叉树
[leetcode/lintcode 题解]大厂算法面试高频题: 序列化和反序列N叉树
114 0
解决TCP网络传输“粘包”问题
当前在网络传输应用中,广泛采用的是TCP/IP通信协议及其标准的socket应用开发编程接口(API)。TCP/IP传输层有两个并列的协议:TCP和UDP。其中TCP(transport control protocol,传输控制协议)是面向连接的,提供高可靠性服务。
1140 0
[leetcode/lintcode 题解] 算法面试真题详解:给树浇水的时间
[leetcode/lintcode 题解] 算法面试真题详解:给树浇水的时间
73 0
JAVA常见算法题(十五)
package com.xiaowu.demo; /** * * 输入三个整数x,y,z,请把这三个数由小到大输出。 * * @author WQ * */ public class Demo15 { public static void main(String[] ar...
533 0
JAVA常见算法题(十七)
package com.xiaowu.demo; //输出九九乘法表。 public class Demo17 { public static void main(String[] args) { table(9); } /** * 我用白话文解释"\t"的意思是:在同一个缓冲区内横向跳8个空格,JDK1.
722 0
Ubuntu问题sudo: /etc/sudoers is mode 0640should be 0440的解决方法
Ubuntu问题sudo: /etc/sudoers is mode 0640, should be 0440的解决方法 以前一直使用Fedora系统,今天偶尔用了用Ubuntu Linux系统,感觉那个sudo有点很不适应啊。
649 0
+关注
kissjz
Keep It Simple , Stupid. 独立博客:白水东城(www.baishuidongcheng.com)
185
文章
44
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载