Nicksxs's Blog

题目介绍

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

前阵子做了zk 的集群升级迁移，大概情况是原来是一个三节点的 zk 集群（最小可用
大概是

1
2
3

zk1 192.168.2.1
zk2 192.168.2.2
zk3 192.168.2.3

在 zoo.cfg 中的配置就是如下

1
2
3

server.1=192.168.2.1:2888:3888
server.2=192.168.2.2:2888:3888
server.3=192.168.2.3:2888:3888

加节点

需要将集群迁移到 192.168.2.4（简称 zk4），192.168.2.5（简称 zk5），192.168.2.6（简称 zk6） 这三台机器上，目前新的这三台机器上是没有 zk 部署的, 我们想要的是数据不丢失，那主要考虑的就是滚动升级，这里我其实犯了几个错误，也特别说明下
首先我们想要新的三台机器加进去，所以我在zk4，zk5，zk6 的配置是这样

1
2
3
4
5
6

server.1=192.168.2.1:2888:3888
server.2=192.168.2.2:2888:3888
server.3=192.168.2.3:2888:3888
server.4=192.168.2.4:2888:3888
server.5=192.168.2.5:2888:3888
server.6=192.168.2.6:2888:3888

这样起来发现状态是该节点没起来，
PS：查看当前节点状态可以通过 ./zkServer.sh status 来查看
第一个问题是我需要一个myid文件，标识我是哪个节点，里面的内容就写 4或 5 或 6 这样就行了，并且这个文件的路径应该在配置文件中指定的dataDir=数据目录下
第二个问题是困扰我比较久的，我在按上面的配置启动节点后，发现这几个节点都是没起来的，并且有 FastLeaderElection@xxx - Notification time out: 60000 这个报错，一开始以为是网络不通，端口没开这些原因，检查了下都是通的，结果原因其实跟我之前的一个考虑是相关的，当有六个节点的时候，理论上需要有半数以上的节点可用，集群才会是健康的，但是按我这个方式起来，其实我配置了六个节点，但是其中三个都是不可用的（包括自身节点），那么它自然是没办法正常工作，所以这里其实也需要滚动添加，类似于这样
我的 zk4 的配置应该是这样

1
2
3
4

server.1=192.168.2.1:2888:3888
server.2=192.168.2.2:2888:3888
server.3=192.168.2.3:2888:3888
server.4=192.168.2.4:2888:3888

然后 zk5 的配置

1
2
3
4
5

server.1=192.168.2.1:2888:3888
server.2=192.168.2.2:2888:3888
server.3=192.168.2.3:2888:3888
server.4=192.168.2.4:2888:3888
server.5=192.168.2.5:2888:3888

接着 zk6 的配置就可以是全部了

1
2
3
4
5
6

server.1=192.168.2.1:2888:3888
server.2=192.168.2.2:2888:3888
server.3=192.168.2.3:2888:3888
server.4=192.168.2.4:2888:3888
server.5=192.168.2.5:2888:3888
server.6=192.168.2.6:2888:3888

然后为了集群完全更新，就继续在 zk4 和 zk5 加上其他节点，这样我的 6 节点集群就起来了

下节点

这里我踩了另外一个坑，或者说没搞清楚两种方式的差别，

第一种

首先说说我没采用的第一种方式，（也是比较合理的）其实上面这个集群有个明显的问题，老集群其实还是各自认了一个三节点的集群，其中 zk3 是主节点，对于 zk1，zk2，zk3 来说它们能看到的就只有这三个节点，对于后三个 zk4，zk5，zk6 节点来说他们能连上其余五个节点，可以认为这是个六节点的集群，那么比较合理的操作应该是在老的三节点上把后面三个也都加进来，即每个节点的配置里 server 都有 6 个，然后我再对老的节点进行下线，这里下线需要注意的比较理想的是下一个节点就要修改配置，挪掉下线的节点后进行一遍重启，比如我知道了集群中的 leader 是在 zk3 上面，那么我先将 zk1 和 zk2 下掉，那么在我将 zk1 下线的之后，我将其他的五个节点都删除 zk1 的配置，然后重启，这样其实不是必须，但相对会可靠些，理论上我也可以在下掉 zk1 和 zk2 之后再修改配置重启其余节点。而当只剩下 zk3，zk4，zk5，zk6 四个节点的集群后，并且每个节点里的配置也只有这四个 server，我再下线 zk3 这个 leader 的时候，就会进行选举，再选出新的 leader，因为刚好是三节点，同样保证了最小可用。

第二种

这也是我踩坑的一种方式，就是我没有修改原来三节点的配置，并且我一开始以为可以通过下线 zk1，zk2，zk3（进行选举）的方式完成下线，然后再进行重启，但是这种方式就是我上面说的，原来的三节点里我下掉 zk1 还是能够正常运行，但是我下线 zk2 的时候，这个集群就等于是挂了，小于最小可用了，这样三节点都挂了，而且对于新加入的三个节点来说，又回到了最初起不来一样状态，六节点里只有三节点在线，导致整个集群都挂了，所以对于我这样的操作来说，我需要滚动修改启动，在下线 zk1 的时候就需要把 zk4，zk5，zk6 中的 zk1 移除后重启，当然这样唯一的好处就是可以少重启几个，同样继续下线 zk2 的时候，把 zk2 移除掉再重启，其实在移除 zk1 后修改重启后，在下线 zk2 的时候，集群就会重新选举了，因为 zk2 下线的时候，zk3 还是会一起下线。这个是我们需要特别注意的

在目前的房子也差不多租了四五年了，楼下邻居换了两拨了，我们这栋楼装修了不知道多少次，因为是学区的原因，房子交易的频率还是比较高的，不过比较神奇的我们对门的没换过，而且一直也没什么交集（除了后面说的水管爆裂），就进出的时候偶尔看到应该是住着一对老夫妻，感觉年纪也有个七八十了。

对对面这户人家的印象，就是对面的老头子经常是我出门上班去了他回来，看着他颤颤巍巍地走楼梯，我看到了都靠边走，而且有几次还听见好像是他儿子在说他，”年假这么大了，还是少出去吧”，说实话除了这次的事情，之前就有一次水管阀门爆裂了，算是有点交集，那次大概是去年冬天，天气已经很冷了，我们周日下午回来看到楼梯有点湿，但是没什么特别的异常就没怎么注意，到晚上洗完澡，楼下的邻居就来敲门，说我们门外的水表那一直在流水，出门一看真的是懵了，外面水表那在哗哗哗地流水，导致楼梯那就跟水帘洞一样，仔细看看是对面家的水表阀门那在漏水，我只能先用塑料袋包一下，然后大冬天（刚洗完澡）穿着凉拖跑下去找物业保安，走到一楼的时候发现水一直流到一楼了，楼梯上都是水流下来，五楼那是最惨的，感觉门框周边都浸透了，五楼的也是态度比较差的让我一定要把水弄好了，但是前面也说了谁是从对门那户的水表阀那出来的，理论上应该让对面的处理，结果我敲门敲了半天对面都没反应，想着我放着不管也不太好，就去找了物业保安，保安上来看了只能先把总阀关了，我也打电话给维修自来水管的，自来水公司的人过了会也是真的来修了，我那会是挺怕不来修，自来水公司的师傅到了以后拿开一看是对面那户的有个阀门估计是自己换上去的，跟我们这的完全不一样，看上去就比较劣质，师傅也挺气的，大晚上被叫过来，我又尝试着去敲门也还是没人应，也没办法，对面老人家我敲太响到时候出来说我吓到他们啥的，第二天去说也没现场了。

前面的这件事是个重要铺垫，前几天 LD 下班后把厨余垃圾套好袋子放在门口，打算等我下班了因为要去做核酸（hz 48 小时核酸）顺便带下去，结果到了七点多，说对面的老太太在那疯狂砸门了，LD 被吓到了不敢开门，老太太在外面一边砸门一边骂，“你们年轻人怎么素质这么差”（他们家也经常在门口放垃圾，我们刚来住的时候在楼梯转角他们就放这个废弃的洗衣机，每次走楼梯带点东西都要小心翼翼地走，不然都过不去，然后我赶紧赶回去，结果她听到我回家了，还特意开门继续骂，“你们年轻人怎么素质这么差，垃圾放在这里”，我说我们刚才放在这，打算待会做核酸的时候去扔掉，结果他们家老头，都已经没了牙齿，在那瞪大眼睛说，“你们早上就放在这了的，”我说是LD 刚才下班了放的，争论了一会，我说这个事情我们门口放了垃圾，这会我就去扔掉了，但是你们家老太太这么砸门总不太好，像之前门口水管爆掉了，我敲了门没人应，我也没要砸门一定把你们叫醒，结果老头老太说我们的水管从来没换过，不可能破的（其实到这，再往后说就没意思了，跟这么不要脸的人说多了也只是瞎扯），一会又回到这个垃圾的问题，那个老头说“你们昨天就放在这里了的”，睁着眼说瞎话可真是 666，感觉不是老太太拦着点他马上就要冲上来揍我了一样，事后我想想，这种情况我大概只能躺地上装死了，当这个事情发生之前我真的快把前面说的事情（水管阀坏了）给忘了，虽然这是理论上不该我来处理，除非是老头老太太请求我帮忙，这事后面我也从没说起过，本来完全没交集，对他们的是怎么样的人也没概念，总觉得年纪大了可能还比较心宽和蔼点，结果没想到就是一典型的坏人变老了，我说你们这么砸门，我老婆都被吓得不敢开门，结果对面老头老太太的儿子也出来了说，“我们就是敲下门，我母亲是机关单位退休的，所以肯定不会敲门很大声的，你老婆觉得吓到了是你们人生观价值观有问题”，听到这话我差点笑出来，连着两个可笑至极的脑残逻辑，无语他妈给无语开门，无语到家了。对门家我们之前有个印象就是因为我们都是顶楼，这边老小区以前都是把前后阳台包进来的，然后社区就来咨询大家的意见是不是统一把包进来的违建拆掉，还特地上来六楼跟他们说，结果对面的老头就说，“我要去住建局投诉你们”，本来这个事情是违法的，但是社区的意思也是征求各位业主的意见，结果感觉是社区上门强拆了一样，为老不尊，坏人变老了的典范了。