剑指offer|牛客网剑指offer——python实现（更新15题）剑指offer|python3

1.斐波那契数列大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，n<=39）。
循环实现，时间复杂度n

def Fibonacci(self, n): if n == 0: return 0 if n == 1: return 1 a = 1 b = 0 ret = 0 for i in range(0, n-1): #[0,n-1) ret = a + b b = a a = ret return ret

递归实现，时间复杂度2^n

def Fibonacci(self, n): if n == 0: return 0 if n == 1: return 1 if n > 1： num = self.Fibonacci(n-1) + self.Fibonacci(n-2) return num

2.跳台阶一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

a.假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1)
b.假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)
c.由a和b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2)
d.然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1，只有两阶的时候可以有 f(2) = 2
e.可以发现最终得出的是一个斐波那契数列

def jumpFloor(self, number): # write code here if number == 1: return 1 a = 1 b = 1 for i in range(1, number): ret = a + b b = a a = ret return ret

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

思路1：每个台阶可以看作一块木板，让青蛙跳上去，n个台阶就有n块木板，最后一块木板是青蛙到达的位子，必须存在，其他 (n-1) 块木板可以任意选择是否存在，则每个木板有存在和不存在两种选择，(n-1) 块木板就有 [2^(n-1)] 种跳法，可以直接得到结果

思路2：因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级
跳1级，剩下n-1级，则剩下跳法是f(n-1)
跳2级，剩下n-2级，则剩下跳法是f(n-2)
跳n级，剩下n-2级，则剩下跳法是f(0)
所以f(n)=f(n-1)+f(n-2)+…+f(1)+f(0)
因为f(n-1)=f(n-2)+f(n-3)+…+f(1)+f(0)
所以f(n)=2*f(n-1)

def jumpFloorII(self, number): # write code here return pow(2,number-1)

4.二维数组中的查找在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

从右上角的数开始找：
大于则向下，第一行的数无需对比
小于则向左，最后一列的数无需对比

def Find(self, target, array): # write code here rows = len(array) cols = len(array[0]) if rows >0 and cols >0: i=0 j= cols - 1 while i < rows and j >= 0: value = https://www.it610.com/article/array[i][j] if value == target: return True elif value> target: j -= 1 else: i += 1 return False

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

# -*- coding:utf-8 -*- class Solution: # s 源字符串 def replaceSpace(self, s): # write code here #方法一一次遍历时间 O(n)空间O(n) result = '' for i in s: if i == ' ': result += '%20' else: result += i return result # 方法二使用内置函数 return s.replace(' ','%20')

6.用两个栈实现队列 【剑指offer|牛客网剑指offer——python实现（更新15题）】用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

第一个栈临时保存插入的数据，当调用弹出函数的时候，如果stack2不为空则直接弹出；为空则把stack1中的数据全部弹出放到stack2中。这样不会存在冲突，而且由于stack2保存的是以前的老数据，弹出一定都符合队列的规律

class Solution: def __init__(self): self.stack1 = [] self.stack2 = [] def push(self, node): self.stack1.append(node) def pop(self): if self.stack2: return self.stack2.pop() else: while self.stack1: self.stack2.append(self.stack1.pop()) return self.stack2.pop()

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

旋转后的数组先递增，然后突然断层，让后又递增，所以，只要找到数组突然变小的那个数字即可。
二分查找法：如果中间点大于首元素，说明最小数字在后面一半，如果中间点小于尾元素，说明最小数字在前一半。依次循环。同时，当一次循环中首元素小于尾元素，说明最小值就是首元素。

但是当首元素等于尾元素等于中间值，只能在这个区域顺序查找。

class Solution: def minNumberInRotateArray(self, rotateArray): # 优化后的遍历 if rotateArray is None: return None temp = rotateArray[0] for i in range(len(rotateArray) - 1): if rotateArray[i] > rotateArray[i+1]: temp = rotateArray[i+1] break return temp# binarySearch O(lg(n)) if not rotateArray: return 0 left = 0 right = len(rotateArray) - 1 while left <= right: mid = (left + right) >> 1 # (left +right)/2 if rotateArray[mid] < rotateArray[mid-1]: return rotateArray[mid] elif rotateArray[mid] < rotateArray[right]: right = mid - 1 else: left = mid + 1 return 0

8.调整数组顺序使奇数位于偶数前面输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

数组里的任意相邻两个数必须是{奇数，偶数}的形式，任何出现{偶数，奇数}的形式，都要把两个数交换位置。套用冒泡排序的思想，只需要将原来冒泡排序的判断条件从比较两个数的大小改为判断相邻两个数是否为{奇数，偶数}的形式即可。

def reOrderArray(self, array): # 时间复杂度O(n)，空间复杂度O(n) ret = [] for i in array: if i % 2 == 1: ret.append(i) for i in array: if i % 2 == 0: ret.append(i) return ret # 简化代码 odd,even = [],[] for i in array: odd.append(i) if i % 2 == 1 else even.append(i) return odd + even# 冒泡排序法，时间复杂度O(n^2) arrayLen = len(array) for i in range(arrayLen): for j in range(arrayLen - i - 1): if array[j] % 2 == 0 and array[j + 1] % 2 == 1: array[j + 1],array[j] = array[j],array[j + 1] return array

9. 包含min函数的栈定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。

def __init__(self): self.stack = [] self.min_stack = [] def push(self, node): self.stack.append(node) #如果min_stack为空，或者当前结点值小于等于栈最后的那个值 if not self.min_stack or node <= self.min_stack[-1]: self.min_stack.append(node) def pop(self): if self.stack[-1] == self.min_stack[-1]: self.min_stack.pop() self.stack.pop() def top(self): return self.stack[-1] def min(self): return self.min_stack[-1]

10.栈的压入、弹出序列输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

pushV压入栈，循环判断压入栈的顶部和当前弹出栈的顶部数据是否相等，相等则弹出，最终栈为空代表序列正确

def IsPopOrder(self, pushV, popV): # write code here if pushV == [] or len(pushV) != len(popV): return None stack,index = [],0 for item in pushV: stack.append(item) while stack and stack[-1] == popV[index]: stack.pop() index += 1 ''' if stack == []: return True else: return False ''' return True if stack == [] else False

11.不用加减乘除做加法写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

两个数异或：相当于每一位相加，而不考虑进位；
两个数相与，并左移一位：相当于求得进位；
将上述两步的结果相加

python没有无符号左移操作，所以需要越界检查，加法是异或，进位是与<<1
https://blog.csdn.net/lrs1353281004/article/details/87192205

def Add(self, num1, num2): # write code here while(num2): num1,num2 = (num1^num2) & 0xFFFFFFFF,((num1&num2)<<1) & 0xFFFFFFFF return num1 if num1<=0x7FFFFFFF else ~(num1^0xFFFFFFFF)# 用 ctypes 来定义 c 语言的数据类型 import ctypes def c_int(v): return ctypes.c_int(v).valuewhile num2 != 0: num1, num2 = c_int(num1 ^ num2), c_int((num1 & num2) << 1) return num1

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

n与n-1进行按位与，最靠右的1置零，其他的高位的1没有发生变化，每运行一次，就可以知道有一个1

负数在计算机是以补码存在的，最高位为1，而负数往右移，符号位不变，符号位1往右移，最终可能会出现全1的情况，导致死循环，与0xFFFFFFFF相与，可以消除负数的影响

def NumberOf1(self, n): # write code here n = 0xFFFFFFFF & n count = 0 for c in str(bin(n)): if c == "1": count += 1 return count# write code here count = 0 for i in range(32): mask = 1 << i if n & mask != 0: count += 1 return count#循环次数最少 count = 0 if n < 0: n = n & 0xffffffff while n: count += 1 n = (n - 1) & n return count

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

# -*- coding:utf-8 -*- class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: # 返回构造的TreeNode根节点 def reConstructBinaryTree(self, pre, tin): if not pre or not tin: return None if len(pre) != len(tin): return None # 取出pre的第一个值：根节点 root = pre[0] rootNode = TreeNode(root) # 找到在中序遍历中的根节点所在的索引位置 pos = tin.index(root) # 中序遍历的列表的左右节点分开切片成两个列表 tinLeft = tin[0:pos] tinRight = tin[pos + 1:] # 前序遍历的列表的左右节点分开切片成两个列表 preLeft = pre[1:pos + 1] preRight = pre[pos + 1:]leftNode = self.reConstructBinaryTree(preLeft, tinLeft) rightNode = self.reConstructBinaryTree(preRight, tinRight)rootNode.left = leftNode rootNode.right = rightNode return rootNode

14.字符串的排列输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

# -*- coding:utf-8 -*- class Solution: def Permutation(self, ss): if len(ss) <= 1: return ss res = set() # 遍历字符串，固定第一个元素，第一个元素可以取a,b,c...，然后递归求解 for i in range(len(ss)): for j in self.Permutation(ss[:i] + ss[i+1:]): # 依次固定了元素，其他的全排列（递归求解） res.add(ss[i] + j) # 集合添加元素的方法add(),集合添加去重（若存在重复字符，排列后会存在相同，如baa,baa） return sorted(res)# sorted()能对可迭代对象进行排序,结果返回一个新的list

15.求1+2+3+…+n 求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。