Python练习题集合+剑指offer

超、凢脫俗 2022-05-15 08:15 320阅读 0赞

所有的剑指offer中的算法题的python实现可以查看：

[第一部分][Link 1]

[第二部分][Link 2]

[第三部分][Link 3]

--------------------

![20200423163038326.PNG][]

最好自己画图和创建虚拟数据进行理解。

**目录**

1. 输入某年某月某日，判断这是这一年的第几天

2.打印出 5 种不同形式的九九乘法表

3.判断101 - 200 之间有多少个素数， 并输出所有的素数

5.一球从100 米高度落下，每次落地后反弹的高度是原高度的一半；求它在第10次落地时，经过多少米？第10次反弹多高？

6.猴子吃桃问题，每天吃所剩桃子总数的一半加1 个，直到第10天，只剩下 1个桃子

7.打印出特定图形

8.有一组分数序列：2/1, 3/2, 5/3, 8/5, .....求出这个数列的前20 项的和

9.求 1+2！+3！。。。+20！的累加和

10.使用递归方法求阶乘10！

11.利用递归函数调用方式，将所输入的5个字符，以相反顺序打印出来。

12 求一个3\*3 矩阵的对角线的和

13.现有一个排好序的数组，输入一个数，要求按原来的顺序插入到数组中

剑指offer中的一些题目：

1.输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

2.用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

3.输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。

4.旋转数组的最小数字

5.斐波那契数列

6.青蛙跳台阶

7.变态跳台阶

8.矩形覆盖

9.求二进制 1 的个数

10.数字的整数次方

--------------------

### 1. 输入某年某月某日，判断这是这一年的第几天 ###

#coding=gbk
    '''
    Created on 2018年8月27日
    
    @author: Somebody
    '''
    # 1. 输入某年某月某日，判断这是这一年的第几天
    #特殊情况：闰年，如果输入日期大于2月，闰年需要加1 
    year = int(input('year:\n'))
    month = int(input('month:\n'))
    day = int(input('day:\n'))
    
    #判断输入的天数是否正确
    # 1, 3, 5, 7, 8, 10 腊
    month_count = [31, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    if ((year % 400 ==0) or (year % 4 ==0 and year % 100 != 0)):
        month_count.insert(1, 29)
    else: 
        month_count.insert(1, 28)
    print(month_count)
    if(day > month_count[month - 1]):
        print('输入的天数是错误的')
        
    else:
        if (0< month <= 12):
            sum =0 
            for i in range(month -1):
                sum += month_count[i]
        else:
            print('data error')
        sum += day 
        print('该天是该年的第%d 天\n' %sum)
    # year:
    # 2000
    # month:
    # 3
    # day:
    # 1
    # [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    # 该天是该年的第61 天

### 2.打印出 5 种不同形式的九九乘法表 ###

（输出的数字的形式类似于第 7 道题中的打印出图形的例子， 这里可以将数字看做是 7 中的字符 \* ）

#完整格式输出九九乘法表
    for i in range(1, 10):
        for j in range(1, 10):
            result = i * j 
            print('%d*%d = %2d' %(i, j, result), end = "  ")
        print()
    # 1*1 =  1  1*2 =  2  1*3 =  3  1*4 =  4  1*5 =  5  1*6 =  6  1*7 =  7  1*8 =  8  1*9 =  9  
    # 2*1 =  2  2*2 =  4  2*3 =  6  2*4 =  8  2*5 = 10  2*6 = 12  2*7 = 14  2*8 = 16  2*9 = 18  
    # 3*1 =  3  3*2 =  6  3*3 =  9  3*4 = 12  3*5 = 15  3*6 = 18  3*7 = 21  3*8 = 24  3*9 = 27  
    # 4*1 =  4  4*2 =  8  4*3 = 12  4*4 = 16  4*5 = 20  4*6 = 24  4*7 = 28  4*8 = 32  4*9 = 36  
    # 5*1 =  5  5*2 = 10  5*3 = 15  5*4 = 20  5*5 = 25  5*6 = 30  5*7 = 35  5*8 = 40  5*9 = 45  
    # 6*1 =  6  6*2 = 12  6*3 = 18  6*4 = 24  6*5 = 30  6*6 = 36  6*7 = 42  6*8 = 48  6*9 = 54  
    # 7*1 =  7  7*2 = 14  7*3 = 21  7*4 = 28  7*5 = 35  7*6 = 42  7*7 = 49  7*8 = 56  7*9 = 63  
    # 8*1 =  8  8*2 = 16  8*3 = 24  8*4 = 32  8*5 = 40  8*6 = 48  8*7 = 56  8*8 = 64  8*9 = 72  
    # 9*1 =  9  9*2 = 18  9*3 = 27  9*4 = 36  9*5 = 45  9*6 = 54  9*7 = 63  9*8 = 72  9*9 = 81 
    print('左上角打印出九九乘法表')
    for i in  range(1, 10):
        for j in range(i, 10):
            result = i * j 
            print('%d * %d = %2d'%(i, j, result), end= " ")
        print()
    # 左上角打印出九九乘法表
    # 1 * 1 =  1 1 * 2 =  2 1 * 3 =  3 1 * 4 =  4 1 * 5 =  5 1 * 6 =  6 1 * 7 =  7 1 * 8 =  8 1 * 9 =  9 
    # 2 * 2 =  4 2 * 3 =  6 2 * 4 =  8 2 * 5 = 10 2 * 6 = 12 2 * 7 = 14 2 * 8 = 16 2 * 9 = 18 
    # 3 * 3 =  9 3 * 4 = 12 3 * 5 = 15 3 * 6 = 18 3 * 7 = 21 3 * 8 = 24 3 * 9 = 27 
    # 4 * 4 = 16 4 * 5 = 20 4 * 6 = 24 4 * 7 = 28 4 * 8 = 32 4 * 9 = 36 
    # 5 * 5 = 25 5 * 6 = 30 5 * 7 = 35 5 * 8 = 40 5 * 9 = 45 
    # 6 * 6 = 36 6 * 7 = 42 6 * 8 = 48 6 * 9 = 54 
    # 7 * 7 = 49 7 * 8 = 56 7 * 9 = 63 
    # 8 * 8 = 64 8 * 9 = 72 
    # 9 * 9 = 81 
    print('打印出右上角的九九乘法表')
    for i in range(1, 10):
        for k in range(1, i):
            print(end = "           ")
        for j in range(i, 10):
            result = i * j 
            print('%d * %d = %2d'%(i, j, result), end= " ")
        print()
    # 打印出右上角的九九乘法表
    # 1 * 1 =  1 1 * 2 =  2 1 * 3 =  3 1 * 4 =  4 1 * 5 =  5 1 * 6 =  6 1 * 7 =  7 1 * 8 =  8 1 * 9 =  9 
    #            2 * 2 =  4 2 * 3 =  6 2 * 4 =  8 2 * 5 = 10 2 * 6 = 12 2 * 7 = 14 2 * 8 = 16 2 * 9 = 18 
    #                       3 * 3 =  9 3 * 4 = 12 3 * 5 = 15 3 * 6 = 18 3 * 7 = 21 3 * 8 = 24 3 * 9 = 27 
    #                                  4 * 4 = 16 4 * 5 = 20 4 * 6 = 24 4 * 7 = 28 4 * 8 = 32 4 * 9 = 36 
    #                                             5 * 5 = 25 5 * 6 = 30 5 * 7 = 35 5 * 8 = 40 5 * 9 = 45 
    #                                                        6 * 6 = 36 6 * 7 = 42 6 * 8 = 48 6 * 9 = 54 
    #                                                                   7 * 7 = 49 7 * 8 = 56 7 * 9 = 63 
    #                                                                              8 * 8 = 64 8 * 9 = 72 
    #                                                                                         9 * 9 = 81 
    print('打印出左下角的九九乘法表')
    for i in range(1, 10):
        for j in range(1, i+1):
            result = i * j 
            print('%d * %d = %2d'%(j, i, result), end= " ")
        print()
    # 打印出左下角的九九乘法表
    # 1 * 1 =  1 
    # 1 * 2 =  2 2 * 2 =  4 
    # 1 * 3 =  3 2 * 3 =  6 3 * 3 =  9 
    # 1 * 4 =  4 2 * 4 =  8 3 * 4 = 12 4 * 4 = 16 
    # 1 * 5 =  5 2 * 5 = 10 3 * 5 = 15 4 * 5 = 20 5 * 5 = 25 
    # 1 * 6 =  6 2 * 6 = 12 3 * 6 = 18 4 * 6 = 24 5 * 6 = 30 6 * 6 = 36 
    # 1 * 7 =  7 2 * 7 = 14 3 * 7 = 21 4 * 7 = 28 5 * 7 = 35 6 * 7 = 42 7 * 7 = 49 
    # 1 * 8 =  8 2 * 8 = 16 3 * 8 = 24 4 * 8 = 32 5 * 8 = 40 6 * 8 = 48 7 * 8 = 56 8 * 8 = 64 
    # 1 * 9 =  9 2 * 9 = 18 3 * 9 = 27 4 * 9 = 36 5 * 9 = 45 6 * 9 = 54 7 * 9 = 63 8 * 9 = 72 9 * 9 = 81 
    print('打印出右下角的九九乘法表')
    for i in range(1, 10):
        for k in range(1, 10 -i):
            print(end = "           ")
        for j in range(1, i+1):
            result = i * j 
            print('%d * %d = %2d'%(j, i, result), end= " ")
        print()
    # 打印出右下角的九九乘法表
    #                                                                                         1 * 1 =  1 
    #                                                                              1 * 2 =  2 2 * 2 =  4 
    #                                                                   1 * 3 =  3 2 * 3 =  6 3 * 3 =  9 
    #                                                        1 * 4 =  4 2 * 4 =  8 3 * 4 = 12 4 * 4 = 16 
    #                                             1 * 5 =  5 2 * 5 = 10 3 * 5 = 15 4 * 5 = 20 5 * 5 = 25 
    #                                  1 * 6 =  6 2 * 6 = 12 3 * 6 = 18 4 * 6 = 24 5 * 6 = 30 6 * 6 = 36 
    #                       1 * 7 =  7 2 * 7 = 14 3 * 7 = 21 4 * 7 = 28 5 * 7 = 35 6 * 7 = 42 7 * 7 = 49 
    #            1 * 8 =  8 2 * 8 = 16 3 * 8 = 24 4 * 8 = 32 5 * 8 = 40 6 * 8 = 48 7 * 8 = 56 8 * 8 = 64 
    # 1 * 9 =  9 2 * 9 = 18 3 * 9 = 27 4 * 9 = 36 5 * 9 = 45 6 * 9 = 54 7 * 9 = 63 8 * 9 = 72 9 * 9 = 81

### 3.判断101 - 200 之间有多少个素数， 并输出所有的素数 ###

from math import sqrt 
    h = 0 
    leap = 1 # 1 代表是素数
    for m in range(101, 201):
        k = int(sqrt(m))
        for i in range(2, k+1):
            if(m % i ==0):
                leap = 0
                break
        if(leap == 1):
            print('%2d'%m, end =" ")
            h += 1
            if(h % 5 ==0):
                print()
        leap = 1  
    # 101 103 107 109 113 
    # 127 131 137 139 149 
    # 151 157 163 167 173 
    # 179 181 191 193 197 
    # 199

### 5.一球从100 米高度落下，每次落地后反弹的高度是原高度的一半；求它在第10次落地时，经过多少米？第10次反弹多高？ ###

#第一次落地时，为100米；第二次落地时，弹回50米，又落下50米，共200米
    Sn = 100.0
    Hn = 100.0/ 2
    for i in range(2, 11):
        Sn += 2* Hn 
        Hn /= 2
    print('总共经过%f米'%Sn)
    print('第10次反弹的高度为：%f'%Hn)
    # 总共经过299.609375米
    # 第10次反弹的高度为：0.097656

### 6.猴子吃桃问题，每天吃所剩桃子总数的一半加1 个，直到第10天，只剩下 1个桃子 ###

#采用逆向思维
    x1 = 1
    for day in range(9, 0, -1):
        x2 = (x1+1) * 2
        x1 = x2 
    print(x2)   # 1534

### 7.打印出特定图形 ###

from sys import stdout 
    for i in range(4):
        for j in range(3-i):
            stdout.write(' ') #右方的空格不考虑
        for k in range(2*i + 1):  
            stdout.write('*')
        print()
    #    *
    #   ***
    #  *****
    # *******
    # 只需要考虑左方的空格和*出现的方程式规律， 如k， 第0行出现1个， 第1行出现3个，所以可以得到方程  y = 2x + 1 
    
    #打印相反方向
    from sys import stdout 
    for i in range(4):
        for j in range(i):
            stdout.write(' ')
        for k in range(-2 * i+7):
            stdout.write('*')
        print()
    # *******
    #  *****
    #   ***
    #    *

### 8.有一组分数序列：2/1, 3/2, 5/3, 8/5, .....求出这个数列的前20 项的和 ###

[a, b = b, a+b 的区别可以参考;][a_ b _ b_ a_b]

#使用3种方法
    a = 1.0
    b = 2.0
    sum = 0.0
    # for i in range(1, 21):
    #     sum += b/a
    #     t = b
    #     b = a + b 
    #     a = t
    # print(sum)
    
    # for i in range(1, 21):
    #     sum += b/a 
    #     a, b = b, a+b 
    # print(sum)
    
    from _functools import reduce
    list= []
    for i in range(1, 21):
        a, b = b, a+b 
        list.append(b/a)
    sum = reduce(lambda x, y: x+y, list)
    print(sum)
    # 32.278294788817234

### 9.求 1+2！+3！。。。+20！的累加和 ###

#方法1 
    sum = 0
    t = 1
    for n in range(1, 21):
        t *= n  # 进行累乘了
        sum += t 
    print(sum)  # 2561327494111820313
    
    #方法2
    def operation(x):
        s = 1
        for i in range(1, x+1):
            s *= i 
        return s 
    list = range(1, 21)
    sum1 = sum(map(operation, list))
    print(sum1) # 2561327494111820313

### 10.使用递归方法求阶乘10！ ###

def fact(i):
        sum = 0
        if (i == 0):
            sum = 1
        else:
            sum = i * fact(i-1)
        return sum 
    print(fact(10)) # 3628800

### 11.利用递归函数调用方式，将所输入的5个字符，以相反顺序打印出来。 ###

str = input('请输入若干字符：')
     
    def reverse(x):
        if x == -1:
            return ''
        else:
            return str[x] + reverse(x-1)
     
    print(reverse(len(str)-1))

### 12 求一个3\*3 矩阵的对角线的和 ###

str = input('输入数字')# 输入9 个以 ， 为分隔符的数字
    str = str.split(sep=',')
    print('输入的数字为：%s'%str)
    a = []
    sum = 0
    for i in range(3):
        a.append([])    #数组
        for j in range(3*i, 3*(i+1)):   #间隔 
            a[i].append(int(str[j]))
    print(a)
    for i in range(3):
        sum += a[i][i]
    print(sum)
    # 输入的数字为：['1', '1', '1', '1', '6', '1', '1', '1', '10']
    # [[1, 1, 1], [1, 6, 1], [1, 1, 10]]
    # 17

### 13.现有一个排好序的数组，输入一个数，要求按原来的顺序插入到数组中 ###

#方法1
    print()
    a = [1,4,6,9,13,16,19,28,40,100]
    print(len(a)) #11 
    a.append(0)
    n = len(a)    
    number = int(input("insert a new number:\n"))
    end = a[n -2]
    if number > end:
        a[n-1] = number
    else:
        for i in range(n-1):
            if a[i] > number:
                temp1 = a[i]
                a[i] = number
                for j in range(i + 1,n): #将数字后移
                    temp2 = a[j]
                    a[j] = temp1
                    temp1 = temp2
                break
    print(a)
    #insert a new number:
    #12
    #[1, 4, 6, 9, 12, 13, 16, 19, 28, 40, 100]
    
    #方法2
    list = [1,3,5,7,9,11,15,16,17,18,0]
    a1 = int(input('请输入一个数：'))
     
    list.append(a)
    list.sort()
    print(list)
    
    #方法3
    if a > list[len(list) -1]:
        list.append(a)
    else:
        for i in range(len(list)):
            if a < list[i]:
                list.insert(i, a)
                break
    print(list)

## 剑指offer中的一些题目： ##

### 1.输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。 ###

# -*- coding:utf-8 -*-
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        # 返回从尾部到头部的列表值序列，例如[1,2,3]
        def printListFromTailToHead(self, listNode):
            # write code here
            li = []
            
            while listNode:
                li.append(listNode.val)
                listNode = listNode.next 
            return li[::-1]

### 2.用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。 ###

class Solution:
        def __init__(self):
            self.stack1 = []
            self.stack2 = []
        def push(self, node):
            # write code here
            self.stack1.append(node)
        def pop(self):
            # return xx
            if len(self.stack2) > 0:
                return self.stack2.pop()
            while self.stack1:
                self.stack2.append(self.stack1.pop())
            if len(self.stack2) > 0:
                return self.stack2.pop()

### 3.输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。 ###

### 4.旋转数组的最小数字 ###

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组\{3,4,5,1,2\}为\{1,2,3,4,5\}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

### 5.斐波那契数列 ###

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

n<=39

# -*- coding:utf-8 -*-
    class Solution:
        def Fibonacci(self, n):
            # write code here
            a, b = 0, 1
            if n==0:
                return a
            else:
                for i in range(n):
                    a, b = b, a+b
                return a

### 6.青蛙跳台阶 ###

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。算法思想：依然是斐波那切数列问题，当跳一节台阶时还有n-1个台阶，当第一次跳两个台阶时，还有n-2个台阶要跳。同样转化为斐波那契数列问题。

# -*- coding:utf-8 -*-
    class Solution:
        def jumpFloor(self, number):
            # write code here
            if number <= 0:
                return 1 
            elif number <3:
                return number
            else:
                a, b = 1, 2
                for i in range(3, number+1):
                    a, b = b, a+b 
                return b

有公式：可以分步骤进行

![1, n=1 \\\\ 2, n=2 \\\\ f(n-1)+f(n-2), n\\ge3][1_ n_1 _ 2_ n_2 _ f_n-1_f_n-2_ n_ge3]

### 7.变态跳台阶 ###

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

| 1 ,(n=0 )

f(n) = | 1 ,(n=1 )

| 2\*f(n-1),(n>=2)

![f(1)=1, f(2)=2,f(3)=4\\cdots\\cdots f(n)=2\*f(n-1)=2^\{n-1\}][f_1_1_ f_2_2_f_3_4_cdots_cdots f_n_2_f_n-1_2_n-1]

# -*- coding:utf-8 -
    
    class Solution:
        def jumpFloorII(self, number):
            # write code here
            if number <=1:
                return 1 
            else:
                return 2*self.jumpFloorII(number-1)

### 8.矩形覆盖 ###

我们可以用2\*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\*1的小矩形无重叠地覆盖一个2\*n的大矩形，总共有多少种方法？

算法思想：当第一步是竖着放，右边还剩n-1个区域，当第一步横着放时，左下角应必须横着放，右边还剩n-2个区域，可以看出这仍斐波那切数列问题f(n)=f(n-1)+f(n-2)

# -*- coding:utf-8 -*-
    class Solution:
        def rectCover(self, number):
            # write code here
            if number < 3:
                return number 
            else:
                a, b = 1, 2
                for i in range(2, number):
                    a, b = b, a+b 
                return b

### 9.求二进制 1 的个数 ###

问题：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

# -*- coding:utf-8 -*-
    class Solution:
        def NumberOf1(self, n):
            # write code here
            count = 0
            if n <0:    
                n = n&0xffffffff
            while n:
                count += 1
                n = n&(n-1)
            return count

print(bin(-6&0xFFFFFFFF)) #30个1  0b11111111111111111111111111111010

### 10.数字的整数次方 ###

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

# -*- coding:utf-8 -*-
    class Solution:
        def Power(self, base, exponent):
            result = 1
            if base == 0:
                return 0
            if exponent == 0:
                return 1
            if exponent < 0:
                for i in range(-exponent):
                    result = result * base
                return 1/result
            for i in range(exponent):
                result = result * base
            return result

[Link 1]: https://blog.csdn.net/qq_40587575/article/details/88675889
[Link 2]: https://blog.csdn.net/qq_40587575/article/details/88767488
[Link 3]: https://blog.csdn.net/qq_40587575/article/details/88920399
[20200423163038326.PNG]: /images/20220515/f1ee689e71754696a3d1de03183578e7.png
[a_ b _ b_ a_b]: https://blog.csdn.net/qq_40587575/article/details/80557768
[1_ n_1 _ 2_ n_2 _ f_n-1_f_n-2_ n_ge3]: https://private.codecogs.com/gif.latex?1%2C%20n%3D1%20%5C%5C%202%2C%20n%3D2%20%5C%5C%20f%28n-1%29&plus;f%28n-2%29%2C%20n%5Cge3
[f_1_1_ f_2_2_f_3_4_cdots_cdots f_n_2_f_n-1_2_n-1]: https://private.codecogs.com/gif.latex?f%281%29%3D1%2C%20f%282%29%3D2%2Cf%283%29%3D4%5Ccdots%5Ccdots%20f%28n%29%3D2*f%28n-1%29%3D2%5E%7Bn-1%7D