部分代码参考🐮客网大佬
1 二维数组的查找：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
m = len(array)
n = len(array[0])
i,j = 0, n-1
while i <= m -1 and j >=0:
cur = array[i][j]
if cur == target:
return True
elif cur < target:
i = i+1
elif cur > target:
j = j-1
return False
注意行列数的求法
注意找到数组的规律，合理的缩小搜寻范围
2 请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
# -*- coding:utf-8 -*-
class Solution:
# s 源字符串
def replaceSpace(self, s):
# write code here
sr = ''
for i in s:
if i ==' ':
sr = sr + '%20'
else:
sr = sr + i
return sr 直接替换会出现字符串长度不匹配的问题
注意遍历方法，字符串的连接
3 输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
# -*- 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 here
out =[]
if listNode is None:
return out
while listNode is not None:
out.append(listNode.val)
listNode = listNode.next
#out.append(listNode.val)
out.reverse()
return out reverse的用法
list的强大功能（append，reverse）
链表的表示方法（.val .next）
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
elif len(pre) == 1:
return TreeNode(pre[0])
else:
res = TreeNode(pre[0])
res.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],tin[:tin.index(pre[0])])
res.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1: ],tin[tin.index(pre[0])+1:])
return res 通过找规律，从而使用递归的方式来解决
对异常值的处理，程序的鲁棒性
递归的写法，index用法： Python index() 方法检测字符串中是否包含子字符串 str ，如果指定 beg（开始） 和 end（结束） 范围，则检查是否包含在指定范围内，
str.index(str, beg=0, end=len(string))
该方法与 python find()方法一样，只不过如果str不在 string中会报一个异常
res来构建一个list
5 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
# -*- coding:utf-8 -*-
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()
elif not self.stack1:
return None
else:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop() 初始化
判断的顺序（会引起错误）
栈的操作（push 与 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 not rotateArray:
return 0
else:
for i in range((len(rotateArray)) -1):
if rotateArray[i] <= rotateArray[i+1]:
pass
else:
return rotateArray[i+1]
找到交叉点
也可采用类似二分查找的方法
异常值的处理
7 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
res=[0,1,1,2]
while len(res)<=n:
res.append(res[-1]+res[-2])
return res[n]
注意本题中不能用递归（超时）
利用list构造，循环后得到值，之后return结果即可
8 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
# write code here
res = [1,2]
print(len(res))
while number >= len(res):
res.append(res[-1]+res[-2])
return res[number-1]
抽象问题的能力，其实跟上题一样
9 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
# -*- coding:utf-8 -*-
class Solution:
def jumpFloorII(self, number):
# write code here
return 2**(number-1) 找数学规律，每个台阶都有两种可能，最后一个台阶只有一个可能
10 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
# write code here
if number == 0:
return 0
res = [1,2,3]
while number >= len(res):
res.append(res[-1]+ res[-2])
return res[number-1] 矩阵竖放，n-1
矩阵横放，n-2
实质还是斐波那契数列，熟练掌握通过list实现的用法
11 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
# write code here
count = 0
if n<0:
n = n & 0xffffffff
while(n):
n = n &(n-1)
count = count+1
return count 时间要求，要采用位运算
对负数的处理
找规律，一个数和自身减一做位与运算，会消去最右边的一个1
12 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
# -*- coding:utf-8 -*-
class Solution:
def Power(self, base, exponent):
# write code here
if exponent == 0:
return 1
elif exponent<0:
base2 = base
for i in range(abs(exponent)-1):
base2 = base*base2
base2 = 1/base2
return base2
else:
base1 = base
for i in range(exponent-1):
base1 = base*base1
return base1 考察代码的鲁棒性，要考虑到0，负数等各种情况
注意可以设置全局变量作为标志位
13 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
# -*- coding:utf-8 -*-
class Solution:
def reOrderArray(self, array):
# write code here
for i in range(len(array)):
for j in range(len(array)-1):
if array[j]%2 ==0 and array[j+1]%2 !=0:
temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
return array
可以采用双指针算法，但是此题中要求相对位置不变
利用冒泡算法相似的原理，每次比较相邻两位
注意对都是偶数的情况的处理
14 输入一个链表，输出该链表中倒数第k个结点。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindKthToTail(self, head, k):
# write code here
if head == None or k ==0:
return None
res = []
while head:
res.append(head)
head = head.next
if k > len(res):
return None
else:
return res[-k] 对异常值的处理
None用法
利用res来构造一个list
对K的判断
可以采用一前一后双指针法
输出的是结点而不是结点的值
15 输入一个链表，反转链表后，输出新链表的表头。
# -*- 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 not pHead or not pHead.next :
return pHead
last = None
while pHead:
tmp = pHead.next
pHead.next = last
last = pHead
pHead = tmp
return last
对异常值的处理
搞清楚tmp，last的含义
可以画图便于理解
在处理完一个节点后，last与pHead的调换，注意tmp的用法
16 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
# -*- 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
copy = ListNode(0)
pHead = copy
while pHead1 and pHead2:
if pHead1.val <= pHead2.val:
copy.next = pHead1
copy = copy.next
pHead1 = pHead1.next
elif pHead1.val > pHead2.val:
copy.next = pHead2
copy = copy.next
pHead2 = pHead2.next
if pHead1 and not pHead2:
copy.next = pHead1
else:
copy.next = pHead2
return pHead.next
初始化一个链表的方法
备份链表的头指针（pHead）
注意比较的是结点的大小还是结点的值的大小
注意返回值
其他：
find可以用来查找str
reverse() 函数用于反向列表中元素
python内置的sorted()函数就可以对list进行排序它还可以接收一个key函数来实现自定义的排序，例如按绝对值大小排序：
>>> sorted([36, 5, -12, 9, -21], key=abs)
[5, 9, -12, -21, 36] lambda就是用来定义一个匿名函数的，如果还要给他绑定一个名字的话，就会显得有点画蛇添足，通常是直接使用lambda函数。如下所示：
add = lambda x, y : x+y
add(1,2) # 结果为3
self在定义时需要定义，但是在调用时会自动传入。
self的名字并不是规定死的，但是最好还是按照约定是用self
self总是指调用时的类的实例。
京公网安备 11010502036488号