algorithm

面试刷题总结(五)- 贪心算法

天字第一条:永远不要首先尝试贪心算法,并尝试证明它是对的。而要使用动态规划推出一个算法,然后可以尝试简化到贪心算法。

尤其是在面试中,基本不会出现贪心算法,太 tricky 了。如果一个面试官问了一个题目,并且他只会用贪心算法解,那么这个面试官水平也一般,这样的公司不去也罢。

相比动态规划来说,贪心算法一般来说:

  1. 要求条件更严格,也就是贪心选择条件;
  2. 时间复杂度往往更低,能达到线性时间复杂度。

贪心选择性质:每一步都选择局部最优解,而局部最优解恰好是全局最优解。贪婪一般需要预排序,证明贪婪成立可以采用数学归纳法,或者证明不会有更好的方法

区间问题

合并、排序区间也是一个常见的问题。

例题

LeetCode 56

LeetCode 57 合并区间

这道题关键之处在于合并后,把剩余的区间直接加上来,这样就不用考虑不少特殊情况了。

class Solution:
    def insert(self, intervals, newInterval):
        ans = []
        start, end = newInterval
        remainder = 0
        for x, y in intervals:
            if start <= y:
                if end < x:
                    break  # 找到了结尾了
                start = min(start, x)
                end = max(end, y)
            else:
                ans.append([x, y])
            remainder += 1
        ans.append([start, end])
        ans += intervals[remainder:]
        return ans

会议室 II

LeetCode 矩形重叠问题

参考资料

  1. 面试不会考贪心算法

刷 LeetCode 的经验

最近断断续续面试了三个月,也拿了一些大厂(美团百度阿里)的 offer, 分享下刷题经验

  • 一定要使用自己最擅长的语言,不要想其他的,不要引入额外的复杂度;
  • 复习基础算法,如排序,二分查找,树的遍历等,同时做一些基础题;
  • 简单的递归,比如树的一些题目,是最容易引导你进入刷题状态的;
  • 递归是几乎所有有技巧的题目的基础,栈是递归、树是递归、回溯也是递归、动归更是递归;
  • 除了递归之外,剩下的基本是考察基础操作的题目,比如螺旋打印矩阵等等,一定要注意细节;
  • 每道题 10 分钟完全没思路就看答案;
  • 如果连续有 5 道题目看答案了,去补习知识,不要再做了;
  • 代码超过 20 行了,一般情况下说明写的有问题,直接看答案(确实有个别非常繁琐的题目,面试一般不考);
  • 开始的时候按分类刷,不要按顺序刷;
  • 如果遇到完全没有思路的题目,不要悲伤,不要觉得自己是个傻瓜。秉承「闻过则喜」的态度,试想如果是面试时候恰好考到这道题目呢?
  • 刷过了过几天又忘了也没关系,根据艾宾浩斯记忆曲线,前几天是忘得最快的时候,多看几遍;
  • 当然,死记硬背是没用的,一定要理解题目;
  • 做题的时候身边要有白纸,随时在纸上画下示意图,不要空想;
  • 做了几道同类题之后,总结做题模板,比如说 backtracking 的做题模板;
  • 后期刷熟了,不要分类刷,随机刷;
  • 已有的题库就当做例题,反复看,彻底学透。每周参加周赛,做新题,作为模拟面试。

最后一点,刷 LeetCode 其实就像是大学里的期末考试,如果你两周复习时间可以搞定一门期末考试,那么两周时间也完全能搞定 LeetCode。要做到「战略上藐视,战术上重视」。

按照考察的方面,题目大概分成两类:

  1. 递归;
  2. 其他题目。

对于递归题目,拿到题目首先要思考:

  1. 怎么才能把题目的输入规模缩小,简化为规模更小的问题
  2. 另一方面基础情形是什么

然后再考虑选用哪种实现方式,是回溯还是动归。

特别注意的地方

  • 不要沉迷于研究语言特性。

    就像上面说的,使用自己最熟悉,日常使用最多的语言。不要觉得 C++ 或者 Java 或者 Whatever 刷题最爽,或者你看的答案采用了什么语言,抓住主要矛盾,你是来刷题的,不是学习新语言的。我之前犯得错误就是边学 Rust 边刷题。

  • 不要沉迷于数论

    LeetCode 上有一些涉及到数论的题目,但是代码面试不是 ACM, 也不是你的大学期末考试。最多熟悉一下排列组合算法、全排列和欧几里得算法就行了,不要沉迷于数论。

  • 要总结自己的特殊问题

    说了这么多,都是共性的问题,但是每个人都会有自己特殊的问题。比如说我的问题就在于不太敢用字典,总觉得会让人感觉投机取巧,我一个工作四年的人,肯定是知道字典的,但是做算法题的时候总在潜意识里避免使用。实际上 LeetCode 第一题就用到了字典。

面试刷题总结(十)- 指针类题目与窗口

链表的指针题目

一般使用 dummy head 的话,循环条件是 while p.next, 而不使用的话,则是 while p.

递归反转列表

int reverseList(ListNode node) {
    if (node == null || node.next == null) {
        return node;
    }
    ListNode head = reverseList(node.next);
    node.next.next = node;
    node.next = null;
    return head;
}

都比较简单,主要是细节的使用。

  • LeetCode 24
  • LeetCode 25
  • LeetCode 206

参考资料

  1. https://mp.weixin.qq.com/s/YFe9Z35CE4QWPDmPNitd4w

前缀和

前缀和这个概念可以说是「会者不难,难者不会」,概念本身是很简单的,但是如果不知道的话,好多题就两眼一抹黑了。前缀和即为数组从 0 到当前位置的和,类似的概念还有后缀和,前缀积,后缀积等。

presum[0] = A[0]
presum[i] = presum[i-1] + A[i]

例题

求数组中绝对值最小的子数组

利用前缀和的性质:A[i] + A[i+1] + ... + A[j] = presum[j] - presum[i-1] 前缀和排序,取差值最小值。

有一道题,求两个时间之间的差值,其实是类似的。当差值直接累加计算不好求的时候可以转换为前缀和的差。

把一个数组从中间 p 位置分开,使得 a[0]+…+a[p-1] 与 a[p]+a[p+1]+…+a[n-1] 差值最小?

也就是使得:presum - (total - presum) = 2 * presum - total 最小。

参考资料

  1. https://www.cnblogs.com/AndyJee/p/4474073.html

面试刷题总结(六)-栈和队列

栈本身是一种特别简单的数据结构,这里就不多说了,主要记录一些以前不会的题目。

单调栈

单调栈就是满足单调性的栈。比如递增的栈,如果新的元素比栈顶的元素小的话,就要一直弹出,直到找到满足条件的栈顶,然后再入栈。

单调队列

单调队列使用两个队列组成。其中一个是普通的队列,另一个是维护大小顺序的队列。这里的队列不是严格的队列,而是可以从尾部弹出的双端队列。

from collections import deque

class MonoQueue:
    def __init__(self):
        self.q = deque()  # 实际储存数据
        self.m = deque()  # 维护单调关系,队首元素总是最大值

    def push(self, x):
        self.q.append(x)
        while len(self.m) > 0 and self.m[-1] < x:
            self.m.pop()
        self.m.append(x)

    def pop(self):
        x = self.q.popleft()
        if self.m[0] == x:
            self.m.popleft()
        return x

    def __len__(self):
        return len(self.q)

    def top(self):
        return self.m[0]

例题

单调队列的题目

  • LC84. Largest Rectangle in Histogram
  • LC239. Sliding Window Maximum
  • LC739. Daily Temperatures
  • LC862. Shortest Subarray with Sum at Least K
  • LC901. Online Stock Span
  • LC907. Sum of Subarray Minimums

POJ3250 Bad Hair Day

有 N 头牛从左到右排成一排,每头牛有一个高度 h[i],设左数第 i 头牛与「它右边第一头高度 >= h[i]」的牛之间有 c[i] 头牛,试求 sum(c[i])。

这道题使用单调栈做。

def sum_distance(H):
    ans = 0
    stack = []
    for h in H:
        # 单调递减的栈
        while stack and stack[-1] < h:
            stack.pop()
        ans += len(stack)
        stack.append(h)
    return ans

参考资料

  1. https://oi-wiki.org/ds/monotonous-stack/
  2. https://www.hankcs.com/program/algorithm/poj-3250-bad-hair-day.html
  3. https://oi-wiki.org/ds/monotonous-queue/
  4. https://oi.men.ci/monotone-queue-notes/

小技巧

时间复杂度需要优化

如果你的算法和预期的时间复杂度还差一些数量级,那么考虑下是不是某个操作可以转化成 hash 查表,这样这个操作就是 O(1) 了。

如何证明算法正确

一般使用归纳法。

UnionFind 算法

unionfind 算法是用于计算图中的节点连通性的算法。其中连同的意思是满足『自反』『对称』『传递』三个意思的连通。

class UnionFind:
    def __init__(self, count):
        self.count = count
        self.parents = list(range(count))  # 初始化时 parent 指针指向自己

    def union(self, p, q):
        """把 p, q 两个节点连通起来"""
        p_root = self.find(p)
        q_root = self.find(q)
        if p_root == q_root:
            return
        self.parents[p_root] = q_root
        self.count -= 1

    def find(self, p):
        """找到 p 节点的根节点"""
        while self.parents[p] != p:
            p = self.parents[p]
        return p

    def is_connected(p, q):
        p_root = self.find(p)
        q_root = self.find(q)
        return p_root == q_root

在上面的算法中,我们发现 union 和 is_connected 主要依赖于 find 的时间复杂度。而在树极端不平衡的情况下,是可能退化到 O(n) 的,所以不优化的前提下,时间复杂度是 O(n)。

优化1 – 保持树平衡

class UnionFind:
    def __init__(self, count):
        self.count = count
        self.parents = list(range(count))  # 初始化时 parent 指针指向自己
        self.sizes = [1] * count  # 记录每棵树的大小

    def union(self, p, q):
        """把 p, q 两个节点连通起来"""
        p_root = self.find(p)
        q_root = self.find(q)
        if p_root == q_root:
            return
        if self.sizes(p_root) > self.sizes(q_root):
            self.parents[q_root] = p_root
            self.sizes[p_root] += self.sizes[q_root]
        else:
            self.parents[p_root] = q_root
            self.sizes[q_root] += self.sizes[p_root]
        self.count -= 1

经过这个优化之后,时间复杂度就降到 O(logN) 了。

优化2 – 路径压缩

在调用 find 函数的时候,把

class UnionFind:
    def find(self, p):
        """找到 p 节点的根节点"""
        while self.parents[p] != p:
            # 神奇的路径压缩
            self.parents[p] = self.parents[self.parents[p]]
            p = self.parents[p]
        return p

Go 语言实现

type UnionFind struct {
    count int,
    parents []int,
    sizes []int
}

func NewUnionFind(n int) (*UnionFind) {
    parents := make([]int, n)
    sizes := make([]int, n)
    for i := 0; i < n; i++ {
        parents[i] = i
        sizes[i] = 1
    }
    return &UnionFind{n, parents, sizes)
}

func (uf *UnionFind) Union (p, q int) {
    pRoot := uf.Find(p)
    qRoot := uf.Find(q)
    if pRoot == qRoot {
        return
    }
    if uf.sizes[pRoot] < uf.sizes[qRoot] {
        uf.parents[pRoot] = qRoot
        uf.sizes[qRoot] += uf.sizes[pRoot]
    } else {
        uf.parents[qRoot] = pRoot
        uf.sizes[pRoot] += uf.sizes[qRoot]
    }
    uf.count -= 1
}

func (uf *UnionFind) Find(p int) int {
    while uf.parents[p] != p {
        uf.parents[p] = uf.parents[uf.parents[p]]
        p = uf.parents[p]
    }
    return p
}

func (uf *UnionFind) IsConnected(p, q int) bool {
    pRoot := uf.Find(p)
    qRoot := uf.Find(q)
    return pRoot == qRoot
}

LeetCode 题目

LeetCode 200 岛屿的数量

这个题就很简单了,简直是 UnionFind 的直接应用。

  1. Union-Find 并查集算法详解

面试刷题总结(三) – 深度优先搜索与回溯

回溯(backtrack)是一种系统性地搜索问题解答的方法。为了实现回溯,首先需要为问题定义一个解空间(solution space),这个空间必须至少包含问题的一个解(可能是最优的)。深度优先搜索方法本质上是对解空间的深度优先遍历,也就是说要做到「心中有树」。

回溯问题往往使用同一套代码可以解决一个问题的好几个变种。所以我们解决问题的时候应该首先尝试解决最基础的形式:判定是否有解或者有几个解,然后再去具体求解路径。

本质上来说,回溯就是一种暴力解法。

解题模板

核心就是 for 循环里面的递归,在递归调用之前「做选择」,在递归调用之后「撤销选择」。下面的 if 不可行 其实就是剪枝的过程。给定的函数往往不一定满足回溯的函数签名,添加一个 helper 函数就好了。track 就是路径的意思,所以回溯(backtrack)本身就是路径退回的意思。

需要注意的是,剪枝虽然能够提高程序运行速度,但是对于时间复杂度往往没有改善。回溯算法的时间复杂度往往是 O(2^n)

选择列表  # 题目给定
ans = []
def backtrack( track , pos ):
    """
    track: 当前路径
    pos: 当前位置,或者是剩下的未访问元素
    """
    if 满足结束条件 :  # base case
        ans.add( track )
        return

    # 通过考虑 pos,可以让选择列表小一点
    for 选择 in 选择列表 [pos] :
        if 不可行 :
            continue
        做选择  # track -> new_track
        backtrack( new_track , 选择 )
        撤销选择  # new_track -> track

我们可以看到回溯的空间复杂度实际上就是路径的最大长度。ans 参数完全可以写到 backtrack 函数中一直传递,但是本来 backtrack 函数的参数就够多了,我还是建议把他作为一个全局变量或者闭包外的变量,这样清晰一些。

另外值得注意的一点是,我们传递了 pos 这个变量,实际上从这里很容易转变成动态规划了。实际上这里的 pos 就是动态规划中遍历数组的索引。

改变函数签名与参数传递

正如上面所说的,回溯算法往往是需要定义一个 helper 函数的。

回溯最好把结果变量作为一个全局变量和输入变量都定义在外边,这样方便一些,不然就得一路传递下去,容易出问题。backtrack 函数接收两个参数:

  1. 当前路径
  2. 当前遍历位置

这里其实是更广义的 result in parameter 还是 result in return value 的问题。最好给用户用的函数是 result in return value 的,自己的内部实现可以是 result in parameter 的。另外也可以用闭包实现 result in parameter 的效果,也就是说不传递参数,直接从 closure 中读取。其实也可以用一个全局变量来做,都是类似的效果。

—存疑—
固定传递的参数也包括了向下传递还是向上返回。具体来说有以下几种:

  1. 向下传递额外参数,如边界等,这个参数可能是随着调用在变的。
  2. 向上返回额外参数,也就是后续遍历才能够使用到返回的值。
    —存疑结束—

例题

对于 Python 来说,一般没必要使用全局变量,可以使用内部函数访问闭包内的变量。

LeetCode 17

这道题可以说是最最简单的一道 dfs 题目了。

参考

  1. https://www.dailycodingproblem.com/blog/an-introduction-to-backtracking/
  2. https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/hui-su-suan-fa-xiang-jie-xiu-ding-ban
  3. https://www.cnblogs.com/hustcat/archive/2008/04/09/1144645.html
  4. https://www.1point3acres.com/bbs/thread-583166-1-1.html
  5. https://zhuanlan.zhihu.com/p/92782083

面试刷题总结(二) – 分治

分解 -> 解决子问题 -> 合并

分治的时间复杂度

正如上一节所说的,分治问题在递归过程中实际上是遍历了状态空间树,所以时间复杂度的计算也需要根据树的高度和每一层的时间复杂度来计算。

recursion-tree

T(n) = a T(n/b) + f(n), if f(n) ∈ O(n^d), d >=0
T(n)∈ { 
    O(n^d), a < b^d;
    O(n^d logn), a = b^d;
    O(n^(logba), a > b^d;
}

通过 O(n) 的时间,把 n 的问题,变为了两个 n/2 的问题,复杂度是多少?

T(n) = 2T(n/2) + O(n)
    = 2 * 2T(n/4) + O(n) + O(n)
    = n + nlogn
    ≈ O(NlogN)

通过 O(1) 的时间,把 n 的问题,变成了两个 n/2 的问题,复杂度是多少?

T(n) = 2T(n/2) + O(1)
    = 2 * 2T(n/4) + O(1) + O(1)
    = n + (1 + 2 + 4 +…+ n)
    ≈ n + 2n
    ≈ O(n)

对于 O(nlogn) 的算法 T(n) = 2T(n/2) + O(n)

证明一般采用数学归纳法,反证法

改变函数签名与参数传递

参见递归中的说明

例题

LeetCode 241

class Solution:
    def diffWaysToCompute(self, s: str) -> List[int]:
        if s.isdigit():
            return [int(s)]
        ans = []
        for i in range(len(s)):
            if s[i] in ("+", "-", "*"):
                left = self.diffWaysToCompute(s[:i])
                right = self.diffWaysToCompute(s[i+1:])
                for l in left:
                    for r in right:
                        if s[i] == "+":
                            ans.append(l+r)
                        elif s[i] == "-":
                            ans.append(l-r)
                        else:
                            ans.append(l*r)
        return ans

参考资料

  1. https://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247487045&idx=3&sn=e9f67f1fd33649c60478638c1d6cc2d9
  2. https://oi-wiki.org/basic/divide-and-conquer/