[python 刷题] 刷题常用函数

• [python 刷题] 刷题常用函数
  • 不知道怎么归类
    • lambda
    • sorted
  • string
    • f-strings
  • dict/hashtable
    • get(key, default_value)
    • ==
    • defaultdict
    • Counter
  • list/array
    • list comprehension
    • deque
    • 2d array
      • divmod
  • itertools
    • accumulate

[python 刷题] 刷题常用函数

最近直到未来一段时间之内应该都会用 python 刷题了，所以记一下碰到的还蛮好用的方法

按照分区实现，基本上刷一个类型的题，了解一些常用函数，就更新一下

这里假设你对编程语言有一定的了解，常用的 if/elif/else，while, for/range，或者新建一个比较常用的数据类型，如初始化 list/array, tuple, dict 这种就不写了

不知道怎么归类

一些比较常用，不太依赖于某种数据类型的函数……？

lambda

lambda 单独作为一个 section，其语法为 lambda arguments: expression，这是一个不会也无所谓，但是稍微了解一下会方便很多的存在

一些简单的用法为：

# 返回一个 list，值为原本 list 的平方
map(lambda x: x * x, some_list)

# 过滤奇数
list(filter(lambda x: x % 2 == 0, some_list))
1
2
3
4
5

如果只需要写一个 不被重复 并且比较短的函数，lambda 是一个比较合适的选项

sorted

语法为：sorted(iterable, key, reverse)，其中因为 sorted 可以接受整个 iterable，因此也可以根据一些特质去进行排序。因为接受的是 iterable，因此 tuple 也可以使用 sorted

另外对比 array.sort()，sorted() 不会修改原有的数据类型，而是返回一个新的数据类型，因此在有 不修改 input 这种需求，或是对 dict 进行排序的需求时，就很方便

其中 key 是一个 function，这里使用 lambda 就很方便，如 [python 刷题] 347 Top K Frequent Elements 一个解法是对字符出现的频率进行排序，这里就可以使用 sorted(): sorted_map = sorted(map.items(), key=lambda x: x[1], reverse=True)

string

f-strings

f-strings 指代的是 python 中的 formatted string，主要用于可以对字符串进行修改，大多数情况下需要搭配其他的函数进行使用

如 271. Encode and Decode Strings 这一题中，format string 可以使用：

def encode(self, strs: List[str]) -> str:
  """Encodes a list of strings to a single string.
  """
  return ''.join(map(lambda s: f'{len(s)}#{s}', strs))
1
2
3
4

来代替原本的循环

dict/hashtable

get(key, default_value)

这里用语获取值，如果 dict 中不存在值的话，就是用第二个参数

如：d = {}

d.get('c') 没有任何输出，返回值为

d.get('c', 0) 返回 0

多用于从 dict 中获取 value 进行修改

==

[python 刷题] 242 Valid Anagram 里有稍微提到过，python 中对 dict 使用 == 基本上等同于一个深对比，而不是直接对比地址

因此判断两个 dict 是否相等，可以使用 dict1 == dict2 进行判断

defaultdict

这里主要针对 dict 中需要保存非原始类型的题目，defaultdict 会提供默认值，这样直接使用 dict[key].append() 这样就不会报错，同时也不需要用 if/else 去创建一个新的数据类型

Counter

Counter 是一个特异化的 dict，字如其名，主要用于计数

依旧以 [python 刷题] 242 Valid Anagram 这道题为例，完全手写 dict 的答案为：

class Solution:
def isAnagram(self, s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    char_dict = {}
    for l in s:
        if l in char_dict:
            char_dict[l] = char_dict[l] + 1
        else:
            char_dict[l] = 1

    for l in t:
        if l not in char_dict:
            return False
        if char_dict[l] == 1:
            del char_dict[l]
        else:
            char_dict[l] = char_dict[l] - 1

    return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

使用 Counter 和 == 两个特性的答案为：

class Solution:
  def isAnagram(self, s: str, t: str) -> bool:
      return collections.Counter(s) == collections.Counter(t)
1
2
3

一般需要对频率进行操作的话，我个人建议还是用 defaultdict 或是 dict，但是只是对频率进行读取，使用 Counter 会方便很多

list/array

list comprehension

这是一个很强大的功能，熟练使用我觉得只能靠积累

里面可以嵌套 if/else 和循环，语法为：[expression for item in iterable if condition else condition]，其中 else 可以省略，下面依旧举几个例子说明：

# flatten 2d array
flat_array = [num for row in matrix for num in row]

# get even number from 1-9
[x for x in range(10) if x % 2 == 0]

# captilize word in list
[word.capitalize() for word in words]
1
2
3
4
5
6
7
8

这个搭配嵌套一些上面的知识点，还是可以写出点比较有意思的代码的，依旧用 [python 刷题] 347 Top K Frequent Elements 为例，之前笔记里的解法为：

class Solution:
  def topKFrequent(self, nums: List[int], k: int) -> List[int]:
      count = {}
      freq = [[] for i in range(len(nums) + 1)]

      for n in nums:
          count[n] = 1 + count.get(n, 0)
      for n, c in count.items():
          freq[c].append(n)

      res = []
      for i in range(len(freq) - 1, 0, -1):
          for n in freq[i]:
              res.append(n)
              if len(res) == k:
                  return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1-liner 的解法为：

class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    return [val[0] for i, val in enumerate(sorted(collections.Counter(nums).items(), key=lambda x: x[1], reverse=True)) if i < k]
1
2
3

有趣的是，其是这样的写法也没有慢很多：

大概是 python 内部对 list compression 做的优化吧

deque

即 double ended queue，是 python 中的 collections 中包含的数据结构

其优势在于向 list 的头部和尾部进行修改，时间复杂度都为 $O(1)$

因此它对应的增删方法除了有 append 和 pop，还有对应额 appendleft 和 popleft

2d array

divmod

a, b = divmod(x, y) 相当于：

a = x // y
b = x % y
1
2

属于稍微方便一点的小优化

itertools

accumulate

prefix sum的对应函数……？

用法如下：

data = [1, 2, 3, 4, 5]
result = list(itertools.accumulate(data))
print(result) # [1, 3, 6, 10, 15]
1
2
3