1. 阶乘后的零
给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
示例 1：
输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0
示例 2：
输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0
示例 3：
输入：n = 0
输出：0
提示：
0 <= n <= 10^4
进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？
出处：
https://edu.csdn.net/practice/24289744
代码：
class Solution: def trailingZeroes(self, n: int) -> int: zero_count = 0 current_multiple = 5 while n >= current_multiple: zero_count += n // current_multiple current_multiple *= 5 return zero_count # %% s = Solution() print(s.trailingZeroes(5)) print(s.trailingZeroes(100))
输出：
1
24
以下这种写法更简洁：
class Solution: def trailingZeroes(self, n: int) -> int: count = 0 while n > 0: count += n // 5 n //= 5 return count
2. 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:
输入: s = ""
输出: 0
提示：
0 <= s.length <= 5 * 10^4
s 由英文字母、数字、符号和空格组成
出处：
https://edu.csdn.net/practice/24289745
代码：
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: i = 0 j = 0 m = 0 hset = {} while j < len(s): char = s[j] index = hset.get(char) if index is not None and index > i: i = index m = m if m > j - i + 1 else j - i + 1 hset[char] = j + 1 j += 1 return m # %% s = Solution() print(s.lengthOfLongestSubstring('abcabcbb')) print(s.lengthOfLongestSubstring('pwwkew'))
输出：
3
3
3. LRU 缓存机制
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制(https://baike.baidu.com/item/LRU)
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例：
输入 ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4] 解释 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4
提示：
1 <= capacity <= 30000 <= key <= 100000 <= value <= 10^5- 最多调用
2 * 10^5次get和put
出处：
https://edu.csdn.net/practice/24289743
代码：
class LRUCache: def __init__(self, capacity): """ :type capacity: int """ self.maxlength = capacity self.array = {} self.array_list = [] def get(self, key): """ :type key: int :rtype: int """ value = self.array.get(key) if value is not None and self.array_list[0] is not key: index = self.array_list.index(key) self.array_list.pop(index) self.array_list.insert(0, key) value = value if value is not None else -1 return value def put(self, key, value): """ :type key: int :type value: int :rtype: void """ if self.array.get(key) is not None: index = self.array_list.index(key) self.array.pop(key) self.array_list.pop(index) if len(self.array_list) >= self.maxlength: key_t = self.array_list.pop(self.maxlength - 1) self.array.pop(key_t) self.array[key] = value self.array_list.insert(0, key) #%% lRUCache = LRUCache(2) lRUCache.put(1, 1) lRUCache.put(2, 2) val = lRUCache.get(1) print(val) lRUCache.put(3, 3) val = lRUCache.get(2) print(val) lRUCache.put(4, 4) val = lRUCache.get(1) print(val) val = lRUCache.get(3) print(val) val = lRUCache.get(4) print(val)c
输出：
1
-1
-1
3
4
