反转链表Ⅱ
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
分析：
这种题实现的方法可能比较多，但是我这里使用头插法去实现。m-n范围内进行反转，那么只需要将这部分的链表顺序头插在m-1位的后面即可。后面再拼接起来。
防止m包含头部，可以引入一个头节点进行处理。在具体的处理上可能有点繁琐，因为头插的时候遍历这个节点插入要改变结构，要在插入前将后侧nextNode存储下来下次使用。
具体实现代码为：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { ListNode value=new ListNode(0);//头节点 value.next=head; ListNode team=value;//临时节点 int index=1;//记录标记 while (index<m) { team=team.next; index++; } //team 后面需要头插 ListNode tail=team.next;//m节点，最后会在最后 ListNode node=team.next; while (index<=n) { ListNode nextNode=node.next;//先储存右侧节点 node.next=team.next;//插入第一步。将自己右侧指向 team.next=node;//插入第二步，前面team指过来 node=nextNode; index++; } tail.next=node; //逆置的链表和后面节点连接 return value.next; } }
复原ip地址
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
例如：“0.1.2.201” 和 “192.168.1.1” 是 有效的 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效的 IP 地址。
示例 1：
输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000" 输出：["0.0.0.0"]
示例 3：
输入：s = "1111" 输出：["1.1.1.1"]
示例 4：
输入：s = "010010" 输出：["0.10.0.10","0.100.1.0"]
示例 5：
输入：s = "101023" 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
0 <= s.length <= 3000 s 仅由数字组成
分析
本题的话是一种典型的回溯算法，不过这题剪枝的方法非常重要，否则会产生很多不必要的计算。
不考虑其他条件，其实就是要枚举所有的划分方式，然后分成4份、每个数字满足条件，且刚好用完所有数字。而本题设计递归函数的时候，可以带上当前index和当前数字数量进行向下递归，且向下的时候要注意数字大小在0-255且0不能做其他数字前缀。另外还可以进行其他剪枝(从字符剩余数量判断能否组成答案每位1-3位)。
具体代码为：
class Solution { public List<String> restoreIpAddresses(String s) { List<String>list=new ArrayList<String>(); List<String>value=new ArrayList<String>(); char ch[]=s.toCharArray(); dfs(value,list,ch,0,0); return value; } private void dfs(List<String> value, List<String> list, char[] ch, int index, int num) { // TODO Auto-generated method stub if(num==4&&index==ch.length) { StringBuilder sBuilder=new StringBuilder(); sBuilder.append(list.get(0)); for(int i=1;i<4;i++) { sBuilder.append('.'); sBuilder.append(list.get(i)); } value.add(sBuilder.toString()); } else if(num==4||index>=ch.length) return; else { if((4-num)*3<ch.length-index-1||ch.length-index<4-num)//剩下的已经不可能 { return; } else if (ch[index]=='0') { list.add("0"); dfs(value, list, ch, index+1, num+1); list.remove(list.size()-1); } else { StringBuilder sBuilder=new StringBuilder(); for(int i=0;i<3&&index+i<ch.length;i++) { sBuilder.append(ch[index+i]); if(i==2&&Integer.parseInt(sBuilder.toString())>255) return; list.add(sBuilder.toString()); dfs(value, list, ch, index+i+1, num+1); list.remove(list.size()-1); } } } } }
二叉树的中序遍历
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
示例 4：
输入：root = [1,2] 输出：[2,1]
示例 5：
输入：root = [1,null,2]
提示：
树中节点数目在范围 [0, 100] 内 -100 <= Node.val <= 100
分析
中序遍历可以看这篇：数据结构与算法—二叉树的层序、前序中序后序(递归、非递归)遍历
上代码：
/** * 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 { public List<Integer> inorderTraversal(TreeNode root) { List<Integer>value=new ArrayList<Integer>(); dfs(root,value); return value; } private void dfs(TreeNode root, List<Integer> value) { // TODO Auto-generated method stub if(root==null) return; dfs(root.left, value); value.add(root.val); dfs(root.right, value); } }
原创不易，bigsai请你帮两件事帮忙一下:
star支持一下， 您的肯定是我在平台创作的源源动力。
微信搜索「bigsai」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。
记得关注、咱们下次再见！
