package com.demo.s26;

/**
 *  删除有序数组中的重复项
 *  给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
 *
 * 由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
 *
 * 将最终结果插入 nums 的前 k 个位置后返回 k 。
 *
 * 不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
 *
 * 判题标准:
 *
 * 系统会用下面的代码来测试你的题解:
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }

}

package com.demo.s25;

import java.util.ArrayList;
import java.util.List;

/**
 * K 个一组翻转链表
 * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
 *
 * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 *
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/reverse-nodes-in-k-group
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
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 class Solution {
    // 定一个数据结构，存放链表 分组
    class Pharse {
        //链表开始节点
        ListNode begin;
        //链表开始节点
        ListNode end;
        //链表是否需要翻转
        boolean reverse;

        public Pharse(ListNode begin, ListNode end, boolean reverse) {
            this.begin = begin;
            this.end = end;
            this.reverse = reverse;
        }

        public void reverseSubGroup() {
            //前置节点都未null
            ListNode pre = null;
            //当前节点为begin
            ListNode cur = begin;
            //开始翻转
            while(true) {
                ListNode tmp = cur.next;
                cur.next = pre;
                pre = cur;
                //需要判断翻转结束条件
                if(cur == end || tmp == null){
                    break;
                } else {
                    cur = tmp;
                }
            }
            //转向后给出新的交换后的 begin end
            ListNode tmp = begin;
            begin = end;
            end = tmp;
        }
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        //判断入参
        if(k == 1) {
            //一个元素直接返回
            return head;
        }
        //哑巴节点，标记头结点
        ListNode pre = new ListNode(0);
        //当前节点从head开始
        ListNode cur = head;
        //开始位置
        boolean flag = false;
        //链表分组
        List<Pharse> pharses = new ArrayList<>();
        //链表开始
        ListNode start = null;
        //链表结束
        ListNode end = null;
        //开始分组
        for(int i = 0; cur != null; i++) {
            //k个元素 开始的位置
            if(i % k == 0 && !flag) {
                start = cur;
                flag = true;
                //区间就一个元素了，开始即是结束
                if(cur.next == null) {
                    end = cur;
                    pharses.add(new Pharse(start, end, false));
                }
                //k个元素后 结束的位置
            } else if((i + 1) % k == 0 && flag) {
                end = cur;
                flag = false;
                pharses.add(new Pharse(start, end, true));
                //区间没有满k个元素，提前结束
            } else if(cur.next == null) {
                end = cur;
                pharses.add(new Pharse(start, end, false));
            }
            //下一个元素
            cur = cur.next;
        }
        ListNode ph = pre;
        for(Pharse pharse : pharses) {
            if(pharse.reverse) {
                //每个区间内翻转
                pharse.reverseSubGroup();
            }
            //多个区间指针反向修改
            ph.next = pharse.begin;
            ph = pharse.end;
        }

        return pre.next;

    }
}

package com.demo.s24;

/**
 * 两两交换链表中的节点
 * 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
 *
 */

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 class Solution {

    public ListNode swapPairs(ListNode head) {
        //新建哑巴节点，存放头结点
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        //从哑巴节点开始 往后找到后两个节点
        while (temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;

            //交换节点
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummyHead.next;

    }
}

package com.demo.s239;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
 *
 * 返回 滑动窗口中的最大值 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/sliding-window-maximum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<Integer>();
        for (int i = 0; i < k; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                //非最大值出队列
                deque.pollLast();
            }
            //找到k个最大值 对应的下标放到队列中
            deque.offerLast(i);
        }
        //定义结果数组
        int[] ans = new int[n - k + 1];
        //前面找到的那个第一次窗口k个最大值 放入数组
        ans[0] = nums[deque.peekFirst()];
        //继续遍历数组
        for (int i = k; i < n; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            //如果超过当前窗口范围 移出窗口
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            //把窗口最后一次的最大值放到结果数组中
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }

}

package com.demo.s236;


/**
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 *
 * 图示两个链表在节点 c1 开始相交：
 *
 *
 *
 * 题目数据 保证 整个链式结构中不存在环。
 *
 * 注意，函数返回结果后，链表必须 保持其原始结构 。
 *
 * 自定义评测：
 *
 * 评测系统 的输入如下（你设计的程序 不适用 此输入）：
 *
 * intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
 * listA - 第一个链表
 * listB - 第二个链表
 * skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
 * skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
 * 评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/intersection-of-two-linked-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 */
public class Solution {
}

package com.demo.s234;

/**
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 *
 *
 */
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 class Solution {
        public boolean isPalindrome(ListNode head) {
                if(head == null || head.next == null) {
                        return true;
                }
                ListNode slow = head, fast = head;
                ListNode pre = null;
                while(fast != null && fast.next != null) {
                        ListNode tmp = slow;
                        slow = slow.next;
                        fast = fast.next.next;
                        tmp.next = pre;
                        pre = tmp;
                }
                if(fast != null) {
                        slow = slow.next;
                }
                while(pre != null && slow != null) {
                        if(pre.val != slow.val) {
                                return false;
                        }
                        pre = pre.next;
                        slow = slow.next;
                }
                return true;
        }
}

package com.demo.s232;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
 *
 * 实现 MyQueue 类：
 *
 * void push(int x) 将元素 x 推到队列的末尾
 * int pop() 从队列的开头移除并返回元素
 * int peek() 返回队列开头的元素
 * boolean empty() 如果队列为空，返回 true ；否则，返回 false
 * 说明：
 *
 * 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
 * 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/implement-queue-using-stacks
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class MyQueue {
    //两个栈 一个入栈
    Deque<Integer> inStack;
    //两个栈 一个出栈
    Deque<Integer> outStack;

    public MyQueue() {
        inStack = new LinkedList<Integer>();
        outStack = new LinkedList<Integer>();
    }

    public void push(int x) {
        //push进inStack
        inStack.push(x);
    }

    public int pop() {
        //如果outStack为空
        if (outStack.isEmpty()) {
            //将inStack写入到outStack
            in2out();
        }
        //从outStack读出
        return outStack.pop();
    }

    public int peek() {
        if (outStack.isEmpty()) {
            in2out();
        }
        //从outStack取栈顶元素
        return outStack.peek();
    }

    public boolean empty() {
        //inStack、outStack都为空
        return inStack.isEmpty() && outStack.isEmpty();
    }

    private void in2out() {
        //inStack写入outStack
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }


}

public class Solution {

}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

package com.demo.s23;

/**
 * 合并K个升序链表
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 */

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 class Solution {
    public ListNode merge2Lists(ListNode lista, ListNode listb) {
        //哑巴节点方便返回链表head
        ListNode dum = new ListNode();
        //遍历链表 cur 为当前节点
        ListNode cur = dum;
        while(true) {
            //遍历完lista
            if(lista == null) {
                cur.next = listb;
                break;
            }
            //遍历完listb
            if(listb == null) {
                cur.next = lista;
                break;
            }
            //按照升序排列链表
            if(lista.val <= listb.val) {
                cur.next = lista;
                lista = lista.next;
            } else {
                cur.next = listb;
                listb = listb.next;
            }
            //链表节点后移一位
            cur = cur.next;
        }
        return dum.next;
    }

    //多个链表合并，变为两两合并
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) {
            return null;
        }
        if(lists.length == 1) {
            return lists[0];
        }
        ListNode dum = null;
        //多个链表两两合并
        for(int i =0 ;i < lists.length; i ++) {
            dum = merge2Lists(dum, lists[i]);
        }
        return dum;
    }
}

package com.demo.s226;

/**
 * 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
 */

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;
     }
 }
public
class Solution {
        public TreeNode invertTree(TreeNode root) {
                if (root == null) {
                        return null;
                }
                TreeNode left = invertTree(root.left);
                TreeNode right = invertTree(root.right);
                root.left = right;
                root.right = left;
                return root;
        }


}

package com.demo.s221;

import java.util.HashMap;
import java.util.Map;

/**
 * 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
 */
public class Solution {
public int maximalSquare(char[][] matrix) {
        int maxSide = 0;
        //判断 边界情况
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return maxSide;
        }
        int rows = matrix.length, columns = matrix[0].length;
        //新建一个dp二维数组
        int[][] dp = new int[rows][columns];
        for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
        //遇到1的情况 考虑动态转移方程
        if (matrix[i][j] == '1') {
        //边界的情况，初始化为1
        if (i == 0 || j == 0) {
        dp[i][j] = 1;
        } else {
        //左侧、上侧、左上侧 三个 最大值加1
        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
        }
        //更新最大值 正方形长度
        maxSide = Math.max(maxSide, dp[i][j]);
        }
        }
        }
        //计算面积
        int maxSquare = maxSide * maxSide;
        return maxSquare;
        }

        }