20181124

Overview:


Algorithm: 三数之和

题目

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

例如,给定数组 nums = [-1,0,1,2,-1,-4],

满足要求的三元组集合为:
[
    [-1,0,1],
    [-1,-1,2]
]

思路

这道题目暂时没想到更优的方法,只好先采用暴力寻找法了。关键的地方在于,a + b + c = 0,所以可以先找到两个数 a 和 b,就可以间接确定要寻找的 c 值。如果数组是排好序的,寻找 c 只需要 O($\lg n$) 的时间复杂度。但 a 和 b 的两层遍历,需要 O($n^2$) 时间复杂度。所以总体上算法的时间复杂度是 O($n^2\lg n$)。

测试用例及代码实现

Review: An Introduction to Git Merge and Git Rebase: What They Do and When to Use Them

作为一名开发者,Git 是不可避免的版本控制工具。上一篇 ARTS 中分享了你不应该使用 rebase 的几个理由,但在这篇分享中,作者比较了 git rebasegit merge 的优势和劣势,说明了应该在什么情况下使用 rebase,在什么情况下使用 merge。以下是正文:

首先,Git Merge 和 Git Rebase 都是为了解决相同的问题--合并多个分支上的改变为一个分支。但它们的实现方式是完全不同的。

Git Merge

merge 总是会提交某些改变到其他的分支上去,即将源分支上的内容合并到目标分支上。在这个过程中,只有目标分支被改变,源分支历史保持不变。

优势
劣势
使用姿势

合并 master 分支到 feature 分支上:

$ git checkout feature
$ git merge master

(or)

$ git merge master feature

这样将在 feature 分支上创建一个新的「合并提交」,以保留两个分支的历史。

Git Rebase

rebase 是合并一个分支上改变到另一个分支的另一种方式。它会压缩所有的变化到一个 patch 中,然后将这个 patch 合并到目标分支上。

但和 merge 不同的是,rebase 会使得提交历史变得平坦,因为它将已完成的作业从一个分支转移到另一个分支。在这个过程中,不需要的历史记录被消除了。

优势
劣势
使用姿势

rebase feature 分支到 master 分支上:

$ git checkout feature
$ git rebase master

通过重写 feature 分支的每个 commit,就将 feature 分支移动到了 master 分支上。

交互式的 rebase

这种方式允许修改每个 commit 并将其移动到新分支上。相比自动化的方式,这样有时候更有用,因为它可以完整控制每个 commit 历史。一个典型的场景是在合并 feature 分支到 master 前先使用 rebase 来清理掉混乱的历史。

$ git checkout feature
$ git rebase -i master

这将打开编辑器列出将要移动的所有 commit:

pick 22d6d7c Commit message#1
pick 44e8a9b Commit message#2
pick 79f1d2h Commit message#3

这确定了 rebase 执行后这个分支应该具有的样子。通过重排这些序列,你可以使提交历史变成你想要的样子。比如可以使用 fixupsquashedit 等代替 pick

该用哪一个?

因为每个团队不一样,没法概括地说决定用哪个。但我们需要从某个地方开始。

决定用 rebase 或 merge 时,每个团队都需要考虑很多问题。因为事实证明,一种工作流程并不比另一种更好,这取决于您的团队。需要考虑整个团队的 rebase 和 git 能力水平,并且综合对可追溯性和合并历史的重视程度。来决定应该使用哪一种。并且需要在明确的分支策略的背景下考虑 merge 和 rebase。

我的建议

随着团队的增长,总是使用 merge 越来越难以管理开发中的改变。为了拥有一个干净的、可读性强的提交历史,使用 rebase 会更加有效。

通过考虑一下情况,您可以充分使用 rebase:

Technique

这周偶然看到一篇文章,里面列出了很多实用的命令行工具,可以大大提高效率。其中有些是我已经在用的,有些是还不知道的;有些是对系统自带工具的增强,也有些是系统没有带的功能。分享给大家:

Share: 视频压缩编码的基本原理

Share 部分分享一个之前写的一个笔记,关于音视频压缩的原理。写的很简略,暂时也不修改了。这段时间也在持续学习音视频相关内容,后期统一整理。


ARTS project is a learning project initiated by Hao Chen. A means learning a Algorithm on LeetCode,R means Reviewing an English article about programer,T means learning a Technique skill,and S means doing a Share with others that influence people. Adhere to every week at least one year!

This article was posted on my blog and Github using the MIT Open Source License.