网站开发后台软件,时尚网站模板代码,网站建站免费空间,网站建设公司营业执照经营范围前言#xff1a;
哈喽大家好#xff0c;前段时间在小红书和牛客上发了面试的经验贴#xff0c;很多同学留言问算法的具体解法#xff0c;今天就详细写个帖子回复大家。
因为csdn是写的比较详细#xff0c;所以更新比较慢#xff0c;大家见谅~~
就题目而言#xff0c;…前言
哈喽大家好前段时间在小红书和牛客上发了面试的经验贴很多同学留言问算法的具体解法今天就详细写个帖子回复大家。
因为csdn是写的比较详细所以更新比较慢大家见谅~~
就题目而言前两题是平时刷题常见的第三题没有见过需要认真思考下
最后希望找工作的同学都能收获心仪的offer
求两个数的最大公约数
链接
这道题没有找到原题链接找到一个近似的题目
1979. 找出数组的最大公约数 - 力扣LeetCodehttps://leetcode.cn/problems/find-greatest-common-divisor-of-array/description/ 给你一个整数数组 nums 返回数组中最大数和最小数的 最大公约数 。 两个数的 最大公约数 是能够被两个数整除的最大正整数。 思路
辗转相除法原理 两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。 例如欲求252和105的最大公约数因为 252÷1052...42所以这个最大公约数也是42与105的最大公约数(4221×2)。在这个过程中较大的数缩小了所以继续进行同样的计算可以不断缩小这两个数直至余数为零。这时所剩下的还没有变成零的数就是两数的最大公约数。
我们将上述过程翻译成递归代码得到如下代码
class Solution:def findGCD(self, nums: List[int]) - int:def gcd(x,y):if xy:x,y y,xif x0:return yreturn 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 capacityself.cnt 0self.queue []self.dic defaultdict(int)def get(self, key: int) - int:if key not in self.dic:return -1del 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] valueelif self.cnt self.capacity:self.queue.append(key)self.dic[key] valueself.cnt1else: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 cntcnt 0words tuple(words)cachedef dfs(w,words,length):if w not in words:global cntcnt max(cnt,length)returnn len(w)for i in range(n):temp ww w[0:i] w[i1:]dfs(w,words,length1)w tempfor w in words:dfs(w,words,0)return cnt
