头像

wyyang


访客:478

离线:2小时前


活动打卡代码 LeetCode 91. 解码方法

wyyang
2小时前
class Solution {
    public int numDecodings(String s) {
        // acw 类似于青蛙跳楼梯。dp[i] 表示长度为i的串所能表示的个数。dp[i] = dp[i - 1] + dp[i - 2]
        // 条件是 s[i]范围在1-9 , 或s[i-1]*10 + s[i] 在10 - 26范围内
        int length = s.length();
        s = " " + s;
        int[] dp = new int[length + 1];
        dp[0] = 1;
        for (int i = 1; i <= length; i++) {
            if (s.charAt(i) - '0' > 0 && s.charAt(i) - '0' <= 9 ) dp[i] += dp[i - 1];
            if (i > 1 && ((s.charAt(i - 1) - '0') * 10 + (s.charAt(i) - '0')) >= 10 && ((s.charAt(i - 1) - '0') * 10 + (s.charAt(i) - '0')) <= 26) dp[i] += dp[i - 2];
        }

        return dp[length];
    }
}



wyyang
1天前
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        // acw 中序遍历是有序的树就是二叉搜索树,是等价的关系
        // 要求高度差绝对值 不超过1,所以根取mid。
        return build(nums, 0, nums.length - 1);
    }

    TreeNode build(int[] nums, int l, int r) {
        if (l > r) return null;
        int mid = (l + r) >> 1;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(nums, l, mid - 1);
        root.right = build(nums, mid + 1, r);

        return root;
    }
}



wyyang
1天前
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        // acw 跟正常的层序遍历一样,区别是偶数层的结果要反转一下,然后再插到最终结果中
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int cnt = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> tmpRes = new ArrayList<>();
            while (size-- > 0) {
                TreeNode t = queue.poll();
                tmpRes.add(t.val);
                if (t.left != null) queue.offer(t.left);
                if (t.right != null) queue.offer(t.right);
            }

            if (++cnt % 2 == 0) Collections.reverse(tmpRes);
            res.add(tmpRes);
        }

        return res;
    }
}



wyyang
1天前
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        // acw 正常层序遍历,然后将结果反转一下就可以了
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> tmpRes = new ArrayList<>();
            while (size-- > 0) {
                TreeNode t = queue.poll();
                tmpRes.add(t.val);
                if (t.left != null) queue.offer(t.left);
                if (t.right != null) queue.offer(t.right);
            }

            res.add(tmpRes);
        }

        Collections.reverse(res);
        return res;
    }
}


活动打卡代码 LeetCode 101. 对称二叉树

wyyang
1天前
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true; 
        return dfs(root.left, root.right);
    }

    boolean dfs(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null || left.val != right.val) return false;
        // acw 递归判断左子树的左儿子和右子树的右儿子, 左子树的右儿子和右子树的左儿子是否也相等
        return dfs(left.left, right.right) && dfs(left.right, right.left);
    }
}


活动打卡代码 LeetCode 100. 相同的树

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

        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}



wyyang
1天前
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    long preVal = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        // acw 中序遍历其是有序的。preVal保存前一个值
        if (!isValidBST(root.left)) return false;
        if (root.val <= preVal) return false;
        preVal = root.val;
        if (!isValidBST(root.right)) return false;
        return true;
    }
}



wyyang
2天前
class Solution {
    public int numTrees(int n) {
        // acw 两种方法,这一个卡特林数,直接用数学求解出来。
        // 递归求解,枚举根结点的位置从1 - n, dp[i] 表示以长度为i为二叉搜索树的数量,dp[i] = 左子树的数量 X 右子树的数量
        // 子树的长度 j 从1 - i - 1 和 i + 1 - n 对应dp[j - 1 - 1 + 1] 即dp[j - 1] 和dp[i - (j + 1) + 1] 即dp[i - j]
        // 累加所有子树数量。计算出dp[i]
        int[] dp = new int[n + 1];
        dp[0] = 1;
        // 枚举每个根结点
        for (int i = 1; i <= n; i++) {
            // 左右子树的长度范围
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        return dp[n];
    }
}



wyyang
2天前
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) return new ArrayList<>();
        // acw 二叉搜索树的中序遍历是有序的。根节点可以取1 -n 中任意一个,记为k,则其构成的子树数量是左子树l - k-1可以构成的数量乘以右子树
        // k + 1 - r构成子树的数量。
        return dfs(1, n);
    }

    List<TreeNode> dfs(int l, int r) {
        List<TreeNode> res = new ArrayList<>();
        if (l > r) {
            res.add(null);
            return res;
        }

        // 遍历并构造每个根结点
        for (int i = l; i <= r; i++) {
            // 递归构造左右子树
            List<TreeNode> leftTree = dfs(l, i - 1);
            List<TreeNode> rightTree = dfs(i + 1, r);
            for (TreeNode lt : leftTree) {
                for (TreeNode rt : rightTree) {
                    TreeNode root = new TreeNode(i);
                    root.left = lt;
                    root.right = rt;
                    res.add(root);
                }
            }

        }

        return res;
    } 
}



wyyang
3天前
迭代方法:
class Solution {
    List<Integer> res = new ArrayList<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) return Collections.emptyList();
        inorderTraversal(root.left);
        res.add(root.val);
        inorderTraversal(root.right);

        return res;
    }
}