第 86 场周赛：矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方

1、题目描述

3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。

给定一个由整数组成的row x col 的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？

注意：虽然幻方只能包含 1 到 9 的数字，但 grid 可以包含最多15的数字。

示例 1：

img

输入: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]
输出: 1
解释: 
下面的子矩阵是一个 3 x 3 的幻方：而这一个不是：总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。

示例 2:

输入: grid = [[8]]
输出: 0

提示:

  • row == grid.length
  • col == grid[i].length
  • 1 <= row, col <= 10
  • 0 <= grid[i][j] <= 15
2、解题思路

  1. 问题分析：

    • 需要遍历 grid 中所有可能的 3 × 3 子矩阵。
    • 对于每个子矩阵，检查它是否满足幻方的条件。

  2. 幻方的条件：

    • 包含 1 到 9 的不同数字。
    • 每行、每列以及两条对角线的和都等于 15。

  3. 优化：

    • 幻方的中心必须是 5，因此可以提前过滤掉中心不是 5 的子矩阵。

  4. 算法设计：

    • 遍历 grid 中所有可能的 3 × 3 子矩阵。
    • 对于每个子矩阵，检查是否满足幻方的条件。
    • 统计满足条件的子矩阵数量。
3、代码实现
C++
class Solution {
public:// 检查一个 3x3 矩阵是否是幻方bool ismagic(array<int, 9> m) {int count[16] = {0}; // 用于统计数字出现的次数for (auto n : m) {// 检查数字是否在 1 到 9 之间且不重复if (n < 1 || n > 9 || ++count[n] > 1) {return false;}}// 检查每行、每列以及两条对角线的和是否等于 15return m[0] + m[1] + m[2] == 15 && m[3] + m[4] + m[5] == 15 &&m[6] + m[7] + m[8] == 15 && m[0] + m[3] + m[6] == 15 &&m[1] + m[4] + m[7] == 15 && m[2] + m[5] + m[8] == 15 &&m[0] + m[4] + m[8] == 15 && m[2] + m[4] + m[6] == 15;}int numMagicSquaresInside(vector<vector<int>>& grid) {if (grid.size() < 3 || grid[0].size() < 3) {return 0; // 如果 grid 的大小小于 3x3，直接返回 0}int m = grid.size(), n = grid[0].size();int res = 0;                           // 记录幻方的数量for (int i = 0; i < m - 2; i++) {      // 遍历所有可能的起始行for (int j = 0; j < n - 2; j++) {  // 遍历所有可能的起始列if (grid[i + 1][j + 1] != 5) { // 如果中心不是 5，跳过continue;}array<int, 9> v; // 用于存储 3x3 子矩阵的元素int w = 0;for (int r = i; r < i + 3; r++) { // 提取 3x3 子矩阵for (int c = j; c < j + 3; c++) {v[w++] = grid[r][c];}}res += ismagic(v); // 检查是否是幻方}}return res; // 返回幻方的数量}
};
Java
class Solution {// 检查一个 3x3 矩阵是否是幻方private boolean ismagic(int[] m) {int[] count = new int[16]; // 用于统计数字出现的次数for (int n : m) {if (n < 1 || n > 9 || ++count[n] > 1) { // 检查数字是否在 1 到 9 之间且不重复return false;}}// 检查每行、每列以及两条对角线的和是否等于 15return  m[0] + m[1] + m[2] == 15 && m[3] + m[4] + m[5] == 15 &&m[6] + m[7] + m[8] == 15 && m[0] + m[3] + m[6] == 15 &&m[1] + m[4] + m[7] == 15 && m[2] + m[5] + m[8] == 15 &&m[0] + m[4] + m[8] == 15 && m[2] + m[4] + m[6] == 15;}public int numMagicSquaresInside(int[][] grid) {if (grid.length < 3 || grid[0].length < 3) {return 0; // 如果 grid 的大小小于 3x3，直接返回 0}int m = grid.length, n = grid[0].length;int res = 0; // 记录幻方的数量for (int i = 0; i < m - 2; i++) { // 遍历所有可能的起始行for (int j = 0; j < n - 2; j++) { // 遍历所有可能的起始列if (grid[i + 1][j + 1] != 5) { // 如果中心不是 5，跳过continue;}int[] v = new int[9]; // 用于存储 3x3 子矩阵的元素int w = 0;for (int r = i; r < i + 3; r++) { // 提取 3x3 子矩阵for (int c = j; c < j + 3; c++) {v[w++] = grid[r][c];}}res += ismagic(v) ? 1 : 0; // 检查是否是幻方}}return res; // 返回幻方的数量}
}
Python
class Solution:def ismagic(self, m):count = [0] * 16  # 用于统计数字出现的次数for n in m:if n < 1 or n > 9 or count[n] > 0:  # 检查数字是否在 1 到 9 之间且不重复return Falsecount[n] += 1# 检查每行、每列以及两条对角线的和是否等于 15return (m[0] + m[1] + m[2] == 15and m[3] + m[4] + m[5] == 15and m[6] + m[7] + m[8] == 15and m[0] + m[3] + m[6] == 15and m[1] + m[4] + m[7] == 15and m[2] + m[5] + m[8] == 15and m[0] + m[4] + m[8] == 15and m[2] + m[4] + m[6] == 15)def numMagicSquaresInside(self, grid):if len(grid) < 3 or len(grid[0]) < 3:return 0  # 如果 grid 的大小小于 3x3，直接返回 0m, n = len(grid), len(grid[0])res = 0  # 记录幻方的数量for i in range(m - 2):  # 遍历所有可能的起始行for j in range(n - 2):  # 遍历所有可能的起始列if grid[i + 1][j + 1] != 5:  # 如果中心不是 5，跳过continuev = [grid[r][c] for r in range(i, i + 3) for c in range(j, j + 3)]  # 提取 3x3 子矩阵res += 1 if self.ismagic(v) else 0  # 检查是否是幻方return res  # 返回幻方的数量

在这里插入图片描述

4、复杂度分析

  1. 时间复杂度：

    • 遍历所有可能的 3 × 3 子矩阵：O((m−2)×(n−2))。
    • 检查每个子矩阵是否是幻方：O(1)。
    • 总时间复杂度：O((m−2)×(n−2))。

  2. 空间复杂度：

    • 使用常数级别的额外空间，空间复杂度为 O(1)。

Q2、[中等] 钥匙和房间

1、题目描述

有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。

当你进入一个房间，你可能会在里面找到一套 不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。

给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。

示例 1：

输入：rooms = [[1],[2],[3],[]]
输出：true
解释：
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。

示例 2：

输入：rooms = [[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。

提示：

  • n == rooms.length
  • 2 <= n <= 1000
  • 0 <= rooms[i].length <= 1000
  • 1 <= sum(rooms[i].length) <= 3000
  • 0 <= rooms[i][j] < n
  • 所有 rooms[i] 的值 互不相同
2、解题思路

  1. 问题分析：

    • 房间和钥匙的关系可以看作是一个图，其中房间是节点，钥匙是边。
    • 从 0 号房间开始，通过钥匙逐步解锁其他房间。
    • 需要判断是否可以从 0 号房间访问到所有其他房间。

  2. 算法设计：

    • 使用广度优先搜索（BFS）或深度优先搜索（DFS）遍历图。
    • 从 0 号房间开始，将所有可以访问的房间加入集合。
    • 最终检查集合的大小是否等于 n。

  3. 优化：

    • 使用 BFS 或 DFS 确保所有可达房间都被访问。
3、代码实现
C++
class Solution {
public:bool canVisitAllRooms(vector<vector<int>>& rooms) {int n = rooms.size();       // 房间的数量unordered_set<int> visited; // 记录已访问的房间queue<int> q;               // BFS 队列q.push(0);                  // 从 0 号房间开始visited.insert(0);          // 标记 0 号房间为已访问while (!q.empty()) {       // BFS 过程int index = q.front(); // 取出当前房间q.pop();for (const auto& key : rooms[index]) { // 遍历当前房间的钥匙if (!visited.count(key)) {         // 如果钥匙对应的房间未被访问q.push(key);                   // 加入队列visited.insert(key);           // 标记为已访问}}}return visited.size() == n; // 判断是否访问了所有房间}
};

class Solution {
private:vector<int> visited;int num;void dfs(vector<vector<int>>& rooms, int x) {visited[x] = true;num++;for (const auto& it : rooms[x]) {if (!visited[it]) {dfs(rooms, it);}}}public:bool canVisitAllRooms(vector<vector<int>>& rooms) {int n = rooms.size();num = 0;visited.resize(n);dfs(rooms, 0);return num == n;}
};
Java
class Solution {public boolean canVisitAllRooms(List<List<Integer>> rooms) {int n = rooms.size(); // 房间的数量Set<Integer> visited = new HashSet<>(); // 记录已访问的房间Queue<Integer> q = new LinkedList<>(); // BFS 队列q.offer(0); // 从 0 号房间开始visited.add(0); // 标记 0 号房间为已访问while (!q.isEmpty()) { // BFS 过程int index = q.poll(); // 取出当前房间for (int key : rooms.get(index)) { // 遍历当前房间的钥匙if (!visited.contains(key)) { // 如果钥匙对应的房间未被访问q.offer(key); // 加入队列visited.add(key); // 标记为已访问}}}return visited.size() == n; // 判断是否访问了所有房间}
}
Python
class Solution:def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:n = len(rooms)  # 房间的数量visited = set()  # 记录已访问的房间q = deque()  # BFS 队列q.append(0)  # 从 0 号房间开始visited.add(0)  # 标记 0 号房间为已访问while q:  # BFS 过程index = q.popleft()  # 取出当前房间for key in rooms[index]:  # 遍历当前房间的钥匙if key not in visited:  # 如果钥匙对应的房间未被访问q.append(key)  # 加入队列visited.add(key)  # 标记为已访问return len(visited) == n  # 判断是否访问了所有房间

在这里插入图片描述

4、复杂度分析
  1. 时间复杂度：
    • 每个房间和钥匙最多被访问一次，时间复杂度为 O*(*n+k)，其中 n 是房间的数量，k 是钥匙的总数。
  2. 空间复杂度：
    • 使用 visited 集合和队列 q，空间复杂度为 O(n)。

Q3、[中等] 将数组拆分成斐波那契序列

1、题目描述

给定一个数字字符串 num，比如 "123456579"，我们可以将它分成「斐波那契式」的序列 [123, 456, 579]。

形式上，斐波那契式 序列是一个非负整数列表 f，且满足：

  • 0 <= f[i] < 231 ，（也就是说，每个整数都符合 32 位 有符号整数类型）
  • f.length >= 3
  • 对于所有的0 <= i < f.length - 2，都有 f[i] + f[i + 1] = f[i + 2]

另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。

返回从 num 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。

示例 1：

输入：num = "1101111"
输出：[11,0,11,11]
解释：输出 [110,1,111] 也可以。

示例 2：

输入: num = "112358130"
输出: []
解释: 无法拆分。

示例 3：

输入："0123"
输出：[]
解释：每个块的数字不能以零开头，因此 "01"，"2"，"3" 不是有效答案。

提示：

  • 1 <= num.length <= 200
  • num 中只含有数字
2、解题思路

  1. 问题分析：

    • 需要将字符串 num 拆分成一个斐波那契式序列。
    • 序列中的每个整数必须满足 0 <= f[i] < 2^31。
    • 序列的长度至少为 3，且满足斐波那契性质。
    • 拆分时，不能有前导零（除非是 0 本身）。

  2. 算法设计：

    • 使用回溯法枚举所有可能的拆分方式。
    • 对于每个可能的拆分，检查是否满足斐波那契性质。
    • 如果找到满足条件的序列，则返回结果。

  3. 优化：

    • 在回溯过程中，如果当前数字超过 2^31 - 1，则直接剪枝。

    • 如果当前数字不满足斐波那契性质，则剪枝。

3、代码实现
C++
class Solution {
public:vector<int> splitIntoFibonacci(string num) {vector<int> list;                            // 用于存储斐波那契序列backtrack(list, num, num.length(), 0, 0, 0); // 调用回调函数return list;                                 // 返回结果}bool backtrack(vector<int>& list, string num, int length, int index, long long sum, int prev) {if (index == length) {return list.size() >= 3; // 如果遍历完字符串序列且序列长度 >= 3, 返回 true}long long curr = 0; // 当前数字for (int i = index; i < length; ++i) {if (i > index && num[index] == '0') {break; // 如果有前导零, 直接剪枝}curr = curr * 10 + (num[i] - '0'); // 计算当前数字if (curr > INT_MAX) {break; // 如果当前数字超过 2^31 - 1, 剪枝}if (list.size() >= 2) {if (curr < sum) {continue; // 如果当前数字小于 sum, 继续增加数字} else if (curr > sum) {break; // 如果当前数字大于 sum，剪枝}}list.push_back(curr); // 将当前数字加入序列if (backtrack(list, num, length, i + 1, prev + curr, curr)) {return true;}list.pop_back(); // 回溯, 移除当前数字}return false; // 如果没有找到满足条件的序列, 返回 false}
};
Java
class Solution {public List<Integer> splitIntoFibonacci(String num) {List<Integer> list = new ArrayList<>(); // 用于存储斐波那契序列backtrack(list, num, num.length(), 0, 0, 0); // 调用回溯函数return list; // 返回结果}private boolean backtrack(List<Integer> list, String num, int length, int index, long sum, long prev) {if (index == length) {return list.size() >= 3; // 如果遍历完字符串且序列长度 >= 3，返回 true}long curr = 0; // 当前数字for (int i = index; i < length; i++) {if (i > index && num.charAt(index) == '0') {break; // 如果有前导零，直接剪枝}curr = curr * 10 + (num.charAt(i) - '0'); // 计算当前数字if (curr > Integer.MAX_VALUE) {break; // 如果当前数字超过 2^31 - 1，剪枝}if (list.size() >= 2) {if (curr < sum) {continue; // 如果当前数字小于 sum，继续增加数字} else if (curr > sum) {break; // 如果当前数字大于 sum，剪枝}}list.add((int) curr); // 将当前数字加入序列if (backtrack(list, num, length, i + 1, prev + curr, curr)) {return true; // 如果找到满足条件的序列，返回 true}list.remove(list.size() - 1); // 回溯，移除当前数字}return false; // 如果没有找到满足条件的序列，返回 false}
}
Python
class Solution:def splitIntoFibonacci(self, num: str) -> List[int]:def backtrack(index, sum_val, prev, path):if index == len(num):return len(path) >= 3  # 如果遍历完字符串且序列长度 >= 3，返回 Truecurr = 0  # 当前数字for i in range(index, len(num)):if i > index and num[index] == "0":break  # 如果有前导零，直接剪枝curr = curr * 10 + int(num[i])  # 计算当前数字if curr > 2**31 - 1:break  # 如果当前数字超过 2^31 - 1，剪枝if len(path) >= 2:if curr < sum_val:continue  # 如果当前数字小于 sum，继续增加数字elif curr > sum_val:break  # 如果当前数字大于 sum，剪枝path.append(curr)  # 将当前数字加入序列if backtrack(i + 1, prev + curr, curr, path):return True  # 如果找到满足条件的序列，返回 Truepath.pop()  # 回溯，移除当前数字return False  # 如果没有找到满足条件的序列，返回 Falseresult = []backtrack(0, 0, 0, result)return result

在这里插入图片描述

4、复杂度分析

  1. 时间复杂度：

    • 最坏情况下，回溯的时间复杂度为 O(2n)，其中 n 是字符串的长度。
    • 由于剪枝的存在，实际运行时间会大大减少。

  2. 空间复杂度：

    • 使用递归栈和结果列表，空间复杂度为 O(n)。

Q4、[困难] 猜猜这个单词

1、题目描述

给你一个由 不同 字符串组成的单词列表 words ，其中 words[i] 长度均为 6 。words 中的一个单词将被选作秘密单词 secret 。

另给你一个辅助对象 Master ，你可以调用 Master.guess(word) 来猜单词，其中参数 word 长度为 6 且必须是 words 中的字符串。

Master.guess(word) 将会返回如下结果：

  • 如果 word 不是 words 中的字符串，返回 -1 ，或者
  • 一个整数，表示你所猜测的单词 word 与 秘密单词 secret 的准确匹配（值和位置同时匹配）的数目。

每组测试用例都会包含一个参数 allowedGuesses ，其中 allowedGuesses 是你可以调用 Master.guess(word) 的最大次数。

对于每组测试用例，在不超过允许猜测的次数的前提下，你应该调用 Master.guess 来猜出秘密单词。最终，你将会得到以下结果：

  • 如果你调用 Master.guess 的次数大于 allowedGuesses 所限定的次数或者你没有用 Master.guess 猜到秘密单词，则得到 "Either you took too many guesses, or you did not find the secret word." 。
  • 如果你调用 Master.guess 猜到秘密单词，且调用 Master.guess 的次数小于或等于 allowedGuesses ，则得到 "You guessed the secret word correctly." 。

生成的测试用例保证你可以利用某种合理的策略（而不是暴力）猜到秘密单词。

示例 1：

输入：secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"], allowedGuesses = 10
输出：You guessed the secret word correctly.
解释：
master.guess("aaaaaa") 返回 -1 ，因为 "aaaaaa" 不在 words 中。
master.guess("acckzz") 返回 6 ，因为 "acckzz" 是秘密单词 secret ，共有 6 个字母匹配。
master.guess("ccbazz") 返回 3 ，因为 "ccbazz" 共有 3 个字母匹配。
master.guess("eiowzz") 返回 2 ，因为 "eiowzz" 共有 2 个字母匹配。
master.guess("abcczz") 返回 4 ，因为 "abcczz" 共有 4 个字母匹配。
一共调用 5 次 master.guess ，其中一个为秘密单词，所以通过测试用例。

示例 2：

输入：secret = "hamada", words = ["hamada","khaled"], allowedGuesses = 10
输出：You guessed the secret word correctly.
解释：共有 2 个单词，且其中一个为秘密单词，可以通过测试用例。

提示：

  • 1 <= words.length <= 100
  • words[i].length == 6
  • words[i] 仅由小写英文字母组成
  • words 中所有字符串 互不相同
  • secret 存在于 words 中
  • 10 <= allowedGuesses <= 30
2、解题思路
  1. 问题分析：
    • 需要从 words 中猜出秘密单词 secret。
    • 每次调用 Master.guess(word) 会返回 word 与 secret 的匹配数目。
    • 需要在允许的猜测次数内找到 secret。
  2. 算法设计：
    • 使用启发式方法，每次选择一个单词进行猜测，并根据返回的匹配数目缩小可能的候选单词范围。
    • 通过计算单词之间的匹配数目，选择能够最大程度减少候选单词数量的单词进行猜测。
  3. 优化：
    • 使用预计算的匹配矩阵 H，其中 H[i][j] 表示 words[i] 和 words[j] 的匹配数目。
    • 在每次猜测后，根据匹配数目过滤候选单词。
3、代码实现
C++
class Solution {
private:vector<vector<int>> H; // 匹配矩阵, H[i][j] 表示 words[i] 和 words[j] 的匹配数目// 选择下一个猜测的单词int solve(vector<int>& possible, vector<int>& path) {if (possible.size() <= 2) {return possible[0]; // 如果候选单词数量 <= 2，直接返回第一个}vector<int> ansgrp = possible;int ansguess = -1;// 遍历所有可能的猜测单词for (int guess = 0; guess < H.size(); ++guess) {if (find(path.begin(), path.end(), guess) ==path.end()) {                  // 如果 guess 未被猜测过vector<vector<int>> groups(7); // 根据匹配数目分组for (int j : possible) {if (j != guess) {groups[H[guess][j]].push_back(j);}}// 找到最大的组vector<int> maxgroup = groups[0];for (int i = 0; i < 7; ++i) {if (groups[i].size() > maxgroup.size()) {maxgroup = groups[i];}}// 选择能够最小化最大组的猜测单词if (maxgroup.size() < ansgrp.size()) {ansgrp = maxgroup;ansguess = guess;}}}return ansguess;}public:void findSecretWord(vector<string>& words, Master& master) {int N = words.size();H = vector<vector<int>>(N, vector<int>(N, 0)); // 初始化匹配矩阵for (int i = 0; i < N; ++i) {for (int j = i; j < N; ++j) {int match = 0;for (int k = 0; k < 6; ++k) {if (words[i][k] == words[j][k]) {match++;}}H[i][j] = H[j][i] = match; // 计算匹配数目}}vector<int> possible; // 候选单词列表vector<int> path;     // 已猜测的单词列表for (int i = 0; i < N; ++i) {possible.push_back(i);}while (!possible.empty()) {int guess = solve(possible, path);        // 选择下一个猜测单词int matches = master.guess(words[guess]); // 调用 Master.guessif (matches == words[0].length()) {return; // 如果猜中，直接返回}vector<int> possible2; // 新的候选单词列表for (int j : possible) {if (H[guess][j] == matches) {possible2.push_back(j); // 根据匹配数目过滤候选单词}}possible = possible2;path.push_back(guess); // 将猜测单词加入已猜测列表}}
};
Java
class Solution {private int[][] H; // 匹配矩阵，H[i][j] 表示 words[i] 和 words[j] 的匹配数目// 选择下一个猜测的单词private int solve(List<Integer> possible, List<Integer> path) {if (possible.size() <= 2) {return possible.get(0); // 如果候选单词数量 <= 2，直接返回第一个}List<Integer> ansgrp = possible;int ansguess = -1;// 遍历所有可能的猜测单词for (int guess = 0; guess < H.length; guess++) {if (!path.contains(guess)) { // 如果 guess 未被猜测过List<List<Integer>> groups = new ArrayList<>(7);for (int i = 0; i < 7; i++) {groups.add(new ArrayList<>());}for (int j : possible) {if (j != guess) {groups.get(H[guess][j]).add(j); // 根据匹配数目分组}}// 找到最大的组List<Integer> maxgroup = groups.get(0);for (int i = 0; i < 7; i++) {if (groups.get(i).size() > maxgroup.size()) {maxgroup = groups.get(i);}}// 选择能够最小化最大组的猜测单词if (maxgroup.size() < ansgrp.size()) {ansgrp = maxgroup;ansguess = guess;}}}return ansguess;}public void findSecretWord(String[] words, Master master) {int N = words.length;H = new int[N][N]; // 初始化匹配矩阵for (int i = 0; i < N; i++) {for (int j = i; j < N; j++) {int match = 0;for (int k = 0; k < 6; k++) {if (words[i].charAt(k) == words[j].charAt(k)) {match++;}}H[i][j] = H[j][i] = match; // 计算匹配数目}}List<Integer> possible = new ArrayList<>(); // 候选单词列表List<Integer> path = new ArrayList<>(); // 已猜测的单词列表for (int i = 0; i < N; i++) {possible.add(i);}while (!possible.isEmpty()) {int guess = solve(possible, path); // 选择下一个猜测单词int matches = master.guess(words[guess]); // 调用 Master.guessif (matches == words[0].length()) {return; // 如果猜中，直接返回}List<Integer> possible2 = new ArrayList<>(); // 新的候选单词列表for (int j : possible) {if (H[guess][j] == matches) {possible2.add(j); // 根据匹配数目过滤候选单词}}possible = possible2;path.add(guess); // 将猜测单词加入已猜测列表}}
}
Python
class Solution:def __init__(self):self.H = []  # 匹配矩阵，H[i][j] 表示 words[i] 和 words[j] 的匹配数目# 选择下一个猜测的单词def solve(self, possible: List[int], path: List[int]) -> int:if len(possible) <= 2:return possible[0]  # 如果候选单词数量 <= 2，直接返回第一个ansgrp = possibleansguess = -1# 遍历所有可能的猜测单词for guess in range(len(self.H)):if guess not in path:  # 如果 guess 未被猜测过groups = [[] for _ in range(7)]  # 根据匹配数目分组for j in possible:if j != guess:groups[self.H[guess][j]].append(j)# 找到最大的组maxgroup = groups[0]for i in range(7):if len(groups[i]) > len(maxgroup):maxgroup = groups[i]# 选择能够最小化最大组的猜测单词if len(maxgroup) < len(ansgrp):ansgrp = maxgroupansguess = guessreturn ansguessdef findSecretWord(self, words: List[str], master: "Master") -> None:N = len(words)self.H = [[0] * N for _ in range(N)]  # 初始化匹配矩阵for i in range(N):for j in range(i, N):match = 0for k in range(6):if words[i][k] == words[j][k]:match += 1self.H[i][j] = self.H[j][i] = match  # 计算匹配数目possible = list(range(N))  # 候选单词列表path = []  # 已猜测的单词列表while possible:guess = self.solve(possible, path)  # 选择下一个猜测单词matches = master.guess(words[guess])  # 调用 Master.guessif matches == len(words[0]):return  # 如果猜中，直接返回possible = [j for j in possible if self.H[guess][j] == matches]  # 根据匹配数目过滤候选单词path.append(guess)  # 将猜测单词加入已猜测列表

在这里插入图片描述

4、复杂度分析
  1. 时间复杂度：
    • 时间复杂度：O(N2logN)，其中 N 是单词的总数
  2. 空间复杂度：
    • 空间复杂度：O(N2)


本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.pswp.cn/web/82523.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【AI News | 20250604】每日AI进展

【AI News | 20250604】每日AI进展

AI Repos 1、jaaz Jaaz是一款免费开源的AI设计代理&#xff0c;作为Lovart的本地替代品&#xff0c;它能实现图像、海报、故事板的设计、编辑和生成。Jaaz集成了LLM&#xff0c;可智能生成提示并批量生成图像&#xff0c;支持Ollama、Stable Diffusion等本地及API模型。用户可…
阅读更多...
Docker load 后镜像名称为空问题的解决方案

Docker load 后镜像名称为空问题的解决方案

在使用 docker load命令从存档文件中加载Docker镜像时&#xff0c;有时会遇到镜像名称为空的情况。这种情况通常是由于在保存镜像时未正确标记镜像名称和标签&#xff0c;或者在加载镜像时出现了意外情况。本文将介绍如何诊断和解决这一问题。 一、问题描述 当使用 docker lo…
阅读更多...
SQL进阶之旅 Day 14：数据透视与行列转换技巧

SQL进阶之旅 Day 14：数据透视与行列转换技巧

【SQL进阶之旅 Day 14】数据透视与行列转换技巧 开篇 欢迎来到“SQL进阶之旅”系列的第14天&#xff01;今天我们将探讨数据透视与行列转换技巧&#xff0c;这是数据分析和报表生成中的核心技能。无论你是数据库开发工程师、数据分析师还是后端开发人员&#xff0c;行转列或列…
阅读更多...
haribote原型系统改进方向

haribote原型系统改进方向

在时钟中断、计时器和键盘输入方面&#xff0c;一些创新性的改进方向&#xff1a; 时钟中断 (PIT / inthandler20) 动态节拍 (Tickless Kernel)&#xff1a;当前的 PIT 中断以固定频率&#xff08;约 100Hz&#xff09;触发&#xff0c;即使系统空闲或没有即将到期的计时器&…
阅读更多...
LabVIEW基于 DataSocket从 OPC 服务器读取数据

LabVIEW基于 DataSocket从 OPC 服务器读取数据

LabVIEW 中基于 DataSocket 函数从 OPC 服务器读取数据的功能&#xff0c;为工业自动化等场景下的数据交互提供了解决方案。通过特定函数实现 URL 指定、连接建立与管理、数据读取&#xff0c;相比传统 Socket 通信和 RESTful API &#xff0c;在 OPC 服务器数据交互场景有适配…
阅读更多...
SimpleDateFormat 和 DateTimeFormatter 的异同

SimpleDateFormat 和 DateTimeFormatter 的异同

在Java开发中Date类型转String类型是比较常见的&#xff0c;其中最常用的是以下几种方式&#xff1a; 1. 使用SimpleDateFormat&#xff08;Java 8之前&#xff09; import java.text.SimpleDateFormat; import java.util.Date;public class DateToStringExample {public sta…
阅读更多...
《前端面试题：CSS对浏览器兼容性》

《前端面试题：CSS对浏览器兼容性》

CSS浏览器兼容性完全指南&#xff1a;从原理到实战 跨浏览器兼容性是前端开发的核心挑战&#xff0c;也是面试中的高频考点。查看所有css属性对各个浏览器兼容网站&#xff1a;https://caniuse.com 一、浏览器兼容性为何如此重要&#xff1f; 在当今多浏览器生态中&#xff0c…
阅读更多...
【stm32开发板】单片机最小系统原理图设计

【stm32开发板】单片机最小系统原理图设计

一、批量添加网络标签 可以选择浮动工具中的N&#xff0c;单独为引脚添加网络标签。 当芯片引脚非常多的时候&#xff0c;选中芯片&#xff0c;右键选择扇出网络标签/非连接标识 按住ctrl键即可选中多个引脚 点击将引脚名称填入网络名 就完成了引脚标签的批量添加 二、电源引…
阅读更多...
golang连接sm3认证加密（app）

golang连接sm3认证加密（app）

文章目录 环境文档用途详细信息 环境 系统平台&#xff1a;Linux x86-64 Red Hat Enterprise Linux 7 版本&#xff1a;4.5 文档用途 golang连接安全版sm3认证加密数据库,驱动程序详见附件。 详细信息 1.下载Linux golang安装包 go1.17.3.linux-amd64.tar.gz 1.1. 解压安…
阅读更多...
node实例应用

node实例应用

打开vscode,创建node项目,直接进入一个干净的文件夹&#xff0c;打开控制台 一 项目初始化 1. 初始化包管理 npm init -y2. 安装express npm install express4.17.1 3. 根目录下创建app.js,引入express // 引入expree const express require(express)// 创建实例 const …
阅读更多...
Springboot——整合websocket并根据type区别处理

Springboot——整合websocket并根据type区别处理

文章目录 前言架构思想项目结构代码实现依赖引入自定义注解定义具体的处理类定义 TypeAWebSocketHandler定义 TypeBWebSocketHandler 定义路由处理类配置类&#xff0c;绑定point制定前端页面编写测试接口方便跳转进入前端页面 测试验证结语 前言 之前写过一篇类似的博客&…
阅读更多...
vscode命令行debug

vscode命令行debug

vscode命令行debug 一般命令行debug会在远程连服务器的时候用上&#xff0c;命令行debug的本质是在执行时暴露一个监听端口&#xff0c;通过进入这个端口&#xff0c;像本地调试一样进行。 这里提供两种方式&#xff1a; 直接在命令行中添加debugpy&#xff0c;适用于python…
阅读更多...
Hot100 Day02（移动0，乘最多水的容器、三数之和、接雨水）

Hot100 Day02（移动0，乘最多水的容器、三数之和、接雨水）

移动零 题目链接 题目描述&#xff1a; 思路&#xff1a;上述蓝色箭头代表当前遍历的元素&#xff0c;红色数字则是当前空位0的位置&#xff0c;每一次遇到非0元素&#xff0c;就是讲该元素的位置和空位0的位置进行交换&#xff0c;同时空位0的下标1. 代码 class Solution …
阅读更多...
(eNSP）配置WDS手拉手业务

(eNSP）配置WDS手拉手业务

1.实验拓扑 2.基础配置 [SW1]dis cu # sysname SW1 # vlan batch 10 100 110 120 # dhcp enable # interface Vlanif10ip address 192.168.10.2 255.255.255.0 # interface Vlanif100ip address 192.168.100.2 255.255.255.0dhcp select interfacedhcp server excluded-ip-add…
阅读更多...
lua的笔记记录

lua的笔记记录

类似python的eval和exec 可以伪装成其他格式的文件&#xff0c;比如.dll 希望在异常发生时&#xff0c;能够让其沉默&#xff0c;即异常捕获。而在 Lua 中实现异常捕获的话&#xff0c;需要使用函数 pcall&#xff0c;假设要执行一段 Lua 代码并捕获里面出现的所有错误&#xf…
阅读更多...
【DeepSeek】【Dify】：用 Dify 对话流+标题关键词注入，让 RAG 准确率飞跃

【DeepSeek】【Dify】：用 Dify 对话流+标题关键词注入，让 RAG 准确率飞跃

1 构建对话流处理数据 初始准备 文章大纲摘要 数据标注和清洗 代码执行 特别注解 2 对话流测试 准备工作 大纲生成 清洗片段 整合分段 3 构建知识库 构建 召回测试 4 实战应用测试 关键词提取 智能总结 测试 1 构建对话流处理数据 初始准备 构建对话变量 用…
阅读更多...
RabbitMQ 开机启动配置教程

RabbitMQ 开机启动配置教程

RabbitMQ 开机启动配置教程 在本教程中&#xff0c;我们将详细介绍如何配置 RabbitMQ 以实现开机自动启动。此配置适用于手动安装的 RabbitMQ 版本。 环境准备 操作系统&#xff1a;CentOS 7RabbitMQ 版本&#xff1a;3.8.4Erlang 版本&#xff1a;21.3 步骤 1. 安装 Erla…
阅读更多...
第N1周：one-hot编码案例

第N1周：one-hot编码案例

&#x1f368; 本文为&#x1f517;365天深度学习训练营中的学习记录博客 &#x1f356; 原作者&#xff1a;K同学啊 一、one-hot编码概念 自然语言处理&#xff08;NLP&#xff09;中的文本数字化&#xff1a;文字对于计算机来说就仅仅只是一个个符号&#xff0c;计算…
阅读更多...
Linux 云服务器部署 Flask 项目（含后台运行与 systemd 开机自启）

Linux 云服务器部署 Flask 项目（含后台运行与 systemd 开机自启）

一、准备工作 在开始正式部署之前，请确认以下前提条件已经准备好： 你有一台运行 Linux 系统（CentOS 或 Ubuntu）的服务器； 服务器有公网 IP，本例中使用：111.229.204.102； 你拥有该服务器的管理员权限（可以使用 sudo）； 打算使用 Flask 构建一个简单的 Web 接口； 服务…
阅读更多...
散货拼柜业务：多货主财务结算如何高效管理？

散货拼柜业务：多货主财务结算如何高效管理？

散货拼柜业务满足了小批量发货客户的需求&#xff0c;由于无法满足海运整柜的条件&#xff0c;其模式通常涉及多个货主共同分摊同一集装箱的运输项目。这种业务模型虽然在成本上具备优势&#xff0c;但其复杂的财务结算过程往往给公司带来了挑战。 散货拼柜业务的特点在于其小…
阅读更多...
最新文章

Copyright @ 2022~2023