ARTS_WEEK18

这算是拖了很就是ARTS总结了，前段时间一直在准备面试，只有每天的算法题坚持下来了。并且这周的题目都挺难的，重新回顾一遍都不一定能再写出来，更多的只是去回顾了思想。

而每周的ARTS却放了比较久。加上后来上班，也比较忙，恰好在这个五一，把所有的ARTS全部补齐。

凭记忆，这周的每日一题好像都比较难，基本上每道题目都是一个奇妙的旅程。

1. although

1.1. 每日一练

1.1.1. 圆圈中最后剩下的数字

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: CDz
 * Create: 2020-03-30 22:05
 * <p>
 * 面试题62. 圆圈中最后剩下的数字
 * 0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
 * <p>
 * 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入: n = 5, m = 3
 * 输出: 3
 * 示例 2：
 * <p>
 * 输入: n = 10, m = 17
 * 输出: 2
 **/

约瑟夫环的问题，先给出递推公式f(n,m)=(f(n-1,m)+m)%n。

公式的推导过程——表格画图：

假设n=8,m=4

0	1	2	~~3~~	4	5	6
4	5	6	~~7~~	0	1	2
0	1	2	~~4~~	5	6
5	6	0	~~1~~	2
2	5	6	~~0~~
~~2~~	5	6
5	~~6~~
5

有上述推导过程我们可知道最终结果是5，也就是说f(8,4)=5最终的幸存者下标为5。

问题一：此时我们知道n=8,m=4时的胜利者下标为5，在第一行（8人）里，胜利者的下标为5，那么在第二行（7人）里胜利者的下标变化成几了？

从表格我们可以看出，每次我们kill掉一个人时，后面的数字都会重新从下标为0开始放置。也就是说，第一轮kill的人后所有的下标都需要向左移动m位。

那么就可以推测出第二行（7人）的胜利者下标变化成了5-4=1下标为1。

问题二：我们知道第二行（7人）胜利者的下标为1倒推第一行（8人）的胜利者的下标是几？

其实这是上一个问题的逆工程，所有元素右移m=4位。所有下标+4，公式表示f(8) = f(7) + 4，避免数组越界f(8) = (f(7) + 4)%8。

问题三：将人数改成N，报到M数时kill。

因为每一次kill一轮后，胜利者都会向左移动M位。f(N,M) = (f(N-1,M)+M)%N。并且我们可以确定的知道f(1,M) = 0,顾可以一点点的往上推算。

约瑟夫环——公式法（递推公式）

 /**
     * https://blog.csdn.net/u011500062/article/details/72855826
     * 约瑟夫环的递推公式
     *
     * f(n,m)=(f(n-1,m)+m)%n
     * @param n
     * @param m
     * @return
     */
    public int lastRemaining(int n, int m) {
        int ans = 0;
        for (int i = 2; i <= n; i++) {
            ans =(m+ans)%i;
        }
        return ans;
    }

1.1.2. 排序数组

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: CDz
 * Date: 2020-03-31
 * Time: 下午2:31
 * 912. 排序数组
 * 给你一个整数数组 nums，请你将该数组升序排列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [5,2,3,1]
 * 输出：[1,2,3,5]
 * 示例 2：
 *
 * 输入：nums = [5,1,1,2,0,0]
 * 输出：[0,0,1,1,2,5]
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 50000
 * -50000 <= nums[i] <= 50000
 */

考量经典的排序算法：

插入排序：

冒泡排序：

归并排序：

快速排序：

public int[] sortArray(int[] nums) {
		//API排序
        Arrays.sort(nums);
        return nums;
}

1.1.3. LFU缓存

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: CDz
 * Create: 2020-04-05 17:29
 * <p>
 * 460. LFU缓存
 * 设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。
 * <p>
 * get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
 * put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。
 * <p>
 * 一个项目的使用次数就是该项目被插入后对其调用 get 和 put 函数的次数之和。使用次数会在对应项目被移除后置为 0。
 * <p>
 * 进阶：
 * 你是否可以在 O(1) 时间复杂度内执行两项操作？
 * <p>
 * 示例：
 * <p>
 * LFUCache cache = new LFUCache( 2  capacity (缓存容量)  );
 * <p>
 * cache.put(1,1);
 * cache.put(2,2);
 * cache.get(1);       // 返回 1
 * cache.put(3,3);    // 去除 key 2
 * cache.get(2);       // 返回 -1 (未找到key 2)
 * cache.get(3);       // 返回 3
 * cache.put(4,4);    // 去除 key 1
 * cache.get(1);       // 返回 -1 (未找到 key 1)
 * cache.get(3);       // 返回 3
 * cache.get(4);       // 返回 4
 **/

方法一：使用map来实现

public class Week18HLFUCache460 {

    /**
     * 思路，内容通过map来存储
     *
     * 再使用一个 map存储频率值
     *
     * key为频率，value此频率下所有value的集合，根据时间排序
     *
     * map到达最大长度的时候，获取最小频率的list，并且干掉时间离当前现在最远的
     *
     * 故value需要包装
     */
    static class LFUCache {

        private Map<Integer,Node> cache;

        private Map<Integer,LinkedHashSet<Node>> freqMap;

        private int minFreq;

        private int capacity;

        public LFUCache(int capacity) {
            this.cache = new HashMap<>(capacity);
            this.freqMap = new HashMap<>();
            this.capacity = capacity;
        }

        public int get(int key) {

            if (capacity==0)return -1;
            Node node = cache.get(key);
            if (node==null)return -1;

            incfreqNode(node);
            return node.value;
        }

        private void incfreqNode(Node node) {
            LinkedHashSet<Node> freqSet = freqMap.get(node.freq);
            freqSet.remove(node);
            if (node.freq==minFreq&&freqSet.size()==0){
                minFreq++;
            }
            node.freq = node.freq+1;

            LinkedHashSet<Node> nextFreqSet = freqMap.computeIfAbsent(node.freq, k -> new LinkedHashSet<>());
            nextFreqSet.add(node);
        }

        public void put(int key, int value) {

            if (capacity==0)return;
            if (cache.containsKey(key)){
                //存在直接更新
                //更新cache
                Node node = cache.get(key);
                node.value = value;
                //更新频率list
                incfreqNode(node);
            }else {
                //不存在 需要判断是否map size最大值
                if (cache.size()==capacity){
                    //最大值 需要删除一个
                    Node dieNode = removeNode();
                    cache.remove(dieNode.key);
                }
                //添加需要添加到两个地方
                Node newNode = new Node(key, value);
                addNode(newNode);
            }
        }

        private void addNode(Node newNode) {
            //cache添加
            cache.put(newNode.key,newNode);
            //添加频率队列
            LinkedHashSet<Node> freqSet = freqMap.computeIfAbsent(newNode.freq, k -> new LinkedHashSet<>());
            freqSet.add(newNode);
            //更新频率最小值
            minFreq = 1;
        }

        private Node removeNode() {
            LinkedHashSet<Node> freqSet = freqMap.get(minFreq);
            Iterator<Node> iterator = freqSet.iterator();
            Node dieNode = iterator.next();
            freqSet.remove(dieNode);
            return dieNode;
        }
    }


    static class Node{
         int key;
         int value;
         int freq = 1;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public Node() {
        }
    }

    /**
     * LFUCache cache = new LFUCache( 2  capacity (缓存容量)  );
     *  * <p>
     *  * cache.put(1,1);
     *  * cache.put(2,2);
     *  * cache.get(1);       // 返回 1
     *  * cache.put(3,3);    // 去除 key 2
     *  * cache.get(2);       // 返回 -1 (未找到key 2)
     *  * cache.get(3);       // 返回 3
     *  * cache.put(4,4);    // 去除 key 1
     *  * cache.get(1);       // 返回 -1 (未找到 key 1)
     *  * cache.get(3);       // 返回 3
     *  * cache.get(4);       // 返回 4
     * @param args
     */
    public static void main(String[] args) {
        LFUCache lfuCache = new LFUCache(2);
        lfuCache.put(1,1);
        lfuCache.put(2,2);
        System.out.println(lfuCache.get(1));
        lfuCache.put(3,3);
        System.out.println(lfuCache.get(2));
        System.out.println(lfuCache.get(3));
        lfuCache.put(4,4);
        System.out.println(lfuCache.get(1));
        System.out.println(lfuCache.get(3));
        System.out.println(lfuCache.get(4));

    }
/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

}

方法二：自定义双链表实现

public class Week18HLFUCache460_1 {

    static class LFUCache {

        private final Map<Integer, Node> cache;


        private final FreqDoublyLinkedList first;
        private final FreqDoublyLinkedList last;

        private int capacity;

        {
            first = new FreqDoublyLinkedList();
            last = new FreqDoublyLinkedList();
            first.next = last;
            last.pre = first;
        }

        public LFUCache(int capacity) {
            this.cache = new HashMap<>(capacity);
            this.capacity = capacity;
        }

        public int get(int key) {
            if (capacity <= 0 || !cache.containsKey(key)) return -1;
            Node node = cache.get(key);
            icrFreq(node);
            return node.value;
        }




        public void put(int key, int value) {
            if (capacity==0)return;
            if (cache.containsKey(key)) {
                //存在
                Node node = cache.get(key);
                icrFreq(node);
                node.value= value;
            }else {
                //不存在
                if (cache.size()==capacity) {
                    //已满
                    //删除一个最小频率 最old的node
                    FreqDoublyLinkedList minFreqLinkedList = first.next;
                    Node oldNode = minFreqLinkedList.tail.pre;
                    cache.remove(oldNode.key);
                    minFreqLinkedList.remove(oldNode);
                }
                Node newNode = new Node(key, value);
                if (first.next.freq==1){
                    FreqDoublyLinkedList next = first.next;
                    next.addNode(newNode);
                }else {
                    FreqDoublyLinkedList minFreq = new FreqDoublyLinkedList(1);
                    minFreq.addNode(newNode);
                    addDoublyLinkedList(first,minFreq);
                }
                cache.put(key,newNode);
            }

        }

        private void icrFreq(Node node) {
            FreqDoublyLinkedList linkedList = node.doublyLinkedList;
            FreqDoublyLinkedList nextLinkedList = linkedList.next;

            linkedList.remove(node);
            //判断linkedList 是否为空
            if (linkedList.head.next==linkedList.tail){
                //说明 linkedList 已空删除
                removeDoublyLinkedList(linkedList);
            }

            node.freq++;
            if (nextLinkedList.freq==node.freq){
                nextLinkedList.addNode(node);
            }else {
                FreqDoublyLinkedList freqDoublyLinkedList = new FreqDoublyLinkedList(node.freq);
                freqDoublyLinkedList.addNode(node);
                addDoublyLinkedList(nextLinkedList.pre,freqDoublyLinkedList);
            }

        }

        private void addDoublyLinkedList(FreqDoublyLinkedList pre, FreqDoublyLinkedList newFreq) {
            newFreq.next = pre.next;
            pre.next.pre=newFreq;
            pre.next=newFreq;
            newFreq.pre=pre;
        }

        private void removeDoublyLinkedList(FreqDoublyLinkedList delLinkedList) {
            delLinkedList.pre.next = delLinkedList.next;
            delLinkedList.next.pre=delLinkedList.pre;
        }

    }


    static class Node {
        int key;
        int value;
        int freq = 1;
        Node pre;
        Node next;

        private FreqDoublyLinkedList doublyLinkedList;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public Node() {
        }
    }

    static class FreqDoublyLinkedList {
        FreqDoublyLinkedList pre;
        FreqDoublyLinkedList next;

        Node head;
        Node tail;

        int freq;

        public FreqDoublyLinkedList(int freq) {
            this.freq = freq;
            initNodeLinedList();
        }

        public FreqDoublyLinkedList() {

        }

        private void initNodeLinedList() {
            Node head = new Node();
            Node tail = new Node();
            head.next = tail;
            tail.pre = head;

            this.head = head;
            this.tail = tail;
        }


        public void remove(Node node) {
            node.pre.next = node.next;
            node.next.pre=node.pre;
        }

        public void addNode(Node newNode) {
            newNode.next = head.next;
            head.next.pre=newNode;
            head.next=newNode;
            newNode.pre=head;
            newNode.doublyLinkedList = this;
        }
    }


    /**
     * LFUCache cache = new LFUCache( 2  capacity (缓存容量)  );
     * * <p>
     * * cache.put(1,1);
     * * cache.put(2,2);
     * * cache.get(1);       // 返回 1
     * * cache.put(3,3);    // 去除 key 2
     * * cache.get(2);       // 返回 -1 (未找到key 2)
     * * cache.get(3);       // 返回 3
     * * cache.put(4,4);    // 去除 key 1
     * * cache.get(1);       // 返回 -1 (未找到 key 1)
     * * cache.get(3);       // 返回 3
     * * cache.get(4);       // 返回 4
     *
     *
     * ["LFUCache","put","put","get","get","get","put","put","get","get","get","get"]
     * [[3],[2,2],[1,1],[2],[1],[2],[3,3],[4,4],[3],[2],[1],[4]]
     *
     * [null,null,null,2,1,2,null,null,3,2,-1,4]
     * [null,null,null,2,1,2,null,null,-1,2,1,4]
     * @param args
     */
    public static void main(String[] args) {
        LFUCache lfuCache = new LFUCache(3);
        lfuCache.put(2,2);
        lfuCache.put(1,1);
        System.out.println(lfuCache.get(2));
        System.out.println(lfuCache.get(1));
        System.out.println(lfuCache.get(2));
        lfuCache.put(3,3);
        lfuCache.put(4,4);
        System.out.println(lfuCache.get(3));
        System.out.println(lfuCache.get(2));
        System.out.println(lfuCache.get(1));
        System.out.println(lfuCache.get(4));

    }
/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

}

1.1.4. 接雨水

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: CDz
 * Create: 2020-04-04 22:38
 * 42. 接雨水
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * <p>
 * <p>
 * <p>
 * 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
 * <p>
 * 示例:
 * <p>
 * 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出: 6
 **/

public int trap(int[] height) {

        if (height.length == 0) return 0;

        Stack<Integer> stack = new Stack<>();

        int ans = 0;

        for (int i = 0; i < height.length; i++) {
            //curr 遍历值大于 栈里新添加的最新元素
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                //弹出栈中最新的值
                int curIdx = stack.pop();
                while (!stack.isEmpty()&&height[stack.peek()]==height[curIdx]){
                    //如果有相等的高度继续弹出
                    stack.pop();
                }

                if (!stack.isEmpty()){

                    Integer stackTop = stack.peek();
                    //计算宽度
                    //stackTop 为 left左柱子
                    //height[i]为right右柱子
                    //高度为：min(left,right)
                    //宽度为：i-stackTop-1 水的宽度是 左右柱子不算在内的，即为左右柱子中间的宽度
                    ans+=(Math.min(height[stackTop],height[i])-height[curIdx])*(i-stackTop-1);
                }
            }
            stack.add(i);
        }
        return ans;
    }

1.1.5. 生命游戏

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: CDz
 * Create: 2020-04-02 23:16
 * <p>
 * 289. 生命游戏
 * 根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
 * <p>
 * 给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
 * <p>
 * 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
 * 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
 * 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
 * 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
 * 根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。
 * <p>
 * <p>
 * <p>
 * 示例：
 * <p>
 * 输入：
 * [
 * [0,1,0],
 * [0,0,1],
 * [1,1,1],
 * [0,0,0]
 * ]
 * 输出：
 * [
 * [0,0,0],
 * [1,0,1],
 * [0,1,1],
 * [0,1,0]
 * ]
 * <p>
 * <p>
 * 进阶：
 * <p>
 * 你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
 * 本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？
 **/

本地的关键点是，中间状态的表示。需要定义一个中间状态这样便于记录，如何定义一个中间状态？使用二进制的方式（JAVA中以0b开头的表示二进制数）定义。

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡； 01 表示过去活着现在死了
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；11 表示过去活着现在也活着
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；01 表示过去活着现在死了
如果死细胞周围正好有三个活细胞，则该位置死细胞复活； 10 表示过去死的现在活着

使用二进制位来表达：

1 -> 0b01
0 -> 0b00

/**
     * 本地关键点，设置中间状态
     * <p>
     * 1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡； 01 表示过去活着现在死了
     * 2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；11 表示过去活着现在也活着
     * 3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；01 表示过去活着现在死了
     * 4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活； 10 表示过去死的现在活着
     * <p>
     * <p>
     * 使用二进制表达
     * 1 0b01
     * 0 0b00
     *
     * @param board
     */

    public void gameOfLife(int[][] board) {
        int n = board.length;
        int m = board[0].length;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {

                int count = getAliveNum(board, i, j);

                if ((board[i][j] & 1) > 0) {
                    //此位置为活着细胞
                    if (count >= 2 && count <= 3) {
                        //下一个状态还是活
                        board[i][j] = 0b11;
                    }

                } else if (count == 3) {
                    //此位置为死细胞
                    //并且count 为3 复活
                    //01
                    board[i][j] = 0b10;
                }

            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                board[i][j] >>= 1;
            }
        }
    }

    int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1};
    int[] dy = {0, 0, -1, 1, -1, 1, -1, 1};


    private int getAliveNum(int[][] board, int i, int j) {

        int count = 0;
        for (int k = 0; k < 8; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) {
                continue;
            }
            count+=(board[x][y]&1);
        }

        return count;
    }

1.1.6. 有效括号的嵌套深度

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: CDz
 * Create: 2020-04-01 21:45
 *
 * 1111. 有效括号的嵌套深度
 * 有效括号字符串 定义：对于每个左括号，都能找到与之对应的右括号，反之亦然。详情参见题末「有效括号字符串」部分。
 *
 * 嵌套深度 depth 定义：即有效括号字符串嵌套的层数，depth(A) 表示有效括号字符串 A 的嵌套深度。详情参见题末「嵌套深度」部分。
 *
 * 有效括号字符串类型与对应的嵌套深度计算方法如下图所示：
 *
 *
 * 给你一个「有效括号字符串」 seq，请你将其分成两个不相交的有效括号字符串，A 和 B，并使这两个字符串的深度最小。
 *
 * 不相交：每个 seq[i] 只能分给 A 和 B 二者中的一个，不能既属于 A 也属于 B 。
 * A 或 B 中的元素在原字符串中可以不连续。
 * A.length + B.length = seq.length
 * 深度最小：max(depth(A), depth(B)) 的可能取值最小。
 * 划分方案用一个长度为 seq.length 的答案数组 answer 表示，编码规则如下：
 *
 * answer[i] = 0，seq[i] 分给 A 。
 * answer[i] = 1，seq[i] 分给 B 。
 * 如果存在多个满足要求的答案，只需返回其中任意 一个 即可。
 *
 *
 *
 * 示例 1：
 *
 * 输入：seq = "(()())"
 * 输出：[0,1,1,1,1,0]
 * 示例 2：
 *
 * 输入：seq = "()(())()"
 * 输出：[0,0,0,1,1,0,1,1]
 * 解释：本示例答案不唯一。
 * 按此输出 A = "()()", B = "()()", max(depth(A), depth(B)) = 1，它们的深度最小。
 * 像 [1,1,1,0,0,1,1,1]，也是正确结果，其中 A = "()()()", B = "()", max(depth(A), depth(B)) = 1 。
 *
 *
 * 提示：
 *
 * 1 < seq.size <= 10000
 *
 *
 * 有效括号字符串：
 *
 * 仅由 "(" 和 ")" 构成的字符串，对于每个左括号，都能找到与之对应的右括号，反之亦然。
 * 下述几种情况同样属于有效括号字符串：
 *
 *   1. 空字符串
 *   2. 连接，可以记作 AB（A 与 B 连接），其中 A 和 B 都是有效括号字符串
 *   3. 嵌套，可以记作 (A)，其中 A 是有效括号字符串
 * 嵌套深度：
 *
 * 类似地，我们可以定义任意有效括号字符串 s 的 嵌套深度 depth(S)：
 *
 *   1. s 为空时，depth("") = 0
 *   2. s 为 A 与 B 连接时，depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是有效括号字符串
 *   3. s 为嵌套情况，depth("(" + A + ")") = 1 + depth(A)，其中 A 是有效括号字符串
 *
 * 例如：""，"()()"，和 "()(()())" 都是有效括号字符串，嵌套深度分别为 0，1，2，而 ")(" 和 "(()" 都不是有效括号字符串。
 * 通过次数12,165提交次数15,840
 **/

public int[] maxDepthAfterSplit(String seq) {

        int[] res = new int[seq.length()];
        int depth = 0;

        for (int i = 0; i < seq.length(); i++) {
            char c = seq.charAt(i);
            if (c=='('){
                depth++;
                res[i] = depth%2;
            }else {
                res[i] = depth%2;
                depth--;
            }
        }
        return res;
    }

1.1.7. 字符串转换整数 (atoi)

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: CDz
 * Create: 2020-04-03 23:53
 * 8. 字符串转换整数 (atoi)
 * 请你来实现一个 atoi 函数，使其能将字符串转换成整数。
 * <p>
 * 首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
 * <p>
 * 如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
 * 假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
 * 该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
 * 注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
 * <p>
 * 在任何情况下，若函数不能进行有效的转换时，请返回 0 。
 * <p>
 * 提示：
 * <p>
 * 本题中的空白字符只包括空格字符 ' ' 。
 * 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: "42"
 * 输出: 42
 * 示例 2:
 * <p>
 * 输入: "   -42"
 * 输出: -42
 * 解释: 第一个非空白字符为 '-', 它是一个负号。
 * 我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
 * 示例 3:
 * <p>
 * 输入: "4193 with words"
 * 输出: 4193
 * 解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
 * 示例 4:
 * <p>
 * 输入: "words and 987"
 * 输出: 0
 * 解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
 * 因此无法执行有效的转换。
 * 示例 5:
 * <p>
 * 输入: "-91283472332"
 * 输出: -2147483648
 * 解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
 * 因此返回 INT_MIN (−231) 。
 **/

public int myAtoi(String str) {

        str = str.trim();

        char[] chars = str.toCharArray();
        int length = chars.length;

        if (length == 0) return 0;

        boolean negative = false;
        int index = 0;
        if (chars[0] == '-') {
            index++;
            negative = true;
        } else if (chars[0] == '+') {
            index++;
        } else if (!Character.isDigit(chars[0])) {
            return 0;
        }

        int ans = 0;
        while (index < length && Character.isDigit(chars[index])) {

            int i = chars[index] - '0';
            if (ans > (Integer.MAX_VALUE - i) / 10) {
                //本应该是 ans*10+i>Integer.MAX_VALUE
                //但是 ans*10+i可能超出Integer.MAX_VALUE的范围
                return negative?Integer.MIN_VALUE:Integer.MAX_VALUE;
            }
            ans = ans * 10 + i;
            index++;
        }
        return negative ? -ans : ans;
    }

2. review

3. tip

3.1. Spring核心

IOC
- Spring Bean
- applicationcontext
AOP

3.2. http三次握手、四次挥手

3.2.1. 为什么HTTP连接时非要三次握手，为什么不能是两次？

原因：在互联网中，有一个大的前提假设，对方不一定能收到消息，这是最大的不确定，一切都是基于此设计。

三次握手过程：

请求连接端C1发送 (SYN=1,seq=C1_isn)
服务器S1收到C1消息,并返回ACK+SYN(SYN=1,seq=S1_isn,ack=(C1_isn+1))
客户端C1收到S1的ACK+SYN，于是建立连接

我们现在假设只有两次握手，也就是只有没有第三步。

有一种情况，

当第一步发送连接请求
正好此时网络波动，导致S1延迟收到消息，因为只有两次握手此时服务端发送ACK回信息后端口打开。
但是此时C1客户端因为发送的连接请求有超时统计，此时已经超时。
C1会发送重试刚刚建立请求的信息，并且并不会理。
于是server端就接受到了两次C1请求开设了两个连接，其中有一个（第一个）是闲置状态，造成资源浪费。

3.2.2. 为什么HTTP断开是四次挥手？为什么不能是三次？

原因是，HTTP是以流传输的协议，而断开的一方可能是任意时刻，包括另一方流并没有发送完的情况。

连接断开流程：

C1一方发起断开请求
S1接收到断开请求，只返回给C1知道断开了，并不返回其他信息
- 因为这个时候可能还有流没有传输完
- 接着C1收到S1收到了断开请求的ACK
当S1发送完信息流后，主动发送给C1断开请求
C1接收到断开后HTTP连接断开

4.1. 学习方法

4.1.1. 架构自己的知识

这是受到刘润的启发，须鲸式学习。

什么叫须鲸式学习？

须鲸是一种海底生物，它吃食物的过程是，张开大嘴一直向前进，经过的所有东西都进去嘴里，选择性的留下自己需要的。

可以看到这个关键是如何选择性的留下自己需要的？。

架构自己的知识体系。

想清楚自己要吸收那些知识，将一个知识框架罗列出来，记在心中，脑海中有一张树形的图。

接下来就是海量的去接触知识，并且匹配自己的知识框架。

当然这个过程中并不是说框架永远一成不变。随着自己的知识积累，它是有变化的，时长反思，但是大的框架最好不要变。

永远来记住，反馈是冠军的早餐。

任何知识，脱离了反馈，那其实只是了解而已。

算法（Hard难度）、spring总结、HTTP协议总结、须鲸式学习

1. although

1.1. 每日一练

1.1.1. 圆圈中最后剩下的数字

1.1.2. 排序数组

1.1.3. LFU缓存

1.1.4. 接雨水

1.1.5. 生命游戏

1.1.6. 有效括号的嵌套深度

1.1.7. 字符串转换整数 (atoi)

2. review

3. tip

3.1. Spring核心

3.2. http三次握手、四次挥手

3.2.1. 为什么HTTP连接时非要三次握手，为什么不能是两次？

3.2.2. 为什么HTTP断开是四次挥手？为什么不能是三次？

4.1. 学习方法

4.1.1. 架构自己的知识

CATALOG

FEATURED TAGS

FRIENDS

1. although

1.1. 每日一练

1.1.1. 圆圈中最后剩下的数字

1.1.2. 排序数组

1.1.3. LFU缓存

1.1.4. 接雨水

1.1.5. 生命游戏

1.1.6. 有效括号的嵌套深度

1.1.7. 字符串转换整数 (atoi)

2. review

3. tip

3.1. Spring核心

3.2. http三次握手、四次挥手

3.2.1. 为什么HTTP连接时非要三次握手，为什么不能是两次？

3.2.2. 为什么HTTP断开是四次挥手？为什么不能是三次？

4. share

4.1. 学习方法

4.1.1. 架构自己的知识

CATALOG

FEATURED TAGS

FRIENDS