每一步向前都是向自己的梦想更近一步，坚持不懈，勇往直前！
第一题：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;
}
}