LeetCode 之组合总和系列(Combination Sum)

LeetCode 中有多道组合总和(Combination Sum)的题,这些题目都是比较经典的,面试很可能会问到。我这一想,还真是。今天就来简单总结下这一系列题目,总结很重要,还要时而回顾!

Combination Sum I

第一道题的描述如下:

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
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

所有数字(包括 target)都是正整数。
解集不能包含重复的组合。
示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

注意点:

  • candidates 中的数字可以无限制重复被选取。
  • 解集不能包含重复的组合。

这时候头脑里很快就会产生一个思路:无限遍历该数组,直到其元素之和满足条件,然后塞入集合中。

这个想法没问题,不过在这过程中我们怎么才能满足解集不能包含重复的组合。这个条件呢?

对对对,那就是确定一个 index,我们要保证数组不往回找就是了。

解题代码如下:

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
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(candidates);
recursive(list, new ArrayList<>(), candidates, target, 0);
return list;
}

/**
*
* @param list
* 总的输出 list
* @param tempList
* 存放的 list
* @param nums
* 数组
* @param remain
* 剩余值
* @param index
* 数组下标
*/
private void recursive(List<List<Integer>> list, List<Integer> tempList, int[] nums, int remain, int index) {

if (remain < 0) // return 或者进行 add 操作后就开始执行弹出尾部元素 塞入下个元素
return;
else if (remain == 0)
list.add(new ArrayList<>(tempList)); // 这里需要注意不能直接 list.add(tempList),最终 tempList 所指向的对象是空的,
// 所以需要 new 一个新对象,将值复制进去
else {
for (int i = index; i < nums.length; i++) {
tempList.add(nums[i]); // 挨个塞入
recursive(list, tempList, nums, remain - nums[i], i); // 由于元素可重复 所以是 i
tempList.remove(tempList.size() - 1); // 挨个弹出
}
}
}

我这注释什么的都有,理解起来不成问题吧。这里需要注意的就是两个点:list.add(new ArrayList<>(tempList)); recursive(list, tempList, nums, remain - nums[i], i);

这里先对数组进行排序可以使计算更快,当然你也可以不排序。

Combination Sum II

第二道对第一道稍微加工了一下,描述如下:

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
给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明:

所有数字(包括目标数)都是正整数。
解集不能包含重复的组合。
示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]

注意点:

  • candidates 中的每个数字在每个组合中只能使用一次。
  • 解集不能包含重复的组合。

是的,这里把条件改了,数组中的每个元素在每个组合中只能使用一次!

这就意味着每次递归操作时其下标都需要往后移一位了!

代码如下:

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
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(candidates);
recursive(list, new ArrayList<>(), candidates, target, 0);
return list;

}

/**
* DFS 添加每个满足条件的集合
*
* @param list
* 最终返回集合
* @param tempList
* 每个满足条件的子集合
* @param candidates
* 数组
* @param remain
* 剩余值
* @param index
* 数组下标
*/
private void recursive(List<List<Integer>> list, List<Integer> tempList, int[] candidates, int remain, int index) {
if (remain < 0)
return;
else if (remain == 0)
list.add(new ArrayList<>(tempList));
else {
for (int i = index; i < candidates.length; i++) {
if (i > index && candidates[i] == candidates[i - 1]) // 说明两个值相等且之前一个值已经返回
continue;
tempList.add(candidates[i]);
recursive(list, tempList, candidates, remain - candidates[i], i + 1); // 规定数组中每个数字在每个组合中只能使用一次
tempList.remove(tempList.size() - 1);
}
}
}

相比较上一题的代码,这次只是加了一个条件判断以及递归中元素下标加了一。

这里就要对数组先进行排序操作了,新增的条件判断也是为了优化代码执行速度。

Combination Sum III

再来看第三道变形,描述如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。

说明:

所有数字都是正整数。
解集不能包含重复的组合。
示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

这次不给出数组了,而是规定了数组中元素的取值范围。

双手一摊,这还不是一样吗,不给我就自己造就是了!

注意点:

  • 解集不能包含重复的组合。

解题代码如下:

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
public List<List<Integer>> combinationSum3(int k, int n) {
int[] nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
List<List<Integer>> list = new ArrayList<>();
dfs(list, new ArrayList<>(), nums, k, n, 0);
return list;

}

/**
*
* @param list
* 最终返回的 list
* @param tempList
* 作为寻求满足条件的暂存 list
* @param nums
* 数组
* @param reNum
* 剩余的元素个数
* @param reSum
* 剩余的总和
* @param index
* 数组下标
*/
private void dfs(List<List<Integer>> list, List<Integer> tempList, int[] nums, int reNum, int reSum, int index) {
if (reNum < 0 || reSum < 0) // 两者有其一小于 0 就是不满足条件
return;
if (reNum == 0 && reSum == 0) // 两者都为 0 时满足条件,塞入
list.add(new ArrayList<>(tempList));
else if (reNum == 0 || reSum == 0) // 两者中有且只有一者等于 0 就不满足条件
return;
else {
for (int i = index; i < nums.length; i++) {
tempList.add(nums[i]);
dfs(list, tempList, nums, reNum - 1, reSum - nums[i], i + 1); // 不能重复元素 所以 i + 1
tempList.remove(tempList.size() - 1);
}
}
}

真不愧为机智小少年……

Combination Sum IV

第四道变形就复杂了一些了,描述如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
给定一个由正整数组成且不存在重复数字的数组,找出和为给定目标正整数的组合的个数。

示例:

nums = [1, 2, 3]
target = 4

所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意,顺序不同的序列被视作不同的组合。

因此输出为 7。

这里数组的元素可以重复,且组合的元素也能相同,但是顺序要不同。

一开始当然就是无脑循环了,然后满足条件就加上一,结果就是超时……

说明这么暴力不行的……

后来一想,无脑循环就相当于每一次都从头进行循环算了一遍,很多都是重复的计算。

对了,DP 浮现在了脑中,在那飘啊飘。

代码如下:

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
private int[] dp;

/**
* DP
*
* @param nums
* @param target
* @return
*/
public int combinationSum4(int[] nums, int target) {
dp = new int[target + 1];
Arrays.fill(dp, -1);
dp[0] = 1;
return helper(nums, target);
}

private int helper(int[] nums, int target) {
if (dp[target] != -1) {
return dp[target]; // 若是之前的已经计算过了 直接返回
}
int res = 0;
for (int i = 0; i < nums.length; i++) {
if (target >= nums[i]) { // 所有组合的种数相加
res += helper(nums, target - nums[i]);
}
}
dp[target] = res; // 计算后赋值用于之后的数字使用
return res;
}

用空间换取时间的操作,DP + 递归稍微费点脑。

还有一种解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* DP
*
* @param nums
* @param target
* @return
*/
public int combinationSum4(int[] nums, int target) {
int[] comb = new int[target + 1];
comb[0] = 1;
for (int i = 1; i < comb.length; i++) {
for (int j = 0; j < nums.length; j++) {
if (i - nums[j] >= 0) {
comb[i] += comb[i - nums[j]];
}
}
}
return comb[target];
}

好了,组合总和系列(Combination Sum)的题目总结完了。记住了回溯


使用 ssh 反向隧道穿透 NAT 访问 Linux 内网主机

使用 ssh 反向隧道穿透 NAT 访问内网主机

前言

由于公司经常会有项目需要去业主那边搭建服务器,基本不需要什么流量所以就准备用 4G 网卡搭建。而该网卡无固定公网 ip,只有内网 ip,我们目的就是为了可以远程操控以避免有时因业务需要往业主那边跑,要是地方比较远来回一趟也得花个把星期,不划算。所以就研究了下 ssh 隧道穿透来满足我们的需求。

场景

现在我们有三台机子:

  • A:公司内网电脑(Win 10)
  • B:公司内网服务器(Linux,固定外网 ip:58.247.33.44,ssh 开放端口:8862)
  • C:业主那边 4G 网卡搭建的服务器(Linux,无固定外网 ip,ssh 开放端口:22)

操作前:A 可以访问 B,C 能上网也能访问 B,但是 B 不能访问 C,A 不能访问 C
我们需要满足:A 可以访问 C

当然,很多远程桌面软件可以满足我们这个需求,但是由于太不方便和不稳定,还是考虑 ssh。(安装 ssh 可见底文的附加安装指令

配置

配置 B 服务器

  • 修改服务器上的 sshd 设置

vim /etc/ssh/shhd_config 建议使用 vim,vim 比 vi 更强大(安装 vim 可见底文的附加安装指令

  • 把 GatewayPorts 打开(去掉前面的 # 号注释,没有就直接在底下添加)

GatewayPorts yes 打开允许映射端口

  • 存盘后退出,并重新启动 sshd (不知如何操作文件的自行上网查阅)

service ssh restart 这个具体得看你 service 的实际名字(Ubuntu 下 service --status-all 可以查看所有服务状态)

配置 C 服务器

可以进行映射操作了

ssh -NfR 1234:localhost:22 user@58.247.33.44 -p8862

N 参数,表示只连接远程主机,不打开远程shell。

f 参数,表示后台运行。

R 参数接受三个值,分别是”远程主机端口:目标主机:目标主机端口”。

p 参数,表示指定 ssh 对外开放的端口号。

user 是 B 服务器的用户。

这条命令的意思,就是让 B 服务器监听它自己的 1234 端口,然后将所有数据经由 B 服务器转发到 C 服务器的 22 端口。这就被称为”远程端口绑定”。

这里每次连接需要输入 B 服务器的密码,不太方便,待会再详细介绍。

映射操作后我们可以发现在 B 服务器上已经开启了 1234 端口的监听,已经可以通过 1234 端口进行 ssh 连接到 C 服务器了。

密钥验证,直接登录

接回上面说的每次需要输入密码的问题,我们可以用 ssh 密钥来实现自动登录。

在 C 服务器上生成公钥和私钥

ssh-keygen (一直 enter)

ls ~ /.ssh/ 查看是否生成,显示如下

id_rsa id_rsa.pub known_hosts

ssh-copy-id user@58.247.33.44 复制到 B 服务器中

好了,这样就不需要每次都输入 B 服务器密码了。

autossh 实现自动重连

由于上述的 ssh 反向连接十分不稳定,可能随时断开,一旦断开就无法进行访问了。所以我们需要 autossh,它可以实现自动重连。(安装 autossh 可见底文的附加安装指令

autossh -M 5678 -NR 1234:localhost:22 user@58.247.33.44 -p8862

M 参数,指定了 autossh 的监听端口,监听是否断开然后进行重连操作

autossh 本身就是后台执行,所以就省去了 f 参数。

到这里就很完美了,可是还不够。要是 C 服务器宕机重启了怎么办,autossh 又不会自动执行。

实现开机自启

这里以 Ubuntu 18.04 为例。

ls /lib/systemd/system 执行该指令我们可以看到许多启动脚本,我们需要操作的就是 rc.local.service

打开脚本内容,我们在最后面加上一段:

1
2
3
[Install]  
WantedBy=multi-user.target
Alias=rc-local.service

保存退出。

由于 ubuntu-18.04 默认是没有 /etc/rc.local 这个文件的,需要自己创建。

1
2
sudo touch /etc/rc.local
chmod 755 /etc/rc.local

这里千万别忘记给 rc.local 文件设置可执行权限,不然没用。

rc.local 中你就可以编写脚本了。注意开头 #!/bin/bash 不可少

例如我的是:

1
2
3
4
#!/bin/bash
LOG_TIME=`date "+%Y-%m-%d %H:%M:%S"`
echo '123456' | sudo -S autossh -M 5678 -NR 1234:localhost:2223 user@58.247.33.44 -p8862
echo "autossh restart:"$LOG_TIME >>/usr/local/autossh.log

这里我是用 root 权限执行,123456 是 C 服务器的用户密码。 >> 表示追加,不覆盖。同时打印了执行的时间。

最后一步,前面我们说 systemd 默认读取 /etc/systemd/system 下的配置文件, 所以还需要在 /etc/systemd/system 目录下创建软链接。

ln -s /lib/systemd/system/rc.local.service /etc/systemd/system/

可以了,重启系统查看脚本是否执行,日志中是否有内容。

参考博文

笔者参考了如下博文并进行了整理实验:

附加安装

  • 更新源列表

sudo apt-get update

  • 安装 ssh

sudo apt-get install openssh-client 安装客户端 (反向隧道需要)

sudo apt-get install openssh-server 安装服务端

  • 安装 vim
1
2
sudo apt-get remove vim-common
sudo apt-get install vim

Ubuntu 18.04 中 vi 方向键有点问题,vim 很好用。

  • 安装 autossh

sudo apt-get install autossh

  • 安装 net-tools

当发现输入 ifconfig 不可用时

sudo apt install net-tools 装之


科幻十月(2018)

近些日子里差不多都在看《三体》,专业书籍都抛到脑后了,甚是着迷。

《三体》中每本序言都说了“基石”二字。刘慈欣先生真是可谓中国科幻届领军人物!其脑洞之大,学术之广,思维之严谨。书中大量出现了数学、物理等知识,众多专业术语,还将中外古今大多名人汇聚一起,展开“搏斗”,来回穿梭于时光长廊。

这几周每每到了周末,我便早上泡了杯麦片弄了点简易早餐(就是搞了个手抓饼),吃完躺床上稍稍休整便开始动手收拾《三体》世界,奔向不远的城建职业学院中去。到了那差不多十一点半,便顺道去了其食堂解决了中午伙食,这学校看上去有点年代的样子,环境倒是还不错就是人不多。吃完我就去图书馆里找了个位置开始翻起来。

当我一开始看的时候我就想起来了前几年看过的那本《天才在左,疯子在右》。其中有个微观故事我印象十分深刻,大致讲的是有个人不停洗澡洗手,洗到脱皮还是要洗,他说要把身上的细菌洗掉,细菌占领了我们,我们的世界其实是在它们的控制之下。是啊,生活中到处都是它们,我们处处被监视,自以为是的我们又怎么会知道它们到底是个什么样的存在。

自以为历尽沧桑,其实刚蹒跚学步,自以为掌握了竞争的秘密,其实远没有竞争的资格。

  • 射手假说:有一名神枪手,在一个靶子上,每隔10cm打出一个洞。设想这个靶子上生活着一种二维智能生物,它们中的科学家在对自己的宇宙进行观察后,发现了一个伟大的定律:每隔 10cm 单位,必然会有一个洞。 它们把这个神枪手一时兴起的随意行为,看成自己宇宙中的铁律。

  • 农场主假说:一个农场里有一群火鸡,农场主每天上午11点来给它们喂食。火鸡中的一名科学家观察这个现象,一直观察了近一年都没有出现例外,于是它也发现了自己宇宙中的伟大定律:每天早上 11 点,就有食物降临。 它在感恩节早晨向大家宣布了这个定律,但这天早上 11 点食物没有降临,农场主进来把他们都捉去杀了。

给时光以生命,给岁月以文明。

将人类这种生物剖析得连骨头渣子都不剩,大量反映了人性的情节。我试想,倘若真有朝一日三体人入侵地球,地球上会不会出现极权只需五秒钟的情况。不敢想,真的可怕,越想越可怕。我们都是虫子,不敢仰望星空。

看完《三体》后整个人精神状况都不好了,本来就是有点悲观主义思维,现在却像打上了思想烙印,觉得这世界随时都会爆炸。。


不过常看看这类书籍对我们还是很有好处的。码农,不就需要思维发散,眼界开阔,炸开世界视角。这能使我们想的更多,头脑更加灵活,逻辑能力自然也就上去了,看得还是很爽的。何况,刘慈欣先生怎么说也算是同行啊,要向先生看齐!

成功者有个特点,他们都具有前沿的思维,能够灵敏地感知未来的变化并能很快去拥抱现实。刘老在 06 年便能在脑中浮现如此气势磅礴的场景,读完作品我真是深深被其折服了。以后的日子里还需要再锻炼触觉,开阔视野,发散思维,并在实际生活中能应用自如,走向成功之路!

期待三体电影~


今早著名主持人李咏抗癌去世的消息出现在了大众面前,曾经站在台上“我是李咏,我们下期再见!”的声音虽然已经很久没有听到,但也算是从小看着他的节目长大。现在我们长大了,他却不见了。生命真的很脆弱,不由得又想起了《三体》中多次爆发的伤亡场景。

听我姑父说我爷爷是前列腺癌去世的。这种癌症遗传率很高,不知道我会不会中招,惨兮兮。冬眠技术啥时候能普及啊,我要冬眠,我要去未来看看人还是不是人。


链表找环方法证明(拒绝误人子弟)

前言

今天又想起来了这个问题,之前最开始是在其他论坛中看到有人说起了这个面试题。

当时只是翻了下,大致了解了如何判断链表中是否有闭环,用两个快慢指针解决,但是没有了解如何去找到闭环开始的节点。

刚上网搜了下,一群垃圾博主乱七八糟胡说八道,就知道从其他地方复制粘贴,都不过脑子的。谁说较快指针一定就是第二次在环上移动就能遇到较慢指针的,我这么个渣渣都能一眼看出来毛病一群人还复制粘贴都说 2,你们还真是 2!

问题描述

一条链表如何判断是否有环?若是有环那怎么找到链表环的入口?

解决思路

  • 先判断是否有环

思路:用快慢两个指针分别从链表头开始,慢指针 -> next,快指针 -> next -> next,这样如果有环那快指针务必会跑到慢指针后面,随即两者之间的距离一次会缩小一步,最终相遇。若是未相遇且快指针的 next 为 null,则说明链表无环。

  • 若是有环怎么找到环入口

链表中有闭环即快慢两指针相遇了,见下方的手工图:

链表闭环

一切清晰明了。让我们再来捋一捋。

当两指针在 P 点相遇,我们可列出如下等式:

1
2
3
4
2(L+x) = L+x+n*H        (n >= 1) // n 为快指针在闭环上的圈数
=> 2L+2x = L+x+n*H (n >= 1)
=> L = n*H-x (n >= 1)
=> L = n*(H-x)+(n-1)x (n >= 1)

到这里,是不是有种扒光了的快感,哈哈。
网上许多博客就是把 n 默认当成了 1,实则不然。

思路:故我们可以这样做,当 l1 与 l2 相遇时,再来一个 l3 指针从链表头开始,而 l1 继续走,l2 就可以终结其使命没必要继续走了。此时 l1 和 l3 指针都是指向其 next。当 l3 指针到达环入口时,l1 也必然到达了环入口,即 l1 和 l3 指针会在环入口相遇,从而可求得入口位置。

参考博客


二分搜索之搜索数组中目标元素的首尾下标

今天总结一下二分搜索。假设这里的数组已经是升序排序好了的。

我们知道二分搜索的效率很高,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用 O(log n) 完成搜索任务。它的基本思想:将 n 个元素分成个数大致相同的两半,取 a[n/2] 与需要查找的目标值 x 作比较,如果 x=a[n/2] 则找到 x,算法运算终止。详情可跳转百度百科

  • 我们通常最基本的二分搜索是这样实现的(Java):

    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
    /**
    * 二分搜索
    *
    * @param arr
    * 已升序排序数组
    * @param key
    * 目标查找值
    * @return
    */
    public static int commonBinarySearch(int[] arr, int key) {
    int low = 0;
    int high = arr.length - 1;
    int middle = 0; // 定义middle

    if (key < arr[low] || key > arr[high] || low > high) {
    return -1;
    }

    while (low <= high) {
    middle = (low + high) / 2;
    if (arr[middle] > key) {
    // 比关键字大则关键字在左区域
    high = middle - 1;
    } else if (arr[middle] < key) {
    // 比关键字小则关键字在右区域
    low = middle + 1;
    } else {
    return middle;
    }
    }

    return -1; // 未找到结果,返回-1
    }

    若是数组中存在搜索目标元素,则只要查找到任意一个便会返回该值;若是没有找到即返回 -1。

  • 来看下一种,只返回目标元素第一次出现的位置下标(伪代码):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    l = -1; u = n
    while l+1 != u
    m = (l + u) / 2
    if x[m] < t
    l = m
    else
    u = m
    p = u
    if p >= n || x[p] != t
    p = -1

    n 为数组的长度,p 就是最终我们需要的下标。若是 while 循环出来的最终结果 u >= n (其实最大也只会等于 n)或者 x[u] != t(t 为我们的目标元素),那么也就是无结果,返回 -1。

  • 我们再来看最后一个 function(该方法参数不同使得结果可以返回元素第一个出现的下标或者最后一个下标,也是 Java):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    /**
    *
    * @param nums
    * 已经升序排序好的数组
    * @param target
    * 搜索目标元素
    * @param left
    * 是否是查找第一个元素下标。true:查找目标元素第一个出现下标, false:查找目标元素最后一个出现下标
    * @return
    */
    private int extremeInsertionIndex(int[] nums, int target, boolean left) {
    int lo = 0;
    int hi = nums.length;

    while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (nums[mid] > target || (left && target == nums[mid])) {
    hi = mid;
    } else {
    lo = mid + 1;
    }
    }
    return lo;
    }

    目标元素出现的第一个下标:int leftIdx = extremeInsertionIndex(nums, target, true);

    目标元素出现的最后一个下标:int rightIdx = extremeInsertionIndex(nums, target, false) - 1;这里需要减一,需要注意。


总结一下:二分搜索只需要注意它的边界值,原先的数组下标范围是 [0..n-1],当你用 lo = 0, hi = n-1 去运行时,对应条件满足情况下值的赋值应该是 lo = mid + 1, hi = mid - 1;而若是用 lo = -1, hi = n 去作为条件运行时,对应条件满足情况下值的赋值就应该为 lo = mid, hi = mid,因为它两个值都是作为边界值。[0, n]、[-1, n-1]也是如此。


相关链接:


凉爽九月(2018)

近几日天愈发见凉,夜晚也裸睡不得了。

这帮人,唉。步入社会后确实大家之间的联系会越来越少,有这个心境,时间上也不允许啊,都得赚钱吃饭没办法……

本来是原先计划五人中秋一同去重庆耍几天。可奈何机票小贵,下不了这个手,何况有人明年还准备在苏州买婚房了,攒钱中,羡慕。后,众人纷纷拿不准放松地点,最终决定周边自驾游,先去杭州再去横店,这是计划。

什么!?女朋友亲戚忌日周年?还有这种事情的?何况婚都还没接呢,这就得过去,还是个大事。对了,就是明年准备在苏州买婚房那位,然后就五人缺席一人,计划照旧。

提前一个月我就买好了来回车票,就等那天放飞了,一年到头没有个生活,唉,哭唧唧。

什么!?临时上头派你去大连出差?还有这种事情的?连中秋都在大连过,我的乖乖宝贝啊。

又缺一人,剩三人。谁玩球谁玩!遂,计划猝!

车票退回,亏几十手续费。特么还买了张杭州博览会的门票,二十,也废了。哭唧唧。

临时决定还是回家吧,买了 22 号下午的票,24 号上午回来。哭唧唧。


不说那些伤心事了。

最近欧皇啊,豆瓣上海观影活动中连抽中了两次。

  • 第一次是《悲伤逆流成河》(不是郭敬明导的),讲的是校园暴力的。我没有看过小说原著,不过说实在的郭敬明骂声很多,但是他的书看的人还不少,至少我这个年龄层次的,挺多,小女生就喜欢看这些。电影看完后感触也是有的,反映了很多人性的东西,电影全程看完也没有睡意,我比较幸运从小也没有经历过那些校园暴力,最多也就只是一些小朋友之间的矛盾。看完之后我在想,那些真实世界里经历过校园暴力的人的身心会怎么样,他们可能那时候小也许没有想那么多,但是等到长大了,懂事后,回头想起那段时间,会是个什么样的心情。电影放完之后还来了两电影中新人演员,都很年轻,演技虽然青涩也是可认可的,其中主演的演技真的很用力,感染力很强!

悲伤逆流成河 点映

我说来个中间点的位置,结果给我来了张最后排的还是个角落。。

  • 然后昨天去看的《李茶的姑妈》,开心麻花出品国产喜剧。这个赞!国产喜剧除了星爷很少能让观众全场一直笑到最后的,我也是笑出了声,边上那些女孩子就更别说了,猪声……支持国产喜剧,看好开心麻花!没拍图片,也是做了个角落不过还好,不是最后排了。(卢靖姗身材真棒!!真喜欢这种健康的身材)

本来是计划中秋去放飞顺道回趟家,然后国庆宅出租房七天领悟自然真理。

现在变成了中秋回家,国庆回家。也好,趁着假期在家多呆呆,山美水清环境好(家附近在通国道,环境其实破坏了很多啊)。

我姐中秋把一个男的叫到家里来吃了个饭,通过相亲认识的,这还是第一个来家里吃饭的,不知道能不能成。人嘛看上去还行,就这样看吧,老姐也是要奔三了。至于我嘛,现在只想躺在床上顺道还把钱给赚了。婚姻这事,看缘分吗?

又跟家里聊了下,爸妈都是普通农民,辛苦一辈子把我和我姐拉扯大又盖了个新房,已经是很了不起了。现在就是家里种着几亩葡萄,收获季节比较忙。等到我要结婚买房了也不能太指望家里,毕竟他们二老还要养老的,需要备点钱,虽然以后每月都有养老金。

现在是这么想的,先在上海再打拼几年,能多赚点钱就赚,当然身体还是继续要锻炼的。看以后缘分有没有,如果缘分来了,购房资格有了,手上又能够勉强付得起个首付了,那就没准要扎根上海了。不过这还太遥远了。


今天真是厉害了,骑个自行车被交警拦下来记录信息警告了。。

说下次再抓到就要罚款 50 块了,运气不好运气不好,也是我的第一次了。

以后骑车得小心了,负责的交警也是好的,确实随着共享单车出现这个自行车越来越难管理了。大城市是得好好整顿整顿。


我就是对未知的特别感兴趣,什么都想了解下,也特别喜欢扩宽自己的眼界。世界变化太快,生活中也经常时不时会触及到不同的领域,俗话说技多不压身,多学学总没错。但也说要专精。我个人是觉得,眼界是一定要不断扩宽,不能做一只井底之蛙。在领域不断放大的同时也要放绝大多的精力在某一个具体领域中探求,前提是你要清楚找准了自己想要专精的领域。不过这就是难处了,大多都是在迷茫中啊。

失败了不可怕,可怕的是失败后无法重拾的心。

每年要给自己定些目标。用一张图来结束此篇:

扩宽眼界


整理一些 JDK 中 Integer 实用但不常用的方法

直接开搞。

toString

该方法进行了重载,一种是 toString(int i, int radix),另一个是 toString(int i)。一个参数的方法就相当于 toString(int i, 10),看代码便知,何况其官网注释也有:

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
public static String toString(int i, int radix) {
if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
radix = 10;

/* Use the faster version */
if (radix == 10) {
return toString(i);
}
// int 32位
char buf[] = new char[33];
boolean negative = (i < 0);
int charPos = 32;

if (!negative) {
i = -i;
}
// 根据进制取余转换
while (i <= -radix) {
buf[charPos--] = digits[-(i % radix)];
i = i / radix;
}
buf[charPos] = digits[-i];

if (negative) {
buf[--charPos] = '-';
}

return new String(buf, charPos, (33 - charPos));
}

不过该方法需注意: If the first argument is negative, the first element of the result is the ASCII minus character '-' ('\u005Cu002D'). If the first argument is not negative, no sign character appears in the result. 例如:

1
2
Integer.toString(-44, 2)  // -101100
Integer.toBinaryString(-44) // 11111111111111111111111111010100

若是负数,用该方法求得的值只是正数前加了个 “-“ 。

toBinaryString

类似的几个方法也一并列出了。 toBinaryString(int i) 转二进制方法,toOctalString(int i) 转八进制方法,toHexString(int i) 转十六进制方法。

1
2
3
Integer.toBinaryString(-44) // 11111111111111111111111111010100
Integer.toOctalString(44) // 54
Integer.toHexString(44) // 2c

parseUnsignedInt

与 toString 方法一样进行了重载。 parseUnsignedInt(String s)parseUnsignedInt(String s, int radix) 这是 JDK 1.8 新增的方法,作用就是将字符串参数解析为第二个参数指定的基数中的无符号整数。

1
2
3
Integer.parseUnsignedInt("11111111111111111111111111010100", 2) // -44
Integer.parseUnsignedInt("44", 10) // 44
Integer.parseUnsignedInt("44") // 44

decode

该方法将 String 解码为整数。 接受指定语法的十进制,十六进制和八进制数。源码如下:

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
public static Integer decode(String nm) throws NumberFormatException {
int radix = 10;
int index = 0;
boolean negative = false;
Integer result;

if (nm.length() == 0)
throw new NumberFormatException("Zero length string");
char firstChar = nm.charAt(0);
// Handle sign, if present
if (firstChar == '-') {
negative = true;
index++;
} else if (firstChar == '+')
index++;

// Handle radix specifier, if present
if (nm.startsWith("0x", index) || nm.startsWith("0X", index)) {
index += 2;
radix = 16;
}
else if (nm.startsWith("#", index)) {
index ++;
radix = 16;
}
else if (nm.startsWith("0", index) && nm.length() > 1 + index) { // 0 后面长度要大于 1
index ++;
radix = 8;
}

if (nm.startsWith("-", index) || nm.startsWith("+", index))
throw new NumberFormatException("Sign character in wrong position");

try {
result = Integer.valueOf(nm.substring(index), radix);
result = negative ? Integer.valueOf(-result.intValue()) : result;
} catch (NumberFormatException e) {
// If number is Integer.MIN_VALUE, we'll end up here. The next line
// handles this case, and causes any genuine format error to be
// rethrown.
String constant = negative ? ("-" + nm.substring(index))
: nm.substring(index);
result = Integer.valueOf(constant, radix);
}
return result;
}

使用测试如下:

1
2
3
4
Integer.decode("0xff") // 255
Integer.decode("#ff") // 255
Integer.decode("-07") // -7
Integer.decode("-071") // -57

highestOneBit

该方法返回一个 int 值,该值最多只有一位,位于指定 int 值中最高位(“最左侧”)1 的位置。 如果指定的值在其二进制补码表示中没有一位,即,如果它等于零,则返回零。

1
Integer.highestOneBit(44) // 32

44 对应的二进制为 0010 1100,只选中其最左侧的 “1” 那就是 0010 0000,也就是 25 = 32

lowestOneBit

该方法返回一个 int 值,该值最多只有一位,位于指定 int 值中最低位(“最右侧”)1 的位置。 如果指定的值在其二进制补码表示中没有一位,即,如果它等于零,则返回零。

1
Integer.lowestOneBit(44) // 4

44 对应的二进制为 0010 1100,只选中其最右侧的 “1” 那就是 0000 0100,也就是 22 = 4

numberOfLeadingZeros

该方法计算首部零的个数。

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
/**
* 首先在 jvm 中一个 int 类型的数据占 4 个字节,共 32 位,其实就相当于一个长度为 32 的数组。
*
* 那我们要计算首部 0 的个数,就是从左边第一个位开始累加 0 的个数,直到遇到一个非零值。
*/
public static int numberOfLeadingZeros(int i) {
// HD, Figure 5-6
if (i == 0)
return 32;
int n = 1;
// 下面的代码就是定位从左边开始第一个非零值的位置,在定位过程中顺便累加从左边开始 0 的个数
// 将 i 无符号右移 16 位后,有二种情况;
// 情况1. i=0,则第一个非零值位于低 16 位,i 至少有 16 个 0,同时将 i 左移 16 位(把低 16 位移到原高 16 位的位置,这样情况 1 和情况 2 就能统一后续的判断方式)
// 情况2. i!=0,则第一个非零值位于高 16 位,后续在高 16 位中继续判断
// 这个思路就是二分查找,首先把32位的数分为高低 16 位,如果非零值位于高 16 位,后续再将高 16 位继续二分为高低 8 位,一直二分到集合中只有 1 个元素
if (i >>> 16 == 0) { n += 16; i <<= 16; }
// 判断第一个非零值是否位于高 8 位
if (i >>> 24 == 0) { n += 8; i <<= 8; }
// 判断第一个非零值是否位于高 4 位
if (i >>> 28 == 0) { n += 4; i <<= 4; }
// 判断第一个非零值是否位于高 2 位
if (i >>> 30 == 0) { n += 2; i <<= 2; }
n -= i >>> 31;
return n;
}

测试看看:

1
Integer.numberOfLeadingZeros(44) // 26

int 4 个字节,一个字节八位,所以有 32 位。44 对应完整二进制就是 0000 0000 0000 0000 0000 0000 0010 1100。所以从左边开始数起共有 26 个零。

numberOfTrailingZeros

返回指定 int 值的二进制补码表达式中最低位(“最右侧”)1 之后的零位数。

1
Integer.numberOfTrailingZeros(44) // 2

44 对应二进制 0010 1100。其最右侧 “1” 之后的零的个数就是 2。

bitCount

返回指定 int 值的二进制补码中 1 的个数。

1
2
Integer.bitCount(44) // 3
Integer.bitCount(-44) // 28

44 对应的二进制补码为 0000 0000 0000 0000 0000 0000 0010 1100。1 有 3 个。

-44 对应的二进制补码为 1111 1111 1111 1111 1111 1111 1101 0100。1 有 28 个。


动态规划之 0-1 背包问题详解

前言

背包问题是比较经典的动态规划算法题,之前没接触过算法都没听说过这个,也是后来在 leetcode 中刷题时才了解到,惭愧惭愧啊。算法的世界太奇妙,数学一直都是那么令人着迷。今天来总结一下这个 01 背包问题。注:这里的物品不可拆分。

动态规划

首先了解下什么是动态规划。动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著《Dynamic Programming》,这是该领域的第一本著作。

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。

详情可见:动态规划

问题详解

问题描述

给定 N 种物品和一个背包。物品i的重量是 Wi,其价值位 Vi,背包的容量为 C。问应该如何选择装入背包的物品,使得转入背包的物品的总价值为最大。

问题分析

在选择物品的时候,对每种物品只有两种选择,要么装入,要么不装入。因此,此为一个 0-1 背包问题。
01 背包的递归公式为:

1
2
3
m[i,0] = m[0,j] = 0
m[i,j] = m[i-1,j] ,j < wi
m[i,j] = max(m[i-1,j-wi]+vi, m[i-1,j]) ,j >= wi

其中,m[i,j]为前 i 件物品中选择若干件,放入承重为 j 的背包中,得到的最大的价值。

wi 为第 i 件商品的重量。

vi 为第 i 件商品的价值。

例题讲解

有编号为 a,b,c,d,e 的五件物品,他们的重量分别为 4,5,6,2,2,价值分别为 6,4,5,3,6,现在给你一个承重为 10 的背包,怎么实现价值最大。

根据上述公式可以得到一个数据表,表从上向下生成:

name weight value 1 2 3 4 5 6 7 8 9 10
a 4 6 0 0 0 6 6 6 6 6 6 6
b 5 4 0 0 0 6 6 6 6 6 10 10
c 6 5 0 0 0 6 6 6 6 6 10 11
d 2 3 0 3 3 6 6 9 9 9 10 11
e 2 6 0 6 6 9 9 12 12 15 15 15

故可以根据公式码出如下实现代码:

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
70
71
72
73
74
public static void main(String[] args) {

int n = 5;// 5件物品,物品编号为a,b,c,d,e(下面为多加一件物品,第一个物品为虚拟的物品)
int weight[] = { 0, 4, 5, 6, 2, 2 };// 物品的重量
int value[] = { 0, 6, 4, 5, 3, 6 }; // 对应物品的价值
int c = 10; // 背包容量
int state[] = { 0, 0, 0, 0, 0, 0 };// 开始状态
char name[] = { ' ', 'a', 'b', 'c', 'd', 'e' };
int maxValue = getMaxValue(n, weight, value, state, c);
System.out.println("最大价值为 = " + maxValue);
System.out.print("放入的物品为 :");
for (int i = 1; i <= 5; i++) {
if (state[i] == 1) {
System.out.print(name[i] + " ");
}
}

// System.out.println();
}

/**
*
* @param n
* 物品数量
* @param weight
* 物品对应重量(数组下标从0开始,故第一个物品为虚拟物品)
* @param value
* 物品对应价值(数组下标从0开始,故第一个物品为虚拟物品)
* @param state
* 物品的开始状态
* @param c
* 背包的容量
* @return
*/
public static int getMaxValue(int n, int weight[], int value[], int state[], int c) {
// n 为物品的数量,数组时需要加 1,此时可以从 0,1,...n 个物品,共 n+1 个商品,其中第 0 个为虚构物品
// 对于物品的价值,可以写成 2 维数组
int m[][] = new int[n + 1][c + 1]; // n 为 0,1,2...(n-1),背包重量为 0,1,2...C
int i, j;

for (i = 0; i <= n; i++) {
m[i][0] = 0;
}
for (j = 0; j <= c; j++) {
m[0][j] = 0;
}

for (i = 1; i <= n; i++) {
// System.out.println();
for (j = 1; j <= c; j++) {
if (j < weight[i]) { // 新的物品太重,无法放下
m[i][j] = m[i - 1][j];
} else {// 分为放和不放 取较大值
m[i][j] = Math.max(m[i - 1][j - weight[i]] + value[i], m[i - 1][j]);
}
// System.out.print("m["+i+"]["+j+"]="+m[i][j]+" ");
// System.out.print(m[i][j]+" ");
}
}

// 根据其最大价值,反向推断是否添加了物品 i

j = c;
for (i = n; i > 0; i--) {
if (m[i][j] > m[i - 1][j]) {// 物品 i 添加到了序列列表
state[i] = 1;
j = j - weight[i];
} else { // 没有添加
state[i] = 0;
}
}

return m[n][c]; // 最大价值
}

输出结果为:

1
2
最大价值为 = 15
放入的物品为 :a d e

具体实现看上述代码即可,注释齐全,简单易懂。

参考资料


笑口常开

摘录自贾平凹先生散文集《自在独行》中的《笑口常开》。在生活中找寻乐而开笑之事。

著作得以出版,殷切切送某人一册,扉页上恭正题写:“赠 xxx 先生存正。”一月过罢,偶尔去废旧书报收购店见到此册,遂折价买回,于扉页上那条提款下又恭正题写:“再赠 xxx 先生存正。”写毕邮走,踅进一家酒馆坐喝,不禁乐而开笑。

大学毕业,年届三十,婚姻难就,累得三朋四友八方搭线,但一次一次介绍终未能成就。忽一日,又有人送来游票,郑重讲明已物色着一位姑娘,同意明日去公园 xx 桥第三根栏杆下见面。黎明早起,赶去约会,等候的姑娘竟是两年前曾经别人介绍见过面的。姑娘说:“怎么又是你?”掉身而去。木木在桥上立了半晌,不禁乐而开笑。

好友 x 君,编辑十五年杂志,清苦贫困,英年早逝。保存下那一支笔和一副深度近视镜。租三轮车送亡友去火葬场火化,待化的队列冗长,忽见墙上张贴有“本场优待知识分子”,立即返回取来编辑证书,果然火化提前,免受尸体臭烂,不禁乐而开笑。

入厕所大便完毕,发现未带手纸,见旁边有被揩过的一片脏纸,应急欲用,缺进来一个人蹲坑,只好等着那人便后先走。但那人也是没手纸,为难半天,也发现那片脏纸,企图我走后应急。如此相持许久,均心照不宣,后同时欲先下手为强,偏又进来一人,背一篓,拄一铁条,为捡废纸者,铁条一点,扎去脏纸入篓走了。两人对视,不禁乐而开笑。

居住于 A 城的伯父,沉沦于二十年右派生涯,早妻离子散,平反后已垂垂暮老,多回忆早年英武及故友。我以他大学的一位女生名义去信慰藉,不想他立即复信,只好信来信往,谈当年的友情,谈数十年的思念,谈现在鳏寡人的处境,及至发展到黄昏恋。我半月一封,连续四年不断,且信中一再说要去见他,每次日期将至又以患病推延。伯父终老弱病倒,我去看他,临咽气说:“我等不及她来了。她来了,你把这个箱子交她。”又说一句:“我总没白活。”安详瞑目。掩埋了伯父,打开箱子,竟是我写给他的近百封信,得意为他在爱的幸福中度过晚年,不禁乐而开笑。

陪领导去某地开会,讨论席上,领导突然脖子发痒,用手去摸,摸出一个肉肉的小东西,脸色微红旋又若无其事说:“我还以为是个虱子哩!”随手丢到地上。我低头往地上瞅,说:“噢,我还以为不是个虱子哩!”会后领导去风景区旅游,而我被命令返回,列车上买一个鸡爪边嚼边想,不禁乐而开笑。

有了妻子便有了孩子,仍住在那不足十平方米的单间里。出差马上就要走了,一走又是一月,夫妻想亲热一下,孩子偏死不离家。妻说:“小宝,爸爸要走了,你去商店打些酱油,给你爸爸做一顿好吃的吧!”孩子提了酱油瓶出门,我说:“拿这个去,”给了一大口浅底盘子,“别洒了啊!”孩子走了,关门立即行动。毕,赶忙去车站,于巷口远远看见孩子双手捧盘,一步一小心地回来,不禁乐而开笑。

夜里正在床上半醒半睡,有人影推门闪进来,在立柜里翻,翻出一堆破衣服和书报,扔了;再往架板上翻,翻出各类米袋子、面袋子和书报,扔了;在桌斗里又翻,是一堆读书卡片,凑眼前看了看,扔了。咕哝了一句顺门便走,我在床上说:“朋友,把门拉上,夜里有风的。”小偷把门拉上了。天明起来整理房间,一地乱书乱报,竟发现找了好久未找着的一份资料,不禁乐而开笑。

上大街回来,挤了一身臭汗,牢骚道:“用枪得在街十字路口扫一通!”回家一杯茶未喝尽,楼梯上步声杂乱,巷中有人呼:“大街上有人用枪打死几十个人了!”遂也往街上跑,街上人山人海,弯腰往里挤,问:“尸体在哪儿?”一熟人说:“不是说是你讲的吗?”忽记得那一句顺口的牢骚,不禁乐而开笑。

剧场里正巧和一位官太太邻座,太太把持不住放一屁,四周骚哗;骂问:“谁放的?不文明!”太太窘极不语,骂问声更甚。我站起说:“我放的!”众人骚哗即息,却以手作扇风状,太太也扇,畏我如臭物,回望她不禁乐而开笑。

出外突然有人迎面过来打招呼,立即停下,作疑惑状。“你不认识我了?”“怎不认识?”于是握手,互问哪儿来,到哪儿去,互问老人康健孩子可乖,互说又胖了,又瘦了,半天的淡而无味的话。分手了,终想不起这是谁,不禁乐而开笑。

弄文学的穷朋友来家侃山,酒瘾发而酒瓶仅能空出一杯酒,取马鬃四根,各人蘸吮,却大声划拳:“八匹马,五魁手……你一盅(鬃)!我一盅(鬃)!”窗外卖茶蛋的老妪对老翁说:“怪不得咱出钱让人家写文章宣传咱不干,人家钱多酒量也大,喝了整晌也未醉!”听着不禁乐而开笑。

路过一条小巷,忽见有长队排出,以为又在出售紧俏物件了,急忙列入其中,排到跟前,方见是巷口唯一的厕所,居民等候出恭,不禁乐而开笑。

去给孩子买一双袜子,昨日看时价是一元,今日是一元二角,怏怏出店门,打响一个喷嚏,喷带出一口痰。正想是售货员在嘲笑我,我方有喷嚏打出,一位戴“卫管员”袖章的人却责斥我吐了痰要罚五角钱。掏出那一元钱,卫管员没零钱找,遂再当地吐一口,愤愤而走,走过十步,不禁乐而开笑。

出差去旅社住宿,服务员开发票将“作协”写成“做鞋”,不禁乐而开笑。

夏月偏停电,爬十二层楼梯去办公室,气喘吁吁到门口了,门钥匙却和自行车钥匙系在一起,遗忘在车子锁孔了,不禁乐而开笑。

路遇一女子,回望我嫣然一笑,极感幸福,即趋而前去搭话,女子闪进一家商店,尾随入店,玻璃上映出自己衣服纽扣错位,不禁乐而开笑。

名字是自己的,别人却用得最多,不禁乐而开笑。

写完《笑口常开》草稿,去吸一根烟,返身要眷写时,草稿不见了,妻说:“是不是一大页写过的纸,我上厕所用了。”惊呼:“那是一篇散文!”妻说:“白纸舍不得用,我只说写过的纸就没用了。”急奔厕所,幸而已臭但未全湿,捂鼻子抄出此份,不禁乐而开笑。


SpringBoot2 整合 WebSocket 简单实现聊天室功能

一个很简单的 Demo,可以用 WebSocket 实现简易的聊天室功能

一反常态,我们先来看一下效果,如下:

嫌麻烦的可以直接去我的 GitHub 获取完整无码 Demo。

概述

  • WebSocket 是什么?

WebSocket 是一种网络通信协议。RFC6455 定义了它的通信标准。

WebSocket 是 HTML5 开始提供的一种在单个 TCP 连接上进行全双工通讯的协议。

  • 为什么需要 WebSocket ?

了解计算机网络协议的人,应该都知道:HTTP 协议是一种无状态的、无连接的、单向的应用层协议。它采用了请求/响应模型。通信请求只能由客户端发起,服务端对请求做出应答处理。

这种通信模型有一个弊端:HTTP 协议无法实现服务器主动向客户端发起消息。

这种单向请求的特点,注定了如果服务器有连续的状态变化,客户端要获知就非常麻烦。大多数 Web 应用程序将通过频繁的异步 JavaScript 和 XML(AJAX)请求实现长轮询。轮询的效率低,非常浪费资源(因为必须不停连接,或者 HTTP 连接始终打开)。

  • WebSocket 如何工作?

Web浏览器和服务器都必须实现 WebSockets 协议来建立和维护连接。由于 WebSockets 连接长期存在,与典型的 HTTP 连接不同,对服务器有重要的影响。

基于多线程或多进程的服务器无法适用于 WebSockets,因为它旨在打开连接,尽可能快地处理请求,然后关闭连接。任何实际的 WebSockets 服务器端实现都需要一个异步服务器。

实现

首先去 start.spring.io 快速下载一个 springboot Demo,记得选中 Websocket 依赖。

然后将项目导入你的 IDE 中。

新建一个 config 类用来注册我们的 websocket bean。

我的是 WebSocketConfig.java :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
@Configuration
public class WebSocketConfig {

/**
* 自动注册使用了@ServerEndpoint注解声明的Websocket endpoint
*
* @return
*/
@Bean
public ServerEndpointExporter serverEndpointExporter() {
return new ServerEndpointExporter();
}

}

该加上的注解别忘了加,项目启动时 springboot 会自动去扫描注解的类。

然后是消息接收处理 websocket 连接、关闭等钩子。

MyWebSocket.java :

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
@ServerEndpoint(value = "/websocket")
@Component
public class MyWebSocket {

// 静态变量,用来记录当前在线连接数。应该把它设计成线程安全的。
private static int onlineCount = 0;

// concurrent包的线程安全Set,用来存放每个客户端对应的MyWebSocket对象。
private static CopyOnWriteArraySet<MyWebSocket> webSocketSet = new CopyOnWriteArraySet<MyWebSocket>();

// 与某个客户端的连接会话,需要通过它来给客户端发送数据
private Session session;

/**
* 连接建立成功调用的方法
*/
@OnOpen
public void onOpen(Session session) {
this.session = session;
webSocketSet.add(this); // 加入set中
addOnlineCount(); // 在线数加1
System.out.println("有新连接加入!当前在线人数为 : " + getOnlineCount());
try {
sendMessage("您已成功连接!");
} catch (IOException e) {
System.out.println("IO异常");
}
}

/**
* 连接关闭调用的方法
*/
@OnClose
public void onClose() {
webSocketSet.remove(this); // 从set中删除
subOnlineCount(); // 在线数减1
System.out.println("有一连接关闭!当前在线人数为 : " + getOnlineCount());
}

/**
* 收到客户端消息后调用的方法
*
* @param message
* 客户端发送过来的消息
*/
@OnMessage
public void onMessage(String message, Session session) {
System.out.println("来自客户端的消息:" + message);

// 群发消息
for (MyWebSocket item : webSocketSet) {
try {
item.sendMessage(message);
} catch (IOException e) {
e.printStackTrace();
}
}
}

/**
* 发生错误时调用
*/
@OnError
public void onError(Session session, Throwable error) {
System.out.println("发生错误");
error.printStackTrace();
}

public void sendMessage(String message) throws IOException {
this.session.getBasicRemote().sendText(message);
// this.session.getAsyncRemote().sendText(message);
}

/**
* 群发自定义消息
*/
public static void sendInfo(String message) throws IOException {
for (MyWebSocket item : webSocketSet) {
try {
item.sendMessage(message);
} catch (IOException e) {
continue;
}
}
}

public static synchronized int getOnlineCount() {
return onlineCount;
}

public static synchronized void addOnlineCount() {
MyWebSocket.onlineCount++;
}

public static synchronized void subOnlineCount() {
MyWebSocket.onlineCount--;
}
}

关键就是@OnOpen@OnClose等这几个注解了。每个对象有着各自的 session,其中可以存放个人信息。当收到一个客户端消息时,往所有维护着的对象循环 send 了消息,这就简单实现了聊天室的聊天功能了。

其中 websocket session 发送文本消息有两个方法:getAsyncRemote()和 getBasicRemote()。 getAsyncRemote 是非阻塞式的,getBasicRemote 是阻塞式的。

然后我用了 Controller 来简单跳转测试页面,也可以直接访问页面。

InitController.java :

1
2
3
4
5
6
7
8
9
@Controller
public class InitController {

@RequestMapping("/websocket")
public String init() {
return "websocket.html";
}

}

websocket.html :

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
70
71
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>My WebSocket Test</title>
</head>
<body>

Welcome<br/>
<input id="text" type="text" />
<button onclick="send()">Send</button>
<button onclick="closeWebSocket()">Close</button>
<div id="message">
</div>

</body>

<script type="text/javascript">

var websocket = null;

//判断当前浏览器是否支持WebSocket
if('WebSocket' in window){
websocket = new WebSocket("ws://localhost:8080/websocket");
}
else{
alert('Not support websocket')
}

//连接发生错误的回调方法
websocket.onerror = function(){
setMessageInnerHTML("error");
};

//连接成功建立的回调方法
websocket.onopen = function(event){
setMessageInnerHTML("open");
}

//接收到消息的回调方法
websocket.onmessage = function(event){
setMessageInnerHTML(event.data);
}

//连接关闭的回调方法
websocket.onclose = function(){
setMessageInnerHTML("close");
}

//监听窗口关闭事件,当窗口关闭时,主动去关闭websocket连接,防止连接还没断开就关闭窗口,server端会抛异常。
window.onbeforeunload = function(){
websocket.close();
}

//将消息显示在网页上
function setMessageInnerHTML(innerHTML){
document.getElementById('message').innerHTML += innerHTML + '<br/>';
}

//关闭连接
function closeWebSocket(){
websocket.close();
}

//发送消息
function send(){
var message = document.getElementById('text').value;
websocket.send(message);
}
</script>
</html>

要注意,这里没有用到任何模板引擎,所有直接把 websocket.html 放在 static 文件夹下就可以访问了。

所有的这些搞好就可以运行了,一个简单的效果就能出来。

End.

参考