题目
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
解释：
- 在 strs 中没有字符串可以通过重新排列来形成
"bat"。 - 字符串
"nat"和"tan"是字母异位词，因为它们可以重新排列以形成彼此。 - 字符串
"ate"，"eat"和"tea"是字母异位词，因为它们可以重新排列以形成彼此。
题解
本题的关键是怎样寻找异位词并且存储异位词？想到了利用哈希表，python里利用字典实现哈希表，于是问题变成了字典的键怎么设定，题解给了一个很好的答案，用排序后的每个字符串，这样不同的字符串异位词映射的就是同一个算法，思路还是太巧妙了，有在认真的学习哈希表
在实现的过程中，还是遇到了一些意想不到的问题，比如python的排序算法是为列表内置的，那我应该怎样为字符串排序，于是自己实现了一个选择排序（找最小+嵌套有序遍历），这个找最小里需要每次移除最小字符串，但是自己没考虑到重复移除的情况，错了一些题，后面发现replace里有次数移除，python真厉害呀；中间还有一个空字符串无法排序和寻找最小问题，平时写代码要考虑健壮性哇
哈希有数组和map两种实现方式，map参考上一段排序为键，数组利用hash[26]=0为初始值，这个适合范围不大的数组
选择排序+哈希表
class Solution:
# 对于输入列表，遍历，每个都重新排序，作为新的字符串数组的键值对
# 每进入一个新的字符串数组，都排序，然后检查是否有已有键值对，如果没有，则新建一个键值对，值添加为这个字符串
def findsmall(self,str3):
if str3 == '':
return str3
smallstr = str3[0]
for strx in str3:
if strx < smallstr:
smallstr=strx
return smallstr
def selectionsort(self, str1):
# 对输入字符串进行重新排列
newstr=''
len1 = len(str1)
if len1==0:
return str1
for i in range(len1):
x = self.findsmall(str1)
newstr+=x
# 仅删除匹配的第一个字符
str1=str1.replace(x,'',1)
return newstr
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
hash1={}
for str1 in strs:
print(str1)
sorted_str1 = self.selectionsort(str1)
print(sorted_str1)
if sorted_str1 in hash1:
hash1[sorted_str1].append(str1)
else:
hash1[sorted_str1]=[]
hash1[sorted_str1].append(str1)
return list(hash1.values())
内置排序+哈希表
class Solution:
# 对于输入列表，遍历，每个都重新排序，作为新的字符串数组的键值对
# 每进入一个新的字符串数组，都排序，然后检查是否有已有键值对，如果没有，则新建一个键值对，值添加为这个字符串
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
hash1={}
for str1 in strs:
print(str1)
sorted_str1 = ''.join(sorted(str1))
print(sorted_str1)
if sorted_str1 in hash1:
hash1[sorted_str1].append(str1)
else:
hash1[sorted_str1]=[]
hash1[sorted_str1].append(str1)
return list(hash1.values())
哈希数组+内置排序
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
hash1={}
for str1 in strs:
print(str1)
count=[0]*26
for i in str1:
count[ord(i)-ord('a')]+=1
if tuple(count) in hash1:
hash1[tuple(count)].append(str1)
else:
hash1[tuple(count)]=[]
hash1[tuple(count)].append(str1)
return list(hash1.values())参考答案极简版
它相对于数组哈希的改进只有自动初始化一个字典，这个字典的初始值是一个空列表
你的代码已经比较高效了，但可以通过使用 `collections.defaultdict` 来进一步简化逻辑，避免手动检查键是否存在。以下是优化后的代码：
### 优化后的代码
```python
from collections import defaultdict
from typing import List
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups = defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
groups[tuple(count)].append(s)
return list(groups.values())
```
### 优化点说明
1. **使用 `defaultdict`**:
- `defaultdict(list)` 会自动初始化不存在的键为一个空列表，因此无需手动检查键是否存在。
- 原代码中的 `if-else` 逻辑可以简化为直接 `append`。
2. **变量名简化**:
- 将 `hash1` 改为更具描述性的 `groups`。
- 将 `str1` 改为更简洁的 `s`，`i` 改为 `c`（表示字符）。
3. **移除调试语句**:
- 删除了 `print(str1)`，因为它在最终代码中不需要。
### 进一步简化（使用排序作为键）
如果你不介意稍微降低一点性能（但代码更简洁），可以使用排序后的字符串作为键：
```python
from collections import defaultdict
from typing import List
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups = defaultdict(list)
for s in strs:
groups[''.join(sorted(s))].append(s)
return list(groups.values())
```
### 两种方法的对比
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|--------------------|------------------|------------|------------------------------|
| **字母计数（优化后）** | O(N * L) | O(N * L) | 字符串较长或字符范围固定时 |
| **排序作为键** | O(N * L log L) | O(N * L) | 代码简洁，适合短字符串 |
### 总结
- **如果你追求最高性能**，使用字母计数的方法（第一个优化代码）。
- **如果你追求代码简洁**，使用排序作为键的方法（第二个简化代码）。
两种方法都是正确的，选择取决于你的具体需求！ 🚀我的思考
也是借着这个机会重新复习一下排序，感谢whd老师，我学习的算法底子还在，学一学还是可以捡起来。
字符串怎么排序
list内置直接可以排序，sorted()可以对所有可迭代对象排序，list.sort()只能对列表排序
怎样列表化输出字典的所有键
list(hash.values())
怎样可以让字典的键值里添加很多值
先初始化为空列表，然后添加
选择排序怎么定义
遍历，然后每次都找当前最小值。需要内置函数
了解一下python的内置排序
既可以为列表，字符串等不同对象排序，也可以根据key和lambda来排序
Python 提供了多种排序方式，主要包括 **内置排序函数** 和 **列表排序方法**，适用于不同场景。以下是详细总结：
---
### 1. **内置排序函数 `sorted()`**
- **功能**：对任意可迭代对象排序，**返回新列表**，原数据不变。
- **语法**：
```python
sorted(iterable, key=None, reverse=False)
```
- **特点**：
- 支持所有可迭代对象（列表、字符串、元组、字典等）。
- 通过 `key` 参数自定义排序规则。
- 稳定排序（相等元素的顺序不变）。
#### 示例：
```python
# 对列表排序
nums = [3, 1, 4, 2]
sorted_nums = sorted(nums) # 输出: [1, 2, 3, 4]
# 对字符串排序（按字符ASCII值）
s = "hello"
sorted_s = sorted(s) # 输出: ['e', 'h', 'l', 'l', 'o']
# 按字符串长度排序
words = ["apple", "banana", "cherry"]
sorted_words = sorted(words, key=len) # 输出: ['apple', 'cherry', 'banana']
# 按字典值排序
data = [{"name": "Alice", "age": 25}, {"name": "Bob", "age": 20}]
sorted_data = sorted(data, key=lambda x: x["age"])
```
---
### 2. **列表方法 `list.sort()`**
- **功能**：原地排序列表，**直接修改原列表**，返回 `None`。
- **语法**：
```python
list.sort(key=None, reverse=False)
```
- **特点**：
- 仅适用于列表。
- 性能略优于 `sorted()`（因无需创建新列表）。
#### 示例：
```python
nums = [3, 1, 4, 2]
nums.sort() # nums 变为 [1, 2, 3, 4]
```
---
### 3. **关键参数 `key` 的用法**
通过 `key` 指定排序依据，常见场景：
- **按元素某属性排序**：
```python
students = [("Alice", 90), ("Bob", 85), ("Charlie", 92)]
students.sort(key=lambda x: x[1]) # 按分数排序
```
- **多级排序**：
```python
# 先按分数降序，再按名字升序
students.sort(key=lambda x: (-x[1], x[0]))
```
---
### 4. **降序排序**
设置 `reverse=True`：
```python
nums = [3, 1, 4, 2]
sorted_nums = sorted(nums, reverse=True) # 输出: [4, 3, 2, 1]
```
---
### 5. **特殊排序场景**
#### （1）对字典排序
- **按键排序**：
```python
d = {"b": 2, "a": 1, "c": 3}
sorted_keys = sorted(d.keys()) # 输出: ['a', 'b', 'c']
```
- **按值排序**：
```python
sorted_items = sorted(d.items(), key=lambda x: x[1]) # 输出: [('a', 1), ('b', 2), ('c', 3)]
```
#### （2）自定义对象排序
```python
class Person:
def __init__(self, name, age):
self.name = name
self.age = age
people = [Person("Alice", 25), Person("Bob", 20)]
sorted_people = sorted(people, key=lambda x: x.age)
```
---
### 6. **性能对比**
| 方法 | 时间复杂度 | 空间复杂度 | 是否修改原数据 |
|---------------|------------|------------|----------------|
| `sorted()` | \(O(n \log n)\) | \(O(n)\) | 否 |
| `list.sort()` | \(O(n \log n)\) | \(O(1)\) | 是 |
---
### 7. **注意事项**
1. **字符串排序**：按 Unicode 码点排序（可能不符合语言习惯）。
```python
words = ["苹果", "Banana", "apple"]
sorted_words = sorted(words) # 输出: ['Banana', 'apple', '苹果']
```
2. **混合类型排序**：Python 3 不允许直接比较不同类型（如 `str` 和 `int`）。
---
### 总结
- 需要新列表 → `sorted(iterable)`
- 原地修改列表 → `list.sort()`
- 复杂排序规则 → 使用 `key` 和 `lambda`
掌握这些方法后，可以高效处理绝大多数排序需求！ 🚀
### 按值排序和多级排序详解
#### 1. **按值排序**
当需要对字典的 **值（value）** 进行排序时，可以通过 `sorted()` 的 `key` 参数指定排序依据。
##### 示例代码：
```python
d = {"b": 2, "a": 1, "c": 3}
sorted_items = sorted(d.items(), key=lambda x: x[1])
print(sorted_items) # 输出: [('a', 1), ('b', 2), ('c', 3)]
```
##### 关键点解析：
- **`d.items()`**：
将字典转换为可迭代的 `(key, value)` 元组列表，例如：
```python
[('b', 2), ('a', 1), ('c', 3)]
```
- **`key=lambda x: x[1]`**：
- `lambda x: x[1]` 是一个匿名函数，表示对每个元组 `x`，取其第二个元素（即 `value`）作为排序依据。
- 相当于：
```python
def get_value(item):
return item[1]
sorted_items = sorted(d.items(), key=get_value)
```
#### 2. **多级排序**
当需要按多个条件排序时（例如先按值升序，值相同再按键降序），可以通过 `key` 返回一个元组实现。
##### 示例代码：
```python
d = {"b": 2, "a": 2, "c": 1, "d": 1}
# 按值升序，值相同则按键降序
sorted_items = sorted(d.items(), key=lambda x: (x[1], -ord(x[0])))
print(sorted_items) # 输出: [('d', 1), ('c', 1), ('b', 2), ('a', 2)]
```
##### 关键点解析：
- **`key=lambda x: (x[1], -ord(x[0]))`**：
- 先按 `x[1]`（值）升序排列。
- 若值相同，则按 `-ord(x[0])`（键的 ASCII 码取负，实现降序）排序。
- 元组比较规则：从左到右依次比较各元素。
#### 3. **常见场景**
- **按值降序**：
```python
sorted_items = sorted(d.items(), key=lambda x: -x[1])
```
- **按键排序**（默认行为）：
```python
sorted_items = sorted(d.items()) # 按键升序
```
- **混合排序**（如先按值，再按键）：
```python
sorted_items = sorted(d.items(), key=lambda x: (x[1], x[0]))
```
#### 4. **可视化对比**
| 原始字典 | 排序依据 | 输出结果 |
|-------------------|-------------------------|------------------------------|
| `{'b':2, 'a':1}` | `key=lambda x: x[1]` | `[('a',1), ('b',2)]` |
| `{'b':2, 'a':2}` | `key=lambda x: -x[1]` | `[('b',2), ('a',2)]` |
| `{'b':2, 'a':2}` | `key=lambda x: (x[1], -ord(x[0]))` | `[('b',2), ('a',2)]` |
#### 5. **注意事项**
- **字典无序性**：Python 3.7+ 中字典保持插入顺序，但排序时应显式使用 `items()`。
- **复杂键函数**：若排序逻辑复杂，可定义普通函数替代 `lambda`。
通过灵活组合 `key` 和元组，可以实现任意多级排序需求！