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;
}
//反转链表II
public 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));
}
}