import org.w3c.dom.NodeList;import java.math.BigInteger;
import java.util.*;public class test_04_24 {static class TreeNode{int val;TreeNode left;TreeNode right;public TreeNode(int val){this.val = val;}}static class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }}public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();LinkedList<TreeNode> linkedList = new LinkedList<>();linkedList.offerLast(root);boolean flag = true;while (!linkedList.isEmpty()){List<Integer> ls = new ArrayList<>();int m = linkedList.size();//从左往右if (flag){for (int i=0;i<m;i++){TreeNode node = linkedList.pollFirst();ls.add(node.val);if (node.left!=null){linkedList.offerLast(node.left);}if (node.right!=null){linkedList.offerLast(node.right);}}}else{//从右往左for (int i=0;i<m;i++){TreeNode node = linkedList.pollLast();ls.add(node.val);if (node.right!=null){linkedList.offerFirst(node.right);}if (node.left!=null){linkedList.offerFirst(node.left);}}}flag = !flag;res.add(ls);}return res;}//反转链表IIpublic ListNode reverseBetween(ListNode head, int left, int right) {ListNode leftNode = head;ListNode rightNode = head;ListNode leftNodePre = null;for (int i=1;i<left;i++){leftNodePre = leftNode;leftNode=leftNode.next;}for (int i=1;i<right;i++){rightNode=rightNode.next;}ListNode leftNodeCopy=leftNode;ListNode pre = null;ListNode p=leftNode;ListNode pp = p.next;while (p!=rightNode){p.next=pre;pre=p;p=pp;pp=pp.next;}p.next=pre;if (leftNodePre==null){leftNodeCopy.next=pp;return p;}else{leftNodePre.next=p;leftNodeCopy.next=pp;return head;}}//螺旋矩阵public static List<Integer> spiralOrder(int[][] matrix){int n = matrix.length;int m = matrix[0].length;boolean[][] visited = new boolean[n][m];List<Integer> res = new ArrayList<>();visited[0][0]=true;res.add(matrix[0][0]);dfs(matrix, 0, 0,visited,res);return res;}private static void dfs(int[][] matrix, int posX, int posY, boolean[][] visited, List<Integer> res) {int n = matrix.length;int m = matrix[0].length;//上右下左int[] x = new int[]{-1,0,1,0};int[] y = new int[]{0,1,0,-1};//四个方向for (int i=0;i<4;i++){int newX = posX+x[i];int newY = posY+y[i];if (newX<0||newX>=n){continue;}if (newY<0||newY>=m){continue;}if (visited[newX][newY]){continue;}visited[newX][newY]=true;res.add(matrix[newX][newY]);dfs(matrix,newX,newY,visited,res);}}public static List<Integer> spiralOrder2(int[][] matrix){int n=matrix.length;int m = matrix[0].length;int min = Math.min(n,m);int level = (min&1)==1?min/2+1:min/2;List<Integer> res = new ArrayList<>();//向右for (int k=0;k<level;k++){int i=k;int j=k;while (j<m-k){res.add(matrix[i][j++]);}int size = res.size();j--;i++;while (i<n-k){res.add(matrix[i++][j]);}if (size==res.size()){break;}size=res.size();i--;j--;while (j>=k){res.add(matrix[i][j--]);}if (size==res.size()){break;}j++;i--;while (i>k){res.add(matrix[i--][j]);}}return res;}//最长上升子序列//[1,3,6,7,9,4,10,5,6]public static int lengthOfLIS(int[] nums){int n = nums.length;int[] dp = new int[n];Arrays.fill(dp,1);for (int i=1;i<n;i++){for (int j=i-1;j>=0;j--){if (nums[i]>nums[j]){dp[i]=Math.max(dp[j]+1,dp[i]);}}}return Arrays.stream(dp).max().getAsInt();}//合并k个排序链表public ListNode mergeKLists(ListNode[] lists) {int n = lists.length;ListNode newHead = new ListNode(-1);ListNode p = newHead;while (true){//找出初始int index=-1;for (int i=0;i<n;i++){if (lists[i]!=null){index=i;break;}}//退出条件if (index==-1){break;}//找出最小的for (int i=0;i<n;i++){if (lists[i]!=null&&lists[i].val<lists[index].val){index=i;}}p.next=new ListNode(lists[index].val);p=p.next;lists[index]=lists[index].next;}return newHead.next;}//1 2 3//1 2 3 4//重排链表public static void reorderList(ListNode head) {ListNode slowPre = null;ListNode slow = head;ListNode quick = head;while (quick!=null&&quick.next!=null){slowPre=slow;slow=slow.next;quick=quick.next.next;}ListNode headSecond=slow;if (slowPre!=null){slowPre.next=null;}else{return;}ListNode pre = null;ListNode p = headSecond;ListNode pp=headSecond.next;while (pp!=null){p.next=pre;pre = p;p=pp;pp=pp.next;}p.next=pre;//此时p为第二个头节点ListNode q= head;while (q.next!=null&&p!=null){pp=p.next;p.next=q.next;q.next=p;q=q.next.next;p=pp;}q.next=p;}//字符串相加public static String addStrings(String num1, String num2) {//进位int k=0;int i=num1.length()-1;int j=num2.length()-1;StringBuilder stringBuilder = new StringBuilder();while (i>=0&&j>=0){int res = num1.charAt(i)+num2.charAt(j)-48-48+k;k = res/10;stringBuilder.append(res%10);i--;j--;}while (i>=0){int res = num1.charAt(i)-48+k;k = res/10;stringBuilder.append(res%10);i--;}while (j>=0){int res = num2.charAt(j)-48+k;k=res/10;stringBuilder.append(res%10);j--;}if (k!=0){stringBuilder.append(k);}return stringBuilder.reverse().toString();}static void printList(ListNode head){while (head!=null){System.out.print(head.val+" ");head=head.next;}System.out.println();}//合并区间public static int[][] merge(int[][] intervals) {Arrays.sort(intervals, (a, b) -> a[0] - b[0]);List<int[]> res = new ArrayList<>();for (int[] interval : intervals) {if (res.isEmpty() || res.get(res.size() - 1)[1] < interval[0]) {res.add(interval); // 不重叠，直接添加} else {// 重叠，合并int[] last = res.get(res.size() - 1);last[1] = Math.max(last[1], interval[1]);}}return res.toArray(new int[0][]);}public static void main(String[] args) {int[][] input = {{1,4},{2,3}};int[][] merge = merge(input);System.out.println(Arrays.deepToString(merge));}
}
