前序遍历和中序遍历构建二叉树
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {int preLen = preorder.length;int inLen = inorder.length;if (preLen != inLen)return null;HashMap<Integer, Integer> map = new HashMap<>(preLen);for (int i = 0; i < preLen; i++)map.put(inorder[i], i);return buildTree(preorder, 0, preLen - 1,map, 0, inLen - 1);}private TreeNode buildTree(int[] preorder, int preLeft, int preRight,Map<Integer, Integer> map, int inLeft, int inRight) {if (preLeft > preRight || inLeft > inRight)return null;int rootVal = preorder[preLeft];TreeNode root = new TreeNode(rootVal);int pIndex = map.get(rootVal);int x = pIndex - inLeft + preLeft;root.left = buildTree(preorder, preLeft + 1, x,map, inLeft, pIndex - 1);root.right = buildTree(preorder, x + 1, preRight,map, pIndex + 1, inRight);return root;}
}
旋转链表右移
class Solution {public ListNode rotateRight(ListNode head, int k) {if (k == 0 || head == null || head.next == null)return head;// 找到链表长度和末尾结点 int len = 1;ListNode iter = head;while (iter.next != null) {len++;iter = iter.next;}// 将链表团成环iter.next = head;// 找到新链表的末尾位置所在的下标int n = len - k % len;while (n-- > 0) {iter = iter.next;}// 断开链表ListNode newhead = iter.next;iter.next = null;return newhead;}
}
链表合并
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode temp = new ListNode(-1);ListNode prev = temp; while (list1 != null && list2 != null) {if (list1.val <= list2.val) {prev.next = list1;list1 = list1.next;} else {prev.next = list2;list2 = list2.next;}prev = prev.next; }prev.next = (list1 == null ? list2 : list1);return temp.next; }}
/*** 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 mergeKLists(ListNode[] lists) {return mergeKLists(lists, 0, lists.length);}// 合并从lists[i]到lists[j-1]的数组private ListNode mergeKLists(ListNode[] lists, int i, int j) {int m = j - i;// 合并的全体范围，后续用于折半if (m == 0)return null;if(m==1)return lists[i];ListNode mergeKListsLeft = mergeKLists(lists, i, i + m / 2); // 左边需要合并的有序ListNode mergeKListsRight = mergeKLists(lists, i + m / 2, j); // 右边需要合并的有序return mergeTwo(mergeKListsLeft, mergeKListsRight); // 将最终结果合并}private ListNode mergeTwo(ListNode list1, ListNode list2) {ListNode dummp = new ListNode(-1);ListNode prev = dummp;while (list1 != null && list2 != null) {if (list1.val <= list2.val) {prev.next = list1;list1 = list1.next;} else {prev.next = list2;list2 = list2.next;}prev = prev.next;}if (list1!= null)prev.next = list1;if (list2!= null)prev.next = list2;return dummp.next;}
}
K个一组翻折链表
class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode p = new ListNode(-1, head);int len=0;while (p.next != null) {len++;p = p.next;}ListNode dummy = new ListNode(0, head);ListNode p0 = dummy;ListNode pre = null;ListNode curr = head;while (len >= k) {for (int i = 0; i < k; i++) {ListNode next = curr.next;curr.next = pre;pre = curr;curr = next;}ListNode nxt = p0.next;p0.next.next = curr;p0.next = pre;p0 = nxt;len = len - k;}return dummy.next;}
}
合并区间
class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, (p, q) -> p[0] - q[0]);ArrayList<int[]> ans = new ArrayList<>();for (int[] p : intervals) {int m = ans.size();if (m > 0 && p[0] <= ans.get(m - 1)[1]) {ans.get(m - 1)[1] = Math.max(ans.get(m - 1)[1], p[1]);} elseans.add(p);}return ans.toArray(new int[ans.size()][]);}
}
)
