ADM-201 dump PMP dumps pdf SSCP exam materials CBAP exam sample questions

3个算法策略 – 译学馆
最新评论 (0)


3 Algorithm Strategies

嗨 我是《程序员面试金典》的作者 盖尔·拉克曼·麦克道尔
Hi, I’m Gayle Laakmann McDowell, author of Cracking the Coding Interview.
Today I’m going to talk about three algorithm strategies that I find super useful for solving problems.
这三个算法策略称为:BUD 时/空权衡和DIY(自己动手做)
These three strategies are called BUD, space/time trade-offs, and DIY, do-it-yourself.
第一个要谈的是BUD 它指的是马上过一遍你的暴力解法
The first one we’ll talk about is BUD. BUD means to walk through your brute force,
or whatever your best algorithm is right now,
然后寻找瓶颈 不必要和重复的工作
and look for bottlenecks, unnecessary work, and duplicated work.
我们先来谈谈瓶颈 考虑下面这样一个问题 有两个数组 它们都具有元素互异性
Let’s talk about bottlenecks. Consider the following problem – you have two arrays, both which have
distinct elements, how would you compute the number of elements in common between the two arrays?
一种解决这个问题的方式是 我们从第一个数组中取出每个元素
So one way of doing it is we take each element in the first array
然后遍历第二个数组 检查它是否含有该元素
and we walk through the second array and check if it contains that element.
它的复杂度是O(A*B) 我们正在使用的瓶颈技巧是
That will give us an O of A times B algorithm. So with the bottlenecks technique what we’re doing is
找出瓶颈在哪 以及怎样除掉它 或如何降减少它
say ok where is the bottleneck and how can we get rid of it, or how can we reduce it?
在这种情况下 瓶颈来自这些连续的包含操作
So in this case the bottleneck comes from these continuous contains operations.
Is there 1, is there 5, is there a 12?
What’s the fastest way of doing contains operation?
我们可以使用哈希集——把所有元素放到B中 然后把B放入一个哈希集中
Well we could use a hash set – take everything in B and throw it into a hash set,
算法的复杂度就变成了O(A+B) 这就是瓶颈技巧
and then we can get an O of A plus B algorithm. So that’s the bottleneck technique.
找出瓶颈 真正把重点放在消除它上
Identify the bottleneck and really focus on getting rid of it.
BUD的下一部分是不必要的工作 让我们来考虑这个问题
The next part of BUD is unnecessary work. So let’s consider this problem.
有等式a³+b³=c³+d³找出所有满足0You have the equation a cubed plus b cubed equals c cubed plus d cubed. Find all solutions to that where a
b c and d are integers between 1 and 1000. So one way of doing this is just a brute force.
遍历所有可能的解 然后看看能否满足 a³+b³=c³+d³
Walk through all possible solutions and check to see if a cubed plus b cubed
这样可行 但非常慢 算法的复杂度是O( n⁴ )
equals c cubed plus d cubed. So this will work. It’s very slow, it’ll give us an n to the fourth
但我们可能注意到一件事 你知道 一旦我们发现一个a b c d的可行解
algorithm but one thing we might notice is, hey, you know, once we find
a value of a b c d that works we can add a break statement after that because there
因为对于相同的a b c值 不可能有其他的满足条件的d值了
can’t be more values of d that work for the same value of ab&c. And that should
这应该让我们好好思考 有更快的方式获得存在且唯一的d值解吗 答案是肯定的
make us think well is there a faster way of getting to that? And yes there is,
如果对于每组给定的a b c值 仅有一个d值满足条件 那么我们可以直接求得d了
If there’s only one value of d that works for every given ab&c we can just solve for d.
因此 去除不必要的工作是指 注意这些小的语句
And so this unnecessary work is, pay attention to all these little break
statements and these little, these kind of minor optimizations. Sometimes
有时它们不会改变算法自身的时间复杂度 但却与更大的变化有关
they don’t change the Big O time in and of themselves, but they’re related to bigger
changes that actually will. The third part of BUD is duplicated work so let’s
所以让我们回到 a³+b³=c³+d³ 的问题上去
go back again to this a cubed plus b cubed equals c cubed plus d cubed problem.
One thing you might notice here is that we’re repeating the c/d loop over and
对于每对a/b的每个元素 我们生成所有的c/d配对 并检查每种情况是否匹配
over and over again. For every element for every pair a/b we’re generating all
pairs c/d and checking for matches in every single one. That happens over and
我们该如何改进这种工作呢?好吧 我们能做的一件事是
over again, how can we leverage that work? Well one thing we could do is create
this table of all c/d values and the c cubed plus d cubed result and then for each a/b
然后对于每对a/b 在c³+d³列中寻找与a³+b³相等的值
pair look for the a cubed plus b cubed in that column there. If we want to do that
如果我们想这么做 需要把那个表重构为一个哈希映射
though, let’s really restructure the table as a hash map that maps from a c cubed plus
从c³+d³映射到每对满足条件的c/d 然后对于每对a/b计算a³+b³
d cubed to each pair that got us that. Then for each a/b we can compute a cubed plus b cubed and
再从哈希表中取出符合条件的那些值 这就解决了重复性工作
pull out that match from that hash table. So that’s duplicated work. When you
当你注意到自己老是重复一些工作时 真的需要想想如何
notice yourself doing work over and over again, really think about how can you
调整它们 这些是BUD技巧 检查你的暴力算法或任何
leverage that. So that’s the BUD technique. Walk through your brute force or whatever your
最优解法 并找出瓶颈 不必要和重复性的部分
best algorithm is and look for the bottlenecks, look for the unnecessary work,
and look for the duplicated work. The second technique is space/time
这常常意味着使用一个不同的数据结构 很经常用的是哈希表
trade-offs. So often this means using a different data structure very very
frequently as a hash table and seeing if you can apply it to that problem.
So you’re using more space but hopefully getting a time optimization in the
process. We can see this technique applied to the previous problem. You have
a³+b³=c³+d³ 我们能通过更多地使用一整个空间
this equation a cubed plus b cubed equals c cubed plus d cubed. We were able to save ourselves
来节省时间 这样一个小技巧就是把哈希表
time by using a whole bunch more space. So one just little technique is have
放在你心里的首位 你能通过使用一点额外空间
hash tables at the top of your mind. A lot of times in problems you save
来节省问题里的不少时间 最后要讨论的技巧是
yourself time by using a bit of extra space. The final technique to discuss is
what I call DIY or do it yourself.
我们考虑这个问题 你有两个字符串
So let’s consider this problem. You have two strings –
s是小的字符串 b是大的字符串 找到s在b中的所有排列
s is a small string b is the big string – find all permutations of s within b. So
one brute force way of doing this is generating all the permutations of s and
并在b中一个个查找 但那真的很慢
looking for every single one within b. But that’s going to be really really slow.
我们要讨论一个算法 它花费的时间至少是s!*b
We’re talking about an algorithm that’s going to take at least s factorial times b time
and it might be even worse than that.
让我们放弃它 回到第二步 那是一个很重要的例子 这儿真是一个
Let’s scrap that and go back to step 2, which was a draw big example. So here’s a
很重要的例子 我鼓励你们在这个点上暂停视频
really big example. Now I encourage with this point to pause the video and
并实际去寻找s在b中的排列 因此就照说的那样暂停
actually go in and find all the permutations of s within b. So literally just pause it,
马上去做 在这里暂停视频并计算答案
do it right now, pause the video and compute the answer here.
不管你要怎样做 不必担心算法 就照你想要的方式去做
However you want to do it don’t worry about algorithms, just do it however you want to
一件事是 如果你和大多数人一样 实际照我说的去做
do it. So one thing, that if you’re like most people, and you actually did this as I asked,
你可能已经注意到 你从未生成
you might have noticed that you never actually generated all the
s在b中的所有排列 是吗?你从未生成所有
permutations of s within b did you? You never actually generate all
s的排列 你做的可能更像是这样
permutations of s. What you probably did was something more like this. You
你一边以s长度的窗口在b上移动 一边说 这是不是一个排列
probably moved through b, in windows of size s, saying is this a permutation, is this
这是不是一个排列 这是不是一个排列?或你也许做过其它的 类似取出s的第一个
a permutation, is this a permutation? Or maybe you did something else like take the first
字符 在b里寻找它 然后看看周围的字符
character s, look for that within b, and then look at the surrounding
不论你干什么 你的算法复杂度可能都在s²b左右
characters. Whatever you’re doing your algorithm is probably somewhere between s
也许甚至和O(b)一样快 这在很多问题里出现过
squared times b and maybe even as fast as O of b and this happens for a lot of
有很多问题 人们的算法真的真的很复杂 很慢
problems, there’s a lot of problems where people’s algorithm is really really
或者他们只是被卡住了 考虑到一个实际的例子
complex or really really slow or they just get completely stuck, but given an
actual example, the way that your brain will just intuitively find the right
实际上经常就是一个很好的算法 我这么推荐
output is actually often a pretty good algorithm. So part of why I push so much to
提出一个真正大且复杂的实例 并且保证它的一般性和
come up with a really big example and making sure it’s, you know, really generic
没有特殊情况 就是因为 如果你把自己放到大脑
and doesn’t have special cases in it, is that if you put yourself in position
不得不工作的情况下 你可能就会自然地
where your brain has to do work, you might be able to just have an
从大脑里得出一个算法 因此你的例子必须要足够复杂
algorithm just flow out very naturally from that. So make your examples large and
让你的大脑工作 手动获得结果 不论你想怎样做
let your brain do its thing, get the output manually, however you want to do
然后反推那些思考的过程 精确找出
it and then try to reverse-engineer that thought process and figure out what
exactly did your brain actually do to get that result.
So those are the three techniques I use all the time for solving problems. BUD is
BUD是瓶颈 不必要和重复的工作 时/空权衡 这很多都
bottlenecks, unnecessary work and duplicated work, space/time trade-off so a lot of that
意味着哈希表 然后是自己做 真正的依靠实例
means hash tables, and then do it yourself, really rely on examples and
我们将这些应用于大量的各种各样的问题 能够真正帮助你
these we use for a huge variety of problems and can really help you make a
lot of progress on otherwise difficult problems.
现在你知道了这三个技巧 在一些问题上自己
So now that you know these three techniques try them out on a few
尝试它们吧 祝你们好运
problems of your own. Good Luck.



《程序员面试金典》的作者 盖尔·拉克曼·麦克道尔应对难题的三个算法策略。