分类 五、数据结构与算法 下的文章

一、题目列表：
题目1、斐波那契数列

二、题目
题目1、
描述
大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。

2.代码

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        #result = 0
        #for i in range(n):
        #    result +=  result
        result = [0,1]
        for i in range(2,n+1):
            result.append(result[i-2]+result[i-1])
        return result[n]

一、题目列表：
题目1、用两个栈实现队列JZ9

二、题目
题目1、用两个栈实现队列JZ9
描述
用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

数据范围： nle1000n≤1000
要求：存储n个元素的空间复杂度为 O(n)O(n) ，插入与删除的时间复杂度都是 O(1)O(1)

2.代码

# -*- coding:utf-8 -*-
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  self.stack2 == []:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

一、题目列表：
题目1、

二、题目
题目1、
给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），每段绳子的长度记为 k[1],...,k[m] 。请问 k[1]k[2]...*k[m] 可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18 。

数据范围： 2 le n le 602≤n≤60
进阶：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n)

思路：
为了解决这个问题，我们可以采用一个贪心策略，尽量将绳子剪成尽可能多的3（除了最后可能剩下1或2的情况）。这种策略基于数学上的观察：在相同的总和下，将数字拆分成更多的3（或其他大于2的数）通常能得到更大的乘积，因为乘法的增长是指数级的。

2.代码

# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        # write code here
        if number == 1:
            return 1
        if number == 2:
            return 1
        if number == 3:
            return 2
        n = number % 3
        b = number // 3
        if n == 0:
            return 3 ** b
        if n == 1:
            return 3 ** (b - 1) * 4
        if n == 2:
            return 3 ** b * 2

一、题目列表：
题目1、用两个栈实现队列JZ9

二、题目
题目1、用两个栈实现队列JZ9
描述
用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

数据范围： nle1000n≤1000
要求：存储n个元素的空间复杂度为 O(n)O(n) ，插入与删除的时间复杂度都是 O(1)O(1)

2.代码

# -*- coding:utf-8 -*-
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  self.stack2 == []:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

一、题目列表：
题目1、二进制中1的个数 JZ15
题目2、数值的整数次方 JZ16

  1. & : 按位与操作
    (当其数据类型为十进制整型时，需转化为二进制数据进行计算。)

  2. : 右移操作

  3. 1 是将n的二进制代码右移一个单位(也可理解为n/2)。

二、题目
题目1、二进制中1的个数 JZ15
输入一个整数 n ，输出该数32位二进制表示中1的个数。其中负数用补码表示。

数据范围：- 2^{31} <= n <= 2^{31}-1−2
即范围为:-2147483648<= n <= 2147483647−2147483648<=n<=2147483647
思路：

2.代码

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        # write code here
        count = 0
        for i in range(32):
            if n & 1 :
                count +=1
            n= n>>1
        return count

题目2、数值的整数次方 JZ16

实现函数 double Power(double base, int exponent)，求base的exponent次方。

注意：
1.保证base和exponent不同时为0。
2.不得使用库函数，同时不需要考虑大数问题
3.有特殊判题，不用考虑小数点后面0的位数。
思路：

2.代码

方法一：直接

# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        # write code here
        return base**exponent

方法二：

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