剑指offer打卡-1_Python

斐波那契数列

问题描述与方案

1 1 2 3 5 8 13　... F(n) = F(n-1) + F(n-2) (n > 2)

代码

class Solution:

    def fibonacci(self, n):
        """递归算法(时间复杂度极高O(n)=２^n)"""
        if n == 0:
            return 0
        if n == 1 or n == 2:
            return 1
        if n > 2:
            return self.fibonacci(n - 1) + self.fibonacci(n - 2)

    def fibonacci1(self, n):
        """动态规划问题"""

        if n == 0:
            return 0
        if n == 1:
            return 1
        if n > 1:
            a = 1  # 较大值
            b = 0  # 较小值
            ret = 0
            for i in range(2, n + 1):  # 左闭右开
                ret = a + b
                b = a
                a = ret

            return ret

    def fibonacci2(self, n):
        """列表写法O(n)=n(推荐)"""

        if n == 0:
            return 0
        if n == 1:
            return 1
        result = [0, 1]
        for i in range(2, n + 1):
            result.append(result[i - 1] + result[i - 2])

        return result[-1]

跳台阶问题

问题描述与方案

问题描述1：一只青蛙一次可以跳上1级台阶，也可以跳上2级。
求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）
解决方案：
当n=0 0
n=1 1 
n=2 2
n=3 3
n=4 5
．．．．．．
所以，符合斐波那契数列f(n) = f(n-1) + f(n-2)

问题描述2：一只青蛙一次可以跳上1级台阶，也可以跳上2级,更可以一次跳上n级台阶
求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果
解决方案：
n = 0 0
n = 1 1
n = 2 2
n = 3 4
．．．．．．
所以，f(n) = 2f(n-1)

代码

class Solution:

# 问题一
    def jump_floor(self, n: int):
        """
        :param n: 台阶
        :return: 多少种跳法
        """

        if n == 0 or n == 1 or n == 2:
            return n
        if n >= 3:
            result = [1, 2]
            for i in range(2, n):
                result.append(result[i-1] + result[i-2])

            return result[-1]

    def jump_floor1(self, n: int):

        if n == 0 or n == 1 or n == 2:
            return n

        if n > 2:
            a = 2
            b = 1
            ret = 0
            for i in range(3, n + 1):
                ret = a + b
                b = a
                a = ret

        return ret
# 问题二
    def jump_floor2(self, n: int):

        if n == 0 or n == 1:
            return n

        if n > 2:
            max_val = 1
            temp = 1
            for i in range(2, n + 1):
                temp = 2 * max_val
                max_val = temp

        return temp

    def jump_floor3(self, n: int):
 
        if n == 0 or n == 1:
            return n

        return 2 * self.jump_floor3(n - 1)

二维数据查找

问题描述与方案

问题描述：
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，
判断数组中是否含有该整数,形式如下:
1  2  3  4
2  3  4  5
6  7  8  9
10 11 12 13
解决方案：
1.暴力搜索（遍历）T(O) = n^2
2.考虑数据在存储位置上的存储性质

代码

class Solution:

    def find(self, array, target):
        """不考虑时间复杂度，暴力搜索, T(O)=n^2"""

        for i in range(len(array)):
            for j in range(len(array[i])):
                if array[i][j] == target:
                    return True
        return False

    def find1(self, array, target):
        """T(O) = n"""
        nrows = len(array)
        ncols = len(array[0])
        # 定义维度
        r = nrows - 1
        i = 0
        j = ncols - 1
        flag = False

        while i <= r and j >= 0:  # 右上角进行查找
            if array[i][j] == target:  # 正确查找
                flag = True
                break
            if array[i][j] > target:  # 目标值可能存在于左边
                j -= 1
            if array[i][j] < target:  # 目标值可能存在于底部
                i += 1

        return flag

使用两个栈实现一个队列

问题描述

问题描述：
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

解决方案：
栈：先进后出(列表)
队列：先进先出

一个栈用来接收数据，另一个栈用来输出数据
accept	output
|4| 	|1|
|3| ---	|2|
|2| ---	|3|
|1| 	|4|

代码

class Solution:

    def __init__(self):
        self.accept_stack = []
        self.output_stack = []

    def push(self, val):
        self.accept_stack.append(val)

    def pop(self):

        if not self.output_stack:  # 输出栈空，返回值
            while self.accept_stack:
                self.output_stack.append(self.accept_stack.pop())

        if self.output_stack:  # 有值
            return self.output_stack.pop()
        else:
            return None  # 输入、输出栈同时为空

替换空格

问题描述

问题描述：
请实现一个函数，将一个字符串中的每个空格替换成“%20”。
例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

解决方案：
1. replace
str = "hello world !"
str.replace(" ", "%20")
'hello%20world%20!'
2.遍历元素
自己仿写一个替换函数
3.节省空间，按照实际需求进行替换

代码

class Solution:

    def replace_block(self, str):

        str = str.replace(" ", "%20")

        return str

    def replace_black1(self, str):

        new_str = []

        for i in range(len(str)):
            if str[i] == " ":
                new_str.append("%20")
            else:
                new_str.append(str[i])
        return ''.join(new_str)

    def replace_black2(self, str):

        if str is None:
            return None

        space_num = 0
        for i in range(len(str)):
            if str[i] == " ":
                space_num += 1

        li = len(str) + 2 * space_num
        new_str = [1] * li

        p1 = len(str) - 1
        p2 = len(new_str) - 1

        while p1 >= 0:
            if str[p1] != " ":
                new_str[p2] = str[p1]
                p1 -= 1
                p2 -= 1
            else:
                new_str[p2] = "0"
                new_str[p2 - 1] = "2"
                new_str[p2 - 2] = "%"
                p1 -= 1
                p2 -= 3

        return "".join(new_str)