目录

数据结构定义:

In [1]:
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
        
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# 宽度优先遍历,即从上到下逐层打印
def print_tree(root_node):
    travers = []
    queue = [root_node]
    while len(queue) > 0:
        farther = queue.pop()
        travers.append(farther.val)
        if farther:
            if farther.left:
                queue.insert(0, farther.left)
            if farther.right:
                queue.insert(0, farther.right)
    print(" ".join(map(str, travers)))
    
def print_list(head_node):
    vals = []
    while head_node:
        vals.append(head_node.val)
        head_node = head_node.next
    if len(vals) > 0:
        print(" ".join(map(str, vals)))
    else:
        print("This node list is empty!")

3.数组中重复的数字

在一个长度是n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3},那么对应的输出是重复的数字2或者3.

In [68]:
# 测试用例
test1 = []
test2 = [1]
test3 = [1,2]
test4 = [1,2,1]
In [69]:
# 解题思路:将数据放入哈希表中,查找每次查找重复数字只需O(1)
# 复杂度:O(n)
def findrepeat(a):
    m = {}
    for key,val in enumerate(a):
        if val in m:
            return val
        else:
            m[val] = key
    return []
In [70]:
print(findrepeat(test1))
print(findrepeat(test2))
print(findrepeat(test3))
print(findrepeat(test4))
[]
[]
[]
1

4.二维数组的查找

在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

In [71]:
# 测试用例
test1 = []
test2 = [[]]
test3 = [[1],
         [1]]
test4 = [[1,2],
         [3,4]]
In [72]:
# 从右上角开始判断,如果小于则在左面,如果大于则在右面
# 复杂度:O(m*n)
def findnum(arr,target):
    m = len(arr)
    if m<1:
        return False
    n = len(arr[0])
    if n <1:
        return False
    m -= 1
    n -= 1
    while m >= 0 and n >= 0:
        if arr[m][n] < target:
            m -= 1
            continue
        elif arr[m][n] > target:
            n -= 1
            continue
        else:
            return True
    return False
In [73]:
print(findnum(test1,1))
print(findnum(test2,1))
print(findnum(test3,1))
print(findnum(test4,1))
False
False
True
False

6.从尾到头打印链表

问题描述:输入一个链表的头结点,从尾到头反过来打印出每个结点的值。

In [74]:
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node1.next = node2
node2.next = node3
In [75]:
def printListFromTailToHead(List):
    stack = []
    while List.next:
        stack.append(List.val)
        List = List.next
    stack.append(List.val)
    print(stack[::-1])
In [76]:
printListFromTailToHead(node1)
printListFromTailToHead(node1)
[3, 2, 1]
[3, 2, 1]

7.重建二叉树

问题描述:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出二叉树并输出它的头结点。

解这道题首先要弄明白前序遍历,中序遍历,后序遍历的概念:

  • 前序遍历:先访问根节点,再访问左节点和右节点
  • 中序遍历:先访问左节点,然后访问根节点,最后访问右节点
  • 后序遍历:先访问左节点和右节点,最后访问根节点 这里的前序,中序,后序是指访问根节点的顺序。

解题思路:

  1. 首先根据前序遍历的第一个值确定根结点。
  2. 根节点在中序遍历的左边是左子树,右边是右子树。
  3. 递归对左子树及右子树进行上述操作即可重建二叉树。

In [85]:
test1_front_list = [1,2,4,7,3,5,6,8]
test1_middle_list = [4,7,2,1,5,3,8,6]

test2_front_list = []
test2_middle_list = []
In [86]:
def rebuild_tree(front_list,middle_list):
    if len(front_list)<1 or len(middle_list)<1:
        return None
    root = TreeNode(front_list[0])
    index_mid = middle_list.index(front_list[0])
    root.left = rebuild_tree(front_list[1:index_mid+1],middle_list[:index_mid])
    root.right = rebuild_tree(front_list[index_mid+1:],middle_list[index_mid+1:])
    return root
In [87]:
tree = rebuild_tree(test1_front_list,test1_middle_list)
print_tree(tree)
1 2 3 4 5 6 7 8

9.用两个栈实现队列

问题描述:用两个栈实现一个队列。请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入结点和在队列头部删除结点的功能。

解题思路:

  • 将队列中的数据依次压入第一个栈中,相当于队列正序,可以删除队列末尾。
  • 将第一个栈中的数据依次转移到第二个栈中,相当与队列逆序,此时可以删除队列头
In [97]:
class Queue():
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
        
    def appendTail(self,x):
        if len(self.stack2) > 1:
            while len(self.stack2):
                self.stack1.append(self.stack2.pop())
        self.stack1.append(x)
        
    def deleteHead(self):
        if len(self.stack1) > 1:
            while len(self.stack1):
                self.stack2.append(self.stack1.pop())
        self.stack2.pop()
        
    def print(self):
        if self.stack1:
            print(self.stack1)
        else:
            print(self.stack2)
In [101]:
q = Queue()
q.appendTail(1)
q.appendTail(2)
q.appendTail(3)
q.deleteHead()
q.appendTail(4)
q.deleteHead()
q.appendTail(5)
q.print()
[3, 4, 5]

10.斐波那契数列

问题描述:写一个函数,输入n,求斐波那契(Fibonacci)数列的第n项。

11.旋转数组的最小数字

问题描述:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。

In [109]:
test1 = []
test2 = [3,4,5,2,3]
test3 = [3,4,5]
test4 = [1,2,3]
In [114]:
def search(arr):
    if len(arr)<1:
        return -1
    i = 0
    j = len(arr)-1
    if arr[j]>arr[i]:
        return arr[i]
    
    while j-i>1:
        k = int((i+j)/2)
        if arr[k]>arr[i]:
            i = k
        else:
            j = k
    if j >=0:
        return arr[j]
    else:
        return -1
In [116]:
print(search(test1))
print(search(test2))
print(search(test3))
print(search(test4))
-1
2
3
1

12.矩阵中的路径

问题描述:请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。例如下面矩阵中包含路径“bfce”,但不包含“atsd”.

In [1]:
matrix = [["a", "b", "t", "g"], 
          ["c", "f", "c", "s"], 
          ["j", "d", "e", "h"]]
In [26]:
def dfs(G,path):
    if len(G)<1:
        return False
    if len(G[0])<1:
        return False
    m = ''
    for i in range(len(G)):
        for j in range(len(G[0])):
            if dfs_visit(G,path,m,i,j):
                return True
    return False
            
def dfs_visit(G,path,m,i,j):
    newstr = m+G[i][j]
    if newstr != path[:len(newstr)]:
        return False
    
    m = newstr
    #print(m)
    if newstr ==path:
        return True

    # 上
    if i >0:
        if dfs_visit(G,path,m,i-1,j):
            return True
    # 下
    if i<len(G)-1:
        if dfs_visit(G,path,m,i+1,j):
            return True
    # 左
    if j > 0:
        if dfs_visit(G,path,m,i,j-1):
            return True
    # 右
    if j<len(G[0])-1:
        if dfs_visit(G,path,m,i,j+1):
            return True
In [27]:
print(dfs(matrix,'bfce'))
print(dfs(matrix,'atsd'))
print(dfs(matrix,'shed'))
True
False
True

13.机器人的运动范围

问题描述:地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。请问该机器人能够达到多少个格子?例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。

In [82]:
def robot(limit):
    i = 0
    j = 0
    stack = []
    m = {}
    robot_visit(m,limit,stack,i,j)
    print(stack)
    return len(stack)

def robot_visit(m,limit,stack,i,j):
    key = str(i)+'_'+str(j)
    if key in m:
        return
    m[key] = 1
    if i+j > limit:
        return
    stack.append((i,j))
    if i>0:
        robot_visit(m,limit,stack,i-1,j)
    if j>0:
        robot_visit(m,limit,stack,i,j-1)
    robot_visit(m,limit,stack,i+1,j)
    robot_visit(m,limit,stack,i,j+1)
In [83]:
robot(5)
[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (4, 1), (3, 1), (2, 1), (1, 1), (0, 1), (0, 2), (1, 2), (2, 2), (3, 2), (2, 3), (1, 3), (0, 3), (0, 4), (1, 4), (0, 5)]
Out[83]:
21

14.剪绳子

问题描述:给定一根长度为n的绳子,请把绳子剪成m段(m、n都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]* k[1] * … *k[m]可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

思路: 最优的裁剪方案总可以分为两段最优的裁剪方案,即 $$c[i,j] = c[i,k]*c[k+1,j]$$ 其中k可以通过遍历得到:

$$ c[ i , j ] = \left\{ \begin{array} { ll } { 1 } &{如果i=j}\\ { \max _ { i \leq k < j } \left\{ c[ i , k ] + c[ k + 1 , j ]\right\} }&{如果i<j} \end{array} \right. $$

因为长绳子只以来于短绳子,所以可以自底向上,从段绳子到长绳子建立动态规划。

In [133]:
def cutrope(n):
    m = [1 for _ in range(n)]
    
    for l in range(n):
        q = 1
        for k in range(n):
            q = max(q,k*m[l-k])
        m[l] = q
    return m[n-1]
In [135]:
cutrope(5)
Out[135]:
16

15.二进制中1的个数

问题描述:请实现一个函数,输入一个整数,输出该数二进制表示中1的个数。例如把9表示成二进制是1001,有2位是1。因此如果输入9,该函数输出2。

使用位运算解此题:

In [144]:
def bincount(num):
    flag = 1
    count = 0
    i = 0
    while i<32:
        i +=1
        if num & flag:
            count +=1
        flag = flag <<1
    return count
In [145]:
bincount(9)
Out[145]:
2

16.数值的整数次方

问题描述:实现pow()函数,对数据取整数次方,不需要考虑大数问题。

In [156]:
def power(num,p):
    if p == 0:
        return 1
    pp = int(abs(p))
    result = 1
    for i in range(pp):
        result = result*num
    if p<0:
        return 1/result
    return result
In [157]:
power(2,-4)
Out[157]:
0.0625

18.在O(1)时间删除链表结点

问题描述:给定单向链表的头指针和一个结点指针,定义一个函数在O(1)时间删除该结点

这道题有点脑筋急转弯啊,没有直接删除节点,而是把后一个节点的内容复制到这个节点,然后把后一个节点删掉。需要注意节点是最后一个节点的情况。

19.正则表达式匹配

问题描述:请实现一个函数用来匹配包括.*的正则表达式。模式中的字符.表示任意一个字符,而*表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串aaa与模式a.aab*ac*a匹配,但是与aa.aab*a均不匹配。

20.表示数值的字符串

问题描述:请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。

21.调整数组顺序使奇数位于偶数前面

问题描述:输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分.

In [94]:
test1 = []
test2 = [1]
test3 = [1,2,3,2,6,4,2,7,8,9]
test4 = [1,2,3,4,4,4,4,6,4,2,7,8,9]
In [97]:
def sortbyoddeven(arr):
    if len(arr)<2:
        return arr
    
    i = -1
    j = len(arr)
    while j-i!=1:
        if arr[i+1] %2 ==1:
            i +=1
        else:
            arr[j-1],arr[i+1] = arr[i+1],arr[j-1]
        if arr[j-1]%2 ==0:
            j -=1
        else:
            arr[j-1],arr[i+1] = arr[i+1],arr[j-1]
    return arr
In [98]:
print(sortbyoddeven(test1))
print(sortbyoddeven(test2))
print(sortbyoddeven(test3))

print(sortbyoddeven(test4))
[]
[1]
[1, 9, 3, 7, 6, 4, 2, 2, 8, 2]
[1, 9, 3, 7, 4, 6, 4, 4, 4, 2, 4, 8, 2]

22.链表中倒数第k个节点

问题描述:输入一个链表,输出该链表中倒数第k个结点。为符合计数习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。如:一个链表有6个节点,从头节点开始,它们的值一次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

In [124]:
# 准备测试数据,倒数第3个节点应该为4
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n5 = ListNode(5)
n6 = ListNode(6)
n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n5
n5.next = n6

这题很开阔思维。。。用了两个指针,保持k-1个距离。。。注意倒数第1个和倒数第k个距离为k-1

In [131]:
def printkthNode(n,k):
    head1 = n
    for _ in range(k-1):
        head1 = head1.next
    
    head2 = n
    while head1.next:
        head1 = head1.next
        head2 = head2.next
    return head2.val
In [132]:
printkthNode(n1,3)
Out[132]:
4

23.链表中环的入口节点

问题描述:如果一个链表中包含环,请找出该链表的环的入口结点。如:在1->2->3->4->5->6->3的链表中,包含一个环,环的入口节点是3。

In [137]:
# 测试数据
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n5 = ListNode(5)
n6 = ListNode(6)
n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n5
n5.next = n6
n6.next = n3

剑指offer中给出用双指针解这道题,但是我觉着用哈希表做更简单。

In [142]:
def printEnterNode(node):
    head = node
    m = {}
    while head.next:
        if head.val in m:
            return head.val
        m[head.val] = 1
        head = head.next
    return None
In [143]:
printEnterNode(n1)
Out[143]:
3

24.反转链表

问题描述:输入一个链表的头节点,反转链表并输出反转链表的头节点。

In [2]:
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n5 = ListNode(5)
n6 = ListNode(6)
n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n5
n5.next = n6

三个指针,i,j,k分别代表已经反转的链表,正在改变的节点和未改变的链表

In [3]:
def reverseList(List):
    i = List
    j = i.next
    if j == None:
        return i
    k = j.next
    if k == None:
        i.next = None
        j.next = i
        return j
    
    i.next = None
    while k.next!=None:
        j.next = i
        i = j
        j = k
        k = k.next
    j.next = i
    k.next = j
    
    return k
In [4]:
newlist = reverseList(n1)
print_list(newlist)
6 5 4 3 2 1

25.合并两个排序的链表

问题描述:输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调递增规则。如:链表1:1->3->5;链表2:2->4->6;合并后为:1->2->3->4->5->6。

In [15]:
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n5 = ListNode(5)
n6 = ListNode(6)
n1.next = n3
n3.next = n5
n2.next = n4
n4.next = n6
In [16]:
def margeList(head1,head2):
    if head1 == None:
        return head2
    if head2 == None:
        return head1
    if head1.val < head2.val:
        newlist = margeList(head1.next,head2)
        head1.next = newlist
        return head1
    else:
        newlist = margeList(head1,head2.next)
        head2.next = newlist
        return head2
In [17]:
listAfterMarge = margeList(n1,n2)
print_list(listAfterMarge)
1 2 3 4 5 6

26.树的子结构

问题描述:输入两棵二叉树A和B,判断B是不是A的子结构。

In [49]:
def hasSubtree(tree1, tree2):
    if not tree1 or not tree2:
        return False
    if tree1.val == tree2.val:
        if tree1hastree2(tree1,tree2):
            return True
    return hasSubtree(tree1.left, tree2) or hasSubtree(tree1.right, tree2)
    
def tree1hastree2(tree1,tree2):
    if tree2 is None:
        return True
    if tree1 is None:
        return False
    if tree1.val != tree2.val:
        return False
    if sametree(tree1.right,tree2.right) and sametree(tree1.left,tree2.left):
        return True
In [50]:
n1 = TreeNode(8)
n2 = TreeNode(8)
n3 = TreeNode(7)
n4 = TreeNode(9)
n5 = TreeNode(2)
n6 = TreeNode(4)
n7 = TreeNode(7)

n8 = TreeNode(8)
n9 = TreeNode(9)
n10 = TreeNode(2)

n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n5.left = n6
n6.right = n7

print_tree(n1)

n8.left = n9
n8.right = n10

print_tree(n8)

print(hasSubtree(n1, n8))
8 8 7 9 2 4 7
8 9 2
True

27.二叉树的镜像

问题描述:输入一棵二叉树,输出它的镜像。

In [60]:
def mirrotree(tree):
    if tree == None:
        return None
    tree.left,tree.right = mirrotree(tree.right),mirrotree(tree.left)
    return tree
In [61]:
n1 = TreeNode(8)
n2 = TreeNode(6)
n3 = TreeNode(10)
n4 = TreeNode(5)
n5 = TreeNode(7)
n6 = TreeNode(9)
n7 = TreeNode(11)

n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
n3.right = n7

print_tree(n1)

mirrotree(n1)

print_tree(n1)
8 6 10 5 7 9 11
8 10 6 11 9 7 5

28.对称的二叉树

问题描述:请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

In [62]:
def symmetry(tree):
    return issmmetry(tree,tree)

def issmmetry(tree1,tree2):
    if not tree1 and not tree2:
        return True
    if not tree1 or not tree2:
        return False
    if tree1.val !=tree2.val:
        return False
    return issmmetry(tree1.left,tree2.right) and issmmetry(tree1.right,tree2.left)
In [64]:
n1 = TreeNode(8)
n2 = TreeNode(6)
n3 = TreeNode(6)
n4 = TreeNode(5)
n5 = TreeNode(7)
n6 = TreeNode(7)
n7 = TreeNode(5)

n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
n3.right = n7

print_tree(n1)
print(symmetry(n1))

n3.val = 9

print_tree(n1)
print(symmetry(n1))

n3.val = 6
n3.right = None

print_tree(n1)
print(symmetry(n1))
8 6 6 5 7 7 5
True
8 6 9 5 7 7 5
False
8 6 6 5 7 7
False

29.顺时针打印矩阵

问题描述:输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。

In [82]:
def clockwiseprint(arr):
    clockwise(arr,0)

def clockwise(arr,offset):
    if len(arr)<1:
        return
    if len(arr[0])<1:
        return
    # 计算长宽的开始位置结束位置,及长度
    l_start = offset
    l_end = len(arr)-offset-1
    w_start = offset
    w_end = len(arr[0])-offset-1
    if l_end <0:
        return
    if w_end<0:
        return
    #上
    for i in range(l_start,l_end):
        print(arr[w_start][i])
    #右
    for i in range(w_start,w_end):
        print(arr[i][l_end])
    #下
    for i in range(l_start+1,l_end+1)[::-1]:
        print(arr[w_end][i])
    #左
    for i in range(w_start+1,w_end+1)[::-1]:
        print(arr[i][l_start])
        
    clockwise(arr,offset+1)
In [83]:
numbers = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
clockwiseprint(numbers)
1
2
3
4
8
12
16
15
14
13
9
5
6
7
11
10

30.包含min函数的栈

问题描述:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中,调用min、push及pop的时间复杂度都是O(1)。

In [84]:
class MinStack:
    def __init__(self):
        self.min_stack = []
        self.data_stack = []
    def push(self, value):
        if len(self.min_stack) == 0 or self.min_stack[-1] > value:
            self.min_stack.append(value)
        else:
            self.min_stack.append(self.min_stack[-1])
        self.data_stack.append(value)
    def pop(self):
        assert len(self.min_stack) > 0 and len(self.data_stack) > 0
        self.min_stack.pop()
        return self.data_stack.pop()
    def min_val(self):
        assert len(self.min_stack) > 0 and len(self.data_stack) > 0
        return self.min_stack[-1]
In [85]:
ms = MinStack()
ms.push(3)
ms.push(2)
ms.push(1)
print(ms.min_val())
ms.pop()
print(ms.min_val())
1
2

31.栈的压入、弹出序列

问题描述:输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)

In [91]:
def ispoporder(arr1,arr2):
    if len(arr1) != len(arr2):
        return False
    m = {}
    for key,val in enumerate(arr1):
        m[val] = key
    
    k = 0
    stack = []
    for i in arr2:
        if m[i] >= k:
            for p in arr1[k:m[i]+1]:
                stack.append(p)
            k = m[i]+1
        if i != stack.pop():
            return False
    return True
In [93]:
print(ispoporder([1,2,3,4,5], [4,5,3,2,1]))
print(ispoporder([1,2,3,4,5], [4,3,5,1,2]))
True
False

32.从上到下打印二叉树

问题描述:从上倒下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。

In [246]:
from collections import deque

def print_tree(tree):
    stack = []
    Q = deque()
    Q.append(tree)
    while len(Q):
        n = Q.popleft()
        stack.append(n.val)
        if n.left:
            Q.append(n.left)
        if n.right:
            Q.append(n.right)
    return stack    
In [104]:
n1 = TreeNode(8)
n2 = TreeNode(6)
n3 = TreeNode(10)
n4 = TreeNode(5)
n5 = TreeNode(7)
n6 = TreeNode(9)
n7 = TreeNode(11)

n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
n3.right = n7

print_tree(n1)
Out[104]:
[8, 6, 10, 5, 7, 9, 11]

33.二叉搜索树的后序遍历序列

问题描述:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。

思路:根据后序遍历结果可以知道哪些值是左子树的,哪些值是右子树的,哪个值是根节点。根节点是最优一个值,第一个大于根结点开始的值是右子树的值,前面的是左子树的值。递归的判断是否满足二叉搜索树的条件即可。

In [120]:
def isSearchTree(arr):
    if len(arr)<3:
        return True
    k = 0
    while arr[k]<arr[len(arr)-1]:
        k +=1
    for i in range(k,len(arr)-1):
        if arr[i] < arr[len(arr)-1]:
            return False
    return isSearchTree(arr[:k]) and isSearchTree(arr[k:len(arr)-1])
In [122]:
seq = [5,7,6,9,11,10,8]
print(isSearchTree(seq))

seq = [7,4,6,5]
print(isSearchTree(seq))
True
False

34.二叉树中和为某一值的路径

问题描述:输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

In [163]:
def FindPath(tree,n):
    s = 0
    paths = []
    path = []
    getPathEqs(paths,path,s,tree,n)
    return paths

def getPathEqs(paths,path,s,tree,n):
    if not tree:
        return
    path.append(tree.val)
    s += tree.val
    if s == n and not tree.right and not tree.left:
        paths.append(path.copy())
    getPathEqs(paths,path,s,tree.left,n)
    getPathEqs(paths,path,s,tree.right,n)
    path.pop()
In [164]:
n1 = TreeNode(10)
n2 = TreeNode(5)
n3 = TreeNode(12)
n4 = TreeNode(4)
n5 = TreeNode(7)
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
FindPath(n1, 22)
Out[164]:
[[10, 5, 7], [10, 12]]

35.复杂链表的复制

36.二叉搜索树与双向链表

问题描述:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

In [173]:
def Convert(root):
    # last_node_in_list指向已经转换好的链表的最后一个节点(值最大的节点)
    # 放在list里实现引用传递
    last_node_in_list = [None]
    ConvertNode(root, last_node_in_list)
    # 找到头节点,并返回
    head_node_in_list = last_node_in_list[0]
    while head_node_in_list is not None and head_node_in_list.left is not None:
        head_node_in_list = head_node_in_list.left
    return head_node_in_list

def ConvertNode(root, last_node_in_list):
    if root is None:
        return
    cur = root
    # 左子树
    if cur.left is not None:
        ConvertNode(cur.left, last_node_in_list)
    # 当前节点指向转换好的左子树的最后一个节点
    cur.left = last_node_in_list[0]
    # 左子树最后一个节点指向当前节点
    if last_node_in_list[0] is not None:
        last_node_in_list[0].right = cur
    # 当前节点成为最后一个节点
    last_node_in_list[0] = cur
    # 处理右子树并传如已经处理好的最后一个节点
    if cur.right is not None:
        ConvertNode(cur.right, last_node_in_list)
In [174]:
n1 = TreeNode(10)
n2 = TreeNode(5)
n3 = TreeNode(12)
n4 = TreeNode(4)
n5 = TreeNode(7)
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
head = Convert(n1)
while head:
    print(head.val, end=" ")
    head = head.right
4 5 7 10 12 

37.序列化二叉树

问题描述:请实现两个函数,分别用来序列化和反序列化二叉树。

思路:前序遍历,空分支用$代替

In [182]:
def tree2str(tree):
    if not tree:
        return '$'
    return str(tree.val)+','+tree2str(tree.left)+','+tree2str(tree.right)
In [200]:
n1 = TreeNode(1)
n2 = TreeNode(2)
n3 = TreeNode(3)
n4 = TreeNode(4)
n5 = TreeNode(5)
n6 = TreeNode(6)

n1.left = n2
n1.right = n3
n2.left = n4
n3.left = n5
n3.right = n6

tree2str(n1)
Out[200]:
'1,2,4,$,$,$,3,5,$,$,6,$,$'
In [252]:
def unserialize(s):
    arr = [s]
    return str2tree(arr)
    
def str2tree(s):
    if len(s[0])<1:
        return None
    
    # 取出第一个逗号之前的字符串
    for i in range(len(s[0])):
        if s[0][i] == ',':
            first_str = s[0][:i]
            s[0] = s[0][i+1:]
            break
    else:
        first_str = s[0]
        s[0] = ''

    if first_str == '$':
        return None
    
    node = TreeNode(int(first_str))
    node.left = str2tree(s)
    node.right = str2tree(s)
    return node
In [253]:
tree = unserialize('1,2,4,$,$,$,3,5,$,$,6,$,$')
print_tree(tree)
Out[253]:
[1, 2, 3, 4, 5, 6]

38.字符串的排列

问题描述:输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。

In [258]:
def printAllStr(s):
    printAllByTwoStr('',s)
    
def printAllByTwoStr(s1,s2):
    if s2 == '':
        print(s1)
        
    for i in range(len(s2)):
        f = s2[i]
        o = s2[:i]+s2[i+1:]
        printAllByTwoStr(s1+f,o)
In [259]:
printAllStr('abc')
abc
acb
bac
bca
cab
cba

39.数组中出现次数超过一半的数字

问题描述:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。

使用哈希表,时间和空间复杂度都是$O(n)$

In [260]:
def findNumMoreThanHalfLen(arr):
    m = {}
    for i in arr:
        if i in m:
            m[i] += 1
            if m[i] > len(arr)/2:
                return i
        else:
            m[i] = 1
    return None
In [262]:
data = [2, 4, 5, 1, 9, 3]
print(findNumMoreThanHalfLen(data))

data = [5,2,1,5,5,3,5,4,5]
print(findNumMoreThanHalfLen(data))
None
5

40.最小的k个数

问题描述:输入n个整数,找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。

  • 先快速排序再取前k个数的复杂度为$O(n\log n)$
  • 回顾快速排序的思想,让数组的前一部分小于某个值,后一部分大于某个值,直到结束。这里可以让前k个数小于某个值,后面的数大于某个值。复杂度为$O(n)$。
In [264]:
def partition(data, s, e):
    if s >= e:
        return 
    small = s - 1
    pivot_index = e
    pivot_value = data[pivot_index]
    for i in range(s, e):
        if data[i] < pivot_value:
            small += 1
            if small != i:
                data[small], data[i] = data[i], data[small]
    small += 1
    if small != e:
        data[small], data[e] = data[e], data[small]
    return small
In [265]:
def getLeastNumbers1(data, k):
    if len(data) <= k:
        return data
    s = 0
    e = len(data) - 1
    index = partition(data, s, e)
    while index != k - 1:
        if index > k - 1:
            e = index - 1
            index = partition(data, s, e)
        else:
            s = index + 1
            index = partition(data, s, e)
    return data[:k]
In [266]:
data = [10, 8, 2, 3, 4, 5, 7, 1, 6]
getLeastNumbers1(data, 4)
Out[266]:
[1, 2, 3, 4]

41.数据流中的中位数

问题描述:如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

数据结构 插入的时间复杂度 得到中位数的时间复杂度 得到中位数的思路
没有排序的数组 O(1) O(n) 参考no.39题,使用partition
排序的数组 O(n) O(1) 直接通过下标获取
排序的链表 O(n) O(1) 定义指向中位数的指针
二叉搜索树 平均O(logn),最差O(n) 平均O(logn),最差O(n) 节点中添加一个表示子树节点个数的字段
平衡二叉搜索树AVL 平均O(logn) O(1) 将平衡因子从左右子树的高度差修改成左右子树的节点数目差
最大堆 O(logn) O(1) 用一个最大堆和一个最小堆实现

42.连续子数组的最大和

问题描述:输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

43.从1到n整数中1出现的次数

问题描述:输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。例如输入12,从1到12这些整数中包含1 的数字有1,10,11和12,1一共出现了5次。

44.数字序列中某一位的数字

问题描述:数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第5位(从0开始计数)是5,第13位是1,第19位是4,等等。请写一个函数,求任意第n位对应的数字。

45.把数组排成最小的数

问题描述:输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。

46.把数字翻译成字符串

47.礼物的最大价值

48.最长不含重复字符串的子字符串

49.丑数

50.第一个只出现一次的字符串

51.数组中的逆序对

52.两个链表的第一个公共节点

53.

54.

55.

56.

57.

58.

59.

60.

61.

62.

63.

64.

65.

66.

67.

68.

posted @ 2019-02-27 10:59:31
评论加载中...

发表评论