package com.demo.s155;

import java.util.Stack;

/**
 * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
 *
 * 实现 MinStack 类:
 *
 * MinStack() 初始化堆栈对象。
 * void push(int val) 将元素val推入堆栈。
 * void pop() 删除堆栈顶部的元素。
 * int top() 获取堆栈顶部的元素。
 * int getMin() 获取堆栈中的最小元素。
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/min-stack
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class MinStack {

    //数据
    private Stack<Integer> data;
    //最小栈
    private Stack<Integer> minStack;
    public MinStack() {
        data = new Stack();
        minStack = new Stack();
    }

    public void push(int val) {
        data.push(val);
        if(minStack.size() == 0) {
            minStack.push(val);
        } else {
            //最小值存栈顶，如果不是最小，取栈顶的最小值再存一次，保证pop后 最小值还在栈顶
            minStack.push(Math.min(val, minStack.peek()));
        }
    }

    public void pop() {
        minStack.pop();
        data.pop();
    }

    public int top() {
        return data.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

public class Solution {}
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

package com.demo.s151;

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

/**
 * 给你一个字符串 s ，颠倒字符串中 单词 的顺序。
 *
 * 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
 *
 * 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
 *
 * 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/reverse-words-in-a-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = trimSpaces(s);

        // 翻转字符串
        reverse(sb, 0, sb.length() - 1);

        // 翻转每个单词
        reverseEachWord(sb);

        return sb.toString();
    }

    public StringBuilder trimSpaces(String s) {
        int left = 0, right = s.length() - 1;
        // 去掉字符串开头的空白字符
        while (left <= right && s.charAt(left) == ' ') {
            ++left;
        }

        // 去掉字符串末尾的空白字符
        while (left <= right && s.charAt(right) == ' ') {
            --right;
        }

        // 将字符串间多余的空白字符去除
        StringBuilder sb = new StringBuilder();
        while (left <= right) {
            char c = s.charAt(left);

            if (c != ' ') {
                sb.append(c);
            } else if (sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }

            ++left;
        }
        return sb;
    }

    public void reverse(StringBuilder sb, int left, int right) {
        while (left < right) {
            char tmp = sb.charAt(left);
            sb.setCharAt(left++, sb.charAt(right));
            sb.setCharAt(right--, tmp);
        }
    }

    public void reverseEachWord(StringBuilder sb) {
        int n = sb.length();
        int start = 0, end = 0;

        while (start < n) {
            // 循环至单词的末尾
            while (end < n && sb.charAt(end) != ' ') {
                ++end;
            }
            // 翻转单词
            reverse(sb, start, end - 1);
            // 更新start，去找下一个单词
            start = end + 1;
            ++end;
        }
    }

}

package com.demo.s15;

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

/**
 * 三数之和
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 *
 * 注意：答案中不可以包含重复的三元组。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/3sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //结果list
        List ret = new ArrayList();
        //判断入参
        if(nums.length < 3) return ret;
        //排序数据，方便设置左右边界 遍历
        Arrays.sort(nums);
        //先定义一个元素遍历，作为三个中最小的一个值
        for(int i = 0 ;i< nums.length-2; i++) {
            //判断终止条件
            if(nums[i] > 0)  return ret;
            //忽略到相同的值
            if(i> 0 && nums[i] == nums[i-1]) continue;
            //第二个元素 取区间左边界
            int L = i +1;
            //第三个元素 取区间右边界
            int R = nums.length - 1;
            //如果左右边界重合 则停止
            while(L < R) {
                //如果三数和为0
                if(nums[i] + nums[L] + nums[R] == 0) {
                    //记录三个数
                    List numbers = new ArrayList();
                    numbers.add(nums[i]);
                    numbers.add(nums[L]);
                    numbers.add(nums[R]);
                    ret.add(numbers);
                    //基于已有的和为0 左右移动边界 寻找其他的记录
                    while(L< R && (nums[L] == nums[L+1])) {
                        //忽略相同的数值 左边界右移
                        L++;
                    }
                    while(R > L && nums[R] == nums[R-1]) {
                        //忽略相同的数值 右边界左移
                        R--;
                    }
                    //移动左右边界
                    L++;
                    R--;
                } else if(nums[i] + nums[L] + nums[R] < 0) {
                    // 和小于0  左边界右移
                    L++;
                } else {
                    // 和大于0  右边界左移
                    R--;
                }
            }
        }
        return ret;
    }
}

package com.demo.s148;

/**
 * 排序链表
 * 给你链表的头结点 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 sortList(ListNode head) {
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail) {
        if(head == null) {
            return head;
        }
        if(head.next == tail) {
            head.next = null;
            return head;
        }

        ListNode fast = head;
        ListNode slow = head;
        while(fast != tail) {
            fast  = fast.next;
            slow  = slow.next;
            if(fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode m = sortList(head, mid);
        ListNode n = sortList(mid, tail);
        return mergeList(m, n);
    }
    public ListNode mergeList(ListNode head, ListNode tail) {
        ListNode dum = new ListNode(0);
        ListNode tmp1 = head;
        ListNode tmp2 = tail;
        ListNode tmp = dum;
        while(tmp1 != null && tmp2 != null) {
            if(tmp1.val < tmp2.val) {
                tmp.next = tmp1;
                tmp1 = tmp1.next;
            } else {
                tmp.next = tmp2;
                tmp2 = tmp2.next;
            }
            tmp = tmp.next;
        }
        if(tmp1 != null) {
            tmp.next = tmp1;
        }
        if(tmp2 != null) {
            tmp.next = tmp2;
        }
        return dum.next;
    }
}

package com.demo.s147;

/**
 * 排序链表
 * 给你链表的头结点 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 sortList(ListNode head) {
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail) {
        if(head == null) {
            return head;
        }
        if(head.next == tail) {
            head.next = null;
            return head;
        }

        ListNode fast = head;
        ListNode slow = head;
        while(fast != tail) {
            fast  = fast.next;
            slow  = slow.next;
            if(fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode m = sortList(head, mid);
        ListNode n = sortList(mid, tail);
        return mergeList(m, n);
    }
    public ListNode mergeList(ListNode head, ListNode tail) {
        ListNode dum = new ListNode(0);
        ListNode tmp1 = head;
        ListNode tmp2 = tail;
        ListNode tmp = dum;
        while(tmp1 != null && tmp2 != null) {
            if(tmp1.val < tmp2.val) {
                tmp.next = tmp1;
                tmp1 = tmp1.next;
            } else {
                tmp.next = tmp2;
                tmp2 = tmp2.next;
            }
            tmp = tmp.next;
        }
        if(tmp1 != null) {
            tmp.next = tmp1;
        }
        if(tmp2 != null) {
            tmp.next = tmp2;
        }
        return dum.next;
    }

}

package com.demo.s146;

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

/**
 * LRU 缓存
 * 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
 * 实现 LRUCache 类：
 * LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
 * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 * void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
 * 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
 *
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/lru-cache
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class LRUCache {

    //LRU队列中的元素定义 双向链表存储 方便随机访问 删除 添加操作
    class DLinkedNode {
        //缓存key
        int key;
        //缓存值
        int value;
        //队列前一个节点
        DLinkedNode prev;
        //队列后一个节点
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
    }
    //LRU缓存map<缓存的值, 缓存的元素>
    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    //缓存大小
    private int size;
    //缓存容量
    private int capacity;
    //头结点 尾节点
    private DLinkedNode head, tail;
    //缓存初始化
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        //使用伪头部和伪尾部节点 方便尾部查询，头部删除
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    //查询缓存
    public int get(int key) {
        //先从map中取
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        //如果 key 存在，先通过哈希表定位，再移到头部， 头插尾删。
        moveToHead(node);
        return node.value;
    }

    //存入数据
    public void put(int key, int value) {
        //先从map中取
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            // 添加进哈希表
            cache.put(key, newNode);
            // 添加至双向链表的头部
            addToHead(newNode);
            //记录元素个数
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode tail = removeTail();
                // 删除哈希表中对应的项
                cache.remove(tail.key);
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node.value = value;
            moveToHead(node);
        }
    }

    /**
     *头插
     */
    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    /**
     * 删除节点
     */
    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    /**
     * 删除该节点
     * 并把该节点移动到头部
     */
    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    /**
     * 删除尾部节点
     */
    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }

}
public class Solution {

}

package com.demo.s145;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 二叉树的后序遍历
 * 给你一棵二叉树的根节点 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 List<Integer> postorderTraversal(TreeNode root) {
        //返回值
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        //新建栈
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                //先左孩子入栈
                root = root.left;
            }
            root = stack.pop();
            if (root.right == null || root.right == prev) {
                res.add(root.val);
                prev = root;
                root = null;
            } else {
                stack.push(root);
                //右孩子入栈
                root = root.right;
            }
        }
        return res;
    }
}

package com.demo.s144;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 二叉树的前序遍历
 *
 */
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 List<Integer> preorderTraversal(TreeNode root) {
        //定义结果list
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        //定义队列 遍历时存放当前节点用
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node = root;
        while(stack.size() != 0 || node!= null) {
            while(node != null) {
                res.add(node.val);
                //先当前节点
                stack.push(node);
                //后left节点
                node = node.left;
            }
            //最后右节点
            node = stack.pop();
            node = node.right;
        }
        return res;
    }
}

package com.demo.s143;

/**
 * 重排链表
 * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 *
 * L0 → L1 → … → Ln - 1 → Ln
 * 请将其重新排列后变为：
 *
 * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
 * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/reorder-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

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 void reorderList(ListNode head) {
        if(head == null) {
            return;
        }
        //找链表中间点
        ListNode mid = findMid(head);
        //拆分成前后两个链表
        ListNode l1 = head;
        ListNode l2 = mid.next;
        mid.next = null;
        //翻转后面的链表
        l2 = reverseList(l2);
        //两个链表合并
        mergeList(l1, l2);
    }

    public ListNode findMid(ListNode head) {
        //快指针
        ListNode fast = head;
        //慢指针
        ListNode slow = head;
        while(fast != null && fast.next!= null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //中间点
        return slow;
    }

    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

    public void mergeList(ListNode l1, ListNode l2) {
        while(l1 != null && l2 != null) {
            ListNode l1_tmp = l1.next;
            ListNode l2_tmp = l2.next;
            //l1 指向 l2
            l1.next = l2;
            //l2 要指向 l1.next 也就是未修改指向的l1_tmp
            l2.next = l1_tmp;

            //下一步
            l1 = l1_tmp;
            l2 = l2_tmp;

        }
    }
}

package com.demo.s142;

/**
 * 环形链表 II
 * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 *
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
 *
 * 不允许修改 链表。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/linked-list-cycle-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
public class Solution {
    public ListNode detectCycle(ListNode head) {
        //快慢指针，快指针走两步，慢指针走一步
        ListNode fast = head, slow = head;
        while (true) {
            //快慢指针都走完结束
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            //快慢指针相遇
            if (fast == slow) break;
        }
        fast = head;
        //快慢指针相遇后，此时慢指针走到链表环开始节点的距离，刚好等于head节点到链表环开始节点的距离
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }

}