算法学习的必要性

Time: 2019-08-06

为什么考察算法？

• 算法可以看出候选者够不够聪明
• 实现算法问题，可以控制时间
• 算法问题不能通过背答案蒙混过关
• 算法能力强则工作能力也强

Rabin-Karp算法

面试中不要学习KMP算法，KMP是非常针对性的算法，且很难理解和实现，替代性的算法就是：Rabin-Karp算法。

strStr(): 寻找字符串匹配问题

一种自然的写法：

class Solution:
    def strStr(self, source: str, target: str) -> int:
        if source == None or target == None:
            return -1
        if len(target) == 0:
            return 0
        
        for i in range(len(source) - len(target) + 1):
            j = 0
            for j in range(len(target)):
                if source[i + j] != target[j]:
                    break # 当前内层循环判定不可能相等
            # 加source[i + j] == target[j]的原因是，有可能target就1个字符
            if j == len(target) - 1 and source[i + j] == target[j]:
                return i
        return -1

时空复杂度分析

时间复杂度：O((n-m)*m)
空间复杂度：O(1)

Rabin-Karp算法

哈希表法，将任意给定的Key变成整数。

将内层循环O(m)变成O(1)的时间复杂度，用哈希表。

class Solution:
    def strStr(self, source: str, target: str) -> int:
        if source == None or target == None:
            return -1
        if len(target) == 0:
            return 0
        
        for i in range(len(source) - len(target) + 1):
            # 内层循环比较时可以优化
            if hash(source[i:i+len(target)]) == hash(target):
                return i   
        return -1

哈希法有个问题是，Key-->Value并不保证唯一对应，所以可以需要Double Check.

在哈希值相等时再做O(m)复杂度的检查。

所以下面这种写法是更健壮的：

class Solution:
    def strStr(self, source: str, target: str) -> int:
        if source == None or target == None:
            return -1
        if len(target) == 0:
            return 0
        
        for i in range(len(source) - len(target) + 1):
            # 内层循环比较时可以优化
            if hash(source[i:i+len(target)]) == hash(target):
                if source[i:i+len(target)] == target:
                    return i 
                else:
                    break
        return -1 

END.
时间复杂度: O(n+m)。

这里用到的哈希函数是Python自带的，不是自己实现的。