每日5题Day19 - LeetCode 91 - 95

每一步向前都是向自己的梦想更近一步，坚持不懈，勇往直前！

第一题：91. 解码方法 - 力扣（LeetCode）

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        //注意我们dp的范围是n+1
        int[] dp = new int[n + 1];
        //初始条件，为什么是dp[0] = 1，因为我们转移方程中dp[i]与dp[i-1]有关
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            //如果是0就不管了
            if (s.charAt(i - 1) != '0') {
                dp[i] += dp[i - 1];
            }
            //看连续两位组成的数是否在[0,25]中
            if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
}

第二题：92. 反转链表 II - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1, head);
        ListNode l = dummy, r = dummy;
        int ll = left, rr = right;
        while(ll - 1 > 0){
            l = l.next;
            ll--;
        }
        //找到第left - 1个位置
        ListNode cur = l.next;
        //找到第right + 1个位置
        while(rr + 1 > 0){
            r = r.next;
            rr--;
        }
        ListNode tmp = cur;
        for(int i = 0; i < right - left; i++){
            tmp = tmp.next;
        }
        //反转，先把要反转的部分的尾部指向null
        tmp.next = null;
        ListNode end = cur, pre = null;
        while(cur != null){
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        l.next = pre;
        end.next = r;
        return dummy.next;
    }
}

第三题：93. 复原 IP 地址 - 力扣（LeetCode）

class Solution {
    List<String> res = new ArrayList<>();
    List<String> path = new LinkedList<>();
    public List<String> restoreIpAddresses(String s) {
        traversal(0, s);
        return res;
    }

    private void traversal(int start, String s){
        //刚好到最后一位了，有四个部分的ip
        if(path.size() == 4 && start == s.length()){
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < 3; i++){
                sb.append(path.get(i)).append('.');
            }
            sb.append(path.get(3));
            res.add(new String(sb));
            return;
        }
        //注意判断条件，对于当前位置，每次都是之后的0至2位组合能不能满足条件
        for(int i = 1;  i <= 3 && start + i <= s.length(); i++){
            //注意substring是左开右闭
            String part = s.substring(start, start + i);
            if(isValid(part)){
                path.add(part);
                traversal(start + i, s);
                path.remove(path.size() - 1);
            }
        }
    }
    //判断是否满足，方法类型是boolean
    private boolean isValid(String s){
        if(s.length() > 1 && s.charAt(0) == '0'){
            return false;
        }
        int num = Integer.parseInt(s);
        return num >= 0 && num < 256;
    }
}

第四题：94. 二叉树的中序遍历 - 力扣（LeetCode）

/**
 * 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 {
    List<Integer> res = new LinkedList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        //注意返回类型
        if(root == null){
            return new ArrayList<>();
        }
        //先左边
        inorderTraversal(root.left);
        //左边都结束了，把中间值放进去
        res.add(root.val);
        //走右边
        inorderTraversal(root.right);
        //三个方向都做过了，所以我们返回结果
        return res;
    }
}

 第五题：95. 不同的二叉搜索树 II - 力扣（LeetCode）

class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        return generateTrees(1, n);
    }

    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> trees = new ArrayList<>();
        if (start > end) {
            trees.add(null);
            return trees;
        }
        for (int i = start; i <= end; i++) {
            List<TreeNode> leftSubtrees = generateTrees(start, i - 1);
            List<TreeNode> rightSubtrees = generateTrees(i + 1, end);
            for (TreeNode left : leftSubtrees) {
                for (TreeNode right : rightSubtrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    trees.add(root);
                }
            }
        }
        return trees;
    }
}