1
2
3
4
import sys
for line in sys.stdin:
    data = line.split()
    print(int(data[0]) + int(data[1]))

1
2
data = input().split(' ')

1
2
3
4
5
6
7
8
import sys
line = int(input())
res = []
for i in range(line):
    data = [int(e) for e in input().split(' ')]
    res.append(sum(data))
for r in res:
    print(r)

1
2
3
4
5
6
7
8
9
10
11
12
import sys
 
try:
    while True:
        line = sys.stdin.readline()
        x = line.split()
        if len(line.split()) == 1 :
            continue
        else:
            print(int(x[0])+int(x[1]))
except:
    pass

1
2
3
4
5
6
7
8
9
10
import sys
res = []
while True:
    data = [int(e) for e in input().split()]
    if data[0] == data[1] == 0:
        break
    res.append(sum(data))
    
for r in res:
    print(r)

1
2
3
4
5
6
7
8
9
10
import sys

res = []
try:
    while True:
        data = [int(e) for e in input().split()]
        res.append(sum(data))
except:
    for r in res:
        print(r)

1
2
3
4
5
6
7
8
9
10
11
12
import sys
while True:   # 有while True，则只要没有到最底下就会一直循环进入try，直到到底才会进入except
    nums = set()
    try:
        line_num = int(input())
        for _ in range(line_num):
            nums.add(int(input()))
        for i in sorted(list(nums)):
            print(i)
    except:
        pass
            

1
2
3
4
5
6
7
8
9
10
11
import sys
while True:   # 有while True，则只要没有到最底下就会一直循环进入try，直到到底才会进入except
    nums = set()
    try:
        line_num = int(input())
        for _ in range(line_num):
            nums.add(int(input()))
        for i in sorted(list(nums)):
            print(i)
    except:
        pass

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
raw = num = int(input())

res = []
zhi = 2
maxval = int(num**(1/2))  # 注意有变量时要考虑能不能放到while上，可能会变
while num>=zhi and zhi <= maxval :
    if num < zhi:
        break
    if num%zhi == 0:
        res.append(zhi)
        num //= zhi
    else:
        zhi += 1
if num != 1:   # 注意要再判断一下是否找完了质因子
    res.append(num)
    
print(" ".join(map(str,res))+" ")

1
2
3
4
5
6
7
8
9
10
11
12
13
import collections
num_lines = int(input())
res_dict = {}
for i in range(num_lines):
    [index,num] = map(int,input().split())
    if index in res_dict.keys():
        res_dict[index] += num
    else:
        res_dict[index] = num

# 先用items属性将字典变为可迭代对象，再进行排序。key 默认安装key值排序。
for (index,num) in sorted(res_dict.items(), key=lambda x:x[0], reverse=False ):
    print(index,num)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
data = input().split(';')
direction = {'A':(-1,0),'D':(1,0),'W':(0,1),'S':(0,-1)}
pos_x,pos_y = 0,0
for e in data:
    if e and e[0] in 'ADWS':
        if (len(e)==2 and '0' <= e[1] <= '9') or (len(e)==3 and '0' <= e[1] <= '9' and '0' <= e[2] <= '9'):  # 注意0是最小的 '0'<'00'
                pos_x+=direction[e[0]][0]*int(e[1:])
                pos_y+=direction[e[0]][1]*int(e[1:])
print("{},{}".format(pos_x,pos_y))
        
"""
print( c + " 的ASCII 码为", ord(c))
print( a , " 对应的字符为", chr(a))
"""        

1
res = ``"[ADWS]\\d{1}\\d?"``;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import sys
 
#判断子网掩码是否存在非连续的1，（以下是所有连续1的情况）
lll=['254','252','248','240','224','192','128','0']
A, B, C, D, E, err, pri = 0,0,0,0,0,0,0
 
#检测IP是否有效
def check_ip(ip):
    if len(ip)!=4 or " " in ip: return False
    else:
        for i in range(4):
            if int(ip[i])<0 or int(ip[i])>255:
                return False
        return True
     
     
def check_mask(ms):
    if len(ms)!=4:
        return  False
    if ms[0]=='255':
        if ms[1]=='255':
            if ms[2]=='255':
                if ms[3] in lll:
                    return True
                else:
                    return False
            elif ms[2] in lll and ms[3]=='0':
                return True
            else:
                return False
        elif ms[1] in lll and ms[2]==ms[3]=='0':
            return True
        else:
            return False
    elif ms[0] in lll and ms[2]==ms[3]==ms[4]=='0':
        return True
    else:
        return False
 
#主函数
while True:
     
    string=sys.stdin.readline().strip()
    if string=='':
        break
    list1=string.split('~')[0]  #IP地址分割
    list2=string.split('~')[1]  #子网掩码分割
    ip=list1.split('.')
    ms=list2.split('.')
    if check_mask(ms) and check_ip(ip):
        if 1<=int(ip[0])<=126:
            A+=1
        if 128<=int(ip[0])<=191:
            B+=1
        if 192<=int(ip[0])<=223:
            C+=1
        if 224<=int(ip[0])<=239:
            D+=1
        if 240<=int(ip[0])<=255:
            E+=1
        if int(ip[0])==10 or (int(ip[0])==172 and 15<int(ip[1])<32) or (int(ip[0])==192 and int(ip[1])==168):
            pri+=1
    else:
        err+=1
print('%s %s %s %s %s %s %s'%(A,B,C,D,E,err,pri))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
while True:
    try:
        data = input()
        a = b = c = d = 0
        for e in data:
            if e.isdigit():
                a = 1
            elif e.islower():
                b = 1
            elif e.isupper():
                c = 1
            else:
                d = 1
        flag = True
        for j in range(len(data)-3):
            if data.count(data[j:j+3])>1:
                flag = False
        if len(data)>8 and (a+b+c+d)>=3 and flag:
            print('OK')
        else:
            print('NG')
    except:
        break

1
2
3
4
5
6
7
8
9
        for e in data:
            if e.isdigit():
                a = 1
            elif e.islower():
                b = 1
            elif e.isupper():
                c = 1
            else:
                d = 1

1
data.count(data[j:j+3])

1
2
3
4
5
6
7
8
9
while True:
    try:
        a=int(input())
        if a!=0:
            print (a//2)
        else:
            pass
    except:
        break

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
while True:   # 注意会有多行
    try:
        data = input()
        res = list(data)
        temp = []

        for i,e in enumerate(data):
            if ord('A')<=ord(e)<=ord('Z') or ord('a')<=ord(e)<=ord('z'):
                temp.append(e)
        #     else:
        #         res[i] = e
        temp.sort(key=lambda x: ord(x) if ord('A')<=ord(x)<=ord('Z') else ord(x)-32)

        ind = 0
        for i in range(len(res)):
            if ord('A')<=ord(res[i])<=ord('Z') or ord('a')<=ord(res[i])<=ord('z'):   # 注意‘A’到‘Z’和‘a’到‘z’是不连续的
                res[i] = temp[ind]
                ind+=1

        print("".join(res))
        
    except:
        break

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
while True:   # 注意会有多行
    try:
        data = input()
        res = list(data)
        temp = []

        for i,e in enumerate(data):
            if e.isalpha():
                temp.append(e)
        #     else:
        #         res[i] = e
        temp.sort(key=lambda c:c.lower())

        ind = 0
        for i in range(len(res)):
            if res[i].isalpha():   # 注意‘A’到‘Z’和‘a’到‘z’是不连续的
                res[i] = temp[ind]
                ind+=1

        print("".join(res))
        
    except:
        break

1
2
3
4
5
while True:   # 注意会有多行
    try:
    	pass
		except:
			pass

1
if ord('A')<=ord(res[i])<=ord('Z') or ord('a')<=ord(res[i])<=ord('z'):   # 注意‘A’到‘Z’和‘a’到‘z’是不连续的

1
2
3
4
5
6
7
8
9
10
11
12
def operatStr(num):
    num = int(num,16)   #转换成16进制整数
    print('num is:',num)
    bc = format(num,'b').rjust(4,'0')
    print('bc is:',bc)
    bc = list(bc)
    bc.reverse()
    print('last bc is:',bc)
    num = int(''.join(bc),2)
    print('last num is:',num)
    hc = format(num,'x')
    return hc.upper()

1
2
3
4
5
6
7
8
9
10
11
12
# 自己做的: 排序后前后对比
# 90％ 100％
nums = [2, 3, 1, 0, 2, 5, 3]

def findRepeatNumber(nums) -> int:
    nums_sorted = sorted(nums)
    length = len(nums_sorted)
    for i in range(length-1):
        if nums_sorted[i] == nums_sorted[i+1]:
            return nums_sorted[i]
        
findRepeatNumber(nums)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 法2: 原地替换 不如我的高
nums = [2, 3, 1, 0, 2, 5, 3]

def findRepeatNumber(nums) -> int:
    nums_sorted = sorted(nums)
    length = len(nums_sorted)
    for i in range(length):
        while nums_sorted[i] != i:
            if nums_sorted[i] == nums_sorted[nums_sorted[i]]:
                return nums_sorted[i]
            temp = nums_sorted[i]
            nums_sorted[i] = nums_sorted[temp]
            nums_sorted[temp] = temp
            
findRepeatNumber(nums)

1
2
3
4
5
6
7
8
9
10
11
12
# 法3: hash表
nums = [2, 3, 1, 0, 2, 5, 3]

def findRepeatNumber(nums) -> int:
    hashlist = [False for i in range(len(nums))]
    for i in range(len(nums)):
        if hashlist[nums[i]] == True:
            return nums[i]
        else: 
            hashlist[nums[i]] = True
        
findRepeatNumber(nums)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
matrix = [
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]]

matrix = [[5]]

def findNumberIn2DArray(matrix, target):
    if len(matrix)==0 or len(matrix[0])==0:
        return False  
    
    row = 0
    col = len(matrix[0])-1
    while True:
        if matrix[row][col]==target:
            return True

        if matrix[row][col]>target:
            if (col==0): 
                return False
            else: 
                col -= 1
        elif matrix[row][col]<target:
            if (row==len(matrix)-1):
                return False
            else: 
                row += 1
findNumberIn2DArray(matrix, 5)

1
s = "We are happy."

1
2
3
4
5
6
7
8
9
# 90 100 
# 注意replace() 不改变原str内容能提高, 
# 在 Python 和 Java 等语言中，字符串都被设计成不可变的类型，
# 即无法直接修改字符串的某一位字符，需要新建一个字符串实现。
class Solution:
    def replaceSpace(s: str) -> str:        
        return s.replace(' ','%20')

Solution.replaceSpace(s)

1
2
3
4
5
6
# 切割拼接法
class Solution:
    def replaceSpace(s: str) -> str:    
        lst = s.split(' ')
        return '%20'.join(lst)
Solution.replaceSpace(s)

1
head = [1,3,2]

1
2
3
4
5
6
7
8
9
10
class Solution:
    def reversePrint(head):
        res = []
        while head:
            res.append(head.val)
            head = head.next
        return res[::-1]

head = l1
Solution.reversePrint(head)

1
2
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder:
            return None
        root_val = preorder[0]
        ind = inorder.index(root_val)
        print(ind)
        root = TreeNode(root_val)
        root.left = self.buildTree(preorder[1:ind+1], inorder[:ind])
        root.right = self.buildTree(preorder[ind+1:], inorder[ind+1:])
        return root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def recur(root, left, right):
            if left > right: return                               # 递归终止
            node = TreeNode(preorder[root])                       # 建立根节点
            i = dic[preorder[root]]                               # 划分根节点、左子树、右子树
            node.left = recur(root + 1, left, i - 1)              # 开启左子树递归
            node.right = recur(i - left + root + 1, i + 1, right) # 开启右子树递归
            return node                                           # 回溯返回根节点

        dic, preorder = {}, preorder
        for i in range(len(inorder)):
            dic[inorder[i]] = i
        return recur(0, 0, len(inorder) - 1)

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

    def __init__(self):
        self.A, self.B = [], []
        
    def appendTail(self, value: int) -> None:
        self.A.append(value)

    def deleteHead(self) -> int:
        if self.B: return self.B.pop()
        if not self.A: return -1        
        while self.A:
            self.B.append(self.A.pop())
        return self.B.pop()


# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class CQueue:
    def __init__(self):
        self.s1 = []
        self.s2 = []

    def appendTail(self, value: int) -> None:
        self.s1.append(value)

    def deleteHead(self) -> int:
        if len(self.s2) == 0:
            if len(self.s1) == 0:
                return -1
            while self.s1:
                self.s2.append(self.s1.pop())
        return self.s2.pop()

1
n = 43

1
class Solution:    def fib(self, n: int) -> int:        if n == 0: return 0        if n == 1: return 1        fiblist = [0,1]        for i in range(2,n+1):            fiblist.append((fiblist[i-1]+fiblist[i-2])% 1000000007)        return fiblist.pop()                                

1
# 动态规划方法class Solution:    def fib(self, n: int) -> int:        if n == 0: return 0        if n == 1: return 1        a, b = 0, 1        for _ in range(n):            a, b = b, a+b        return a % 1000000007

1
2
3
solution = Solution()
result = solution.fib(n)
result

1
n = 7

1
2
3
4
5
6
7
8
9
class Solution:
    def numWays(self, n: int) -> int:
        if n == 0: return 0
        if n == 1: return 1
        if n == 2: return 2
        a, b = 1, 2
        for _ in range(n-1):
            a, b = b, a+b
        return a%1000000007

1
2
3
solution = Solution()
result = solution.numWays(n)
result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def minArray(self, numbers: List[int]) -> int:
        l, r = 0, len(numbers)-1
        if numbers[0] < numbers[-1]:
            return numbers[0]
        while l <= r:
            mid = (l+r)//2
            if numbers[mid] > numbers[r]:
                l = mid + 1
            elif numbers[mid] < numbers[r]:
                r = mid  # 不同之处， 要保留右边界
            elif numbers[mid] == numbers[r]:  
                r -= 1  # 不同之处，相同需要一步一步走
        if l > len(numbers) - 1 or numbers[l] > numbers[r]:
            return -1
        return numbers[l]

1
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]word = "ABCCED"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k] or (i,j) in visited: return False
            if k == len(word) - 1: return True
            visited.add((i,j))
            res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
            visited.remove((i,j))
            return res

        for i in range(len(board)):
            for j in range(len(board[0])):
                visited = set()
                if dfs(i, j, 0): return True
        return False

1
2
3
m = 2
n = 3
k = 1

1
2
3
m = 38
n = 12
k = 9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# copy
def digitsum(n):
    ans = 0
    while n:
        ans += n % 10
        n //= 10
    return ans

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        from queue import Queue
        q = Queue()
        q.put((0, 0))
        s = set()
        while not q.empty():
            x, y = q.get()
            if (x, y) not in s and 0 <= x < m and 0 <= y < n and digitsum(x) + digitsum(y) <= k:
                s.add((x, y))
                for nx, ny in [(x + 1, y), (x, y + 1)]:
                    q.put((nx, ny))
        return len(s)
        

1
2
solution = Solution()
solution.movingCount(m,n,k)

1
2
3
4
5
6
7
8
class Solution:
    def cuttingRope(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[2] = 1
        for i in range(3, n + 1):
            for j in range(2, i):
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
        return dp[n]

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0:
            return 0
        if n < 0:
            x, n = 1 / x, -n
        res = 1
        while n:
            if n & 1:
                res *= x
            x *= x
            n >>= 1
        return res

1
2
3
4
5
6
7
8
9
10
# 请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配
# 是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。 
# 
#  示例 1: 
# 
#  输入:
# s = "aa"
# p = "a"
# 输出: false
# 解释: "a" 无法匹配 "aa" 整个字符串。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def isNumber(self, s: str) -> bool:
        import re
        pattern = '\s*[+-]?((\d*\.?\d+)|(\d+\.))([Ee][+-]?\d+)?\s*'
        # pattern = "\\s*[+-]?((\\d*\\.?\\d+)|(\\d+\\.?))([eE][+-]?\\d+)?\\s*"
        # pattern = "\\s*[+-]?((\\d+)|(\\d*\\.\\d+)|(\\d+\\.\\d*))([eE][+-]?\\d+)?\\s*"
        sm = re.fullmatch(pattern, s)
        print(sm)
        if sm:
            return True
        else:
            return False

1
        while l1 and l2:            if l1.val <= l2.val:                cur.next = ListNode(l1.val)                l1 = l1.next            else:                cur.next = ListNode(l2.val)                l2 = l2.next            cur = cur.next  # 注意要往下走了！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        def compare(nodeA,nodeB):
            # B 被遍历空，返回True
            if not nodeB:
                return True
            # 防止 A.val 报错, 值不同，返回False
            if not nodeA or nodeA.val != nodeB.val:
                return False
            # 继续递归遍历后续子树是否相同
            return compare(nodeA.left, nodeB.left) or compare(nodeA.right, nodeB.right)
        if not A or not B:
            return False
        # 通过递归将A的结点分别和B进行比较，这里的 or 具有阻断效应，后面的递归调用不执行，直接向上返回
        return compare(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right, B) 

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def isSym(left,right):
            if not left and not right:
                return True
            if not left or not right or left.val != right.val:
                return False
            return isSym(left.left, right.right) and isSym(left.right, right.left)
        if not root:
            return True
        return isSym(root.left,root.right)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        l,r,t,b,res = 0, len(matrix[0])-1, 0, len(matrix)-1, []  # 注意减1啊
        while True :
            print(l,r,t,b,res)
            for i in range(l, r+1):
                res.append(matrix[t][i])
            t += 1
            if t > b: break
            for i in range(t, b+1):
                res.append(matrix[i][r])
            r -= 1
            if r < l: break
            for i in range(r, l-1, -1):
                res.append(matrix[b][i])
            b -= 1  
            if b < t: break          
            for i in range(b, t-1, -1):
                res.append(matrix[i][l])
            l += 1  
            if l > r: break          
        return res

1
2
3
4
5
6
7
8
9
10
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        while matrix:
            res += matrix.pop(0)
            # print(matrix)
            # 逆时针旋转（这里通过转置+倒序实现）
            matrix = list(zip(*matrix))[::-1]
            # print(matrix)
        return res

1
2
3
4
5
6
7
8
9
10
class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = []
        i = 0
        for num in pushed:
            stack.append(num)
            while stack and stack[-1] == popped[i]:
                stack.pop()
                i += 1
        return not stack

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        def recur(i,j):
            if i >= j:
                return True
            p = i
            while postorder[p] < postorder[j]:
                p += 1
            m = p
            while postorder[p] > postorder[j]:
                p += 1
            return p == j and recur(i, m-1) and recur(m, j-1)
        return recur(0, len(postorder)-1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
        def dfs(root, target):
            if not root:
                return

            path.append(root.val)
            target -= root.val

            if not root.left and not root.right and target == 0:
                res.append(path[:])

            dfs(root.left, target)
            dfs(root.right, target)

            target += root.val
            path.pop()

        res = []
        path = []
        dfs(root, target)
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
        dict = {}
        cur = head
        while cur:
            dict[cur] = TreeNode(cur.val)  # 注意要新建！！！！！
            cur = cur.next
        cur = head
        while cur:
            dict[cur].next = dict.get(cur.next)  # 与直接dict[cur.next]不同是其有默认返回值为None
            dict[cur].random = dict.get(cur.random)
            cur = cur.next
        return dict[head]
    

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        def dfs(cur):
            if not cur: return
            dfs(cur.left) # 递归左子树
            if self.pre: # 修改节点引用
                self.pre.right, cur.left = cur, self.pre
            else: # 记录头节点
                self.head = cur
            self.pre = cur # 保存 cur
            dfs(cur.right) # 递归右子树
        
        if not root: return
        self.pre = None
        dfs(root)
        self.head.left, self.pre.right = self.pre, self.head
        return self.head

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections


class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root: return '[]'
        queue = [root]
        res = []
        while queue:
            cur = queue.pop(0)
            if not cur:
                res.append('null')
            else:
                res.append(str(cur.val))  # 注意，只有不是none的cur才放入queue里
                queue.append(cur.left)
                queue.append(cur.right)
        return '[' + ','.join(res) + ']'
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if data == '[]':
            return None
        vals, i = data[1:-1].split(','), 1
        root = TreeNode(int(vals[0]))
        queue = collections.deque()
        queue.append(root)
        while queue:
            cur = queue.popleft()
            if vals[i] != 'null':
                cur.left = TreeNode(int(vals[i]))
                queue.append(cur.left)
            i += 1
            if vals[i] != 'null':
                cur.right = TreeNode(int(vals[i]))
                queue.append(cur.right)
            i += 1
        return root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def permutation(self, s: str) -> List[str]:
        def dfs(s, path):
            if len(path) == len(s):
                res.append(''.join(path))
                return 
            for i in range(len(s)):
                if i not in visited:
                    path.append(s[i])
                    visited.add(i)
                    dfs(s, path)
                    path.pop()
                    visited.remove(i)
        
        res = []
        path = []
        visited = set()
        dfs(s, path)
        return list(set(res))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cur = nums[0]
        count = 1
        for i in range(1, len(nums)):
            if nums[i] == cur:
                count += 1
            else:
                if count == 0:
                    cur = nums[i]
                    count = 1
                else:
                    count -= 1  
        return cur

1
2
3
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        return  heapq.nsmallest(k, arr)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# leetcode submit region begin(Prohibit modification and deletion)
class MedianFinder:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.lnums = []  # 小顶,保存大的
        self.rnums = []  # 大顶，保存小的, heappush(heap, -num) 和 -heappop(heap) 都要取反。（内部存的是负数）
    def addNum(self, num: int) -> None:
        if len(self.lnums) == len(self.rnums):
            heappush(self.rnums, -num)
            heappush(self.lnums, -heappop(self.rnums)) # 插入取反
        if len(self.lnums) != len(self.rnums):
            heappush(self.lnums, num) # 插入取反
            heappush(self.rnums, -heappop(self.lnums)) # 弹出取反
    def findMedian(self) -> float:
        return self.lnums[0] if len(self.lnums) != len(self.rnums) else (self.lnums[0] + (-self.rnums[0]))/2

1
2
    self.lnums = []  # 小顶,保存大的
    self.rnums = []  # 大顶，保存小的, heappush(heap, -num) 和 -heappop(heap) 都要取反。（内部存的是负数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def countDigitOne(self, n: int) -> int:
        digit, res = 1, 0
        high, cur, low = n//10, n%10, 0
        while high != 0 or cur != 0:
            if cur == 0:
                res += high * digit
            elif cur == 1:
                res += high * digit + low + 1
            else:
                res += (high+1)*digit
            low += cur * digit
            cur = high % 10
            high //= 10
            digit *= 10
        return res