0%

## Leetcode 105 从前序与中序遍历序列构造二叉树(Construct Binary Tree from Preorder and Inorder Traversal) 题解分析

Posted on 2020-12-13 In Java , leetcode , Binary Tree , java , Binary Tree , DFS Views: Disqus:

## 题目介绍

Given preorder and inorder traversal of a tree, construct the binary tree.
给定一棵树的前序和中序遍历，构造出一棵二叉树

### 注意

You may assume that duplicates do not exist in the tree.
你可以假设树中没有重复的元素。(PS: 不然就没法做了呀)

### 例子:

    1
    2
    preorder = [3,9,20,15,7]
    inorder = [9,3,15,20,7]

返回的二叉树

    1
    2
    3
    4
    5
      3
     / \
    9  20
      /  \
     15   7

## 简要分析

看到这个题可以想到一个比较常规的解法就是递归拆树，前序就是根左右，中序就是左根右，然后就是通过前序已经确定的根在中序中找到，然后去划分左右子树，这个例子里是 3，找到中序中的位置，那么就可以确定，9 是左子树，15,20,7是右子树，然后对应的可以根据左右子树的元素数量在前序中划分左右子树，再继续递归就行

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
          // 获取下数组长度
            int n = preorder.length;
            // 排除一下异常和边界
            if (n != inorder.length) {
                return null;
            }
            if (n == 0) {
                return null;
            }
            if (n == 1) {
                return new TreeNode(preorder[0]);
            }
            // 获得根节点
            TreeNode node = new TreeNode(preorder[0]);
            int pos = 0;
            // 找到中序中的位置
            for (int i = 0; i < inorder.length; i++) {
                if (node.val == inorder[i]) {
                    pos = i;
                    break;
                }
            }
            // 划分左右再进行递归，注意下`Arrays.copyOfRange`的用法
            node.left = buildTree(Arrays.copyOfRange(preorder, 1, pos + 1), Arrays.copyOfRange(inorder, 0, pos));
            node.right = buildTree(Arrays.copyOfRange(preorder, pos + 1, n), Arrays.copyOfRange(inorder, pos + 1, n));
            return node;
        }
    }

## Leetcode 155 最小栈(Min Stack) 题解分析

Posted on 2020-12-06 In Java , leetcode , java , stack , stack Views: Disqus:

## 题目介绍

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
设计一个栈，支持压栈，出站，获取栈顶元素，通过常数级复杂度获取栈中的最小元素

- push(x) – Push element x onto stack.
- pop() – Removes the element on top of the stack.
- top() – Get the top element.
- getMin() – Retrieve the minimum element in the stack.

## 示例

Example 1:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    Input
    ["MinStack","push","push","push","getMin","pop","top","getMin"]
    [[],[-2],[0],[-3],[],[],[],[]]

    Output
    [null,null,null,null,-3,null,0,-2]

    Explanation
    MinStack minStack = new MinStack();
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    minStack.getMin(); // return -3
    minStack.pop();
    minStack.top();    // return 0
    minStack.getMin(); // return -2

## 简要分析

其实现在大部分语言都自带类栈的数据结构，Java 也自带 stack 这个数据结构，所以这个题的主要难点的就是常数级的获取最小元素，最开始的想法是就一个栈外加一个记录最小值的变量就行了，但是仔细一想是不行的，因为随着元素被 pop 出去，这个最小值也可能需要梗着变化，就不太好判断了，所以后面是用了一个辅助栈。

## 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    class MinStack {
            // 这个作为主栈
            Stack<Integer> s1 = new Stack<>();
            // 这个作为辅助栈，放最小值的栈
            Stack<Integer> s2 = new Stack<>();
            /** initialize your data structure here. */
            public MinStack() {

            }

            public void push(int x) {
                // 放入主栈
                s1.push(x);
                // 当 s2 是空或者当前值是小于"等于" s2 栈顶时，压入辅助最小值的栈
                // 注意这里的"等于"非常必要，因为当最小值有多个的情况下，也需要压入栈，否则在 pop 的时候就会不对等
                if (s2.isEmpty() || x <= s2.peek()) {
                    s2.push(x);
                }
            }

            public void pop() {
                // 首先就是主栈要 pop，然后就是第二个了，跟上面的"等于"很有关系，
                // 因为如果有两个最小值，如果前面等于的情况没有压栈，那这边相等的时候 pop 就会少一个了，可能就导致最小值不对了
                int x = s1.pop();
                if (x == s2.peek())  {
                    s2.pop();
                }
            }

            public int top() {
                // 栈顶的元素
                return s1.peek();
            }

            public int getMin() {
                // 辅助最小栈的栈顶
                return s2.peek();
            }
        }

## 从清华美院学姐聊聊我们身边的恶人

Posted on 2020-11-29 In 生活 , 吐槽 , 疫情 , 口罩 Views: Disqus:

前几天清华美院学姐的热点火了，然后仔细看了下，其实是个学姐诬陷以为其貌不扬的男同学摸她屁股
然后还在朋友圈发文想让他社死，我也是挺晚才知道这个词什么意思，然后后面我看到了这个图片，挺有意思的
本来其实也没什么想聊这个的，是在 B 站看了个吐槽这个的，然后刚好晚上乘公交的时候又碰到了有点类似的问题
故事描述下，我们从始发站做了公交，这辆公交司机上次碰到过一回，就是会比较关注乘客的佩戴情况，主要考虑到目前国内疫情，然后这次在差不多人都坐满的情况下，可能在提示了三次让车内乘客戴好口罩，但是他指的那个中年女性还是没有反应，司机就转头比较大声指着这个乘客（中年女性）让戴好口罩，然后这个乘客（中年女性）就大声的说“我口罩是滑下来了，你指着我干嘛，你态度这么差，要吃了我一样，我要投诉你”等等，然后可能跟她一块的一个中年女性也是这么帮腔指责司机，比较基本的理解，车子里这么多乘客，假如是处于这位乘客口罩滑下来了而不自知的情况下，司机在提示了三次以后回头指着她说，我想的是没什么问题的，但是这位却反而指责这位司机指着她，并且说是态度差，要吃了她，完全是不可理喻的，并且一直喋喋不休说她口罩滑掉了有什么错，要投诉这个司机，让他可以提前退休了，在其他乘客的劝说下司机准备继续开车时，又口吐芬芳“你个傻，你来打我呀”，真的是让我再次体会到了所谓的恶人先告状的又一完美呈现，后面还有个乘客还是表示要打死司机这个傻，让我有点不明所以，俗话说有人是得理不饶人，前提是得理，这种理亏不饶人真的是挺让人长见识的，试想下，司机在提示三次后，这位乘客还是没有把口罩戴好，如何在不指着这位乘客的情况下能准确的提示到她呢，并且觉得语气态度不好，司机要载着一车的人，因为你这一个乘客不戴好口罩而不能正常出发，有些着急应该很正常吧，可能是平时自己在家里耀武扬威的使唤别人习惯了吧，别人不敢这么大声跟她说话，其实想想这位中年女性应该年纪不会很大，还比较时髦的吧，像一些常见的中年杭州本地人可能是不会说傻*这个词的吧。
杭州的公交可能是在二月份疫情还比较严重的时候是要求上车出示健康码，后面比较缓和以后只要求佩戴好口罩，但是在我们小绍兴，目前还是一律要求检验健康码和佩戴口罩，对于疫情中，并且目前阶段国内也时有报出小范围的疫情的情况下，司机尽职要求佩戴好口罩其实也是为了乘客着想，另一种情况如果司机不严格要求，万一车上有个感染者，这位中年女性被传染了，如果能找到这个司机的话，是不是想“打死”这个司机，竟然让感染者上了车，反正她自己是不可能有错的，上来就是对方态度差，要投诉，自己不戴好口罩啥都没错，我就想知道如果因为自己没戴好口罩被感染了，是不是也是司机的错，毕竟没有像仆人那样点头哈腰求着她戴好口罩。
再说回来，整个车就她一个人没戴好口罩，并且还有个细节，其实这个乘客是上了车之后就没戴好了，本来上车的时候是戴好的，这种比较有可能是觉得上车的时候司机那看一眼就好了，如果好好戴着口罩，一点事情都没有，唉，纯粹是太气愤了，调理逻辑什么的就忽略吧

## 聊聊 Dubbo 的容错机制

Posted on 2020-11-22 In Java , Dubbo , Dubbo - RPC , 容错机制 Views: Disqus:

之前看了 dubbo 的一些代码，在学习过程中，主要关注那些比较“高级”的内容，SPI，自适应扩展等，却忘了一些作为一个 rpc 框架最核心需要的部分，比如如何通信，序列化，网络，容错机制等等，因为其实这个最核心的就是远程调用，自适应扩展其实就是让代码可扩展性，可读性，更优雅等，写的搓一点其实也问题不大，但是一个合适的通信协议，序列化方法，如何容错等却是真正保证是一个 rpc 框架最重要的要素。
首先来看这张图
在集群调用失败时，Dubbo 提供了多种容错方案，缺省为 failover 重试。
各节点关系：

- 这里的 `Invoker` 是 `Provider` 的一个可调用 `Service` 的抽象，`Invoker` 封装了 `Provider` 地址及 `Service` 接口信息
- `Directory` 代表多个 `Invoker`，可以把它看成 `List<Invoker>` ，但与 `List` 不同的是，它的值可能是动态变化的，比如注册中心推送变更
- `Cluster` 将 `Directory` 中的多个 `Invoker` 伪装成一个 `Invoker`，对上层透明，伪装过程包含了容错逻辑，调用失败后，重试另一个
- `Router` 负责从多个 `Invoker` 中按路由规则选出子集，比如读写分离，应用隔离等
- `LoadBalance` 负责从多个 `Invoker` 中选出具体的一个用于本次调用，选的过程包含了负载均衡算法，调用失败后，需要重选

## 集群容错模式

### Failover Cluster

失败自动切换，当出现失败，重试其它服务器 1。通常用于读操作，但重试会带来更长延迟。可通过 retries=”2” 来设置重试次数(不含第一次)。

重试次数配置如下：

<dubbo:service retries=”2” />
这里重点看下 `Failover Cluster`集群模式的实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    public class FailoverCluster implements Cluster {

        public final static String NAME = "failover";

        public <T> Invoker<T> join(Directory<T> directory) throws RpcException {
            return new FailoverClusterInvoker<T>(directory);
        }

    }

这个代码就非常简单，重点需要看`FailoverClusterInvoker`里的代码，`FailoverClusterInvoker`继承了`AbstractClusterInvoker`类，其中invoke 方法是在抽象类里实现的

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    @Override
    public Result invoke(final Invocation invocation) throws RpcException {
        checkWhetherDestroyed();
        // binding attachments into invocation.
        // 绑定 attachments 到 invocation 中.
        Map<String, Object> contextAttachments = RpcContext.getContext().getObjectAttachments();
        if (contextAttachments != null && contextAttachments.size() != 0) {
            ((RpcInvocation) invocation).addObjectAttachments(contextAttachments);
        }
        // 列举 Invoker
        List<Invoker<T>> invokers = list(invocation);
        // 加载 LoadBalance 负载均衡器
        LoadBalance loadbalance = initLoadBalance(invokers, invocation);
        RpcUtils.attachInvocationIdIfAsync(getUrl(), invocation);
        // 调用 实际的 doInvoke 进行后续操作
        return doInvoke(invocation, invokers, loadbalance);
    }
    // 这是个抽象方法，实际是由子类实现的
     protected abstract Result doInvoke(Invocation invocation, List<Invoker<T>> invokers,
                                           LoadBalance loadbalance) throws RpcException;

然后重点就是`FailoverClusterInvoker`中的`doInvoke`方法了，其实它里面也就这么一个方法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    @Override
        @SuppressWarnings({"unchecked", "rawtypes"})
        public Result doInvoke(Invocation invocation, final List<Invoker<T>> invokers, LoadBalance loadbalance) throws RpcException {
            List<Invoker<T>> copyInvokers = invokers;
            checkInvokers(copyInvokers, invocation);
            String methodName = RpcUtils.getMethodName(invocation);
            // 获取重试次数，这里默认是 2 次，还有可以注意下后面的+1
            int len = getUrl().getMethodParameter(methodName, RETRIES_KEY, DEFAULT_RETRIES) + 1;
            if (len <= 0) {
                len = 1;
            }
            // retry loop.
            RpcException le = null; // last exception.
            List<Invoker<T>> invoked = new ArrayList<Invoker<T>>(copyInvokers.size()); // invoked invokers.
            Set<String> providers = new HashSet<String>(len);
            // 循环调用，失败重试
            for (int i = 0; i < len; i++) {
                //Reselect before retry to avoid a change of candidate `invokers`.
                //NOTE: if `invokers` changed, then `invoked` also lose accuracy.
                if (i > 0) {
                    checkWhetherDestroyed();
                    // 在进行重试前重新列举 Invoker，这样做的好处是，如果某个服务挂了，
                    // 通过调用 list 可得到最新可用的 Invoker 列表
                    copyInvokers = list(invocation);
                    // check again
                    // 对 copyinvokers 进行判空检查
                    checkInvokers(copyInvokers, invocation);
                }
                // 通过负载均衡来选择 invoker
                Invoker<T> invoker = select(loadbalance, invocation, copyInvokers, invoked);
                // 将其添加到 invoker 到 invoked 列表中
                invoked.add(invoker);
                // 设置上下文
                RpcContext.getContext().setInvokers((List) invoked);
                try {
                    // 正式调用
                    Result result = invoker.invoke(invocation);
                    if (le != null && logger.isWarnEnabled()) {
                        logger.warn("Although retry the method " + methodName
                                + " in the service " + getInterface().getName()
                                + " was successful by the provider " + invoker.getUrl().getAddress()
                                + ", but there have been failed providers " + providers
                                + " (" + providers.size() + "/" + copyInvokers.size()
                                + ") from the registry " + directory.getUrl().getAddress()
                                + " on the consumer " + NetUtils.getLocalHost()
                                + " using the dubbo version " + Version.getVersion() + ". Last error is: "
                                + le.getMessage(), le);
                    }
                    return result;
                } catch (RpcException e) {
                    if (e.isBiz()) { // biz exception.
                        throw e;
                    }
                    le = e;
                } catch (Throwable e) {
                    le = new RpcException(e.getMessage(), e);
                } finally {
                    providers.add(invoker.getUrl().getAddress());
                }
            }
            throw new RpcException(le.getCode(), "Failed to invoke the method "
                    + methodName + " in the service " + getInterface().getName()
                    + ". Tried " + len + " times of the providers " + providers
                    + " (" + providers.size() + "/" + copyInvokers.size()
                    + ") from the registry " + directory.getUrl().getAddress()
                    + " on the consumer " + NetUtils.getLocalHost() + " using the dubbo version "
                    + Version.getVersion() + ". Last error is: "
                    + le.getMessage(), le.getCause() != null ? le.getCause() : le);
        }

### Failfast Cluster

快速失败，只发起一次调用，失败立即报错。通常用于非幂等性的写操作，比如新增记录。

### Failsafe Cluster

失败安全，出现异常时，直接忽略。通常用于写入审计日志等操作。

### Failback Cluster

失败自动恢复，后台记录失败请求，定时重发。通常用于消息通知操作。

### Forking Cluster

并行调用多个服务器，只要一个成功即返回。通常用于实时性要求较高的读操作，但需要浪费更多服务资源。可通过 forks=”2” 来设置最大并行数。

### Broadcast Cluster

广播调用所有提供者，逐个调用，任意一台报错则报错 2。通常用于通知所有提供者更新缓存或日志等本地资源信息。

## Leetcode 234 回文链表(Palindrome Linked List) 题解分析

Posted on 2020-11-15 Edited on 2020-12-13 In Java , leetcode , Linked List , java , Linked List Views: Disqus:

## 题目介绍

Given a singly linked list, determine if it is a palindrome.
给定一个单向链表，判断是否是回文链表

### 例一 Example 1:

Input: 1->2
Output: false

### 例二 Example 2:

Input: 1->2->2->1
Output: true

### 挑战下自己

Follow up:
Could you do it in O(n) time and O(1) space?

## 简要分析

首先这是个单向链表，如果是双向的就可以一个从头到尾，一个从尾到头，显然那样就没啥意思了，然后想过要不找到中点，然后用一个栈，把前一半塞进栈里，但是这种其实也比较麻烦，比如长度是奇偶数，然后如何找到中点，这倒是可以借助于双指针，还是比较麻烦，再想一想，回文链表，就跟最开始的一样，链表只有单向的，我用个栈不就可以逆向了么，先把链表整个塞进栈里，然后在一个个 pop 出来跟链表从头开始比较，全对上了就是回文了

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public boolean isPalindrome(ListNode head) {
            if (head == null) {
                return true;
            }
            ListNode tail = head;
            LinkedList<Integer> stack = new LinkedList<>();
            // 这里就是一个循环，将所有元素依次压入栈
            while (tail != null) {
                stack.push(tail.val);
                tail = tail.next;
            }
            // 在逐个 pop 出来，其实这个出来的顺序就等于链表从尾到头遍历，同时跟链表从头到尾遍历进行逐对对比
            while (!stack.isEmpty()) {
                if (stack.peekFirst() == head.val) {
                    stack.pollFirst();
                    head = head.next;
                } else {
                    return false;
                }
            }
            return true;
        }
    }