进制转换

		
		a = int('0b101010100110101001110', 2)
		b = int('0o5246516', 8)
		c = int('0x154D4E', 16)
		d = bin(int('0b101010100110101001110', 2))
		e = oct(int('5246516', 8))
		f = hex(int('154D4E', 16))
		print(a, b, c, d, e, f)
		1396046 1396046 1396046 0b101010100110101001110 0o5246516 0x154d4e

字符串

找子串的第一个index：

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        return haystack.find(needle)

判断大小写，转换大小写

str.isupper();
str.isupper();
str.upper()
str.lower()

补充两个字符串

from itertools import zip_longest
a = [i for i in range(10)]
b = [i for i in range(1, 9)]
for num1, num2 in zip_longest(a, b, fillvalue=-1):
    print(num1, num2)
# 0 1
# 1 2
# 2 3
# 3 4
# 4 5
# 5 6
# 6 7
# 7 8
# 8 -1
# 9 -1

数学

python计算指数

pow(a,2)
#求a的平方

双指针，涉及到重复项的，可以从1开始遍历，检查前一项，

例题，删除list中的重复项并且补到list最前面
另外，在python中需要注意，如果用for i in range（）的话，是没有办法在循环中修改i的值的，但是用while可以

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        n = len(nums)
        fast = slow = 1
        while fast < n:
            if nums[fast] != nums[fast - 1]:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        
        return slow

买卖股票的最佳时机 II

def check(prices):

    n = len(prices)
    # dp[i][0] : 第i天结束时，手上没有股票的最大利润
    # dp[i][1] : 第i天结束时，手上持有股票的最大利润
    dp = [[0, 0] for _ in range(n)]
    dp[0][0] = 0
    dp[0][1] = -prices[0]
    for i in range(1, n):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
        dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
    return dp[n-1][0]

if __name__ == "__main__":

    prices = [7, 1, 5, 3, 6, 4]
    a = check(prices)
    print(a)

List

如果要判断某个元素在list中，直接

if c in list:

列表的函数

python列表函数：len()，max()，min()，list()，cmp()

1. len(list)

len()函数是统计列表中有多少元素

lists = [1, 2, 3, 4, 5, 6, 7]
print(len(lists))
# 7

2. max(list)与min(list)

max 与 min 函数返回list中的最大值与最小值

lists = [1, 2, 3, 4, 5, 6, 7]
print(max(lists))
print(min(lists))
# 7 1

3. list(seq)

list()函数可以将其他的数据类型转化成list类型

aTuple = (1, 2, 3, 'abc')
aList = list(aTuple)
print(aList)
# [1, 2, 3, 'abc']

列表的方法

1. list.append()

在列表末尾添加新的对象

aList = [1, 2, "abc"]
aList.append(4)
print(aList)
# [1, 2, 'abc', 4]

2. list.extend()

在列表末尾一次性追加另一个序列中的多个值（用新列表扩展原来的列表）

aList = [1, 2, 3, 'xyz']
bList = [5, 'abc']
aList.extend(bList)
print(aList)
# [1, 2, 3, 'xyz', 5, 'abc']

3. list.insert(index,obj)

将指定对象插入列表的指定位置。

aList = [1, 2, 3, 'xyz']
aList.insert(1,"abc")
print(aList)
# [1, 'abc', 2, 3, 'xyz']

4. list.count()

统计某个元素在列表中出现的次数。

aList = [1, 2, 3, 'xyz', 'xyz']
print(aList.count('xyz'))
# 2

5. list.index()

从列表中找出某个值第一个匹配项的索引位置。

aList = [1, 2, 3, 'xyz', 'xyz']
print(aList.index('xyz'))
# 3

6. list.pop()

移除列表中的一个元素（默认最后一个元素），并且返回该元素的值。

pop()里面可以指定位置的元素，不指定默认就是最后一个

aList = [1, 2, 3, 'xyz']
aList.pop(3)
print(aList) 
# [1, 2, 3]

7. list.remove()

移除列表中某个值的第一个匹配项。

aList = [1, 2, 'xyz', 3, 'xyz']
aList.remove('xyz')
print(aList)
# [1, 2, 3, 'xyz']

8. list.reverse()

反向列表中元素。

aList = [1, 2, 'xyz', 3, 'xyz']
aList.reverse()
print(aList)
# ['xyz', 3, 'xyz', 2, 1]

9. list.sort()

list.sort(cmp=None, key=None, reverse=False)，对原列表进行排序，如果指定参数，则使用比较函数指定的比较函数。

cmp：可选参数, 如果指定了该参数会使用该参数的方法进行排序。

key：主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序。

reverse：排序规则，reverse = True 降序， reverse = False 升序（默认）。

aList = [1, 2, 5, 9, 6]
aList.sort()
print(aList)
# [1, 2, 5, 6, 9]
 
bList = [1, 2, 5, 9, 6]
bList.sort(reverse=True)
print(bList)
# [9, 6, 5, 2, 1]

字符串内字符计数：

class Solution:
    def halvesAreAlike(self, s: str) -> bool:
        VOWELS = "aeiouAEIOU"
        a, b = s[:len(s) // 2], s[len(s) // 2:]
        return sum(c in VOWELS for c in a) == sum(c in VOWELS for c in b)

>>> a = [1,2,3]
>>> b = [4,5,6]
>>> c = [4,5,6,7,8]
>>> zipped = zip(a,b)     # 返回一个对象
>>> zipped
<zip object at 0x103abc288>
>>> list(zipped)  # list() 转换为列表
[(1, 4), (2, 5), (3, 6)]
>>> list(zip(a,c))              # 元素个数与最短的列表一致
[(1, 4), (2, 5), (3, 6)]

>>> a1, a2 = zip(*zip(a,b))          # 与 zip 相反，zip(*) 可理解为解压，返回二维矩阵式
>>> list(a1)
[1, 2, 3]
>>> list(a2)
[4, 5, 6]
>>>

创建列表：

一维
matrix = [0] * n
二维
matrix = [[0] * n for _ in range(m)]
如果用
matrix = [[0]*n]*m
的方法创建二维列表的话，会导致第二行的列表跟着第一行列表的变化而变化

整行整列处理

    def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
        matrix = [[0] * n for _ in range(m)]
        for x, y in indices:
            for j in range(n):
                matrix[x][j] += 1
            for row in matrix:
                row[y] += 1
        return sum(x % 2 for row in matrix for x in row)

pop（）
移除最后一个元素
会返回最后这个元素

所以如果把一个list当作堆栈的话：

nums.insert(0,nums.pop())

表示尾出再从头进来

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def swap(nums, left, right):
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
        
        length = len(nums)
        k %= length
        swap(nums, 0, length-k-1)
        swap(nums, length-k, length-1)
        swap(nums, 0, length-1)

newList = list(reversed(list2))

切片操作

切片的使用可以看做 [start:end:interval]，三者的取值可正可负。其中，start、end、interval有时候可以省略。

a = list(range(1,8))   # [1, 2, 3, 4, 5, 6, 7]
a[:3]  # [1,2,3]  即索引是 [0,3) => a[0]、a[1]、a[2]
a[:-5] # [1,2]  等价于 a[:(-5+a中元素个数7)] = a[:2] = [1,2]
a[:5:2]  # [1,3,5]  先取前5个元素，然后按照间隔2取数
a[:4:-1] # [7,6]  先看interval为负值，故从左往右取，取到下标为4的前一个为止，即能取到a[6]、a[5]
a[:3:-2]  # [7,5]  先看interval为负值，故从右往左取，取到下标为3的前一个为止，即能取到a[6]、a[5]、a[4]，然后按照间隔2取数
a[:-5:-1] # [7,6,5,4]  先看interval为负值，故从右往左取，取到下标为-5的前一个为止，即能取到a[-1]、a[-2]、a[-3]、a[-4]
a[:10] # [1,2,3,4,5,6,7]  即索引是 [0,10)，超过不报错
a[:10:-1] # []  先看interval为负值，故从右往左取，取到下标为10的前一个为止，但是从左到右取最大的下标也才是a[6]，故返回[]
a[:-100:-1] # [7,6,5,4,3,2,1]  先看interval为负值，故从右往左取，取到下标为-100的前一个为止，即能取到a[-1]、a[-2]、a[-3]、a[-4]、a[-5]、a[-6]、a[-7] 
a[::-1] # [7,6,5,4,3,2,1]  先看interval为负值，故从左往右取，取到头（因为end没有指定）为止，即能取到a[-1]、a[-2]、a[-3]、a[-4]、a[-5]、a[-6]、a[-7] ，该方法也是list反转的方法
a[::2] # [1,3,5,7]  每隔2个元素取数
a[3::2] # [4,6]  从a[3]=4开始，每隔2个元素取数

list 可以转化为 set

cur = set(nums)

集合

set是无序的
最长无重复子串

    def func(self, strs: str):
        n = len(strs)
        cur = set()
        left = 0
        right = 0
        maxlen = 0
        while left < n:
            while right < n and strs[right] not in cur:
                cur.add(strs[right])
                right += 1
            maxlen = max(maxlen, len(cur))
            cur.remove(strs[left])
            left += 1
        return maxlen

求交集：

tmp = set(word[0])
	for wd in word:
		tmp = set(wd) & tmp

字典

字典的获取要用dic.get(key)

如果key值存在，返回对应的value值
如果key值不存在，默认返回None，如果需要指定返回值，传值即可

遍历key
dict1 = {'name': 'Rose', 'age': 30, 'sex': '女'}
for key in dict1.keys():
    print(key)

遍历value
dict1 = {'name': 'Rose', 'age': 30, 'sex': '女'}
for value in dict1.values():
    print(value)

遍历键值对
dict1 = {'name': 'Rose', 'age': 30, 'sex': '女'}
for item in dict1.items():
    print(item)

Collections

双向队列

d = collections.deque([])
d.append('a') # 在最右边添加一个元素，此时 d=deque('a')
d.appendleft('b') # 在最左边添加一个元素，此时 d=deque(['b', 'a'])
d.extend(['c','d']) # 在最右边添加所有元素，此时 d=deque(['b', 'a', 'c', 'd'])
d.extendleft(['e','f']) # 在最左边添加所有元素，此时 d=deque(['f', 'e', 'b', 'a', 'c', 'd'])
d.pop() # 将最右边的元素取出，返回 'd'，此时 d=deque(['f', 'e', 'b', 'a', 'c'])
d.popleft() # 将最左边的元素取出，返回 'f'，此时 d=deque(['e', 'b', 'a', 'c'])
d.rotate(-2) # 向左旋转两个位置（正数则向右旋转），此时 d=deque(['a', 'c', 'e', 'b'])
d.count('a') # 队列中'a'的个数，返回 1
d.remove('c') # 从队列中将'c'删除，此时 d=deque(['a', 'e', 'b'])
d.reverse() # 将队列倒序，此时 d=deque(['b', 'e', 'a'])

:=符号的作用是在表达式内获取变量值并赋给新变量。

给定一个单词列表 words和一个整数 k ，返回前k个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

from collections import Counter
class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        # 先获取到一个单词hash表 Counter(words)
        # 题目所给的需要进行的排序优先度为： 数量>字典序
        # 我们可以考虑采用sorted函数，通过关键词 key=lambda x:(数量,字典序) 进行排序
        # 当然，数量是从小到大，而字典序是从大到小，这里需要控制
        # 所以最终的语句为:
        return sorted((cnt:=Counter(words)).keys(),key=lambda x:(-cnt[x],x))[:k]

这个语句等价于：

class Solution:
    def topKFrequent(self, words, k: int):
        cnt=Counter(words)# 按照原来的顺序
        return sorted(cnt.keys(),key=lambda x:(-cnt[x],x))[:k]

哈希表：字符串中的第一个字符

collections.Counter(s)创建之后，还是按照原来的顺序，即c++中的unordered_map

class Solution:
    def firstUniqChar(self, s: str) -> int:
        frequency = collections.Counter(s)
        for i, ch in enumerate(s):
            if frequency[ch] == 1:
                return i
        return -1

defaultdict

这个factory_function可以是list、set、str等等，作用是当key不存在时，返回的是工厂函数的默认值，比如list对应[ ]，str对应的是空字符串，set对应set( )，int对应0，如下举例：

from collections import defaultdict
 
dict1 = defaultdict(int)
dict2 = defaultdict(set)
dict3 = defaultdict(str)
dict4 = defaultdict(list)
dict1[2] ='two'
 
print(dict1[1])
print(dict2[1])
print(dict3[1])
print(dict4[1])

0
set()
 
[]

异位词：

    def solve(self, strs: List[int]) -> List[List[int]]:
        mp = collections.defaultdict(list)

        for st in strs:
            key = "".join(sorted(st))
            mp[key].append(st)
        return list(mp.values())

enumerate

enumerate可以同时提供下标和参数

    hash = dict()
    for i, num in enumerate(nums):
        if target - num in hash:
            return [hash[target - num], i]
        hash[nums[i]] = i
    return []

正则表达式

.sub函数

判断字符串是否为回文串

import regex as re
def intersect():
    s = "A man, a plan, a canal: Panama"
    s = s.lower()
    # s = s.replace(" ", "")
    s = re.sub('[^a-zA-Z\d]+', '', s)
    left = 0
    right = len(s) - 1
    
    # while left < right:
    #     if s[left] != s[right]:
    #         return False
    #     left += 1
    #     right -= 1
    # return True
    #
    return s[:] == s[::-1]  # 等价于双指针
    print(s)

链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

使用：
dummy = ListNode(0, head)

删除倒数第n个节点

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        first = head
        second = dummy
        for i in range(n):
            first = first.next

        while first:
            first = first.next
            second = second.next
        
        second.next = second.next.next
        return dummy.next

求链表的长度

        def getLength(head: ListNode) -> int:
            length = 0
            while head:
                length += 1
                head = head.next
            return length

合并有序链表

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        l1 = list1
        l2 = list2
        prev = ListNode(-1)
        noob = prev
        while l1 and l2:
            if l1.val < l2.val:
                noob.next = l1
                l1 = l1.next
            else:
                noob.next = l2
                l2 = l2.next
            noob = noob.next

        noob.next = l1 if l1 is not None else l2
        return prev.next

二叉树

定义

 class TreeNode:
     def __init__(self, val=0, left=None, right=None):
         self.val = val
         self.left = left
         self.right = right

二叉树的最大深度

深度优先

class Solution(object):
    def maxDepth(self, root):
        self.res = 0
        self.dfs(root, 1)
        return self.res

    def dfs(self, root, level):
        if not root: return
        if root.left is None and root.right is None:
            self.res = max(self.res, level)
        self.dfs(root.left, level + 1)
        self.dfs(root.right, level + 1)

广度优先

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # 空树，高度为 0
        if root == None:
            return 0

        # 初始化队列和层次
        queue = [root]
        depth = 0

        # 当队列不为空
        while queue:
            # 当前层的节点数
            n = len(queue)
            # 弹出当前层的所有节点，并将所有子节点入队列
            for i in range(n):
                node = queue.pop(0)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            depth += 1
        # 二叉树最大层次即为二叉树最深深度
        return depth

中序遍历

class Solution:
    # 中序遍历
    def inOrder(self, root: TreeNode, res):
        if root == None:
            return
        self.inOrder(root.left, res)
        res.append(root.val)
        self.inOrder(root.right, res)


    def isValidBST(self, root: TreeNode) -> bool:
        res = []
        self.inOrder(root, res)
        # 判断 res 是否有序
        for i in range(1, len(res)):
            if res[i] <= res[i - 1]:
                return False
        return True

Python的INT_MAX和INT_MIN

import sys
  largest= sys.maxsize
  smallest = -sys.maxsize - 1

但其实没有int的最大值，因为超过一定长度后python会转化为long int

f-string

>>> price = 95.5
>>> f"He has {price}$"
'He has 95.5$'

>>> f"They have {2+5*2} apples"
'They have 12 apples'

>>> name = "Huang Wei"
>>> f"my name is {name.lower()}"
'my name is huang wei'

>>> import math
>>> f"Π的值为{math.pi}"
'Π的值为3.141592653589793'

join

a=['I','love','China','!']
print(' '.join(a))
print('-'.join(a))
print('*'.join(a))

#结果：
I love China !
I-love-China-!
I*love*China*!

自定义sort

1、首先得到每个字符串长度

2、排序，选择sorted或者 list.sort()进行排序

内置sorted返回一个新的列表，而list.sort是对列表进行操作

sorted(iterable, cmp=None, key=None, reverse=False)
iterable：是可迭代类型;
cmp：用于比较的函数，比较什么由key决定;
key：用列表元素的某个属性或函数进行作为关键字，有默认值，迭代集合中的一项;
reverse：排序规则. reverse = True  降序 或者 reverse = False 升序，有默认值。
返回值：是一个经过排序的可迭代类型，与iterable一样。

按照二维数组的第i-1列大小排序

grid_area.sort(key=lambda x: [x[i - 1] for i in sort_cols])

按照一个数组中不同的维度排序：

tmp.sort(key=lambda x: (-x[1], x[2], x[0])) # sort的lambda

str(sorted(st))
如果只是sorted(st)的话，排序的结果是list返回的
也可以通过"".join(sorted(st))改回字符串

按照字典的key排序：

dia = sorted(dic.items(), key=lambda d: d[0])

按照字典的value排序

dia = sorted(dic.items(), key=lambda d: d[1])

按照二维列表中一维列表长度排序：

res = sorted(tmp, key=lambda i: len(i), reverse=False)

按照二维列表的中子列表的第一维和第二维度排序：第一维倒序，第二维正序

res = tmp.sort(key=lambda x: (-x[0], x[1]))

二分法

class Solution:
    def firstBadVersion(self, n: int) -> int:
        i, j = 1, n
        while i <= j:
            # 向下取整除法计算中点 m 
            m = (i + j) // 2
            # 若 m 是错误版本，则最后一个正确版本一定在闭区间 [i, m - 1]
            if isBadVersion(m): j = m - 1
            # 若 m 是正确版本，则首个错误版本一定在闭区间 [m + 1, j]
            else: i = m + 1
        # i 指向首个错误版本，j 指向最后一个正确版本
        return i

dfs

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        n, m = len(image), len(image[0])
        currColor = image[sr][sc]

        def dfs(x: int, y: int):
            if image[x][y] == currColor:
                image[x][y] = color
                for mx, my in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                    if 0 <= mx < n and 0 <= my < m and image[mx][my] == currColor:
                        dfs(mx, my)

        if currColor != color:
            dfs(sr, sc)
        return image