通过简单的 “刷题” 就能搞定算法笔试题吗?

刷过Leetcode的都知道,每道题的解法可能不止一种,其中不乏让我们望尘莫及的。不过,这些解法花些时间,我们也能看懂,但是我们常常感叹,我们当初怎么就想不到呢!

不知道大家有没有这种感觉?

如果我们拿到一道题目,习惯用写业务逻辑的思路,从开始到结尾按部就班地构思,这种效果好吗?恐怕不太可取!

这样做就真成了刷题了,效果可能不明显。我们做题应该是为了培养思维,在面试时迅速想出高效的实现思路。至于编码,只要平时加以训练,反而应该不是问题。

关注本公众号的会有一些ACM大神,他们强于常人的缘由即在于能很快想出常人短时间难以想到的优秀解法。接下来,以靠近这些大神为目标,和大家一直专注于面试算法题的分析思路、算法思想,以及如何快速在脑海里形成算法伪代码。至于之后的求解代码我放在次要位置,甚至忽略,因为有了算法思路,这些可能就不是重点。

今天,先热身以下。说说动态规划,实话说,dp真的是非常灵活的算法思想,最重要的是找到状态迭代公式,然而这往往是比较有难度的,如果没有有目的的多训练,可能难以在短时间内快速找到状态转化方程。

dp最经典和入门级的例子还是爬楼梯。

每一次你面临两种选择,爬一层,或爬两层,爬到n层一共有多少种方法。 我们面临的第一个疑问:它可以用动态规划吗? 要回答这个问题,可以参考算法导论上给出的两个前提。

通俗地说,假如知道了爬到第i层的所有方法为f(i),0<=i <= n-1 ,那么爬到第i-2层和i-1层的所有方法为: f(i-2), f(i-1) ,此时 i>=2 , 并且爬到第i层后,一定是从第i-2层或第i-1层过来的,则

1f(i) = f(i-2) + f(i-1) ,2<=i<=n
2

这个公式就是状态转移方程,同时它也表明爬到第i层的所有方法,这个子问题的最优解,与整个问题的最优解是一致的。

有了这个迭代公式,自然可以求出爬到任意楼层的所有方法。

根据这个题目,可以有很多变种,比如:

起始位置在第一层,交付这一层的费用后,可以选择向上爬一层或两层,问爬到顶层的最低成本。举个例子,已知 cost[5] = {1,4,5,3,1},则最节省成本的走法为:1 + 5 + 1= 7

如何构思这道题,不难发现,整个问题的最优解和子问题的最优解是一致的,故设爬到第i层的最小成本为f(i),i层的子问题的子问题是爬到第i-2层或第i-1层,如果爬到第i-2层后,支付此楼层费用后,爬两层后可以到第i层,故:

1f(i) = f(i-2) + cost[i-2] 2<=i

同理,从第i-1层过来的费用为:

1f(i) = f(i-1) + cost[i-1] 1<=i

所以,爬到第i层的最低成本即为:

1f(i) = min(f(i-2) + cost[i-2], f(i-1) + cost[i-1] ) 2<=i
2f(0) = 0
3f(1) = cost[0]
4

根据以上迭代公式可以求出爬到任意楼层的的最小成本,爬到第n层的时间复杂度为O(n)

再观察上面的迭代公式,cost[n-1]好像没有遍历到,因为i的最大值为n-1,故等式右侧cost只能取值到cost[n-3]和cost[n-2]

这是一个算法的重要细节,需要考虑!函数的自变量的取值区间需要考虑。

如何解决这个算法的边界呢?最简单的方法使用哨兵sentinel,可以在cost的最后添加一个元素0,确保遍历所有楼层。

当然,还有一些变种,比如在f(0), f(1) 这些边界值上做文章。比如Leetcode的有道题就是这样做的:起始位置可以在第1层或第2层,所以:

1f(1) = 0 //爬到第2层的成本变为0

其他与上面分析完全一致

算法的灵活性就和算法题的灵活性一样,改变一个细微的条件后,就需要考虑对整个算法的影响,有时甚至一个微小的变化,就会导致整个算法重新设计。

所以,算法工程师面临的压力是很大的,需求的一点变化,动辄就要修改整个算法。另一个角度来说,编写算法框架的难度就不言而喻。

要知道学会分析算法题不是一朝一夕的。那么是不是可以跨过这一步呢?

Impossible!

或许刚开始这有些繁琐,耽误时间,但是当它成为你的唯一选择时,它何尝又不是捷径呢?

记得卡内基梅隆cs系最受欢迎的教授prof Kosbie说过,“曾有些学生问我,在CMU怎样才能拿到一个好的分数”,他告诉学生完成每次作业前的材料学习,学生们说为了完成作业要去读这么多书,我们没有时间。他说 “或许这很花费时间,但是这样做可以帮助你深入理解这门课并获得理想的分数,同时为你以后的职业生涯打好根基,并告诉学生:If you don't have time to do that , you don't have time not to do that.

引人深思

本文分享自微信公众号 - Python与机器学习算法频道(alg-channel)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-12-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

洛谷P2196 挖地雷(dp)

12430
来自专栏量子位

300万成交!佳士得刚刚拍卖出首款AI画作,同场碾压毕加索

我叫Edmond de Belamy,是这个星球上第一幅参加艺术品拍卖的AI画作。

10450
来自专栏JetpropelledSnake

Web安全学习笔记之DES算法实例详解

转自http://www.hankcs.com/security/des-algorithm-illustrated.html

16940
来自专栏Python中文社区

智慧城市路在何方?合肥三十万重金诚邀大数据英才!

“随着信息化时代到来,不论是各级政府还是社会大众,在日常工作和生活中,都会遇到诸多制约政府高效运转的痛点、阻碍群众便利生活的难点。因此,全面布局数字合肥建设,加...

13320
来自专栏量子位

清华霸榜,长沙理工异军突起!第三届 CCF CCSP落下帷幕

10月26日上午,经过前一天12个小时的激烈角逐后,2018 大学生计算机系统与程序设计竞赛(CCSP)进入颁奖阶段。

11220
来自专栏大眼瞪小眼

《算法之美》例题

【3.4 拓展问题】编写一个函数,给定一个链表的头指针,要求只遍历一次,将单链表中的元素顺序反转过来。

8110
来自专栏数据结构与算法

BZOJ3498: PA2009 Cakes(三元环)

如果\(v\)的度数\(\leqslant M\),那么就再暴力枚举\(v\)连出去的点\(t\),看\(u\)与\(t\)是否联通(打标记)

9120
来自专栏量子位

diss范式:明星AI公司秋招被爆大规模毁约;CEO戴文渊:责任在我有错认罚

让他道歉的不是产品和代码Bug。戴文渊众所周知的身份是ACM世界冠军、前百度晋升最快T10,顶级机器学习科学家,江湖人称“戴神”。

14230
来自专栏算法修养

LeetCode 129 Sum Root to Leaf Numbers

11020
来自专栏数据结构与算法

2018.10.25解题报告

T1:直接贪心即可。最优策略显然是用第一个序列的大的 和 第二个序列的小的放在一起

7630

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励