每日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  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 res = new ArrayList();
    List path = new LinkedList();
    public List 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  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 res = new LinkedList();
    public List 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 generateTrees(int n) {
        if (n == 0) {
            return new ArrayList();
        }
        return generateTrees(1, n);
    }

    private List generateTrees(int start, int end) {
        List trees = new ArrayList();
        if (start > end) {
            trees.add(null);
            return trees;
        }
        for (int i = start; i <= end; i++) {
            List leftSubtrees = generateTrees(start, i - 1);
            List 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;
    }
}