每日5题Day19 - LeetCode 91 - 95

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

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

class Solution {public int numDecodings(String s) {int n = s.length();//注意我们dp的范围是n+1int[] 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;}//反转，先把要反转的部分的尾部指向nulltmp.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){//刚好到最后一位了，有四个部分的ipif(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);}}}//判断是否满足，方法类型是booleanprivate 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;}
}

---