python笔试例题（快速排序、冒泡排序、二分查找、最长无重复子串、最长回文串长度、合并两个有序链表、输出数组中两数相加=target的下标、用两个栈实现队列、链表中倒数最后k个结点、反转链表...）_python编程笔试题

快速排序

# arr[] --> 排序数组
# low  --> 起始索引
# high  --> 结束索引
# 1.
def quickSort(nums):
    if len(nums) <= 1:
        return nums

    # 左子数组
    left = []
    # 右子数组
    right = []
    # 基准数
    base = nums.pop()

    # 对原数组进行划分
    for x in nums:
        if x < base:
            left.append(x)
        else:
            right.append(x)

    # 递归调用
    return quickSort(left) + [base] + quickSort(right)
    
# 2.
def quickSort(list):
    if len(list) < 2:
        return list

    mid = list[0]
    left = [i for i in list[1:] if i <= mid]
    right = [i for i in list[1:] if i > mid]
    finallyList = quickSort(left) + [mid] + quickSort(right)
    return finallyList


nums = [6, 1, 2, 7, 9, 3, 4, 5, 5, 10, 8]
print(quickSort(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
31
32
33
34
35
36
37
38
39
40

便捷：list的sort方法

vowels = ['e', 'a', 'u', 'o', 'i']
vowels.sort() #升序
vowels.sort(reverse=True) #降序
1
2
3

选择排序

a=[6,5,3,5,6,7]
for i in range(len(a)-1):
   min = i
   for j in range(i+1,len(a)):
       if a[j]<a[min]:
           min = j
   if i!=min:
       a[i],a[min]=a[min],a[i]

print(a)
1
2
3
4
5
6
7
8
9
10

冒泡排序

#冒泡排序
for i in range(len(seq)-1):
    indicator = False
    for j in range(len(seq)-1-i):
        if seq[j]>seq[j+1]:
            seq[j], seq[j+1] = seq[j+1], seq[j]
            indicator = True
    if not indicator:
    	break
1
2
3
4
5
6
7
8
9

堆排序

def heapify(arr, n, i):
    largest = i
    leftIndex = 2 * i + 1
    rightIndex = 2 * i + 2

    if leftIndex < n and arr[i] < arr[leftIndex]:
        largest = leftIndex

    if rightIndex < n and arr[largest] < arr[rightIndex]:
        largest = rightIndex

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # 交换
        print("largest===", largest)
        if largest * 2 < n:
            heapify(arr, n, largest)


def heapSort(arr):
    n = len(arr)

    # Build a maxheap.
    for parentIndex in range(n // 2 - 1, -1, -1):
        print("父节点索引", parentIndex)
        heapify(arr, n, parentIndex)

    # 交换堆顶元素并从上至下调整为大顶堆
    for i in range(n - 1, 0, -1):
        print("交换元素索引",i)
        arr[i], arr[0] = arr[0], arr[i]  # 交换
        heapify(arr, i, 0)


arr = [-1, 26, 5, 77, 1, 61, 11, 59, 15, 48, 19]
heapSort(arr)
n = len(arr)
print(f'排序后：{arr}')
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

希尔排序

def shellSort(alist):
    n = len(alist)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            j = i
            while j >= gap:
                if alist[j] < alist[j - gap]:
                    alist[j], alist[j - gap] = alist[j - gap], alist[j]
                    j -= gap
                    print(j)

                else:
                    break
        gap //= 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

归并排序

#合并两列表
def merge(list1,list2):#a,b是待合并的两个列表,两个列表分别都是有序的，合并后才会有序
    left = 0
    right = 0
    new_list = []
    while left<len(list1) and right<len(list2):
        if list1[left] <= list2[right]:
            new_list.append(list1[left])
            left += 1
            if left == len(list1):
                new_list += list2[right:]
                break
        else:
            new_list.append(list2[right])
            right += 1
            if right == len(list2):
                new_list += list1[left:]
                break
    return new_list


#递归操作
def mergeSort(s):
    if len(s) == 1:
        return s
    list1 = mergeSort(s[0:len(s) // 2])
    list2 = mergeSort(s[len(s) // 2:])
    return merge(list1, list2)



if __name__ == '__main__':
    s = [1, 7, 4, 8, 5, 9]
    print(mergeSort(s))    
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

二分查找

def search(nums, target):
    left = lowwer_bound(nums, target)
    return left
def lowwer_bound(nums, target):
    left, right = 0, len(nums)-1
    while left < right:
        mid = left + (right - left)//2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    if nums[left] != target:
        return -1
    else:
        return left

print(search(['1','2','3','5','6','7'],'6'))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

便捷:：list string —> 查找

# list
vowels.index('e')
# str
str1 = "this is string example....wow!!!";
str2 = "exam";
print str1.find(str2);
# index未找到会报错
print str1.index(str2);
1
2
3
4
5
6
7
8

最长无重复子串的长度

def maxlen(s):
 	dic = {}
    start = 0
    maxLen = 0
    for i,data in enumerate(s):
        if data in dic:
            start = max(start, dic[data] + 1)
        dic[data] = i
        maxLen = max(maxLen, i - start + 1)
    return maxLen
1
2
3
4
5
6
7
8
9
10

数组中数字出现的次数

1.---
from collections import Counter

# 定义一个数组
arr = [1, 2, 1, 3, 2, 4, 3, 1, 2, 4, 5]

# 使用Counter来统计数组中各数出现的次数
count_dict = Counter(arr)

# 输出每个数的出现次数
for num, count in count_dict.items():
    print(f'{num} 出现的次数为 {count} 次')
1
2
3
4
5
6
7
8
9
10
11
12

2.---
def count_occurrences(arr):
    count_dict = {}
    
    for num in arr:
        if num in count_dict:
            count_dict[num] += 1
        else:
            count_dict[num] = 1
    
    return count_dict

# 定义一个数组
arr = [1, 2, 1, 3, 2, 4, 3, 1, 2, 4, 5]

# 使用算法统计数组中各数出现的次数
count_dict = count_occurrences(arr)

# 输出每个数的出现次数
for num, count in count_dict.items():
    print(f'{num} 出现的次数为 {count} 次')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

最长回文串（长度及第一个最长的回文串）

def getLongestPalindrome(A, n):
    max_len = 0
    odd =""
    even = ""
    for i in range(n):
        oddStr = A[i-max_len-1:i+1]
        evenStr = A[i-max_len:i+1]
        if i-max_len-1>=0 and oddStr == oddStr[::-1]:
            max_len+=2
            odd = oddStr
        elif i-max_len>=0 and evenStr == evenStr[::-1]:
            max_len+=1
            even = evenStr
    palindrome = odd if len(odd)>len(even) else even
    print(odd,even)
    return max_len,palindrome
    
print(getLongestPalindrome("abbabbcccca",11))


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

输出数组中两数相加=target的下标（1开始）

def twoSum(self , numbers , target ):
    dic = {}
    for i in range(len(numbers)):
        temp = target - numbers[i]
        if temp in dic:
            return dic[temp]+1,i+1
        dic[numbers[i]] = i
1
2
3
4
5
6
7

反转英文句子

mystr = "How are you? "
# 去掉首尾空格后分割翻转
arr=mystr.strip().split(" ")
result = ' '.join(reversed(arr))
print(result)
1
2
3
4
5

找出a字符串在b字符串中出出现的次数及所有位置

str='jdfabchjhjabcukghjihhkabc'
s='abc'
start_len=0
showNum = str.count(s)
indexList = []
while True:
      num=str.find(s,start_len)
      if num==-1:  # 找不到则返回-1 index找不到会报错
        break
      indexList.append(num)
      start_len=num+len(s)
print(showNum,indexList)
1
2
3
4
5
6
7
8
9
10
11
12

用两个栈实现队列

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        self.stack1.append(node)
    def pop(self):
        if self.stack2 == []:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()
1
2
3
4
5
6
7
8
9
10
11

F(n)斐波那契数列

    def fib(n: int) -> int:
        a, b = 0, 1
        for _ in range(n):
            a, b = b, a + b
        return a
    print(fib(6))
1
2
3
4
5
6

链表中倒数最后k个结点

 def FindKthToTail(self , pHead , k ):
        # write code here
        length = 0
        lt = pHead
        while lt:
            lt=lt.next
            length+=1
        c=0
        while pHead:
            if c==length-k:
                return pHead
            pHead=pHead.next
            c+=1
1
2
3
4
5
6
7
8
9
10
11
12
13

合并两个有序链表

    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # write code here
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        result=ListNode(-1)
        cur = result
        while pHead1 and pHead2:
            if pHead1.val<=pHead2.val:
                cur.next=pHead1
                pHead1=pHead1.next
            else:
                cur.next=pHead2
                pHead2=pHead2.next
            cur=cur.next
        cur.next=pHead1 if pHead1 else pHead2
        return result.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

反转链表

# 反转链表 给一个表头，返回新链表的表头
#     def __init__(self, x):
#         self.val = x
#         self.next = None
def ReverseList(self, pHead):
    # write code here
    pre = None
    cur = pHead
    while cur:
        tmp = cur.next # 保留下一个即将翻转的表头
        cur.next = pre # 将现在要翻转的节点的后继指向前一个节点 pre
        pre = cur # 现在的 P 成为下一个前继节点
        cur = tmp # p 成为下一个要翻转的节点
    return pre
1
2
3
4
5
6
7
8
9
10
11
12
13
14

连续子数组的最大和

    def FindGreatestSumOfSubArray(self , array: List[int]) -> int:
        # write code here
        sum = array[0]
        presum = 0
        for i in array:
            if presum < 0:
                presum = i
            else:
                presum += i
            sum = max(presum,sum)
        return sum
1
2
3
4
5
6
7
8
9
10
11

链表中的节点每k个一组翻转

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @param k int整型 
# @return ListNode类
#
class Solution:
    def reverseKGroup(self , head: ListNode, k: int) -> ListNode:
        # write code here
        # write code here
        # 用于链表头元素
        Phead = ListNode(None)
        p = Phead
        while head:
            count = k
            stack = []
            tmp = head
            # 进栈
            while count and tmp:
                stack.append(tmp)
                tmp = tmp.next
                count -= 1
            # 跳出上面循环，tmp是第k+1的元素
            # 如果循环结束，count不为0，则代表不足k个元素
            if count:
                p.next = head
                break
            # 对k个元素进行反转
            # 出栈
            while stack:
                p.next = stack.pop()
                p = p.next
            # 与剩下链表链接起来
            p.next = tmp
            head = tmp
        return Phead.next
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

两个链表生成相加链表

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head1 ListNode类 
# @param head2 ListNode类 
# @return ListNode类
#
class Solution:
    def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
        # write code here
        if not head1:
            return head2
        if not head2:
            return head1
        list1=self.pushStack(head1)
        list2=self.pushStack(head2)
        carry=0
        head=ListNode(None)
        h=head
        sumStack=[]
        while list1 or list2 or carry:
            x=list1.pop() if list1 else 0
            y=list2.pop() if list2 else 0
            sum = x + y + carry
            carry = sum // 10
            sumStack.append(sum%10)
        while sumStack:
            h.next=ListNode(sumStack.pop())
            h=h.next
        return head.next
    
    def pushStack(self,node:ListNode):
        s=[]
        while node:
            s.append(node.val)
            node=node.next
        return s

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

删除倒数第n个节点

#  1.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @param n int整型 
# @return ListNode类
#
class Solution:
    def removeNthFromEnd(self , head: ListNode, n: int) -> ListNode:
        # write code here
        if not head:
            return None
        slow=head
        fast=head
        for i in range(n):
            fast=fast.next
        if not fast:
            return head.next
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next=slow.next.next
        return head

# 2.
    def removeNthFromEnd(self , head: ListNode, n: int) -> ListNode:

        dic = {}
        cur = head
        i = 0
        while cur:
            dic.update({i: cur})
            cur = cur.next
            i += 1
        if i == n:
            return head.next
        elif n == 1:
            dic[i - n - 1].next = None
        else:
            dic[i - n - 1].next = dic[i - n + 1]
        return 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

判断链表中是否有环

#1.
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        visited = set() 
        while head:
            cur = head
            if cur not in visited:
                visited.add(cur)
            else:
                return True
            head = head.next 
        return False 
        
#2.快慢指针法
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head:
            return False 

        slow = head 
        fast = head.next 

        while fast and fast.next:
            if fast ==slow:
                return True 
            fast= fast.next.next 
            slow = slow.next 
            
        return False 

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

删除有序链表中重复的元素

#  1.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        # write code here 
        if not head:
            return head
        #cur指向头结点
        cur = head
        #当cur.next不为空时
        while cur.next:
            #如果值相同，删除cur.next节点
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            #否则cur后移
            else:
                cur = cur.next
        return head

# 2.超时
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        # write code here 
        if not head or head.next==None:
            return head
        res=ListNode(-1)
        p=res
        s=[]
        while head:
            if head.val not in s:
                s.append(head.val)
            else:
                s.remove(head.val)
        s.reversed()
        for i in s:
            p.next=ListNode(i)
            p=p.next
        return res.next

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

有效括号序列

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return bool布尔型
#
class Solution:
    def isValid(self , s: str) -> bool:
        # write code here
        stack=[]
        for i in range(len(s)):
            if s[i]=='(':
                stack.append(')')
            elif s[i]=='{':
                stack.append('}')
            elif s[i]=='[':
                stack.append(']')
            else:
                if not stack or s[i]!=stack[len(stack)-1]:
                    return False
                stack.pop()
        if not stack:
            return True
        else:
            return False
         
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

最长公共子串

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# longest common substring
# @param str1 string字符串 the string
# @param str2 string字符串 the string
# @return string字符串
#
class Solution:
    def LCS(self , str1: str, str2: str) -> str:
        # write code here
        m=len(str1)
        n=len(str2)
        # m列 n行的二维数组
        dp=[[0 for _ in range(m+1)] for _ in range(n+1)]
        #起始字符串位置
        startIndex=-1
        max_len=0
        for i in range(1,n+1):
            for j in range(1,m+1):
                if str1[j-1]==str2[i-1]:
                    dp[i][j]=dp[i-1][j-1]+1
                    if dp[i][j]>max_len:
                        max_len=dp[i][j]
                        startIndex=i-max_len
                else:
                    dp[i][j]=0
        return str2[startIndex:startIndex+max_len]
# 两行三列的二维数组
# at=[[0]*3]*2
# print("at----",at)
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

树的遍历

class Node(object):
    def __init__(self,val,left=None,right=None):
        self.val = val
        self.left = left
        self.right = right

node = Node("A",Node("B",Node("D"),Node("E")),Node("C",Node("F"),Node("G")))
# 前序遍历
def PreTraverse(root):
    if root == None:
        return
    print(root.val,end=" ")
    PreTraverse(root.left)
    PreTraverse(root.right)

# 中序遍历
def MidTraverse(root):
    if root == None:
        return
    MidTraverse(root.left)
    print(root.val,end=" ")
    MidTraverse(root.right)

# 后序遍历
def AfterTraverse(root):
    if root == None:
        return
    AfterTraverse(root.left)
    AfterTraverse(root.right)
    print(root.val,end=" ")

print("前序遍历",end="")
PreTraverse(node)
print("")
print("中序遍历",end="")
MidTraverse(node)
print("")
print("后序遍历",end="")
AfterTraverse(node)
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

根据前序+中序或后序+中序还原二叉树

1. 前序+中序

# 全局变量记录遍历的结果
result = []

# 前序
def dfs_before(root):
    if root == None:  # 遇到None，说明不用继续搜索下去
        return
    result.append(root)
    dfs_before(root.left)
    dfs_before(root.right)


# 中序遍历
def dfs_middle(root):
    if root == None:
        return
    dfs_middle(root.left)
    result.append(root)
    dfs_middle(root.right)


# 后序遍历
def dfs_after(root):
    if root == None:
        return
    dfs_after(root.left)
    dfs_after(root.right)
    result.append(root)


# 前序+中序重建二叉树
# arr1：前序遍历结果
# arr2：中序遍历结果
def before_middle_bintree(arr1, arr2):
    if len(arr1) == 0:      # 递归边界：如果某棵子树为空，直接返回这棵子树的根节点：空
        return None
    else:
        root = arr1[0]      # 根据前序遍历结果得知根节点
        root_location = -1
        for i, x in enumerate(arr2):        # 找到根节点在中序遍历结果数组当中的位置
            if root == x:
                root_location = i
                break

        # 切割左右子树对应的中序遍历
        left_arr2 = arr2[0:root_location]   # 左子树的中序遍历结果
        right_arr2 = arr2[root_location+1:] # 右子树的中序遍历结果

        # 求左右子树的长度
        num_left = len(left_arr2)
        num_right = len(right_arr2)

        # 依据左右子树的长度，找到左右子树对应的前序遍历结果
        left_arr1 = arr1[1:1+num_left]  # 左子树的前序遍历结果（要刨去根节点，所以从1开始）
        right_arr1 = arr1[1+num_left:]  # 右子树的前序遍历结果（从左子树的最后一个元素的后一个开始）

        left_root = before_middle_bintree(left_arr1, left_arr2) # 递归重建左子树，返回左子树根节点
        right_root = before_middle_bintree(right_arr1, right_arr2)  # 递归重建右子树，返回右子树根节点

        return Node(root, left_root, right_root)    # 重建整棵树

if __name__ == "__main__":

    # 前序+中序还原二叉树
    arr1 = ['A', 'B', 'D', 'E', 'G', 'C', 'F']  # 前序遍历结果
    arr2 = ['D', 'B', 'G', 'E', 'A', 'C', 'F']  # 中序遍历结果
    root = before_middle_bintree(arr1, arr2)    # 重建

    dfs_before(root)
    print([x.val for x in result]) # 检测
    result = []
    dfs_middle(root)
    print([x.val for x in result])  # 检测


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
66
67
68
69
70
71
72
73
74
75

2. 中序+后序

# 后序+中序重建二叉树
# arr1：后序遍历
# arr2：中序遍历
def after_middle_bintree(arr1, arr2):
    if len(arr1) == 0:
        return None
    else:
        root = arr1[-1]
        root_location = -1
        # 找到根节点在中序遍历中的位置
        for i, x in enumerate(arr2):
            if x == root:
                root_location = i
                break
        left_arr2 = arr2[0:root_location]   # 左子树的中序遍历结果
        right_arr2 = arr2[root_location+1:] # 右子树的中序遍历结果

        num_left = len(left_arr2)   # 左子树的节点个数
        num_right = len(right_arr2) # 右子树的节点个数

        left_arr1 = arr1[0:num_left]    # 左子树的后序遍历结果
        right_arr1 = arr1[num_left:-1]  # 右子树的后序遍历结果

        left_root = after_middle_bintree(left_arr1, left_arr2)      # 递归重建左子树
        right_root = after_middle_bintree(right_arr1, right_arr2)   # 递归重建右子树

        return Node(root, left_root, right_root)    # 重建整棵树
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

求二叉树每层节点最大值

class Node:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
def greatest_nodes(root):
    if not root:
        return None

    nodeArr = [root]
    res = []
    while nodeArr:
        nextCheckNodeArr = []
        checkArr = []
        for node in nodeArr:
            if not node:
                continue
            checkArr.append(node.val)
            if node.left:
                nextCheckNodeArr.append(node.left)
            if node.right:
                nextCheckNodeArr.append(node.right)

        nodeArr = nextCheckNodeArr
        res.append(max(checkArr))
    return res
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

求二叉树中的最大节点

    maxTag = None
    node = None
    def maxNode(self,node):
        self.maxTag = None
        if not node:
            return None
        self.maxCheck(node)
        return self.maxTag
        
    def maxCheck(self,root): # 递归，循环二叉树所有节点对象，将最大值的节点对象赋值给node
        if root is None:
            return None
        if root.val > self.maxTag:
            self.maxTag = root.val
            self.node = root
        self.maxCheck(root.left)
        self.maxCheck(root.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二叉树的最大深度

def maxDepth(self , root: TreeNode) -> int:
        # write code here
        if root is None:
            return 0
        if root.left is None and root.right is None:
            return 1
        return  max(self.maxDepth(root.left),self.maxDepth(root.right))+1
1
2
3
4
5
6
7

筛选数组中重复元素

def duplicates(self, arr):
    hashset = set()
    duplication = []
    for i in arr:
        if i not in hashset:
            hashset.add(i)
        else:
            duplication.append(i)
    return duplication

1
2
3
4
5
6
7
8
9
10

5个扑克牌是否是顺子，大小王当成任意的

    def IsContinuous(self, numbers):
        if numbers == None or len(numbers) <= 0:
            return False
        # 把A、J、Q、K转化一下
        transDict = {'A': 1, 'J': 11, 'Q': 12, 'K': 13}
        for i in range(len(numbers)):
            if numbers[i] in transDict:
                numbers[i] = transDict[numbers[i]]

        numbers = sorted(numbers)
        numberOfzero = 0
        numberOfGap = 0

        # 统计0的个数
        i = 0
        while i < len(numbers) and numbers[i] == 0:
            numberOfzero += 1
            i += 1
        # 统计间隔的数目
        small = numberOfzero
        big = small + 1
        while big < len(numbers):
            # 出现对子, 不可能是顺子
            if numbers[small] == numbers[big]:
                return False

            numberOfGap += numbers[big] - numbers[small] - 1
            small = big
            big += 1
        return False if numberOfGap > numberOfzero else True

test = ['A', 3, 2, 5, 0]
test2 = [0, 3, 1, 6, 4]
print(IsContinuous(test2))
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

青蛙跳

# 青蛙跳：一次跳一个台阶/两个台阶
def frog(num):
    a = b =1
    for i in range(num):
        a,b=b,a+b
    return a

# 青蛙跳：一次跳一个台阶/两个台阶/n个台阶
def frog(num):
    if num==0:
        return 0
    return 2**(num-1)
1
2
3
4
5
6
7
8
9
10
11
12