12天刷题Sprint

10.20 - 栈、堆，队列 - Interview-Oriented Sprint - 1 Day Left

栈 Deque<Integer> stack = new ArrayList<Integer>();
- 剑指-09 用两个栈实现队列    (void appendTail(int value); int deleteHead();)
- 剑指-30 包含min函数的栈   (辅助栈; 实现一个带min的链表) 单调递减栈

堆 Queue<Integer> heap = new PriorityQueue<>((x, y) - > (y - x));
- 剑指-40 最小的k个数  (堆排序; 快速排序 ) Top K 经典，返回参数可以是第k个数或者数组
- 剑指-41 数据流中的中位数    (小根堆+大根堆Queue<Integer> heap = new PriorityQueue<>((x, y) - > (y - x)); ) 两种情况分奇数偶数个元素

队列 Deque<Integer> queue= new ArrayList<Integer>();
- 剑指-59-II 队列的最大值   (本质上是求滑动窗口的最大值，用队列维护滑动窗口) 辅助队列
- 剑指-59-I 滑动窗口的最大值   (单调队列模板题) 1. 判断要不要收缩左边界，2. queue维护一个单调递减队列 3.扩大右边界

10.21 - 集合、Java核心类、数组操作 - Interview-Oriented Sprint - 0 Day Left

总结了一些常用的代码片段，欢迎补充。

集合
- 堆 Queue<Integer> minHeap = new  PriorityQueue<Integer>(); // 小根堆
       Queue<Integer> maxHeap = new PriorityQueue<Integer>((x, y) - > (y - x)); // 大根堆
       boolean offer(E e); E poll(); E peek(); int size();
- 栈 Deque<E> stack = new ArrayDeque<E>();
- 队列 Deque<E> queue = new ArrayDeque<E>();
           E peekLast(); E peekFirst();
           offerLast(E e); offerFirst(E e);
           E pollLast(); E pollFIrst();
- 不重复的元素 Set<E> set = new HashSet<E>();
           boolean add(E e); boolean contians(E e); boolean remove(E e); int size();
- 有序列表 List<E> list = new ArrayList<E>();
           boolean add(E e); boolean add(int index, E e);
           int remove(int index); int remove(Object e);
           E get(int index); int size();
- 键值对映射表 Map<K, V> map = new HashMap<K, V>();
           put(K key, V value); V get(K  key); boolean contains(K key);
           for (String key : map.keySet()) {
               Integer value = map.get(key);
           }
           for (Map.Entry<String, Integer> entry : map.entrySet()) {
               String key = entry.getKey();
               Integer value = entry.getValue();
           }

Java核心类
- 字符串 String
            .equals(); .equalsIgnoreCase(); // 比较
            .contains(); .startsWith(); endsWith(); //
            .indexOf(); .lastIndexOf(); // 搜索子串
            .substring(); .substring( , ); // 提取子串
            .trim(); .strip(); stripLeading(); stripTrailing(); // 去除(首尾)空白字符
            .isEmpty(); isBlank(); // 判断是否为空和空白字符串
            .replace( , ); .replaceAll(); // 替换子串
            .split(); // 分割字符串
            .join( , );  // 拼接字符串
- StringBuilder 支持链式操作
            .append(); .insert(, ); charAt(); delete(); deleteCharAt(); indexOf(); lastIndexOf();
- BigInteger 内部用一个int[]数组来模拟一个非常大的整数
            .add(); .subtract(); .multiply(); .divide(); .pow(); .longValueExact();
- Character
           .isLetter(); isDigit(); isWhiteSpace(); isUpperCase(); isLowerCase(); toUpperCase(); toLowerCase(); toString();

数组操作
- Arrays类
      .asList(); .fill(); sort(); copyOf(); copyOfRang(); .toString();

10.22 - 面筋题 - Interview-Oriented Sprint - 0 Day Left

- 4. 寻找两个正序数组的中位数 （二分法）
- 297.二叉树的序列化与反序列化 （前序/中序/后序遍历）
- 22.括号生成 （DFS+少量的剪枝，剪枝的条件为：左括号剩余数目大于右括号剩余数目，以及，左括号剩余数目或右括号剩余数目均大0）
- 剑指Offer 68-II 二叉树的最近公共祖先 (分三种情况：都在左子树、都在右子树、一个在左子树一个在右子树)
- 94.二叉树的中序遍历（迭代) （中序遍历不忘“左链入栈”while (curr != null || !stack.isEmpty())）- 138.复制带随机指针的链表 （Map<原始节点，克隆节点>：1使用hash表存储原始节点和新节点的映射，2连接新节点的next和random指针；
                                               原地址法：1将克隆节点放在原节点后面，2处理random指针）

Interview Day:

1. 个人自我介绍+论文成果说明+一个算法题
输入: 直角坐标系的n个点（x,y)
求有多少对曼哈顿距离和欧几里得距离相等的点

2. 个人自我介绍+最有趣的项目+一个算法题
输入：直线坐标系上，输入多段不相交的区间(排序好的)， 和一个新插入的区间
输出：合并完成的区间
例子：intervals [[1,3] , [5, 6]] newInterval [2,4] - > [[1,4],[5,6]]