Nicksxs's Blog

题目介绍

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

示例

Example 1:

Input: s = “()”
Output: true

Example 2:

Input: s = “()[]{}”
Output: true

Example 3:

Input: s = “(]”
Output: false

Constraints:

• 1 <= s.length <= 10^4
• s consists of parentheses only '()[]{}'.

解析

easy题，并且看起来也是比较简单的，三种括号按对匹配，直接用栈来做，栈里面存的是括号的类型，如果是左括号，就放入栈中，如果是右括号，就把栈顶的元素弹出，如果弹出的元素不是左括号，就返回false，如果弹出的元素是左括号，就继续往下走，如果遍历完了，如果栈里面还有元素，就返回false，如果遍历完了，如果栈里面没有元素，就返回true

代码

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

class Solution {
    public boolean isValid(String s) {

        if (s.length() % 2 != 0) {
            return false;
        }
        Stack<String> stk = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '{' || s.charAt(i) == '(' || s.charAt(i) == '[') {
                stk.push(String.valueOf(s.charAt(i)));
                continue;
            }
            if (s.charAt(i) == '}') {
                if (stk.isEmpty()) {
                    return false;
                }
                String cur = stk.peek();
                if (cur.charAt(0) != '{') {
                    return false;
                } else {
                    stk.pop();
                }
                continue;
            }
            if (s.charAt(i) == ']') {
                if (stk.isEmpty()) {
                    return false;
                }
                String cur = stk.peek();
                if (cur.charAt(0) != '[') {
                    return false;
                } else {
                    stk.pop();
                }
                continue;
            }
            if (s.charAt(i) == ')') {
                if (stk.isEmpty()) {
                    return false;
                }
                String cur = stk.peek();
                if (cur.charAt(0) != '(') {
                    return false;
                } else {
                    stk.pop();
                }
                continue;
            }

        }
        return stk.size() == 0;
    }
}

发生疫情之后，因为正好是春节假期，假期结束的时候还不具备回工作地点办公的条件，所以史无前例地开始了远程办公，以前对于远程办公的概念还停留在国外一些有“格局”的企业会允许员工远程办公，当然对于远程办公这个事情本身我个人也并不是全然支持的态度，其中涉及到很多方面，首先远程办公并不代表就是不用去办公地点上班，可以在家里摸鱼，相对能够得到较高报酬的能够远程办公的企业需要在远程办公期间能够有高效的产出，并且也需要像在公司办公地点一样，能随时被联系到，第二点是薪资福利之外的社保公积金，除非薪资相比非远程办公的企业高出比较多，不然没法 cover 企业额外缴纳的社保公积金，听说有部分企业也会远程办公点给员工上社保，但是毕竟能做到这点的很少，在允许远程办公的企业数量这个本来就不大的基数里，大概率是少之又少了。
疫情这个特殊原因开始的远程办公体验也算是开了个之前不太容易开的头，也跟我前面说的第一点有关系，大部分的企业也会担心员工远程办公是否有与在公司办公地点办公一样或者比较接近的办公效率。同时我们在开始远程办公的时候也碰到了因为原先没做过相应准备而导致的许多问题，首先基础设施上就有几个问题，第一个是办公电脑的问题，因为整个公司各个部门的工作性质和内容不同，并不是每个部门都是配笔记本的，或者有些部门并不需要想研发一样带上电脑 on call，所以那么使用台式机或者没有将笔记本带回家的则需要自己准备电脑或者让公司邮寄。第二个是远程网络的问题，像我们公司有研发团队平时也已经准备好了 vpn，但是在这种时候我们没准备好的是 vpn 带宽，毕竟平时只会偶尔有需要连一下 vpn 到公司网络，像这样大量员工都需要连接 vpn 进行工作的话，我们的初步体验就是网络卡的不行，一些远程调试工作没法进行，并且还有一些问题是可能只有我们研发会碰到，比如我们的线上测试服务器网络在办公地点是有网络打通的，但是我们在家就没办法连接，还有就是沟通效率相关，因为这是个全国性的情况，线上会议工具原先都是为特定用户使用，并且视频音频实时传输所需要的带宽质量要求也是比较高的，大规模的远程会议沟通需求让这些做线上会议的服务也算是碰上了类似双十一的大考了，我们是先后使用了 zoom，腾讯会议跟钉钉视频会议，使用体验上来说是 zoom 做得相对比较成熟和稳定，不过后面腾讯会议跟钉钉视频会议也开始赶上来。
前面说的这几个点都是得有远程办公经验的公司才会提前做好相应的准备，比如可以做动态网络扩容，能够在需要大量员工连接公司网络的情况下快速响应提升带宽，另一些则是偏软性的，比如如如何在远程办公的条件下控制我们项目进度，如果保证沟通信息是否能像当面沟通那样准确传达，这方面其实我的经验也是边实操边优化的，最开始我们可能为了高效同步消息，会频繁的使用视频会议沟通，这其实并不能解决沟通效率问题，反而打扰了正常的工作，后续我们在特别是做项目过程中就通过相对简单的每日早会和日报机制，将每天的进度与问题风险点进行同步确认，只与相关直接干系人进行视频电话沟通确认，并且要保持一个思维，即远程办公比较适宜的是相对比较成熟的团队，平常工作和合作都已经有默契或者说规则并且能够遵守，在这个前提下，将目光专注于做的事情而不是管到具体的人有没有全天都在高效工作。同样也希望国内的环境能够有更多的远程火种成长起来，让它成为更好的工作方式，WLB！

题目介绍

Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

示例

Example 1:

Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true
Explanation: It is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Example 2:

Input: nums = [1,2,3,4], k = 3
Output: false

Constraints:

• 1 <= k <= nums.length <= 16
• 1 <= nums[i] <= 10^4
• The frequency of each element is in the range [1, 4].

解析

看到这个题一开始以为挺简单，但是仔细想想问题还是挺多的，首先是分成 k 组，但是数量不限，应该需要用到回溯的方式，同时对于时间和空间复杂度也有要求，一开始这个代码是超时的，我也试了下 leetcode 上 discussion 里 vote 最高的提交也是超时的，不过看 discussion 里的帖子，貌似是后面加了一些条件，可以帮忙提高执行效率，第三条提示不太清楚意图，具体可以看下代码

代码

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

public boolean canPartitionKSubsets(int[] nums, int k) {
    if (k == 1) {
        return true;
    }
    int sum = 0, n;
    n = nums.length;
    for (int num : nums) {
        sum += num;
    }
    if (sum % k != 0) {
        return false;
    }

    int avg = sum / k;
    // 排序
    Arrays.sort(nums);
    // 做个前置判断，如果最大值超过分组平均值了就可以返回 false 了
    if (nums[n - 1] > avg) {
        return false;
    }
    // 这里取了个巧，先将数组中元素就等于分组平均值的直接排除了
    int calculated = 0;
    for (int i = n - 1; i > 0; i--) {
        if (nums[i] == avg) {
            k--;
            calculated++;
        }
    }

    int[] bucket = new int[k];
    // 初始化 bucket
    for (int i = 0; i < k; i++) {
        bucket[i] = avg;
    }

    // 提前做下边界判断
    if (nums[n - 1] > avg) {
        return false;
    }

    return backTraversal(nums, bucket, k, n - 1 - calculated);
}

private boolean backTraversal(int[] nums, int[] bucket, int k, int cur) {
    if (cur < 0) {
        return true;
    }
    for (int i = 0; i < k; i++) {
        if (bucket[i] == nums[cur] || bucket[i] >= nums[cur] + nums[0]) {
            // 判断如果当前 bucket[i] 剩余的数字等于nums[cur], 即当前bucket已经满了
            // 或者如果当前 bucket[i] 剩余的数字大于等于 nums[cur] + nums[0] ，
            // 因为nums 在经过排序后 nums[0]是最小值，如果加上 nums[0] 都已经超过bucket[i] 了，
            // 那当前bucket[i] 肯定是没法由包含 nums[cur] 的组合组成一个满足和为前面 s/k 的组合了
            // 这里判断的是 nums[cur] ,如果第一次 k 次循环都不符合其实就返回 false 了

            // 而如果符合，就将 bucket[i] 减去 nums[cur] 再次进入递归，
            // 这里进入递归有个收敛参数就是 cur - 1，因为其实判断 cur 递减作为一个结束条件
            bucket[i] -= nums[cur];
            // 符合条件，这里对应着入口，当 cur 被减到 0 了，就表示都符合了因为是根据所有值的和 s 和 k 组除出来的平均值，当所有数都通过前面的 if 判断符合了，并且每个数字都使用了，
            // 即说明已经符合要求了
            if (backTraversal(nums, bucket, k, cur - 1)) return true;
            // 这边是个回退机制，如果前面 nums[cur]没办法组合成和为平均值的话就减掉进入下一个循环
            bucket[i] += nums[cur];
        }
    }
    return false;
}

最后贴个图

在配置项目中其实会留着比较多的问题，由于不同的项目没有比较统一的规划和框架模板，一般都是只有创建者会比较了解（可能也不了解），譬如前阵子在配置一个 springboot + dubbo 的项目，发现了dubbo 连接注册中间客户端的问题，这里可以结合下代码来看
比如有的应用是用的这个

1
2
3
4
5
6
7
8
9
10

<dependency>
    <groupId>org.apache.curator</groupId>
    <artifactId>curator-client</artifactId>
    <version>${curator.version}</version>            
</dependency>
<dependency>
    <groupId>org.apache.curator</groupId>
    <artifactId>curator-recipes</artifactId>
    <version>${curator.version}</version>
</dependency>

有个别应用用的是这个

1
2
3
4
5

<dependency>
    <groupId>com.101tec</groupId>
    <artifactId>zkclient</artifactId>
    <version>0.11</version>
</dependency>

还有的应用是找不到相关的依赖，并且这些的使用没有个比较好的说明，为啥用前者，为啥用后者，有啥注意点，
首先在使用 2.6.5 的 alibaba 的 dubbo 的时候，只使用后者是会报错的，至于为啥会报错，其实就是这篇文章想说明的点
报错的内容其实很简单, 就是缺少这个 org.apache.curator.framework.CuratorFrameworkFactory 类
这个类看着像是依赖上面的配置，但是应该不需要两个配置一块用的，所以还是需要去看代码
通过找上面类被依赖的和 dubbo 连接注册中心相关的代码，看到了这段指点迷津的代码

1
2
3
4
5
6
7

@SPI("curator")
public interface ZookeeperTransporter {

    @Adaptive({Constants.CLIENT_KEY, Constants.TRANSPORTER_KEY})
    ZookeeperClient connect(URL url);

}

众所周知，dubbo 创造了叫自适应扩展点加载的神奇技术，这里的 adaptive 注解中的Constants.CLIENT_KEY 和 Constants.TRANSPORTER_KEY 可以在配置 dubbo 的注册信息的时候进行配置，如果是通过 xml 配置的话，可以在 <dubbo:registry/> 这个 tag 中的以上两个 key 进行配置，
具体在 dubbo.xsd 中有描述

1
2
3
4
5

<xsd:element name="registry" type="registryType">
        <xsd:annotation>
            <xsd:documentation><![CDATA[ The registry config ]]></xsd:documentation>
        </xsd:annotation>
    </xsd:element>

并且在 spi 的配置com.alibaba.dubbo.remoting.zookeeper.ZookeeperTransporter 中可以看到

1
2
3
4
5
6
7
8

zkclient=com.alibaba.dubbo.remoting.zookeeper.zkclient.ZkclientZookeeperTransporter
curator=com.alibaba.dubbo.remoting.zookeeper.curator.CuratorZookeeperTransporter

zkclient=com.alibaba.dubbo.remoting.zookeeper.zkclient.ZkclientZookeeperTransporter
curator=com.alibaba.dubbo.remoting.zookeeper.curator.CuratorZookeeperTransporter

zkclient=com.alibaba.dubbo.remoting.zookeeper.zkclient.ZkclientZookeeperTransporter
curator=com.alibaba.dubbo.remoting.zookeeper.curator.CuratorZookeeperTransporter

而在上面的代码里默认的SPI 值是 curator，所以如果不配置，那就会报上面找不到类的问题，所以如果需要使用 zkclient 的，就需要在<dubbo:registry/> 配置中添加 client="zkclient"这个配置，所以有些地方还是需要懂一些更深层次的原理，但也不至于每个东西都要抠到每一行代码原理，除非就是专门做这一块的。
还有一点是发现有些应用是碰运气，刚好有个三方包把这个类带进来了，但是这个应用就没有单独配置这块，如果不了解或者后续忘了再来查问题就会很奇怪

偶尔来个标题党，不过也是一次比较神奇的经历
上周五下班后跟 LD 约好去吃牛蛙，某个朋友好像对这类都不太能接受，我以前小时候也不常吃，但是这类其实都是口味比较重，没有那种肉本身的腥味，而且肉质比较特殊，吃过几次以后就有点爱上了，这次刚好是 LD 买的新店开业券，比较优惠（我们俩都是有点勤俭持家的，想着小电驴还有三格电，这家店又有点远，骑车单趟大概要 10 公里左右，有点担心，LD 说应该可以的，就一起骑了过去（跟她轮换着骑电驴和共享单车），结果大概离吃牛蛙的店还有一辆公里的时候，电量就报警了，只有最后一个红色的了，一共是五格，最后一格是红色的，提示我们该充电了，这样子是真的有点慌了，之前开了几个月都是还有一两格电的时候就充电了，没有试验过究竟这最后一格电能开多远，总之先到了再说。
这家牛蛙没想到还挺热闹的，我们到那已经快八点了，还有十几个排队的，有个人还想插队（向来是不惯着这种，一边去），旁边刚好是有些商店就逛了下，就跟常规的商业中心差不多，开业的比较早也算是这一边比较核心的商业综合体了，各种品牌都有，而且还有彩票售卖点的，只是不太理解现在的彩票都是兑图案的，而且要 10 块钱一张，我的概念里还是以前 2 块钱一张的双色球，偶尔能中个五块十块的。排队还剩四五个的时候我们就去门口坐着等了，又等了大概二十分钟才排到我们，靠近我们等的里面的位置，好像好几个小女生在那还叫了外卖奶茶，然后各种拍照，小朋友的生活还是丰富多彩的，我们到了就点了蒜蓉的，没有点传说中紫苏的，菜单上画了 N 个🌶，LD 还是想体验下说下次人多点可以试试，我们俩吃怕太辣了吃不消，口味还是不错的，这家貌似是 LD 闺蜜推荐的，口碑有保证。两个人光吃一个蛙锅就差不多了，本来还想再点个其他的，后面实在吃不下了就没点，吃完还是惯例点了个奶茶，不过是真的不好找，太大了。
本来是就回个家的事了，结果就因为前面铺垫的小电驴已经只有一格电了，标题的深夜奔袭十公里就出现了，这个电驴估计续航也虚标挺严重的，电量也是这样，骑的时候显示只有一格电，关掉再开起来又有三格，然后我们回去骑了没一公里就没电了，这下是真的完球了，觉得车子也比较新，直接停外面也不放心，就开始了深夜的十公里推电驴奔袭，LD 看我太累还帮我中间推了一段，虽然是跑过十公里的，但是推着个没电的电驴，还是着实不容易的，LD 也是陪我推着车走，中间好几次说我们把电驴停着打车回去，把电池带回去充满了明天再过来骑车，可能是心态已经转变了，这应该算是一次很特殊的体验，从我们吃完出来大概十点，到最后我们推到小区，大概是过了两个小时的样子，说句深夜也不太过分，把这次这么推车看成了一种意志力的考验，很多事情也都是怕坚持，或者说怕不能坚持，想走得远，没有持续的努力坚持肯定是不行的，所以还是坚持着把车推回来（好吧，我其实主要是怕车被偷，毕竟刚来杭州上学没多久就被偷了自行车留下了阴影），中间感谢 LD，跟我轮着推了一段路，有些下坡的时候还在那坐着用脚蹬一下，离家里大概还有一公里的时候，有个骑电瓶车的大叔还停下来问我们是车破了还是没电了，应该是出于好意吧，最后快到的时候真的非常渴，买了2.5 升的水被我一口气喝了大半瓶，奶茶已经不能起到解渴的作用了，本来以为这样能消耗很多，结果第二天一称还重了，（我的称一定有问题 233