在iTerm2中展现更精致的zsh

本文通过在 iTerm2 中使用我个人编写的 oh-my-zsh 主题,展示一种使命令行界面更加精致美观的方法,但是这个方法只能在 macOS 上使用。因为该方法依赖的工具栈是 iTerm2 + zsh + oh-my-zsh ,其中的 iTerm2 至关重要,而 iTerm2 只有 macOS 的版本。因此,本文主要呈献给 macOS 用户与决定将成为 macOS 用户的读者。

在这个自定义主题中,我替换了 af-magic 主题中的分割线。

Spring Cloud In Docker

应公司要求,本人最近使用 Spring Cloud 做了一个小项目,用它配合 dockerdocker-compose 搭建了一套微服务系统。作为一个很少使用 java 编写工程项目的工程师,我在其中还是遇到了不少问题的,从项目的配置到项目的部署运行,几乎每一阶段都有卡壳。公司保密制度并不允许我泄露项目相关的代码,所以这篇文章仅根据我自学 Spring Cloud 时搭建的 Hello World 项目 总结了遇到的几个主要的困难,以及一些小技巧。

[翻译] Golang切片与内存泄露的情况

在Go语言中,使用切片( Slice )表示数组( Array )某一部分是一种很高效的方式。切片之所以如此有用,除了它们只需要非常少的开销这个事实之外,还有它们总是能够透明地代替一个实际的数组:

1
2
3
4
5
6
7
a := []string{"b", "a", "m", "i", "h", "n", "f"}
sort.Strings(a)
//a 现在等于 ["a", "b", "f", "h", "i", "m", "n"]

b := []string{"b", "a", "m", "i", "h", "n", "f"}
sort.Strings(b[2:4])
//b 现在等于 ["b", "a", "i", "m", "h", "n", "f"]

但是需要记住一个关于切片的重点,尤其是当你要保持它们的引用很长一段时间时:它们持有对底层数组的引用。当然是这样,你很明白,它们不仅仅是一个指向底层数组的指针,然而所以呢?

ssh相关笔记整理

本文是我对自己ssh笔记的整理。

允许用户使用密码登录

目前很多云服务提供商的vps都是只能通过公钥认证访问,而不可以使用password登录的,比如 AWS、CONOHA等。

但是我们在没有严格要求安全性的团队中,常常直接开新用户并使用password访问,并不去收集团队成员的公钥再使用 ssh-copy-id 远程拷贝进vps。

所以,我们就需要手动开启sshd的允许使用password登录的功能。

而与允许使用password登录功能相关的配置在文件 /etc/ssh/sshd_config 中,如下图所示:

就如同注释中所说的,只将 PasswordAuthentication 设置为 no ,用户便只能通过使用公钥登录。反之,将 PasswordAuthentication 设置为 yes , 用户便可以通过使用password登录。

同样,设置其中的 PubkeyAuthentication 可以控制是否允许使用公钥登录。

吴军-为人处世

前言

本文是对人民邮电出版社在微信公众上推送的《吴军:厉害的人是这样为人处世的》等文章的摘抄整理。博学智慧的吴军老师通过这些简单的文章给了我众多为人处世上的启示,我不想私吞,特地将它们摘抄整理后分享给大家。希望不经意间阅读本文的读者也能从中获得些许启示。

众利勿为,众争勿往

简单地讲, 如果一件事大家都觉得有好处,那就不要做了;如果一个东西,大家都在抢,就不要去凑热闹了

我刚到美国时,和美国同学聊起一件事:他们的 议会里总是有一些提反对意见的人

在我看来,事情该不该做是很清晰的,直接投票表决就好,为什么还要在议会里争辩那么长时间?况且最后的结果还是一样的。

但是他们告诉我,事情总有好的一面和坏的一面,如果 大家都一致地认同一件事时,可能是认识不够深刻,一些盲点没有看到,忽视了一些潜在的问题。而这些问题一旦发生,后果极为严重

所以,对于大家都觉得非常好的事情,要很小心,因为我们可能忽视了它的问题。这时候,不妨再听下各方意见,看看有没有疏漏,而辩论就可以达到这样的效果。

此后,我便接受了一个观点, 如果一件事大家都提不出反对意见时,这可能是一个坑,要特别小心

这和中国人的一些智慧不谋而合。

古人说,“日中则移,水满则溢,月盈则亏”,这是自然界的铁律。从人事来看, 众人都觉得有利可图的事情,其实已经没有了利润的空间

Suffix Automaton

后缀自动机是一个有向无环图,节点为状态,有向边为状态转移边的一种有限状态自动机,它可以且仅可以接受一个字符串的所有后缀,并且状态数和转移数都是最少的。

定义

后缀自动机(suffix automaton,以下简称 SAM)的结构包含两部分,有向无环单词图(directed acyclic word graph,以下简称 DAWG)和前缀树(prefix tree)。 SAM 中的每个节点都同时存在于这两个结构中。

我们对一个字符串 \( S \) 构造其 SAM,称 \( S \) 是该 SAM 的 母串(String) ;下文中提到的「子串(Substring)」、「前缀(Prefix)」与「后缀(Suffix)」,如非特殊说明,均指母串的「子串」、「前缀」与「后缀」。

记 \( | S | \) 为字符串 \( S \) 的长度。

DAWG

顾名思义,DAWG 是一个 DAG(有向无环图)。

DAWG 中,除 起始节点(Start) 外,每个 节点(Node) 表示一个或多个子串。

节点之间通过 转移边(Transfer arc) 相连,每条转移边上有一个 字符(Char)

从起始节点沿着转移边走,每条 路径(Path) 都对应着一个子串,即将走过的边上的字符首尾相连得到的子串(显然多条路径会到达同一个节点上)。

我们称在 SAM 上运行一个字符串 \( S \) ,即为从 DAWG 的起始节点开始,第 \( i \) 次沿着字符 \( S_i \)​​ 的转移边走,走完 \( |S| \) 次;如果 \( S \) 是母串的一个后缀,则称到达的节点为 可接受 的节点。

由于 SAM 是一个自动状态机,所以节点也被称为 状态(State)

为什么pass的密码仓库能上传到github?

pass 内置了上传与获取git仓库数据的指令,且官方在教程中也推荐把 .password-store 提交到github,这不禁让人疑惑:"这样真的安全吗?"

确实, .password-store 位于用户 HOME 目录下,是用户使用 pass 时存储所有密码的文件夹,暴露出去在直观上的确感觉很不安全,令人担忧。

但是, .password-store 中所有密码都是通过 gpg 加密的,只要 .password-store 中的数据不足以破解密文,那么用户的所有密码数据都是安全的!

.password-store 中的数据并没有直接记录任何加密用的密钥信息,pass 和 gpg 的配合方式保证了这一点。

后缀数组-倍增法-详解

Prologue

倍增法 求字符串的 后缀数组 本质上其实并不难,但是基于 多个数组与基排序 的实现却非常令人迷惑 —— 众多的数组以及更多的循环让初学者一片混乱,包括我。

本文会由浅入深逐步讲解后缀数组、倍增法以及逐步的优化,并在最后附上完整的代码与基准测试结果。

代码均由 golang 实现,但是不用担心,不会有语法问题困扰你。

什么是后缀数组?

后缀数组( Suffix Array )是一个有序数组,其元数为某一个字符串的所有后缀。

比如:

给定字符串 banana 。显然它所有的后缀为: {"banana", "anana", "nana", "ana", "na", "a"} 。不过,这种表示方式冗长且浪费空间,我们可以直接将其简化为 {0, 1, 2, 3, 4, 5} ,其中每个元素都代表该后缀首字母在原本字符串中的索引号。我们设该数组为 Origin

若要根据 Origin 求出 banana 的后缀数组,我们只需要对 Origin 排序即可:

1
2
3
4
5
6
7
8
Origin                            SuffixArray

0 banana 5 a
1 anana Sort the Suffixes 3 ana
2 nana ----------------> 1 anana
3 ana alphabetically 0 banana
4 na 4 na
5 a 2 nana

所以, banana 的后缀数组为 {5, 3, 1, 0, 4, 2} 。(在本文中为升序)

正如我们所见的,后缀数组本身并不复杂,或则说定义很简单,其高深晦涩的地方在于 通过何种高效的排序方式得出后缀数组

买或不买?这种题目最无聊了!

题目: 1004. To Buy or Not to Buy - Hard Version (35)

此非贪心,亦非动态

当我第一次读完题目时,我天真的以为这道题不是 动态规划 就是 贪心

然而在我无数次思考其最优子结构后,发现这个最优子结构存不存在都没有关系!直接看下面这个状态转移公式:

1
2
A[0][j] = INFINITY
A[m][j] = min{A[m-1][j], A[m-1][j ^ (j&k)] + extra beads in m}

Tarjan算法求无向图的割点与桥

该算法是R.Tarjan发明的。过程与求强连通图的类似。wiki

求割点

基本概念

割点:无向图连通分量中,如果删除其中某点以及与该点相连的边后,连通分量变成不连通,则称该点为割点。

实现

在Tarjan算法的过程中,当前结点u是割点的条件为:

  1. u 为在 dfs 上的根结点, 即 u 的 father 为 nil , 此时需要满足 u 的子结点数量要大于 1 且其中至少有一个子结点满足 v.index==v.lowlink
  2. u 为非根结点, u.index == u.lowlink

注意:度为1(不考虑重边的情况下)的结点虽然满足以上条件,但是不是割点。