题目链接：https://leetcode.cn/problems/merge-intervals/description/
思路：合并区间，只需要先按照左边界排序，然后判断相邻区间是否交接，交接就合并，不交接就记录下来即可。
class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> list = new ArrayList<>();
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
int left = intervals[0][0], right = intervals[0][1];
for(int[] nums : intervals) {
if(nums[0] > right) {
list.add(new int[]{left, right});
left = nums[0];
right = nums[1];
}else {
right = Math.max(right, nums[1]);
}
}
list.add(new int[]{left, right});
int[][] result = new int[list.size()][2];
for(int i = 0; i < list.size(); i++) {
result[i] = list.get(i);
}
return result;
}
}
题目链接：https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/
思路：求二叉树中的最大路径和，对这个路径和的定义是只有一个节点也算，也不一定非得有根节点，所以这种路径和的计算，首先得使用后序遍历，因为每一个节点需要依赖他们的子节点传递的值，对于每一个节点来说，都可以考虑选择左子树或者右子树加入路径，条件就是只要大于零就算是路径的一员，但是相上层返回时，路径又要单一化，即只能是一条边。
class Solution {
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
traverse(root);
return max;
}
int traverse(TreeNode root) {
if(root == null) return 0;
int left = traverse(root.left);
int right = traverse(root.right);
left = left > 0 ? left : 0;
right = right > 0 ? right : 0;
max = Math.max(max, root.val + left + right);
return Math.max(left, right) + root.val;
}
}
题目链接：https://leetcode.cn/problems/edit-distance/description/
思路：编辑距离的题目也是经典的动态规划题，可以对字符串中的字符进行删除、增加、替换。
定义dp[i][j]表示以text1[0, i]和text2[0, j]为结尾的字符串要相等的最小步骤。
其实，如果text1[i] == text2[j]那么dp[i][j]其实是依赖于上一个位置的操作数，即text1[i-1]和text2[j-1]的操作数，即dp[i][j] = dp[i-1][j-1]+1。
这是想等的情况，对于不等的情况，可以选择：
删除：假如对text1删除，其实是依赖于text1[i-1]的位置，即dp[i][j] = dp[i-1][j]+1.
增加：假如对text1增加，其实可以看成对text2删除，即a,ab。即dp[i][j] = dp[i][j-1]+1.
替换：对于替换，只是把text1[i]或者text2[j]进行了替换，这算一步，其他的依赖于前一个步骤的操作数，即dp[i][j] = dp[i-1][j-1]+1.
class Solution {
public int minDistance(String word1, String word2) {
int[][] dp = new int[word1.length()+1][word2.length()+1];
for(int i = 0; i <= word1.length(); i++) dp[i][0] = i;
for(int j = 0; j <= word2.length(); j++) dp[0][j] = j;
for(int i = 0; i < word1.length(); i++) {
for(int j = 0; j < word2.length(); j++) {
if(word1.charAt(i) == word2.charAt(j)) {
dp[i+1][j+1] = dp[i][j];
}else{
dp[i+1][j+1] = Math.min(Math.min(dp[i+1][j], dp[i][j+1]), dp[i][j]) + 1;
}
}
}
return dp[word1.length()][word2.length()];
}
}
题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
思路：删除倒数第N个节点，只需要快慢指针，快指针先走N步，然后快慢指针同步往前走，当快指针走到结尾处时，慢指针的下一个位置就是要删除的节点。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode root = new ListNode(-1, head);
ListNode slow = root, fast = root;
for(int i = 0; i < n; i++) fast = fast.next;
while(fast.next != null) {
slow = slow.next;
fast = fast.next;
}
fast = slow.next;
slow.next = fast.next;
fast.next = null;
return root.next;
}
}
题目链接：https://leetcode.cn/problems/restore-ip-addresses/description/
思路：本题类似于排列，只不过是特定顺序的排列，也是正常做，需要指定递归的起始位置，递归的结束位置为，遍历到结尾，且收集元素数量为4，即可。其他的为正常递归的流程，只不过在判断切分的元素是否是0<=x<=255时，需要判断一下。另外就是早停操作，要剪辑的范围超出了3即要停止。
class Solution {
List<String> list = new ArrayList<>();
List<String> res = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
backTracking(s, 0);
return res;
}
void backTracking(String s, int index) {
if(list.size() == 4) {
if(s.length() == index) res.add(String.join(".", list));
return;
}
for(int i = index; i < s.length() && i - index < 3; i++) {
String t = fun(s, index, i);
if(t != null) {
list.add(t);
backTracking(s, i+1);
list.remove(list.size()-1);
}
}
}
String fun(String s, int x, int y) {
if(x != y && s.charAt(x) == '0') return null;
String t = s.substring(x, y+1);
int k = Integer.valueOf(t);
if(k >= 0 && k <= 255) return t;
return null;
}
}