腾讯春招后端一面（算法篇）

前言：

哈喽大家好，前段时间在小红书和牛客上发了面试的经验贴，很多同学留言问算法的具体解法，今天就详细写个帖子回复大家。

因为csdn是写的比较详细，所以更新比较慢，大家见谅~~

就题目而言，前两题是平时刷题常见的，第三题没有见过，需要认真思考下

最后，希望找工作的同学都能收获心仪的offer

求两个数的最大公约数

链接

这道题没有找到原题链接，找到一个近似的题目

1979. 找出数组的最大公约数 - 力扣（LeetCode）https://leetcode.cn/problems/find-greatest-common-divisor-of-array/description/

给你一个整数数组 nums ，返回数组中最大数和最小数的 最大公约数 。

两个数的 最大公约数 是能够被两个数整除的最大正整数。

思路

辗转相除法原理：

两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。

例如：欲求252和105的最大公约数；因为 252÷105=2...42，所以这个最大公约数也是42与105的最大公约数(42=21×2)。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至余数为零。这时，所剩下的还没有变成零的数就是两数的最大公约数。

我们将上述过程翻译成递归代码，得到如下代码：

class Solution:
    def findGCD(self, nums: List[int]) -> int:
        def gcd(x,y):
            if x>y:
                x,y = y,x
            if x==0:return y
            return gcd(y%x,x)
        
        return gcd(max(nums),min(nums))

lru缓存

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

链接 ：LRUCache. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/lru-cache/

思路

我这里用列表模拟队列，用字典实现缓存，设计了总容量，当前元素数等变量进行模拟

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cnt = 0
        self.queue = []
        self.dic = defaultdict(int)

    def get(self, key: int) -> int:
        if key not in self.dic:
            return -1
        del self.queue[self.queue.index(key)]
        self.queue.append(key)
        # print(self.queue)
        return self.dic[key] 

    def put(self, key: int, value: int) -> None:
        if key in self.dic:
            del self.queue[self.queue.index(key)]
            self.queue.append(key)
            self.dic[key] = value

        elif self.cnt < self.capacity:
            self.queue.append(key)
            self.dic[key] = value
            self.cnt+=1
        else:
            del self.dic[self.queue[0]]
            del self.queue[0]
            self.queue.append(key)
            self.dic[key] = value



# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

最长字符串链

链接：

最长字符串链https://leetcode.cn/problems/longest-string-chain/

给出一个单词数组 words ，其中每个单词都由小写英文字母组成。

如果我们可以 不改变其他字符的顺序 ，在 wordA 的任何地方添加 恰好一个 字母使其变成 wordB ，那么我们认为 wordA 是 wordB 的 前身 。

• 例如，"abc" 是 "abac" 的 前身 ，而 "cba" 不是 "bcad" 的 前身

词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word1 是 word2 的前身，word2 是 word3 的前身，依此类推。一个单词通常是 k == 1 的 单词链 。

从给定单词列表 words 中选择单词组成词链，返回 词链的 最长可能长度 

思路

这道题是这三道中我唯一没有见过的题，但面试中遇到没见过的题也蛮正常的，不要慌，放心做即可。

我们对每一个字符串进行查找，比如 abfd，我们检查bfd,afd,abd,abf这四个字符串在不在words数组中，如果不在就return，否则继续查找，保存最长的链条。

这道题中，我在dfs函数上加了缓存，存储一些已经计算的点，使用tuple()是因为列表无法被哈希话，所以把它转为元组。题解中有很多更好的写法，读者可以多去学习

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        global cnt
        cnt = 0
        words = tuple(words)
        @cache
        def dfs(w,words,length):
            if w not in words:
                global cnt
                cnt = max(cnt,length)
                return
            n = len(w)
            for i in range(n):
                temp = w
                w = w[0:i] + w[i+1:]
                dfs(w,words,length+1)
                w = temp
        for w in words:
            dfs(w,words,0)
        return cnt