學(xué)習(xí)
1.二維數(shù)組中的查找
在一個(gè)二維數(shù)組中橙弱，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序燥狰。請完成一個(gè)函數(shù)棘脐，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)龙致。
# -*- coding:utf-8 -*-
class Solution:
# array 二維列表
def Find(self, target, array ):
# write code here
if array == None or array == []:
return False
rows = len(array) - 1
columns = len(array[0])
col = 0
while rows >= 0 and col < columns :
if array[rows][col] == target:
return True
if array[rows][col] > target:
rows -= 1
if array[rows][col] < target:
col += 1
return False
兩個(gè)方向在變化蛀缝，固定一個(gè)方向，進(jìn)行大小比較目代。
2.替換空格
請實(shí)現(xiàn)一個(gè)函數(shù)屈梁，將一個(gè)字符串中的空格替換成“%20”。例如榛了，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy在讶。
# -*- coding:utf-8 -*-
class Solution:
# s 源字符串
def replaceSpace(self, s):
# write code here
'''
if s == None:
return False
tmp_s = s.split(' ')
return '%20'.join(tmp_s)
'''
return s.replace(' ', '%20')
3.從尾到頭打印鏈表
輸入一個(gè)鏈表，從尾到頭打印鏈表每個(gè)節(jié)點(diǎn)的值霜大。
# -*- 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 her
#借助列表進(jìn)行打印
temp_list = []
if listNode == None:
return temp_list
while listNode != None:
temp_list.append(listNode.val)
listNode = listNode.next
return temp_list[::-1]
#鏈表反轉(zhuǎn)
'''
temp_list = None
relist = []
while listNode != None:
tmpphead = listNode
listNode = listNode.next
tmpphead.next = temp_list
temp_list = tmpphead
while temp_list != None:
relist.append(temp_list.val)
temp_list = temp_list.next
return relist
'''
4.重建二叉樹
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹僧诚。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字遮婶。例如輸入前序遍歷序列{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:
# 返回構(gòu)造的TreeNode根節(jié)點(diǎn)
def reConstructBinaryTree(self, pre, tin):
# write code here
if len(pre) == 0:
return None
root = TreeNode(pre[0])
for i in range(len(tin)):
if tin[i] == root.val:
break
root.left = self.reConstructBinaryTree(pre[1:i + 1], tin[:i])
root.right = self.reConstructBinaryTree(pre[i + 1:], tin[i + 1:])
return root
5.用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
用兩個(gè)棧來實(shí)現(xiàn)一個(gè)隊(duì)列，完成隊(duì)列的Push和Pop操作蹦骑。 隊(duì)列中的元素為int類型慈省。
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):#構(gòu)造兩個(gè)棧用來當(dāng)做進(jìn)和出
self.stack1=[]#進(jìn)
self.stack2=[]#出
def push(self, node):
# write code here
while self.stack2:
self.stack1.append(self.stack2.pop())
self.stack2.append(node)
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2
def pop(self):
# return xx
return self.stack2.pop()
6.旋轉(zhuǎn)數(shù)組的最小數(shù)字
把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)眠菇。 輸入一個(gè)非遞減排序的數(shù)組的一個(gè)旋轉(zhuǎn)边败，輸出旋轉(zhuǎn)數(shù)組的最小元素。 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)捎废，該數(shù)組的最小值為1笑窜。 NOTE：給出的所有元素都大于0，若數(shù)組大小為0登疗，請返回0排截。
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if len(rotateArray) == 0:
return 0
for i in range(len(rotateArray) - 1):
if rotateArray[i] > rotateArray[i + 1]:
rotateArray = rotateArray[i + 1:] + rotateArray[:i + 1]
break
return rotateArray[0]
#二分法查找
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if len(rotateArray) == 0:
return 0
low = 0
high = len(rotateArray) - 1
while low < high:
mid = low + (high - low) / 2
if rotateArray[mid] > rotateArray[high]:
low = mid + 1
elif rotateArray[mid] == rotateArray[high]:
high = high - 1
else:
high = mid
return rotateArray[low]
7. 斐波那契數(shù)列
大家都知道斐波那契數(shù)列嫌蚤，現(xiàn)在要求輸入一個(gè)整數(shù)n，請你輸出斐波那契數(shù)列的第n項(xiàng)断傲。n<=39
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
if n == 0:return 0
if n <= 2:
return 1
num1 = 1
num2 = 1
while n > 2:
num1, num2 = num2, num1 + num2
n -= 1
return num2
8.跳臺階
一只青蛙一次可以跳上1級臺階脱吱，也可以跳上2級。求該青蛙跳上一個(gè)n級的臺階總共有多少種跳法认罩。
解析：前提只有 一次 1階或者2階的跳法箱蝠。 a.如果兩種跳法，1階或者2階垦垂，那么假定第一次跳的是一階宦搬，那么剩下的是n-1個(gè)臺階，跳法是f(n-1); b.假定第一次跳的是2階劫拗，那么剩下的是n-2個(gè)臺階床三，跳法是f(n-2) c.由a\b假設(shè)可以得出總跳法為: f(n) = f(n-1) + f(n-2) d.然后通過實(shí)際的情況可以得出：只有一階的時(shí)候 f(1) = 1 ,只有兩階的時(shí)候可以有 f(2) = 2
# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
# write code here
if number == 0:
return 0
sum_number = [1, 2]
if number < 3:
return sum_number[number - 1]
for i in range(2, number):
sum_number.append(sum_number[i - 1] + sum_number[i - 2])
return sum_number[number - 1]
9.變態(tài)跳臺階
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級杨幼。求該青蛙跳上一個(gè)n級的臺階總共有多少種跳法撇簿。
解析：關(guān)于本題，前提是n個(gè)臺階會有一次n階的跳法差购。分析如下:
f(1) = 1
f(2) = f(2-1) + f(2-2) //f(2-2) 表示2階一次跳2階的次數(shù)四瘫。
f(3) = f(3-1) + f(3-2) + f(3-3)
...
f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n)
說明：
1）這里的f(n) 代表的是n個(gè)臺階有一次1,2,...n階的 跳法數(shù)。
2）n = 1時(shí)欲逃，只有1種跳法找蜜，f(1)=1;
- n = 2時(shí)，會有兩個(gè)跳得方式稳析，一次1階或者2階洗做，這回歸到了問題（1） ，f(2) = f(2-1) + f(2-2)
- n = 3時(shí)彰居，會有三種跳得方式诚纸，1階、2階陈惰、3階畦徘， 那么就是第一次跳出1階后面剩下：f(3-1);第一次跳出2階，剩下f(3-2)抬闯；第一次3階井辆，那么剩下f(3-3)因此結(jié)論是f(3) = f(3-1)+f(3-2)+f(3-3)
- n = n時(shí)，會有n中跳的方式溶握，1階杯缺、2階...n階，得出結(jié)論： f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1)
- 由以上已經(jīng)是一種結(jié)論睡榆，但是為了簡單萍肆，我們可以繼續(xù)簡化： f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1) 可以得出： f(n) = 2*f(n-1)
#一般解法
# -*- coding:utf-8 -*-
class Solution:
def jumpFloorII(self, number):
# write code here
if number == 0:
return 0
sum_number = [1, 2]
if number < 3:
return sum_number[number - 1]
for i in range(2, number):
sum_number.append(sum(sum_number) + 1)
return sum_number[number - 1]
#遞歸解法
# -*- coding:utf-8 -*-
class Solution:
def jumpFloorII(self, number):
# write code here
if number==1 or number==0:
return number
return 2*self.jumpFloorII(number-1)
10.矩形覆蓋
我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形袍榆。請問用n個(gè)21的小矩形無重疊地覆蓋一個(gè)2n的大矩形，總共有多少種方法匾鸥？
2n的大矩形蜡塌，和n個(gè)21的小矩形
其中target2為大矩陣的大小
有以下幾種情形：
1.?target <= 0 大矩形為<= 20,直接return 1；
2.?target = 1大矩形為21勿负，只有一種擺放方法馏艾，return1 ；
3.?target = 2 大矩形為22奴愉，有兩種擺放方法琅摩，return2；
4.?target = n 分為兩步考慮：
第一次擺放一塊 21 的小矩陣锭硼，則擺放方法總共為f(target - 1)
|| | | | |....
|| | | | |....
第一次擺放一塊12的小矩陣房资，則擺放方法總共為f(target-2)
因?yàn)椋瑪[放了一塊12的小矩陣（用表示）檀头，對應(yīng)下方的12（用××表示）擺放方法就確定了轰异，所以為f(targte-2)
||*| | | |....
|-|-| | | |....
# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
# write code here
if number< 3:
return number
sum1 = 1
sum2 = 2
while number >= 3:
sum1, sum2 = sum2, sum1 + sum2
number -= 1
return sum2
11.鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)
輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
'''
整體思路:
1.采用兩個(gè)指針一前一后去遍歷暑始；
2.第一個(gè)指針先遍歷k步搭独，然后第二個(gè)指針開始遍歷；
3.等第一個(gè)指針遍歷到空指針時(shí)廊镜，此時(shí)第二個(gè)指針正好位于倒數(shù)第k個(gè)結(jié)點(diǎn)牙肝。
注意：1.可能輸入的鏈表為空，或者k小于1嗤朴，此時(shí)判斷輸出結(jié)點(diǎn)也為None配椭；
2.輸入的k值大于整個(gè)鏈表的長度，因此需要進(jìn)行必要的判斷雹姊。
'''
class Solution:
def FindKthToTail(self, head, k):
# write code here
if head == None or k < 1:#判斷輸入的有效性
return None
pre_head = head #第一個(gè)指針
while k > 0 and pre_head != None:#k不為0并且指針不為空
pre_head = pre_head.next
k -= 1
if k > 0:#此條件出現(xiàn)的是因?yàn)橐呀?jīng)遍歷完鏈表股缸，但是k值仍不為0，k大于鏈表長度容为。
return None
while pre_head != None:
head = head.next
pre_head = pre_head.next
return head
12.反轉(zhuǎn)鏈表
輸入一個(gè)鏈表乓序，反轉(zhuǎn)鏈表后，輸出新鏈表的表頭
思路： 1.采用頭插法坎背，創(chuàng)建一條新的鏈表； 2.采用Python中的list寄雀，進(jìn)行反轉(zhuǎn) 3.得滤。。盒犹。懂更。眨业。
#頭插法：1.創(chuàng)建一個(gè)頭指針為None的表頭；2.原有鏈表每取出一次表頭就將該表頭.next指向創(chuàng)建的None
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
# write code here
if pHead == None or pHead.next == None:
return pHead
new_pHead = None
while pHead != None:
temp_pHead = pHead
pHead = pHead.next
temp_pHead.next = new_pHead
new_pHead = temp_pHead
return new_pHead
13.合并兩個(gè)有序的鏈表
輸入兩個(gè)單調(diào)遞增的鏈表沮协，輸出兩個(gè)鏈表合成后的鏈表龄捡，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回合并后列表
def Merge(self, pHead1, pHead2):
# write code here
if pHead1 == None:
return pHead2
if pHead2 == None:
return pHead1
if pHead1.val < pHead2.val:
pHeadtemp = pHead1
pHeadtemp.next = self.Merge(pHead1.next,pHead2)
else:
pHeadtemp = pHead2
pHeadtemp.next = self.Merge(pHead1,pHead2.next)
return pHeadtemp
14.包含min函數(shù)的棧
定義棧的數(shù)據(jù)結(jié)構(gòu)慷暂，請?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧中所含最小元素的min函數(shù)聘殖。
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack=[]
self.minstack=[]
def push(self, node):
# write code here
Min=self.min()
self.stack.append(node)
if not Min or node<Min:
self.minstack.append(node)
else:
self.minstack.append(Min)
def pop(self):
# write code here
if self.stack:
self.minstack.pop()
return self.stack.pop()
def top(self):
# write code here
if self.stack:
return self.stack[-1]
def min(self):
# write code here
if self.minstack:
return self.minstack[-1]
15.棧的壓入、彈出序列
輸入兩個(gè)整數(shù)序列行瑞，第一個(gè)序列表示棧的壓入順序奸腺，請判斷第二個(gè)序列是否可能為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等血久。例如序列1,2,3,4,5是某棧的壓入順序突照，序列4,5,3,2,1是該壓棧序列對應(yīng)的一個(gè)彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列氧吐。（注意：這兩個(gè)序列的長度是相等的）
# -*- coding:utf-8 -*-
class Solution:
def IsPopOrder(self, pushV, popV):
# write code here
#如果序列為空或者不等讹蘑，返回False
if not pushV or len(pushV) != len(popV):
return False
#借助輔助list
stack = []
#將壓入序列依次壓入stack中，并比較當(dāng)前棧頂元素是否與pop隊(duì)列的第一個(gè)元素相等筑舅，并依次進(jìn)行比較
for index in pushV:
stack.append(index)
while stack and stack[-1] == popV[0]:
stack.pop()
popV.pop(0)
#如果壓入序列遍歷結(jié)束后座慰，stack不為空則返回False
if stack:
return False
return True
