前序遍歷和中序遍歷構建二叉樹

/*** 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 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);// 得到根在中序遍歷中的下標信息// pIndex-1-inLeft = x-(preLeft+1)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;}
}

鏈表合并

/*** 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 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;  // 更新指針}// 合并后list1和list2最多會有一個沒合并完，直接將鏈表的末尾指針指向未完成合并的鏈表即可prev.next = (list1 == null ? list2 : list1);return temp.next;   // 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個一組翻折鏈表

/*** 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 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) {// 每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()][]);}
}