LeetCode 91-95

91. Decode Ways

分析：

使用动态规划，dp[i] 代表到字符串索引i为止的字符串的解码方法数。
边界条件：比如只要s[0] != 0, dp[0] = 1。还需要在代码中体现出dp[-1] = 1。
转移方程

1. 若s[i] = '0'
         若s[i-1] = '1' 或 '2'，则dp[i] = dp[i-2]
         若s[i-1] != '1' 或 '2'， 则 return 0
2. 若'1' <= s[i] <= '6'
         若s[i-1] = '1' 或 '2'，则dp[i] = dp[i-1] + dp[i-2]
         若s[i-1] != '1' 或 '2'，则dp[i] = dp[i-1]
3. 若'7' <= s[i] <= '9'
         若s[i-1] = '1' ， 则dp[i] = dp[i-1] + dp[i-2]
         若s[i-1] != '1' ，则dp[i] = dp[i-1]

Java：

class Solution {
    public int numDecodings(String s) {
        if ("".equals(s) || s.charAt(0) == '0') {
            return 0;
        }
        int[] dp = new int[s.length()];
        dp[0] = 1;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == '0') {
                if (s.charAt(i - 1) == '0' || s.charAt(i - 1) >= '3') {
                    return 0;
                } else {
                    dp[i] = i - 2 >= 0 ? dp[i - 2] : 1;
                }
            } else if (s.charAt(i) >= '1' && s.charAt(i) <= '6') {
                if (s.charAt(i - 1) == '0') {
                    dp[i] = dp[i - 1];
                } else if (s.charAt(i - 1) >= '1' && s.charAt(i - 1) <= '2') {
                    dp[i] = (i - 2 >= 0 ? dp[i - 2] : 1) + dp[i - 1];
                } else {
                    dp[i] = dp[i - 1];
                }
            } else if (s.charAt(i) >= '7') {
                if (s.charAt(i - 1) == '1') {
                    dp[i] = (i - 2 >= 0 ? dp[i - 2] : 1) + dp[i - 1];
                } else {
                    dp[i] = dp[i - 1];
                }
            }
        }
        return dp[s.length() - 1];
    }
}

92. Reverse Linked List II

分析：

使用头插法，先找到mLeft和p，mLeft代表第m个结点左边的那一个结点，p代表第m个结点。
然后遍历n-m次，每次使用pNext记录p的下一个结点，将这个pNext头插到mLeft结点后面去，p指向pNext的下一个结点，pNext指向mLeft的下一个结点，然后把mLeft的下一个结点指向pNext。
遍历完之后就实现了反转。

Java：

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode mLeft = dummy, p = dummy.next;
        int count = 0;
        while (count < m - 1) {
            mLeft = mLeft.next;
            p = p.next;
            count++;
        }
        for (int i = 0; i < n - m; i++) {
            ListNode pNext = p.next;
            p.next = p.next.next;
            pNext.next = mLeft.next;
            mLeft.next = pNext;
        }
        return dummy.next;
    }
}

93. Restore IP Addresses

class Solution {
    List<String> res = new ArrayList<>();
    List<String> temp = new ArrayList<>();

    public void dfs(int begin, String s) {
        if (temp.size() > 4) {
            return;
        }
        if (begin == s.length() && temp.size() == 4) {
            StringBuilder sb = new StringBuilder();
            for (String str : temp) {
                sb.append(str + ".");
            }
            sb.deleteCharAt(sb.length() - 1);
            res.add(sb.toString());
        }

        for (int i = begin; i < begin + 3 && i < s.length(); i++) {
            String sub = s.substring(begin, i + 1);
            if (sub.length() > 1 && sub.charAt(0) == '0') {
                continue;
            }
            if (sub.length() == 3 && Integer.parseInt(sub) > 255) {
                continue;
            }
            temp.add(sub);
            dfs(i + 1, s);
            temp.remove(temp.size() - 1);
        }
    }

    public List<String> restoreIpAddresses(String s) {
        dfs(0, s);
        return res;
    }
}

94. 二叉树的中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}

95. 不同的二叉搜索树 II

class Solution {
    public List<TreeNode> helper(int start, int end) {
        List<TreeNode> res = new ArrayList<>();
        if (start > end) {
            res.add(null);
            return res;
        }
        for (int i = start; i <= end; i++) {
            List<TreeNode> left = helper(start, i - 1);
            List<TreeNode> right = helper(i + 1, end);
            for (TreeNode l : left) {
                for (TreeNode r : right) {
                    TreeNode root = new TreeNode(i);
                    root.left = l;
                    root.right = r;
                    res.add(root);
                }
            }
        }
        return res;
    }


    public List<TreeNode> generateTrees(int n) {
        if (n < 1) {
            return new ArrayList<>();
        }
        return helper(1, n);
    }
}