[数据结构与算法]2021-07-23力扣day23

139.单词拆分

    public boolean wordBreak(String s, List<String> wordDict) {
        //背包问题
        int len = s.length(), maxw = 0;
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        Set<String> set = new HashSet();
        for(String str : wordDict){
            set.add(str);
            maxw = Math.max(maxw, str.length());
        }
        //往前找时只需要找到最大字符串长度即可
        for(int i = 1; i <= len; i++){
            for(int j = i; j >= 0 && j >= i - maxw; j--){
                if(dp[j] && set.contains(s.substring(j, i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }

101. 对称二叉树

    public boolean isSymmetric(TreeNode root) {
        return isMirror(root,root);
    }
    private boolean isMirror(TreeNode t1,TreeNode t2){
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        return (t1.val==t2.val)&&isMirror(t1.right, t2.left)&& isMirror(t1.left, t2.right);
    }

102. 二叉树的层序遍历

        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<>();
            if (root == null) {
                return res;
            }
            Deque<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                List<Integer> list = new ArrayList<>();
                for (int i = queue.size(); i > 0; i--) {
                    TreeNode t = queue.remove();
                    list.add(t.val);
                    if (t.left != null) {
                        queue.add(t.left);
                    }
                    if (t.right != null) {
                        queue.add(t.right);
                    }
                }
                //将临时list加入最终返回结果中
                res.add(list);
            }
            return res;
        }

103. 二叉树的锯齿形层序遍历

在102的基础上反转即可

 public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<>();
            if (root == null) {
                return res;
            }
            Deque<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            boolean flag=false;//判断在哪一层
            while (!queue.isEmpty()) {
                List<Integer> list = new ArrayList<>();
                for (int i = queue.size(); i > 0; i--) {
                    TreeNode t = queue.remove();
                    list.add(t.val);
                    if (t.left != null) {
                        queue.add(t.left);
                    }
                    if (t.right != null) {
                        queue.add(t.right);
                    }
                }
                if(flag)Collections.reverse(list);
                flag=!flag;
                //将临时list加入最终返回结果中
                res.add(list);
            }
            return res;
        }

104. 二叉树的最大深度

         public int maxDepth(TreeNode root) {
            if(root==null)return 0;
            return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
        }