• 出去面试要贪心,对年薪要贪心,总不能跳个槽工资还降了吧
  • 对股票要贪心,现在跳哪里不是为了股票啊
  • 对签字费要贪心,一时的奖励能争取就要争取
  • 对自己的成长更要贪心,不能错过一点点机会

既然那么贪心,我们也来聊聊贪心这一种常见的算法吧,通过对贪心的活学活用,我们神挡杀神,佛挡杀佛,秒杀一切面试题。

程序员:面试

贪心+构造

有一类面试题目是关于子序列的,在数学上,我们称一个子序列是在原有序列上删掉一些元素而不改变其他元素生成的。比如序列<A, B, D>就是序列<A, B, C, D, E, F>的一个子序列。

一个常见的面试题是假设序列的元素都是a至z,给定一个长序列和k个短序列,如何快速的判断每一个短序列是否是长序列的子序列?
乍一看和贪心没有什么关系,但实际上你可以把贪心的思想运用到检查短序列当中。从短序列的第一个元素起,找到它在长序列中出现的第一个位置,之后对于每一个短序列的元素,找到它在长序列中出现的尽可能靠前的位置,这就是用贪心来构造。

单纯的贪心构造需要O(km+kn)的时间复杂度来处理所有的k个短序列,其中m是短序列的长度,n是长序列的长度。这时候,我们加上一个hash表来辅助解题,预先计算f[i][x]为在长序列第i位后第一次出现x的位置。设我们正在长序列位置i处,检查短序列的元素x,我们可以直接跳至f[i][x]位置。这样经过对长序列构建hash表,每一个短序列我们利用贪心可以在O(m)的时间内求解,总时间复杂度降为O(km+n)。

小结一,贪心并不只是寻找一个问题的最优解,把贪心思想运用到构造问题也会很有效。

贪心+更多限制

贪心算法一般指问题求解时,总是做出在当前看来最好的选择,而不是从整体最优上加以考虑。有时候一个问题第一眼看上去也许不适合用贪心来解决,但是当你加入一些限制,他就变成很明显的贪心问题。

比方说最大子矩阵和的问题。给出一个有正整数和负整数组成的N*N的矩阵,找出其中元素总和最大的子矩阵。比如如下矩阵中第二行第一列到第四行第二列的子矩阵最大。

当第一眼看到整个问题,很容易想到一个暴力的解决方案,那就是枚举矩阵的左上角和右下角,然后只需要常数时间就可以计算出矩阵和。暴力,实现简单,但是需要O(n⁴)的时间复杂度。

乍一看和贪心没有什么关系,但是如果你限制矩阵的左边界,再限制矩阵的右边界,这个最大子矩阵问题就一下变成了一维序列上最大子序列问题了。最大子序列怎么做?贪心!假设当前和为S,当前看到的数为a[i],如果S+a[i]>0那么继续更新最大值,如S+a[i]=0,那么重设S为0,整体复杂度为O(n)。这时我们加上之前枚举左右边界的复杂度,总体时间复杂度降为O(n³)。

小结二,有时候一个最优化问题第一眼看上去和贪心无关,但是当你对题目加上一定的限制后,暴力算法也可以变为时间复杂度更优的贪心算法。

贪心+数据结构

还有一道经典题目出自LeetCode,直方图求最大矩阵面积。给定一个直方图如下,求直方图中能够组成的所有矩形当中面积最大为多少,样例中最大面积为10。

同样,我们可以很容易的想到暴力解法,从左到右枚举矩形的左边界,之后枚举矩形的右边界并且更新矩阵的最高高度。与此同时,我们可以很容易的计算每个枚举结构的矩形面积,并且更新最大矩形面积。这样做的时间复杂度是O(n²)。

想要优化这个算法,也可以从贪心入手。第一个贪心想法,最大的矩形一定包含一个完整的bar,否则我们可以找到一个更高的矩形拥有更大的面积。第二个贪心想法,当我们找到一个包含完整bar的矩形,我们可以不断向左,向右扩展这个矩形,直到无法继续扩展下去。

基本的贪心想法有了,这时候我们只需要有一个数据结构来帮助我们在任意一点找左边和右边比他矮的bar,想到我们是依次扫描每一个bar的,不妨用一个栈来维护高度递增的bar。

也就是说,我们从左至右遍历所有的bar,并将它们放入栈中。如果当前bar的高度小于栈顶的bar,那我们需要反复移除栈顶的bar,设栈顶的bar高为矩形的高,它向左可以延伸到新的栈顶处,向右可以延伸到当前我们所指向的bar。因为每个bar都会进栈和出栈一次,所以总时间复杂度是O(n)。

小结三,贪心是一种思想,配合上合适的数据结构就能事半功倍。

程序员日常
做人一定要区分出是朋友还是合作伙伴
合作伙伴之间麻烦别人,大事小情的请人帮忙需要给点钱
朋友之间千万不能如此,给多给少都是损害了彼此之间的交情
今天犯的这个错误一定要谨记!!!

标签: 程序员, 职业发展