刷题心得

1、如何通过字典的value来访问key

现有博客中介绍过很多实现方法，但是大多数都要求value值必须唯一，真实情况下的实用性太差，这里记录一个简单实用的思路：即构建一个新的字典进行键值的反转，但由于无法保证value值的唯一性，因此新字典中的每个键对应的值需要为一个列表。关键代码如下：

    for key,value in hash.items():
        if value in frequent:
            frequent[value].append(key)
        else:
            frequent[value] = [key]

典型题目为桶排序的「347. 前k个高频元素」和「451. 根据字符出现频率排序」

2、同时获取数组元素出现频率和子序列长度的方法

用一个字典同时存储给定数组的数值及相应数值所在的下标和个数，如下格式：{数值1：[下标1，下标2，...，下标m]}，即{数值：下标列表}的方法来存储，这样既可以获取某数值的范围，也可以通过len()的方法获取特定数值在数组中出现的次数，一举两得。关键代码如下：

    for i,v in enumerate(nums):
        if v in dic:
            dic[v].append(i)
        else:
            dic[v] = [i]
    degree = max(len(i) for i in dic.values())

典型题目为「697. 数组的度」

3、在存储临时判别元素时，尽量用字典或集合，不要用列表、元组和字符串，因为集合和字典的存取时间复杂度为O（1），查询效率更高。此外在查询速度和内存占用方面，列表与字典的区别如下：

• 字典的查询速度永远都是O(1)，速度不会随字典内元素的增加而改变，但是字典的缺点是占用内存过大；
• 列表的查询速度为O(N)，因此列表内元素越多，查询速度越慢，但是列表的优点是占用内存小。

4、在列表中找寻和为target的子列表

此类题目如果按照所求子列表中元素是否是连续的，可以分为①在列表中找寻元素组合 或 ②在列表中找寻子序列。

（1）如果是寻找连续子序列，一般通过哈希表（字典）来实现，可以根据所求结果，将题目分为 ①求满足题意的子列表个数 或 ②求最大子序列长度。如果是求子序列的个数，一般哈希表初始化为{0:1}，保证其提前涵盖了列表中的某个值正好等于target的情况；如果是求连续子序列的最大长度，一般哈希表初始化为{0:-1}，保证其提前涵盖了列表中的最长子序列是从第一个元素就开始的情况。典型题目如下：

• 560.和为k的子数组（求子数组的个数）
• NC125 和为K的连续子数组（求最长子数组的长度）

（2）如果是寻找非连续子序列，即寻找的是列表的元素组合是否能够相加等于target，一般通过dp或DFS/BFS来实现，可以根据所求结果，将题目分为 ①求是否存在某种组合；②求满足题意的组合个数；③求组合元素数量最少的情况；④求所有的组合情况列表。其中①②③一般通过DP来实现，④一般通过DFS/BFS来实现，需要注意的是，②也可以通过DFS来实现，但是可能会超时。典型题目如下：

• 416.分割等和子集（①，0-1背包问题，dp[i] = dp[i] or dp[i-v]）
• 494.目标和（②，0-1背包，dp[i] += dp[i-v]）
• 518.零钱兑换-ii（②，完全背包，dp[i] += dp[i-coin]）
• 322.零钱兑换（③，完全背包，dp[i] = min(dp[i], dp[i-coin] + 1)）
• 279.完全平方数（③，完全背包，dp[i] = min(dp[i], dp[i-v] + 1)）
• 39.组合总和（④，Backtracking，self.dfs(nums[i:], target-nums[i], ans, path+[nums[i]])）
• 40.组合总和-ii（④，Backtracking+剪枝，self.dfs(nums[i+1:], target-nums[i], ans, path+[nums[i]])）
• 216.组合总和-iii（④，Backtracking，self.dfs(nums[i+1:], n-nums[i], k-1, ans, path+[nums[i]])）

5、判断字符串是否是纯数字

# 如果str1是纯数字，则返回True，否则返回False
str1.isdigit()

6、print调整数字的精度及带符号输出

x = 102
y = -103
# 精度控制
print('%.2f' % x) # 102.00
print('{:.2f}'.format(x))  # 102.00

# 精度控制+带符号输出 
print('%+.2f' % x) # +102.00
print('%+.2f' % y) # -102.00
print('{:+.2f}'.format(x)) # +102.00
print('{:+.2f}'.format(y)) # -103.00

7、进制转换

# X进制转十进制：int()转化的结果是一个十进制数
int('X进制数', X)

# X进制转十六进制：先将X进制数转为十进制数，再利用hex函数转十六进制，转化的结果是'0x'开头的十六进制字符串
hex(int('X进制数', X))

# X进制转二进制：先将X进制数转为十进制数，再利用bin函数转二进制，转化的结果是'0b'开头的二进制字符串
bin(int('X进制数', X))

# X进制转八进制：oct()转化的结果是'0o'开头的八进制字符串
oct(X进制数)

8、any与all的使用

any() 函数用于判断给定的可迭代参数 iterable 是否全部为 False，则返回 False，如果有一个为 True，则返回 True。元素除了是 0、空、FALSE 外都算 TRUE。函数等价于：

def any(iterable):
    for element in iterable:
        if element:
            return True
    return False

# 举例：解数独问题中的判断
if any(board[i][col] == target for i in range(9)): return False

all() 函数用于判断给定的可迭代参数 iterable 中的所有元素是否都为 TRUE，如果是返回 True，否则返回 False。元素除了是 0、空、None、False 外都算 True。函数等价于：

def all(iterable):
    for element in iterable:
        if not element:
            return False
    return True

9、判断两个字符串是否含有相同字符

典型题目

• 318.最大单词长度乘积

需要时常回顾的难题：

String

• 242.有效的字母异位词（简单题，ord()函数的作用就是获取字符对应的ASCII数值）
• 696.计数二进制子串
• 647.回文子串

Linked List

• 83.删除排序链表中的重复元素（递归实现）
• 725.分隔链表（循环条件需要记住）

Stack and Queue

• 20.有效的括号（循环中的判断条件要先if判断栈不为空且c在字典中，再弹出元素用if进行比较）

Hash Table

• 594.最长和谐子序列（可以使用for v in hashmap的方法遍历字典，并且用if语句去判断v+1是否在hashmap中）
• 128.最长连续序列

Array and Matrix

• 378.有序矩阵中第-k-小的元素（二分查找在矩阵中的应用）
• 287.寻找重复数（二分查找在列表中的应用，较难）
• 667.优美的排列-ii（等差数列的性质）
• 769.最多能完成排序的块（已遍历元素最大值 == 当前下标）

Bit Manipulation

• 260.只出现一次的数字-iii（很经典的位运算综合题目）
• 190.颠倒二进制位（无符号左移右移经典题目）
• 371.两整数之和（递归，异或，与，左移）
• 318.最大单词长度乘积（或，左移）

Two Pointers

• 680.验证回文字符串-ⅱ

Sort

• ALL

Math

• ALL