斐波那契數列
大家都知道斐波那契數列，現在要求輸入一個整數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
跳臺階
一只青蛙一次可以跳上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
變態跳臺階
一只青蛙一次可以跳上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)
二維陣列中的查找
在一個二維陣列中（每個一維陣列的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序，請完成一個函式，輸入這樣的一個二維陣列和一個整數，判斷陣列中是否含有該整數，
從右上角的數開始找：
大于則向下，第一行的數無需對比
小于則向左，最后一列的數無需對比
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.cnblogs.com/zhaoya2019/p/array[i][j]
if value == target:
return True
elif value > target:
j -= 1
else:
i += 1
return False
替換空格
請實作一個函式，將一個字串中的每個空格替換成“%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')
用兩個堆疊實作佇列
用兩個堆疊來實作一個佇列，完成佇列的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()
旋轉陣列的最小數字
把一個陣列最開始的若干個元素搬到陣列的末尾，我們稱之為陣列的旋轉，
輸入一個非遞減排序的陣列的一個旋轉，輸出旋轉陣列的最小元素，
例如陣列{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
調整陣列順序使奇數位于偶數前面
輸入一個整數陣列，實作一個函式來調整該陣列中數字的順序，使得所有的奇數位于陣列的前半部分，所有的偶數位于陣列的后半部分，并保證奇數和奇數，偶數和偶數之間的相對位置不變，
陣列里的任意相鄰兩個數必須是{奇數，偶數}的形式，任何出現{偶數，奇數}的形式，都要把兩個數交換位置，套用冒泡排序的思想，只需要將原來冒泡排序的判斷條件從比較兩個數的大小改為判斷相鄰兩個數是否為{奇數，偶數}的形式即可，
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
包含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]
堆疊的壓入、彈出序列
輸入兩個整數序列，第一個序串列示堆疊的壓入順序，請判斷第二個序列是否可能為該堆疊的彈出順序，假設壓入堆疊的所有數字均不相等，例如序列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
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/164049.html
標籤：Python