当前位置：首页 > news >正文

【LeetCode】3. 哈希表：字母异位词分组；有效的数独

news 来源：原创 2025/5/7 7:04:45

题目

字母异位词分组

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
示例 2:

输入: strs = [“”]
输出: [[“”]]
示例 3:

输入: strs = [“a”]
输出: [[“a”]]

提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

初次尝试

class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:# step1: create hash maphashMap = []results = {}for i, v in enumerate(strs):# save str valuetempHashMap = dict()# search hashMapfor value in v:tempHashMap[value] = 1add = Truefor map in hashMap:if tempHashMap == map:add = Falseif add == True:hashMap.append(tempHashMap)for index, _ in enumerate(hashMap):if tempHashMap == _:if results.get(index) is None:results[index] = []results[index].append(v)final_results = []for k, v in results.items():final_results.append(v)return final_results

错误

解答错误
106 / 126 个通过的测试用例官方题解
输入
strs =
["ddddddddddg","dgggggggggg"]添加到测试用例
标准输出
[{'d': 1, 'g': 1}]
输出
[["ddddddddddg","dgggggggggg"]]
预期结果
[["dgggggggggg"],["ddddddddddg"]]

分析

对于重复的字符串解析错误，在hashmap里面实则做了去重。
接下来的方向，要考虑重复情况。

            # search hashMapfor value in v:if value not in tempHashMap:tempHashMap[value] = 1else:tempHashMap[value] += 1

完整代码

class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:# step1: create hash maphashMap = []results = {}for i, v in enumerate(strs):# save str valuetempHashMap = dict()# search hashMapfor value in v:if value not in tempHashMap:tempHashMap[value] = 1else:tempHashMap[value] += 1add = Truefor map in hashMap:if tempHashMap == map:add = Falseif add == True:hashMap.append(tempHashMap)for index, _ in enumerate(hashMap):if tempHashMap == _:if results.get(index) is None:results[index] = []results[index].append(v)final_results = []for k, v in results.items():final_results.append(v)return final_results

耗时高，太久没刷了先一步一步来，后面简单题不回顾。

题目：有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 ‘.’ 表示。

示例 1：

输入：board =
[[“5”,“3”,“.”,“.”,“7”,“.”,“.”,“.”,“.”]
,[“6”,“.”,“.”,“1”,“9”,“5”,“.”,“.”,“.”]
,[“.”,“9”,“8”,“.”,“.”,“.”,“.”,“6”,“.”]
,[“8”,“.”,“.”,“.”,“6”,“.”,“.”,“.”,“3”]
,[“4”,“.”,“.”,“8”,“.”,“3”,“.”,“.”,“1”]
,[“7”,“.”,“.”,“.”,“2”,“.”,“.”,“.”,“6”]
,[“.”,“6”,“.”,“.”,“.”,“.”,“2”,“8”,“.”]
,[“.”,“.”,“.”,“4”,“1”,“9”,“.”,“.”,“5”]
,[“.”,“.”,“.”,“.”,“8”,“.”,“.”,“7”,“9”]]
输出：true
示例 2：

输入：board =
[[“8”,“3”,“.”,“.”,“7”,“.”,“.”,“.”,“.”]
,[“6”,“.”,“.”,“1”,“9”,“5”,“.”,“.”,“.”]
,[“.”,“9”,“8”,“.”,“.”,“.”,“.”,“6”,“.”]
,[“8”,“.”,“.”,“.”,“6”,“.”,“.”,“.”,“3”]
,[“4”,“.”,“.”,“8”,“.”,“3”,“.”,“.”,“1”]
,[“7”,“.”,“.”,“.”,“2”,“.”,“.”,“.”,“6”]
,[“.”,“6”,“.”,“.”,“.”,“.”,“2”,“8”,“.”]
,[“.”,“.”,“.”,“4”,“1”,“9”,“.”,“.”,“5”]
,[“.”,“.”,“.”,“.”,“8”,“.”,“.”,“7”,“9”]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与示例1 相同。但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 ‘.’

解答

class Solution:def isValidSudoku(self, board: List[List[str]]) -> bool:# horizontalhorHashMap = [{} for _ in range(9)] recHashMap = [{} for _ in range(9)] for Index, vertical in enumerate(board):# verticalhashmap = dict()for i, value in enumerate(vertical):if value == '.':continueif value in hashmap:return Falseelse:hashmap[value] =1# horizontalif value in horHashMap[i]:return Falseelse:horHashMap[i][value] =1# 检查3x3小宫格是否重复recIndex = (Index // 3) * 3 + (i // 3)if value in recHashMap[recIndex]:return FalserecHashMap[recIndex][value] = 1return True

题目

字母异位词分组

初次尝试

错误

分析

题目：有效的数独

解答

相关文章：