Python 刷题常用知识点

知识点 & 短代码内置API collections sortedcontainers heapq random 数字相关字符相关

知识点 & 短代码

list中要实现O(1)复杂度删除元素的话，可以把待删除的元素和末尾元素交换，然后只删除末尾的就可以。但是会改变顺序

完美二叉树就是满二叉树

求数组nums 中位数


half = len(nums) // 2
中位数： (nums[half] + nums[~half] ) / 2

解释：
~是位运算中的求反
对于一个自然数n，有~n = -n-1
Python中数组的下标可以为负数，-1即代表最后一个，-2代表倒数第二个，-half-1即倒数第half+1个。

数组长度为奇数时，易得下标half和下标-half-1指向同一个数，即最中间的数字，
故取平均数仍然是其本身。中位数成立。

数组长度为偶数时，中位数为中间2个数的平均数，此时下标half为中间右侧的数，
下标-half-1为中间左侧的数。中位数成立。


nums 长度为 n
中位数为 nums[(n + 1) / 2 - 1] + nums[(n + 2)/2 - 1]

内置API

`collections`

collections.defaultdict()

collections.defaultdict(int)，字典初始value定义为0, 如果想定义为列表，直接将参数改为 collections.defaultdict(list)即可

可以通过这个collections.Counter(aa) 来统计aa 中每一位元素出现的个数。对Counter执行 a = a.most_common() 将会根据 val值来递减排序。

字典中的keys() 或者 values()提取出来是一个迭代器，可以通过list(keys() )将其转换为列表

collections.deque

双端队列，append,pop 为从右端进出，popleft为从左端出

`sortedcontainers`

有序列表 from sortedcontainers import SortedList arr= SortedList()

arr.add(), arr.remove()

`heapq`

heapq是没法删除任意元素的，只能删除堆顶元素。如果需要不断的删除元素，添加元素还要保持有序，推荐使用SortedList

`random`


random.randint(1,10)       # 产生 1 到 10 的一个整数型随机数 [1, 10]
random.random()            # 产生 0 到 1 之间的随机浮点数
random.uniform(1.1,5.4)    # 产生  1.1 到 5.4 之间的随机浮点数，区间可以不是整数
random.choice('tomorrow')  # 从序列中随机选取一个元素
random.randrange(1,100,2)  # 生成从1到100的间隔为2的随机整数

数字相关

向上取整：math.ceil( x )

向下取整：math.floor( x )

最大公约数 & 最小公倍数


def gongyue(a, b):
  """
  欧几里得算法----辗转相除法
	  :param a: 第一个数， 较大的数
	  :param b: 第二个数, 较小的数字
	  :return: 最大公约数
  """
  # 如果最终余数为0 公约数就计算出来了
  while(b!=0):
    temp = a % b
    a = b
    b = temp
  return a

# 求两个数的最小公倍数
def gongbei(a,b):
  return a * b / gongyue(a, b)


low = ["Zero","One","Two","Three","Four",
       "Five","Six","Seven","Eight","Nine"]
mid = ["Ten","Eleven","Twelve","Thirteen",
       "Fourteen","Fifteen","Sixteen",
       "Seventeen","Eighteen","Nineteen"]
high = ["","","Twenty","Thirty","Forty",
        "Fifty","Sixty","Seventy","Eighty","Ninety"]
Hundred Thousand Million Billion

闰年 a % 4 == 0 and a% 100 ≠ 0 or a % 400 == 0

字符相关

chr() 数字转字母

ord()字母转数字

26个英文字母 [chr(i) for i in range(97, 123)]

isdigit() 判断数字

ispunct() 判断标点符号

isalpha() 判断字母

二进制字符串转整数


binstr = "0011"
int(binstr, 2)

>> 3

Python对字符串中的字符进行排序：

s = "".join((lambda x: (x.sort(), x)[1])(list(s)))

先转为list,使用sort函数后再转为字符串