LeetCode 474题 “Ones and Zeroes” 是一个经典的动态规划问题。题目要求我们在给定的字符串数组中，选择尽可能多的字符串，同时满足这些字符串中 ‘0’ 和 ‘1’ 的数量分别不超过给定的两个限制值。

题目描述

给你一个二进制字符串数组 strs 和两个整数 m 和 n。

请你找出并返回 strs 的最大子集的大小，该子集中最多包含 m 个 ‘0’ 和 n 个 ‘1’。

示例

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3 输出：4 解释：最多有 4 个字符串可以选择。 可以选择 "10"、"0001"、"1" 和 "0"。

解题思路

我们可以使用动态规划来解决这个问题。定义一个二维数组 dp，其中 dp[i][j] 表示最多包含 i 个 ‘0’ 和 j 个 ‘1’ 的最大子集大小。

1. 初始化：dp[0][0] = 0，因为不包含任何字符串时，’0′ 和 ‘1’ 的数量都是 0。
2. 遍历字符串数组：对于每个字符串，统计其中的 ‘0’ 和 ‘1’ 的数量。
3. 更新 dp 数组：从后向前更新 dp 数组，以避免重复使用同一个字符串。

代码实现

def findMaxForm(strs, m, n):

dp = [[0] * (n + 1) for _ in range(m + 1)]

# 遍历每个字符串
for s in strs:
    zeros = s.count('0')
    ones = s.count('1')

    # 从后向前更新 dp 数组
    for i in range(m, zeros - 1, -1):
        for j in range(n, ones - 1, -1):
            dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)

return dp[m][n]

print(findMaxForm(strs, m, n)) # 输出：4

解释

1. 初始化 dp 数组：创建一个 (m+1) x (n+1) 的二维数组，初始值都为 0。
2. 统计每个字符串的 ‘0’ 和 ‘1’ 数量：使用 s.count('0') 和 s.count('1')。
3. 更新 dp 数组：从后向前更新是为了确保每个字符串只被使用一次。dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1) 表示在当前条件下，选择或不选择当前字符串的最大子集大小。

复杂度分析

• 时间复杂度：O(len(strs) m n)，其中 len(strs) 是字符串数组的长度。
• 空间复杂度：O(m * n)，用于存储 dp 数组。

通过这种方法，我们可以有效地解决 “Ones and Zeroes” 问题，找到满足条件的最大子集大小。

LeetCode 473题 “Matchsticks to Square” 是一个中等难度的题目，主要考察的是回溯算法和深度优先搜索（DFS）。题目要求我们判断是否可以用一组火柴棍组成一个正方形。每根火柴棍的长度都是给定的，并且我们可以使用每根火柴棍一次。

题目描述

给定一个整数数组 nums，其中每个元素代表一根火柴棍的长度。你需要判断是否可以将这些火柴棍排列成一个正方形。

示例

示例 1:

输入: [1,1,2,2,2] 输出: true

解释: 可以组成一个边长为2的正方形，正方形的四条边分别是 {1,1}, {2}, {2}, {2}。

示例 2:

输入: [3,3,3,3,4] 输出: false

解释: 无法将这些火柴棍组成一个正方形。

解题思路

1. 计算总和和边长：
   • 首先计算所有火柴棍的总长度 sum。
   • 如果 sum 不是4的倍数，直接返回 false，因为无法分成四条相等的边。
   • 计算每条边的长度 side = sum / 4。
2. 排序：
   • 将火柴棍按长度从大到小排序，这样可以更快地发现不满足条件的情况。
3. 回溯算法：
   • 使用深度优先搜索（DFS）尝试将火柴棍分配到四条边上。
   • 维护一个数组 sides，表示当前四条边的长度。
   • 逐个尝试将火柴棍放入某一条边，如果某条边的长度超过了 side，则回溯。
4. 剪枝优化：
   • 如果某根火柴棍的长度超过了 side，直接返回 false。
   • 如果当前边的长度为0，则优先放入当前边，这样可以减少不必要的搜索。

代码实现

class Solution: def makesquare(self, nums: List[int]) -> bool: if not nums: return False

    total_length = sum(nums)
    if total_length % 4 != 0:
        return False

    side_length = total_length // 4
    nums.sort(reverse=True)

    if nums[0] > side_length:
        return False

    sides = [0] * 4

    def dfs(index):
        if index == len(nums):
            return sides[0] == sides[1] == sides[2] == side_length

        for i in range(4):
            if sides[i] + nums[index] <= side_length:
                sides[i] += nums[index]
                if dfs(index + 1):
                    return True
                sides[i] -= nums[index]

            # 如果当前边的长度为0，则不需要继续尝试其他边，因为结果会相同
            if sides[i] == 0:
                break

        return False

    return dfs(0)

解释

1. 初始化和预处理：
   • 计算总长度并判断是否可以分成四条相等的边。
   • 将火柴棍按长度从大到小排序。
2. DFS函数：
   • 递归尝试将每根火柴棍放入四条边中的一条。
   • 如果某条边的长度超过了 side_length，则回溯。
   • 如果所有火柴棍都分配完毕且四条边的长度都等于 side_length，则返回 True。
3. 剪枝优化：
   • 如果当前边的长度为0，则不需要继续尝试其他边，因为结果会相同。

通过上述步骤，我们可以有效地判断是否可以用给定的火柴棍组成一个正方形。这个问题的核心在于合理地使用回溯算法和剪枝优化，以减少不必要的搜索空间。

LeetCode 470题的要求是使用一个已有的rand7()函数来实现一个rand10()函数。rand7()函数可以等概率地生成1到7之间的整数，而我们需要设计一个rand10()函数来等概率地生成1到10之间的整数。

思路分析

直接使用rand7()生成1到10之间的数是有挑战的，因为7和10不是倍数关系。我们可以通过以下步骤来实现：

1. 扩展范围：首先，我们可以通过调用两次rand7()来生成一个更大的范围。具体来说，我们可以生成一个1到49的均匀分布。
   • 设x = rand7()，y = rand7()，则可以构造一个数z = (x - 1) * 7 + y，这样z的范围是1到49。
2. 拒绝采样：由于我们需要的是1到10的数，我们可以利用1到49的范围，但需要排除掉一些数。具体来说，如果生成的数在1到40之间，我们可以利用这个数来生成1到10的数；如果生成的数在41到49之间，则重新生成。
3. 映射到1到10：对于在1到40之间的数，我们可以通过取模操作将其映射到1到10。具体来说，z % 10 + 1就可以得到一个1到10之间的数。

代码实现

以下是具体的代码实现：

def rand7():

pass

    x = rand7()
    y = rand7()
    z = (x - 1) * 7 + y

    # 如果z在1到40之间，则接受这个数
    if z <= 40:
        return z % 10 + 1

    # 如果z在41到49之间，重新生成
    # 这里可以进一步优化，利用41到49之间的数来减少重新生成的概率
    # 但为了简单起见，我们直接重新生成

详细解释

1. 生成1到49的数：
   • x = rand7()生成1到7之间的数。
   • y = rand7()生成1到7之间的数。
   • z = (x - 1) * 7 + y将x和y组合成一个1到49之间的数。这里(x - 1) * 7将x映射到0, 7, 14, 21, 28, 35, 42，再加上y（1到7），得到1到49。
2. 拒绝采样：
   • 如果z在1到40之间，我们接受这个数。
   • 如果z在41到49之间，我们重新生成，因为这部分数不能均匀映射到1到10。
3. 映射到1到10：
   • 对于接受的数z，通过z % 10 + 1将其映射到1到10。

时间复杂度

虽然这个方法在最坏情况下可能需要多次调用rand7()，但其期望时间复杂度是常数时间，因为每次重新生成的概率是逐渐减小的。

空间复杂度

这个方法的空间复杂度是O(1)，因为只需要常数级别的额外空间。

通过这种方法，我们成功地将rand7()转换为rand10()，确保了生成的数的均匀性和随机性。

LeetCode 469题是关于判断一个多边形是否为凸多边形的问题。凸多边形是指所有内角都小于180度的多边形，或者等价地说，多边形上任意两点的连线都在多边形内部。

题目描述

给定一个多边形的所有顶点坐标，你需要判断这个多边形是否为凸多边形。

输入

一个二维数组 points，其中每个元素是一个长度为2的数组，表示多边形的一个顶点的坐标。

输出

返回一个布尔值，表示这个多边形是否为凸多边形。

示例

输入: points = [[0,0],[0,1],[1,1],[1,0]] 输出: true

输入: points = [[0,0],[0,1],[1,0]] 输出: false

解题思路

判断一个多边形是否为凸多边形可以通过计算相邻边之间的叉积（cross product）来实现。具体步骤如下：

1. 计算叉积： 对于多边形的每三个连续顶点 (A, B, C)，计算向量 (AB) 和 (BC) 的叉积。叉积的符号可以告诉我们 (B) 点处的转向是左转还是右转。
2. 判断转向：
   • 如果所有相邻边的叉积符号相同（全为正或全为负），则多边形为凸多边形。
   • 如果叉积符号不一致，则多边形不是凸多边形。
3. 处理边界情况：
   • 多边形至少需要3个顶点才能构成一个多边形。
   • 需要考虑顶点顺序的影响，可以统一按照顺时针或逆时针顺序处理。

代码实现

以下是使用Python实现的代码示例：

def isConvex(points): def cross_product(o, a, b):

    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

n = len(points)
if n < 3:
    return False

# 初始化前两个边的叉积符号
pre = 0
for i in range(n):
    # 当前点、下一个点和下下个点
    cur = cross_product(points[i], points[(i + 1) % n], points[(i + 2) % n])
    if cur != 0:
        if pre * cur < 0:
            return False
        pre = cur

return True

print(isConvex(points1)) # 输出: True print(isConvex(points2)) # 输出: False

解释

1. cross_product函数：计算两个向量的叉积。
2. 主函数isConvex：
   • 首先检查顶点数量是否小于3，如果是则直接返回False。
   • 使用一个循环遍历所有顶点，计算每三个连续顶点形成的两个向量的叉积。
   • 如果叉积不为0，检查当前叉积与前一个叉积的符号是否相反，如果是则返回False。
   • 如果所有叉积符号一致，则返回True。

通过这种方法，可以有效地判断一个多边形是否为凸多边形。希望这个解释对你理解并解决LeetCode 469题有所帮助！

LeetCode 上的第 468 题 “Validate IP Address” 要求编写一个函数来验证给定的字符串是否是有效的 IPv4 或 IPv6 地址。IPv4 地址由四个十进制数字组成，每个数字介于 0 到 255 之间，用点（.）分隔。IPv6 地址由八个十六进制数字组成，用冒号（:）分隔。

题目描述

编写一个函数来验证输入的字符串是否是有效的 IPv4 或 IPv6 地址。

示例

示例 1:

输入: "172.16.254.1"

解释: 这是一个有效的 IPv4 地址, 所以返回 "IPv4"。

示例 2:

输入: "2001:0db8:85a3:0:0:8A2E:0370:7334"

解释: 这是一个有效的 IPv6 地址, 所以返回 "IPv6"。

示例 3:

输入: "256.256.256.256"

解释: 这不是一个有效的 IPv4 或 IPv6 地址, 所以返回 "Neither"。

解题思路

1. 判断基础格式：
   • 如果字符串包含点（.），则可能是 IPv4 地址。
   • 如果字符串包含冒号（:），则可能是 IPv6 地址。
2. 验证 IPv4 地址：
   • 按点（.）分割字符串，应该得到四个部分。
   • 每个部分必须是介于 0 到 255 之间的十进制数。
   • 每个部分不能有前导零。
3. 验证 IPv6 地址：
   • 按冒号（:）分割字符串，应该得到八个部分。
   • 每个部分必须是 1 到 4 位的十六进制数。

代码实现

以下是 Python 实现的示例代码：

class Solution: def validIPAddress(self, IP: str) -> str: def isIPv4(s): parts = s.split('.') if len(parts) != 4: return False for part in parts: if not part.isdigit() or not 0 <= int(part) <= 255: return False if part != str(int(part)): # 检查是否有前导零 return False return True

    def isIPv6(s):
        parts = s.split(':')
        if len(parts) != 8:
            return False
        for part in parts:
            if len(part) == 0 or len(part) > 4:
                return False
            for char in part:
                if not (char.isdigit() or 'a' <= char.lower() <= 'f'):
                    return False
        return True

    if isIPv4(IP):
        return "IPv4"
    elif isIPv6(IP):
        return "IPv6"
    else:
        return "Neither"

sol = Solution() print(sol.validIPAddress("172.16.254.1")) # 输出: "IPv4" print(sol.validIPAddress("2001:0db8:85a3:0:0:8A2E:0370:7334")) # 输出: "IPv6" print(sol.validIPAddress("256.256.256.256")) # 输出: "Neither"

详细解释

1. isIPv4 函数：
   • 使用 split('.') 将字符串按点分割。
   • 检查分割后的部分数量是否为 4。
   • 对每个部分进行以下检查：
     • 是否为数字。
     • 转换为整数后是否在 0 到 255 范围内。
     • 去除前导零后是否与原字符串相同。
2. isIPv6 函数：
   • 使用 split(':') 将字符串按冒号分割。
   • 检查分割后的部分数量是否为 8。
   • 对每个部分进行以下检查：
     • 长度是否在 1 到 4 之间。
     • 每个字符是否为数字或十六进制字符（a-f 或 A-F）。
3. 主函数 validIPAddress：
   • 调用 isIPv4 和 isIPv6 函数进行验证，根据结果返回 “IPv4″、”IPv6” 或 “Neither”。

通过这种方式，可以有效地验证给定的字符串是否是有效的 IP 地址，并返回相应的结果。

题目描述：

我们定义字符串 s 的 “环绕字符串” 是将字符串 s 中的字符按照顺序连接成一个圆形。例如，字符串 “abc” 的环绕字符串是 “abcabcabc…” 无限循环。

给定一个字符串 p，你需要找到 p 中不同环绕字符串的最小子串的数量。

示例：

输入: "a" 输出: 1

解释: 字符串列表 ["z", "a", "b", "za", "ab", "zab"].

解题思路：

1. 理解环绕字符串的特性：
   • 环绕字符串是无限循环的，所以我们只需要考虑字符串 p 中连续的子串。
   • 由于是环绕的，字符 'z' 后面可以接字符 'a'。
2. 动态规划的思想：
   • 我们可以用一个数组 count 来记录以每个字符结尾的最长连续子串的长度。
   • 例如，如果 p 中有子串 “abc”，那么 count['c'] 至少为 3。
3. 具体步骤：
   • 初始化一个长度为 26 的数组 count，用于记录每个字符结尾的最长连续子串长度。
   • 遍历字符串 p，记录当前连续子串的长度 length。
   • 如果当前字符和前一个字符是连续的（包括 'z' 到 'a' 的情况），则 length 增加 1，否则重置为 1。
   • 更新 count 数组：count[current_char] = max(count[current_char], length)。
   • 最后，count 数组中的所有元素之和即为答案。

代码实现：

class Solution: def findSubstringInWraproundString(self, p: str) -> int: if not p: return 0

    count = [0] * 26  # 用于记录以每个字符结尾的最长连续子串长度
    length = 0  # 当前连续子串的长度

    for i in range(len(p)):
        if i > 0 and (ord(p[i]) == ord(p[i - 1]) + 1 or (p[i] == 'a' and p[i - 1] == 'z')):
            length += 1
        else:
            length = 1
        count[ord(p[i]) - ord('a')] = max(count[ord(p[i]) - ord('a')], length)

    return sum(count)

sol = Solution() print(sol.findSubstringInWraproundString("a")) # 输出: 1 print(sol.findSubstringInWraproundString("cac")) # 输出: 2 print(sol.findSubstringInWraproundString("zab")) # 输出: 6

解释：

1. 初始化：
   • count 数组初始化为全 0，表示每个字符结尾的最长连续子串长度初始为 0。
   • length 初始为 0，表示当前连续子串的长度。
2. 遍历字符串 p：
   • 对于每个字符，检查它是否和前一个字符连续（包括 'z' 到 'a' 的情况）。
   • 如果连续，length 增加 1；否则，重置 length 为 1。
   • 更新 count 数组，确保记录的是最长连续子串的长度。
3. 计算结果：
   • 最后，count 数组中的所有元素之和即为不同环绕字符串的最小子串数量。

这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)，因为 count 数组的长度是固定的 26。

LeetCode 466题 “Count The Repetitions” 是一个中等难度的字符串问题。题目要求我们计算一个字符串在另一个字符串中的重复次数。具体来说，给定两个字符串 s1 和 s2，我们需要确定 s1 在 s2 中重复的最多次数。

题目描述

定义两个字符串 s1 和 s2，请编写一个函数来计算 s1 在 s2 中重复的最多次数。这里的“重复”是指 s1 可以在 s2 中连续出现多次，并且每次出现的位置可以重叠。

示例

示例 1:

输入: s1 = "ab", s2 = "abab" 输出: 2 解释: "ab" 在 "s2" 中重复了两次。

示例 2:

输入: s1 = "abc", s2 = "abababc" 输出: 1 解释: "abc" 在 "s2" 中重复了一次。

解题思路

1. 暴力解法：
   • 使用双指针分别遍历 s1 和 s2。
   • 每次在 s2 中找到 s1 的一个匹配，记录匹配的次数。
   • 这种方法的时间复杂度为 O(n*m)，其中 n 是 s2 的长度，m 是 s1 的长度。
2. 优化解法：
   • 利用字符串的周期性，找到 s1 在 s2 中的周期性出现模式。
   • 通过计算 s1 和 s2 的最小公倍数来优化匹配过程。
   • 这种方法的时间复杂度可以优化到 O(n + m)。

代码实现

以下是使用优化解法的 Python 代码实现：

def getMaxRepetitions(s1, n1, s2, n2):

index = 0  # s2中的位置
count = 0  # s1重复的次数
recall = {}  # 记录出现过的(s1中的位置, s2中的位置, s1重复的次数)

while True:
    # 遍历s1
    for i in range(len(s1)):
        if s1[i] == s2[index]:
            index += 1
            if index == len(s2):
                index = 0
                count += 1

    # 检查是否已经记录过当前状态
    if (index, count) in recall:
        (prev_index, prev_count) = recall[(index, count)]
        # 计算循环的长度
        circle_len = i - prev_index
        circle_count = count - prev_count
        # 计算总共可以包含多少个循环
        total_count = (n1 - prev_index - 1) // circle_len * circle_count
        # 计算剩余部分
        left_index = prev_index + (n1 - prev_index - 1) % circle_len
        left_count = recall.get((left_index, count), (0, 0))[1]
        return (total_count + left_count) // n2
    else:
        recall[(index, count)] = (i, count)

return count // n2

s1 = "ab" n1 = 1 s2 = "abab" n2 = 1 print(getMaxRepetitions(s1, n1, s2, n2)) # 输出: 2

解释

1. 初始化：
   • index 表示当前在 s2 中的位置。
   • count 表示 s1 在 s2 中重复的次数。
   • recall 是一个字典，用于记录出现过的状态 (index, count) 对应的 (i, count)。
2. 遍历 s1：
   • 对于 s1 中的每个字符，检查是否与 s2 中的当前字符匹配。
   • 如果匹配，更新 index 和 count。
3. 检查循环：
   • 如果当前状态 (index, count) 已经在 recall 中出现过，说明找到了一个循环。
   • 计算循环的长度和循环内的重复次数。
   • 根据循环计算总的重复次数。
4. 返回结果：
   • 计算并返回最终的重复次数。

这个优化解法通过记录状态和检测循环，避免了重复的计算，从而提高了效率。希望这个解释和代码对你理解这道题目有所帮助！

题目描述：

你有 n 个账户，初始余额保存在一个长度为 n 的数组 balances 中，其中第 i 个账户的初始余额是 balances[i]。你可以从任意一个账户向另一个账户转账任意金额（可能为 0），手续费为 1 单位金额。

你需要通过转账使得所有账户的余额都变为 0。请你计算最少需要多少单位金额的手续费。

示例：

输入：balances = [1,0,5,-4,-2] 输出：2 解释：

• 从账户 0 转账 1 单位到账户 4，手续费为 1。
• 从账户 2 转账 5 单位到账户 3，手续费为 1。 总手续费为 2。

解题思路：

1. 理解问题本质：
   • 需要将所有账户的余额变为 0，通过转账操作，每次转账有 1 单位的手续费。
   • 目标是最小化手续费。
2. 数学建模：
   • 将所有正余额的总和记为 totalPositive，所有负余额的总和记为 totalNegative。
   • 由于每次转账都会产生 1 单位的手续费，实际上我们需要关注的是如何通过最少的转账次数将正余额和负余额相互抵消。
3. 关键观察：
   • 每次转账可以看作是将一个正余额和一个负余额相互抵消的过程。
   • 最少转账次数等于正余额和负余额绝对值之和的最小值。
4. 具体步骤：
   • 计算所有账户余额的总和 totalSum。
   • 如果 totalSum 不为 0，则无法通过转账使所有账户余额变为 0，返回 -1。
   • 否则，计算所有正余额的总和 totalPositive 和所有负余额的总和 totalNegative。
   • 最少手续费为 min(totalPositive, -totalNegative)。

代码实现：

class Solution: def minTransfers(self, balances: List[int]) -> int: from collections import defaultdict

    # 计算每个账户的净余额
    net_balances = defaultdict(int)
    for balance in balances:
        net_balances[balance] += 1

    # 只保留非零净余额
    debts = []
    for balance, count in net_balances.items():
        if balance > 0:
            debts.extend([balance] * count)
        elif balance < 0:
            debts.extend([balance] * count)

    # 使用递归 + 回溯的方法求解最小转账次数
    def dfs(index, debts):
        while index < len(debts) and debts[index] == 0:
            index += 1
        if index == len(debts):
            return 0

        min_transfers = float('inf')
        for i in range(index + 1, len(debts)):
            if debts[index] * debts[i] < 0:  # 找到符号相反的账户进行抵消
                debts[i] += debts[index]
                min_transfers = min(min_transfers, 1 + dfs(index + 1, debts))
                debts[i] -= debts[index]  # 回溯

        return min_transfers

    return dfs(0, debts)

sol = Solution() print(sol.minTransfers([1,0,5,-4,-2])) # 输出：2

解释：

1. 计算净余额：
   • 使用 defaultdict 统计每个余额的出现次数。
   • 只保留非零净余额，正余额和负余额分别处理。
2. 递归 + 回溯：
   • 从第一个非零余额开始，尝试与其他符号相反的余额进行抵消。
   • 递归求解剩余余额的最小转账次数，并记录最小值。
   • 回溯恢复状态。
3. 复杂度分析：
   • 时间复杂度：最坏情况下为 O(n!)，因为需要尝试所有可能的抵消组合。
   • 空间复杂度：O(n)，用于存储净余额和递归调用栈。

这种方法虽然理论上复杂度较高，但在实际情况下，通过合理的剪枝和优化，可以在可接受的时间内求解中等规模的问题。

当然可以！LeetCode 上的 “Can I Win”（题目编号 464）是一个中等难度的动态规划问题。下面我将详细解释这个问题的背景、解题思路以及具体的代码实现。

题目描述

在 “Can I Win” 问题中，你正在和一个朋友玩一个游戏。游戏规则如下：

1. 你们轮流从 1 到 maxChoosableInteger 中选择一个整数。
2. 每次选择后，该整数将不能再被选择。
3. 谁选到的整数之和首先达到或超过 desiredTotal，谁就获胜。

你需要判断在先手的情况下，你是否能保证获胜。

输入输出

• 输入：
  • maxChoosableInteger：可以选择的最大整数。
  • desiredTotal：目标和。
• 输出：
  • bool：如果你能保证获胜，返回 True，否则返回 False。

好的，我们来详细讨论一下 LeetCode 上的第 460 题：LFU Cache（最不经常使用缓存）。

题目描述

LFU（Least Frequently Used）缓存是一种缓存替换策略，它根据数据访问的频率来淘汰数据。如果一个数据在缓存中很少被访问，那么它将会被优先淘汰。

你需要实现以下功能：

1. LFUCache(int capacity): 用以初始化一个大小为 capacity 的缓存。
2. int get(int key): 如果键 key 存在于缓存中，则返回其值，同时增加该键的使用频率；如果不存在，则返回 -1。
3. void put(int key, int value): 如果键 key 已存在，则更新其值；如果不存在，则插入该键值对。当缓存容量达到上限时，应该淘汰使用频率最低的数据。

示例

LFUCache cache = new LFUCache( 2 / capacity / );

cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 去除 key 2 cache.get(2); // 返回 -1 (未找到key 2) cache.get(3); // 返回 3 cache.put(4, 4); // 去除 key 1 cache.get(1); // 返回 -1 (未找到 key 1) cache.get(3); // 返回 3 cache.get(4); // 返回 4

解题思路

为了实现 LFU 缓存，我们需要以下几个数据结构：

1. 哈希表 keyToVal：用于存储键到值的映射。
2. 哈希表 keyToFreq：用于存储键到其访问频率的映射。
3. 哈希表 freqToKeys：用于存储频率到具有该频率的所有键的集合的映射。
4. 变量 minFreq：用于记录当前最小的访问频率。

详细实现

初始化

class LFUCache: def init(self, capacity: int): self.capacity = capacity self.keyToVal = {} self.keyToFreq = {} self.freqToKeys = collections.defaultdict(set) self.minFreq = 0

获取值

def get(self, key: int) -> int: if key not in self.keyToVal: return -1

    # 增加该键的使用频率
    old_freq = self.keyToFreq[key]
    self.keyToFreq[key] += 1
    new_freq = self.keyToFreq[key]

    # 更新 freqToKeys
    self.freqToKeys[old_freq].remove(key)
    self.freqToKeys[new_freq].add(key)

    # 如果 old_freq 是最小频率且其对应的集合为空，更新 minFreq
    if not self.freqToKeys[old_freq] and old_freq == self.minFreq:
        self.minFreq += 1

    return self.keyToVal[key]

插入值

def put(self, key: int, value: int) -> None: if self.capacity <= 0: return

    if key in self.keyToVal:
        # 更新值并增加频率
        self.keyToVal[key] = value
        self.get(key)  # 利用 get 方法增加频率
        return

    # 如果缓存已满，需要淘汰一个频率最低的键
    if len(self.keyToVal) >= self.capacity:
        evict_key = next(iter(self.freqToKeys[self.minFreq]))
        self.freqToKeys[self.minFreq].remove(evict_key)
        del self.keyToVal[evict_key]
        del self.keyToFreq[evict_key]

    # 插入新键值对
    self.keyToVal[key] = value
    self.keyToFreq[key] = 1
    self.freqToKeys[1].add(key)
    self.minFreq = 1

总结

LFU 缓存的实现相对复杂，需要维护多个映射关系以确保高效的查找和更新操作。通过使用哈希表和集合，我们能够在 O(1) 的时间复杂度内完成 get 和 put 操作。关键在于合理管理频率信息，并在必要时淘汰最不经常使用的元素。

希望这个详细的解析和代码实现能帮助你理解和解决 LeetCode 上的第 460 题。如果有任何进一步的问题，欢迎继续提问！