比 wordpress,网站seo优化有哪些方面,公交建设公司的官网,搜索引擎优化实训心得摘要#xff1a; 碰到二叉树的问题#xff0c;差不多就是深搜、广搜#xff0c;递归那方面想想了#xff0c;当然如果要考虑一下空间、时间#xff0c;还需要进行剪枝和压缩处理。这题比较简单#xff1a;判断两个树是否相等#xff0c;可以递归的判断子树是否相等…摘要 碰到二叉树的问题差不多就是深搜、广搜递归那方面想想了当然如果要考虑一下空间、时间还需要进行剪枝和压缩处理。这题比较简单判断两个树是否相等可以递归的判断子树是否相等最后找到边界条件就是是否都为空都不为空时节点里面的值是否相等。
一、递归题目描述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(pnullqnull){return true;}else if(pnull||qnull){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, givens leetcode,dict [leet, code]. Return true becauseleetcodecan be segmented asleet code.思路dp的题目写了几道了。核心无非就是确定dp数组和状态转移方程。这几道题都有明显的特点那就是dp数组记录的就是所求的答案所以答案一般都是dp[s.length()]这种形式的。有了上面的总结再来看着道题目。要求一串字母是否可以由所给的字典中的单词拼出来要求返回布尔型。那好也同时提示我们了dp数组就是记录它的子串是否能满足要求类型是布尔型dp[i]表示的是s[0,i-1]这个子串能否满足要求。dp[i]dp[j]s[j,i]是否在字典中(0ji-1)代码import java.util.Set;public class Solution {public boolean wordBreak(String s, SetString dict) {if(snull||s.length()0||dictnull||dict.size()0){return false;}boolean [] dp new boolean [s.length()2];dp[0] true;for(int i1;is.length();i){for(int ji-1;j0;j--){//从尾部扫描单词if(dp[j]truedict.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, givens 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 ArrayListString res new ArrayList();public ArrayListString wordBreak(String s, SetString dict) {dfs(s,s.length(),dict,);return res;}public void dfs(String s,int index,SetString dict,String temp){if(index0){if(temp.length()0){res.add(temp.substring(0,temp.length()-1));//如果写成res.add(temp)则末尾会多一个空格小细节}}for(int iindex-1;i0;i--){if(dict.contains(s.substring(i,index))){dfs(s,i,dict,s.substring(i,index) temp);}}}
}原文链接本文为云栖社区原创内容未经允许不得转载。
