20181201

Overview:


Algorithm: 盛最多水的容器

题目

给定 n 个非负整数 $a_1,a_2,...,a_n$,每个数代表坐标中的一个点 (i, $a_i$) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, $a_i$) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2。

输入:[1,8,6,2,5,4,8,3,7]
输出:49

思路

实际上,这道题就是求某两条垂线构成的最小矩形的面积的最大值。因此最简单的方式就是暴力遍历,对所有可能的两条垂线的组合求其面积,然后取最大值即可。但这种算法的复杂度为 $O(n^2)$。

换一个角度思考,设两条垂线分别为 $x=i$ 和 $x=j$ (i<j),且 $a=j-i$,$b=min(a_i,a_j)$,则面积 $S_{ij}=a*b$。此时只需要将 i、j 中较小的一个加 1 或减 1 即可。

测试用例及代码实现

Technique: git flow

Git 是一个非常优秀的版本控制工具,可以说,只要你是一位程序员,就不能不知道 git。但很多人对 git 的使用都极不规范,就比如在分支管理上。他们通常只维护一个 master 分支,所有的代码都提交到上面。这样,如果你想要同时进行两个新功能的开发,或者多人协作的时候,就会遇到很大的麻烦。由此出现了 git flow 工作流。

git flow 的目的不是为了替代 git 的功能,而是整合 git 相关的命令,形成一个完整的操作流程和规范。即使不用 git flow 相关工具,只要你按照这个步骤来操作就没问题。

首先明确在 git flow 中,定义了 master、feature、develop、release 和 hotfix 五个分支,所有的操作都在这五个分支上完成。其中 master、feature 为长期维护分支,其他为临时分支,用完后需要删除掉。

Share

这周在工作中遇到一个小问题,大体可以抽象为如下代码:

type Handler struct{}

func (h *Handler) Serve(a int) int {
	return a
}

type Itype interface {
	//Serve(int) int
}

func test(ls ...Itype) {
	fmt.Println(reflect.TypeOf(ls))
}

func main() {
	handlers := []*Handler{
		&Handler{},
	}

	test(Handler{}, Handler{})
	test(&Handler{}, &Handler{})
	test(handlers)
	test(handlers...)

}

具体问题是:main 函数里面四个 test 调用,哪些能编译通过,哪些不能通过?如果把注释打开呢?为什么?

看到这里可以先停下来想想,然后再继续。

我验证的结果是,前三个可以编译通过,最后一个调用无法通过。如果把注释打开,则只有第二个函数调用能通过。

解释如下:

分两种情况:注释关闭和注释打开


ARTS 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.