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;
        }

        }

package com.demo.s22;

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

/**
 * 括号生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 */
public class Solution {
    public List<String> generateParenthesis(int n) {
        //定义结果list
        List<String> ans = new ArrayList<String>();
        //回溯法
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }

    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        //如果长度够了 就添加到list 返回  max是括号对数
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }
        //open 左括号个数 close 右括号个数
        //如果 左括号个数没有到最大值
        if (open < max) {
            //就再拼接一个左括号
            cur.append('(');
            //递归 继续拼接
            backtrack(ans, cur, open + 1, close, max);
            //开始回溯 每次减去一个左括号
            cur.deleteCharAt(cur.length() - 1);
        }
        //如果 右括号个数没有到最大值
        if (close < open) {
            cur.append(')');
            backtrack(ans, cur, open, close + 1, max);
            //开始回溯 每次减去一个左括号
            cur.deleteCharAt(cur.length() - 1);
        }
    }


}

package com.demo.s215;

/**
 * 215. 数组中的第K个最大元素
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 *
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/kth-largest-element-in-an-array
 */
public class Solution {
    /**
     * 堆排序问题
     */
    public int findKthLargest(int[] nums, int k) {
        //定义堆的大小
        int heapSize = nums.length;
        //初始构建大顶堆，大小为全部的数组长度
        buildMaxHeap(nums, heapSize);
        //大顶堆每次去掉最大的元素
        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
            //去掉最大元素
            swap(nums, 0, i);
            --heapSize;
            //构建一个次小堆
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }
    //构建大顶堆
    public void buildMaxHeap(int[] a, int heapSize) {
        //复杂度 heapSize / 2
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        }
    }
    //大顶堆
    public void maxHeapify(int[] a, int i, int heapSize) {
        //左子节点  右子节点， 根
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        //堆 大小范围内， 如果 左子节点 > 根
        if (l < heapSize && a[l] > a[largest]) {
            // 根为左子节点
            largest = l;
        }
        //堆 大小范围内， 如果 右子节点 > 根
        if (r < heapSize && a[r] > a[largest]) {
            // 根为右子节点
            largest = r;
        }
        // 根被替换
        if (largest != i) {
            // 执行移动操作
            swap(a, i, largest);
            //重新构建
            maxHeapify(a, largest, heapSize);
        }
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

}

package com.demo.s21;

/**
 * 合并两个有序链表
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 */

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 mergeTwoLists(ListNode list1, ListNode list2) {
        //递归终止条件
        if(list1 == null) {
            return list2;
        }
        //递归终止条件
        if(list2 == null) {
            return list1;
        }
        //从小到大排列
        if(list1.val <= list2.val) {
            //合并子链表
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list2.next, list1);
            return list2;
        }

    }
}

package com.demo.s206;

/**
 * 206. 反转链表
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 */
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 reverseList(ListNode head) {
        //前置节点 后一个节点指向的节点，初始的前置节点为null
        ListNode pre = null;
        //当前节点，从head开始遍历
        ListNode cur = head;
        //当前节点不为null
        while(cur != null) {
            //下一个节点先存中间变量
            ListNode t = cur.next;
            //下一个节点指向前一个节点
            cur.next = pre;
            //当前节点称为前置节点
            pre = cur;
            //下一个节点为当前节点
            cur = t;
        }
        return pre;
    }

}

package com.demo.s200;

public class Solution {
}