学习
1.二维数组中的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
# -*- 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
两个方向在变化，固定一个方向，进行大小比较。
2.替换空格
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为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.从尾到头打印链表
输入一个链表，从尾到头打印链表每个节点的值。
# -*- 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
#借助列表进行打印
temp_list = []
if listNode == None:
return temp_list
while listNode != None:
temp_list.append(listNode.val)
listNode = listNode.next
return temp_list[::-1]
#链表反转
'''
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.重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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):
# 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.用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):#构造两个栈用来当做进和出
self.stack1=[]#进
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.旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为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. 斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。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级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解析：前提只有 一次 1阶或者2阶的跳法。 a.如果两种跳法，1阶或者2阶，那么假定第一次跳的是一阶，那么剩下的是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
# -*- 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.变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解析：关于本题，前提是n个台阶会有一次n阶的跳法。分析如下:
f(1) = 1
f(2) = f(2-1) + f(2-2) //f(2-2) 表示2阶一次跳2阶的次数。
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个台阶有一次1,2,...n阶的 跳法数。
2）n = 1时，只有1种跳法，f(1)=1;
- n = 2时，会有两个跳得方式，一次1阶或者2阶，这回归到了问题（1） ，f(2) = f(2-1) + f(2-2)
- n = 3时，会有三种跳得方式，1阶、2阶、3阶， 那么就是第一次跳出1阶后面剩下：f(3-1);第一次跳出2阶，剩下f(3-2)；第一次3阶，那么剩下f(3-3)因此结论是f(3) = f(3-1)+f(3-2)+f(3-3)
- n = n时，会有n中跳的方式，1阶、2阶...n阶，得出结论： 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)
- 由以上已经是一种结论，但是为了简单，我们可以继续简化： 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个21的小矩形无重叠地覆盖一个2n的大矩形，总共有多少种方法？
2n的大矩形，和n个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)
因为，摆放了一块12的小矩阵（用表示），对应下方的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.链表中倒数第k个结点
输入一个链表，输出该链表中倒数第k个结点
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
'''
整体思路:
1.采用两个指针一前一后去遍历；
2.第一个指针先遍历k步，然后第二个指针开始遍历；
3.等第一个指针遍历到空指针时，此时第二个指针正好位于倒数第k个结点。
注意：1.可能输入的链表为空，或者k小于1，此时判断输出结点也为None；
2.输入的k值大于整个链表的长度，因此需要进行必要的判断。
'''
class Solution:
def FindKthToTail(self, head, k):
# write code here
if head == None or k < 1:#判断输入的有效性
return None
pre_head = head #第一个指针
while k > 0 and pre_head != None:#k不为0并且指针不为空
pre_head = pre_head.next
k -= 1
if k > 0:#此条件出现的是因为已经遍历完链表，但是k值仍不为0，k大于链表长度。
return None
while pre_head != None:
head = head.next
pre_head = pre_head.next
return head
12.反转链表
输入一个链表，反转链表后，输出新链表的表头
思路： 1.采用头插法，创建一条新的链表； 2.采用Python中的list，进行反转 3.。。。。。
#头插法：1.创建一个头指针为None的表头；2.原有链表每取出一次表头就将该表头.next指向创建的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.合并两个有序的链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
# -*- 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函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数。
# -*- 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.栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
# -*- 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中，并比较当前栈顶元素是否与pop队列的第一个元素相等，并依次进行比较
for index in pushV:
stack.append(index)
while stack and stack[-1] == popV[0]:
stack.pop()
popV.pop(0)
#如果压入序列遍历结束后，stack不为空则返回False
if stack:
return False
return True
