ARTS(15)

1 Algorithm

三数之和

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

三数之和这类题目的是leetcode上常见的题目,与之类似的还有两数之和四数之和等等,这类题目的核心就是先排序,然后移动相应的游标,通常只移动两个游标, 剩下的游标保持固定。针对游标对应的数值之和,决定下一轮游标的移动方向。

func threeSum(nums []int) [][]int {
    sort.Sort(Ints(nums))
    if len(nums) < 3 || nums[0] > 0 || nums[len(nums)-1] < 0 {
        return make([][]int, 0)
    }
    header, tail := 0, len(nums)-1
    result := make([][]int, 0)
    for header < tail {
        cursor := header + 1
        for cursor < tail {
            if nums[header]+nums[cursor]+nums[tail] == 0 {
                result = append(result, []int{nums[header], nums[cursor], nums[tail]})
                cursor++
                for nums[cursor] == nums[cursor-1] && cursor < tail {
                    cursor++
                }
                tail --
                for nums[tail] == nums[tail+1] && cursor < tail {
                    tail--
                }
            } else if nums[header]+nums[cursor]+nums[tail] > 0 {
                tail--
            } else {
                cursor++
            }
        }
        tail = len(nums) - 1
        header++
        for header > 0  && header < tail && nums[header] == nums[header-1]{
            header++
        }
    }
    return result
}
type Ints []int
func (ints Ints) Len() int           { return len(ints) }
func (ints Ints) Less(i, j int) bool { return ints[i] < ints[j] }
func (ints Ints) Swap(i, j int)      { ints[i], ints[j] = ints[j], ints[i] }

同时存在重复元素,所以需要考虑跳过连续重复元素。

2 Review

How to think like a programmer - lessions in problem solving
如何像一个程序员思考-学会如何解决问题
如果你对编程感兴趣,你或许听说过这样的引用:

这个国家的每一个人都应该学会在电脑上编程,因为它教会你如何思考 - Steve Jobs

你可能很疑惑这是啥意思,确切的说,为啥像程序员一样思考?并且如何做到这一点?
本质上来讲,这是关于*解决问题的高效的方法*。在这边文章中,我将教会你如何学会这个方法,在最后,你将会知道如何一步步成为一个更好的问题解决者。

2.1 为什么这个重要

解决问题能力是一个基础技能,我们都会遇到问题,或大或小。但是我们该如何处理他们呢?好吧,这个比较随机。除非你有一个系统,下面的方法可能是你如何解决问题的途径,这也是我刚刚开始编程的时候的方法:

  1. 尝试一种解决方案;
  2. 如果它不奏效,试着其他的解决防范;
  3. 如果还是不成功,重复第二个步骤。

有时候你比较幸运,但是这是一个最差的解决问题的方法,而且这个往往浪费大量时间。最好的方法是:

  • 有一个问题解决框架;
  • 不停练习它

所有的雇员,最重要的是解决问题的技能。 解决问题的几乎是所有雇员寻找的能力中最重要的,甚至比编程能力,debug或者系统设计还重要。计算思维方式或者将大而复杂的问题分解的是比技术能力还宝贵,尤其是对于一个找工作人来讲。-- Hacker Rank

2.2 拥有一个框架

为了找到一个框架,我遵循了Tim Ferriss书中建议,它带领我与两位非常杰出的人交流,分别是C.Jordan Ball(在CodeByte上排名前两位的用户)和V. Anton Spraul(Think Like a Programmer: An Introduction to Creative Problem Solving一书的作者)。我问了他们同样的问题,你猜猜怎么着,他们的答案居然是非常相似。过会你就知道他们的答案。
P.S. 这个并不意味着他们在每一件事都是一样,每一个都是不同的,你也同样如此。 但是如果你开始遵循商定好的原则,将会是非常棒,你将会得到很多并且学得更快。

我看到很多新的程序员最大的错误是专注于学习语法而不是学习如何解决问题 -- V.Anton.Spraul

所以当你遇到一个问题,你应该如何做呢?下面就是步骤:

2.2.1 理解

确切的知道这个问题当被问起的时候,大部分难题之所以难因为你并没有理解它(所以这是第一步)。那怎么知道你理解这个问题?就是当你能够用平实的语言解释它。还记得被一个问题所卡住,开始解释它,然后你就立即看到在逻辑上的漏洞,而这个你之前并没有看到。大部分程序员知道这种感觉。
这也是你为什么应该要写下你的问题,画出流程图或者告诉其他人(也有其他人使用橡皮鸭)

如何你不能用简单的术语解释一件事,那么你根本不理解它 -- Richard Feynman

2.2.2 计划

不要一下子进入解决问题中而没有计划,给你解决方案给出一个计划。除了写下确切的步骤,没有其他任何有效的办法。在编程中,这就意味着并不是一下子解决问题,而且花点时间给你的大脑来分析问题和处理相关的信息。为了获得好的计划,回答下面的问题:

给定输入X, 需要什么确切的步骤才能获得输出Y?

P.S. 程序员拥有一个很棒的工具来帮助它完成这个:注释

2.2.3 分解

注意,这是最重要的一步。不要尝试解决一个大问题,你会崩溃的。而是将它分解成子问题,这些子问题更加容易解决了。然后一个个解决这些子问题,从最简单的开始,简单意味着你知道答案(或者接近答案)。最简单的意味这个被解决的子问题不依赖与其他要被解决的子问题。一旦你解决了所有的子问题,将它们连起来。将你的左右紫的子解决方案连接起来就会给你原先问题的解决方案,恭喜!
这个技术是解决问题的基石,请记住它(如有必要,在读一下步骤)。

"如果我能告诉每一个编程的初学者关于解题的能力,我会教他分解问题的能力"
比如,假设你是一个编程的初学者,你被要求编写一个程序读取十个数,并且找到其中第三大的数值;对一个新手来讲,这是一个难题,尽管这个只需要基础的编程语法。如果你被纠缠着呢,那么就应该将这个问题变得简单一点,比如如何找到一个最高的,仍然很困难?那么如何在三个数中找到最大的?或者两个数中的最大者?
把问题降低到你能够很容易的找到解决方案的哪一点,然后将问题一点点展开,并且使得解决方案得到匹配。-- V. Anton Spraul

2.2.4 被困着呢?

到目前为止,你可能坐在那并且思考着:”这个方法似乎不错,但是如果我连子问题都无法解决怎么办?”
首先深呼吸一口;然后,这个非常常见。这个对每一个人来讲,都是很常见。那些最好的程序员和问题解决者的不同点在于他们更关心bug和错误而不是愤怒。事实上,当你面对挫折的时候可以尝试下面三件事

  1. Debug. 一步步地试探你的解决方案,直到发现那里错了,程序员叫这种方法Debugging。debug的艺术就在于弄清楚你事实上告诉电脑所做的内容,而不是你告诉它要做的。
  2. Reassess:回退一步,从另外一个角度看看问题,是否存在一些东西可以抽象出更通用的方法。“有时候我们迷失在细节中,而忽视了更通用的原则,在更通用的层次上"。
  3. Research: Google它,无论你遇到任何问题,其他人可能都已经伴帮你解决过了,找到这个人或者解决方案,哪怕你已经解决这个问题(你可以从别的人的解决方案中学到很多)

2.3 练习

如果你想成为的一个问题解决者,解决很多问题的人,不要想一周之内就成为。你需要练习,练习还是练习,经过大量时间后后,你会意识到这个问题可以被这样解决。
如何练习呢?方法有很多,象棋,数学题目,数独,围棋,大富翁等等。通常在成功人士中练习习惯是微问题解决。比如Peter Thiel玩象棋,Elon Musk打游戏。

如果你想看看一个人在三到五年后在商场上的领导力,看他在游戏中的表现 --- Broyon Reeves

这是是否意味着你需要玩电脑游戏?不。那么电脑游戏是关于啥的?对,就是解决问题的能力。所以你关于练习锁需要做的是找到解决微问题的能力。比如说,我享受编码的乐趣,所以每天我至少解决一个挑战。正如我说的,几乎每一个问题都拥有相同的模式。

2.4 结论

现在你知道了想一个程序员思考意味着什么;你也知道了问题解决能力是可以被塑造的,这还不够,你还知道了如何练习的你这个能力。最后我希望你能遇到更多的问题。

3 Tips

3.1 如何并发性能分析

  1. 确定机器硬件信息(CPU核数和内存大小);
  2. 1个并发的时候,处理响应时间和CPU利用率;
  3. 逐步增加并发量,直到相应时间在预期范围内和CPU利用率达到极致,称为极大并发量。

4 Share

树立为自己打工的概念,工作中除了完成公司和单位的任务, 还在自己个人能力提升上做出了那些努力和进步。个人的价值不单单是所属的单位和公司,而且自己的标签。

Comments
Write a Comment