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

}

package com.demo.s141;

/**
 * 环形链表
 * 给你一个链表的头节点 head ，判断链表中是否有环。
 *
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
 *
 * 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/linked-list-cycle
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
public class Solution {
    public boolean hasCycle(ListNode head) {
        //快指针
        ListNode slow = head;
        //慢指针
        ListNode fast = head;
        //下一步不为null
        while(fast != null && fast.next != null && fast.next.next != null) {
            //快指针走两步
            fast = fast.next.next;
            //慢指针走一步
            slow = slow.next;
            //快慢相遇则出现环
            if(fast == slow) {
                return true;
            }
        }
        return false;
    }
}

package com.demo.s140;

import java.util.*;

/**
 * 单词拆分 II
 * 给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。
 *
 * 注意：词典中的同一个单词可能在分段中被重复使用多次。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/word-break-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 */
public class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Map<Integer, List<List<String>>> map = new HashMap<Integer, List<List<String>>>();
        List<List<String>> wordBreaks = backtrack(s, s.length(), new HashSet<String>(wordDict), 0, map);
        List<String> breakList = new LinkedList<String>();
        for (List<String> wordBreak : wordBreaks) {
            breakList.add(String.join(" ", wordBreak));
        }
        return breakList;
    }

    public List<List<String>> backtrack(String s, int length, Set<String> wordSet, int index, Map<Integer, List<List<String>>> map) {
        if (!map.containsKey(index)) {
            List<List<String>> wordBreaks = new LinkedList<List<String>>();
            if (index == length) {
                wordBreaks.add(new LinkedList<String>());
            }
            for (int i = index + 1; i <= length; i++) {
                String word = s.substring(index, i);
                if (wordSet.contains(word)) {
                    List<List<String>> nextWordBreaks = backtrack(s, length, wordSet, i, map);
                    for (List<String> nextWordBreak : nextWordBreaks) {
                        LinkedList<String> wordBreak = new LinkedList<String>(nextWordBreak);
                        wordBreak.offerFirst(word);
                        wordBreaks.add(wordBreak);
                    }
                }
            }
            map.put(index, wordBreaks);
        }
        return map.get(index);
    }
}

package com.demo.s14;

/**
 * 最长公共前缀
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 *
 * 如果不存在公共前缀，返回空字符串 ""。
 */
public class Solution {
    public String longestCommonPrefix(String[] strs) {
        //特殊情况判断
        if (strs == null || strs.length == 0) {
            return "";
        }
        //取第一个数组做对比
        int length = strs[0].length();
        //字符串个数
        int count = strs.length;
        //遍历字符串字符
        for (int i = 0; i < length; i++) {
            char c = strs[0].charAt(i);
            //对比其他字符串
            for (int j = 1; j < count; j++) {
                //达到其他字符串最大长度 或者 字符匹配不上，则终止
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];

    }
}

package com.demo.s139;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 单词拆分
 * 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
 *
 * 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/word-break
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {

    public boolean wordBreak(String s, List<String> wordDict) {
        if(wordDict.size() == 0) return false;
        Set<Integer> wordLength = new HashSet<>();
        for (String word : wordDict) {
            wordLength.add(word.length());
        }
        //单词去重
        Set<String> dict = new HashSet<>(wordDict);
        Set<String> wrongSet = new HashSet<>();
        return matchWords(s, dict, wordLength, wrongSet);
    }

    public boolean matchWords(String s, Set<String> dict, Set<Integer> wordLength, Set<String> wrongSet) {
        //特殊值判断
        if("".equals(s) || dict.contains(s)) return true;
        //遍历单词所有字符
        for(Integer j : wordLength) {
            if(j > s.length()) return false;
            String sub = s.substring(0, j);
            //截取字符串，找到单词表中存在的子串
            if(dict.contains(sub)) {
                String subEnd = s.substring(j);
                if(!wrongSet.contains(subEnd) && matchWords(subEnd, dict, wordLength, wrongSet)) {
                    return true;
                } else {
                    wrongSet.add(subEnd);
                }
            }
        }
        return false;
    }
}

package com.demo.s138;

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

/**
 * 复制带随机指针的链表
 * 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
 *
 * 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
 *
 * 例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
 *
 * 返回复制链表的头节点。
 *
 * 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
 *
 * val：一个表示 Node.val 的整数。
 * random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
 * 你的代码 只 接受原链表的头节点 head 作为传入参数。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/copy-list-with-random-pointer
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
public class Solution {
    //节点缓存到map
    Map<Node, Node> cachedNode = new HashMap<Node, Node>();

    public Node copyRandomList(Node head) {
        //特殊情况判断
        if (head == null) {
            return null;
        }
        //如果已经缓存说明节点已存在，则不用复制
        if (!cachedNode.containsKey(head)) {
            //复制节点值
            Node headNew = new Node(head.val);
            //缓存新旧节点
            cachedNode.put(head, headNew);
            //新节点next指向下一个新节点
            headNew.next = copyRandomList(head.next);
            //新节点random指向下一个新节点
            headNew.random = copyRandomList(head.random);
        }
        return cachedNode.get(head);
    }
}