Skip to content

Commit 12df302

Browse files
linwtlinwt
authored
Add files via upload
1 parent d899d1d commit 12df302

File tree

66 files changed

+1359
-0
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

66 files changed

+1359
-0
lines changed

‎剑指Offer/01.二维数组中的查找.py

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
# 方法一：逐行遍历
2+
class Solution:
3+
def Find(self, target, array):
4+
for i in range(len(array)):
5+
if target in array[i]:
6+
return 'true'
7+
return 'false'
8+
9+
# 方法二：左下角开始遍历，大于向右，小于向上
10+
class Solution:
11+
def Find(self, target, array):
12+
i, j = len(array)-1, 0
13+
while i>=0 and j<len(array[0]):
14+
temp = array[i][j]
15+
if target>temp:
16+
j += 1
17+
elif target<temp:
18+
i -= 1
19+
else:
20+
return 'true'
21+
return 'false'
22+
23+
while True:
24+
# try/cexept处理输入异常情况
25+
try:
26+
# 输入一个二维数组和一个整数
27+
# L = eval(raw_input())
28+
L = list(eval(raw_input()))
29+
target = L[0]
30+
array = L[1]
31+
S = Solution()
32+
print(S.Find(target, array))
33+
except:
34+
break
35+
36+
# 9,[[1,2,3],[4,5,6]]
37+
# false
38+
# 5,[[1,2,3],[4,5,6]]
39+
# true
40+
41+
42+

‎剑指Offer/02.替换空格.py

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
# 方法一：使用replace()方法
2+
class Solution:
3+
def replaceSpace(self, s):
4+
return s.replace(' ', '%20')
5+
6+
# 方法二：使用列表，元素赋值
7+
class Solution:
8+
def replaceSpace(self, s):
9+
l = list(s)
10+
for i in range(len(l)):
11+
if l[i] == ' ':
12+
l[i] = '%20'
13+
return ''.join(l)
14+
15+
# 方法三：使用列表，添加元素
16+
class Solution:
17+
def replaceSpace(self, s):
18+
a = []
19+
for i in s:
20+
if i == ' ':
21+
a.append('%20')
22+
else:
23+
a.append(i)
24+
return ''.join(a)
25+
26+
# 方法四：使用字符串
27+
class Solution:
28+
def replaceSpace(self, s):
29+
m = ''
30+
for i in s:
31+
if i == ' ':
32+
m += '%20'
33+
else:
34+
m += i
35+
return m

‎剑指Offer/03.从尾到头打印链表.py

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
# 方法一：插入列表
2+
class Solution:
3+
def printListFromTailToHead(self, listNode):
4+
l = []
5+
head = listNode
6+
while head:
7+
l.insert(0, head.val)
8+
head = head.next
9+
return l
10+
11+
# while head:
12+
# l.insert(head.val)
13+
# head = head.next
14+
# return l[::-1]
15+
16+
# while head:
17+
# l.insert(head.val)
18+
# head = head.next
19+
# l.reverse()
20+
# return l
21+
22+
# 方法二：递归
23+
# 递归处理步骤：
24+
# 1、明确方法的作用
25+
# 2、明确递归终止条件
26+
# 3、给出终止时处理方法
27+
# 4、提取重复逻辑，调用自身解决相同问题
28+
class Solution:
29+
# 方法的作用：返回[listNode.next.val, listNode.val]
30+
def printListFromTailToHead(self, listNode):
31+
# 终止条件
32+
if not listNode:
33+
# 处理方法
34+
return []
35+
# 提取重复逻辑，调用自身解决相同的问题
36+
return self.printListFromTailToHead(listNode.next) + [listNode.val]

‎剑指Offer/04.重建二叉树.py

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
class TreeNode:
2+
def __init__(self, x):
3+
self.val = x
4+
self.left = None
5+
self.right = None
6+
7+
class Solution:
8+
# 方法作用：由前序和中序遍历序列得到根的左子树和右子树
9+
def reConstructBinaryTree(self, pre, tin):
10+
# 终止条件
11+
if not pre:
12+
# 处理方法
13+
return None
14+
root = TreeNode(pre[0])
15+
i = tin.index(pre[0])
16+
# 提取重复逻辑
17+
root.left = self.reConstructBinaryTree(pre[1:i+1], tin[:i])
18+
root.right = self.reConstructBinaryTree(pre[i+1:], tin[i+1:])
19+
return root

‎剑指Offer/05.用两个栈实现队列.py

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
# 先进先出
2+
class Solution:
3+
def __init__(self):
4+
self.stack1 = []
5+
self.stack2 = []
6+
def push(self, node):
7+
self.stack1.append(node)
8+
def pop(self):
9+
if not self.stack2:
10+
while self.stack1:
11+
self.stack2.append(self.stack1.pop())
12+
return self.stack2.pop()
13+
return self.stack2.pop()

‎剑指Offer/06.旋转数组的最小数字.py

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
# 方法一：min()函数
2+
class Solution:
3+
def minNumberInRotateArray(self, rotateArray):
4+
if not rotateArray:
5+
return 0
6+
return min(rotateArray)
7+
8+
# 方法二：sorted()函数
9+
class Solution:
10+
def minNumberInRotateArray(self, rotateArray):
11+
if not rotateArray:
12+
return 0
13+
r = sorted(rotateArray)
14+
return r[0]
15+
16+
# 方法三：sort()方法
17+
class Solution:
18+
def minNumberInRotateArray(self, rotateArray):
19+
if not rotateArray:
20+
return 0
21+
rotateArray.sort()
22+
return rotateArray[0]

‎剑指Offer/07.斐波那契数列.py

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
# 斐波那契数列：1,1,2,3,5,8,12
2+
3+
# 方法一：递推，数组追加
4+
class Solution:
5+
def Fibonacci(self, n):
6+
a = [0, 1, 1]
7+
if n < 3:
8+
return a[n]
9+
for i in range(3, n+1):
10+
a.append(a[i-1] + a[i-2])
11+
return a[n]
12+
13+
# 方法二：递推，赋值
14+
class Solution:
15+
def Fibonacci(self, n):
16+
f0, f1 = 0, 1
17+
if n == 0:
18+
return f0
19+
if n == 1:
20+
return f1
21+
for i in range(2, n+1):
22+
f0, f1 = f1, f0+f1
23+
return f1
24+
25+
# 方法三：递归
26+
class Solution:
27+
# 方法的作用：返回前两个数的和
28+
def Fibonacci(self, n):
29+
# 终止条件
30+
if n==0:
31+
# 处理方法
32+
return 0
33+
if n==1:
34+
return 1
35+
# 提取重复逻辑，调用自身解决相同的问题
36+
return self.Fibonacci(n-1) + self.Fibonacci(n-2)

‎剑指Offer/08.跳台阶.py

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
# 思路：f(1)=1 f(2)=2 f(3)=3 f(4)=5 f(5)=8
2+
# 将具体的事物抽象成数学规律。类似斐波那契数列
3+
4+
# 方法一：递推
5+
class Solution:
6+
def jumpFloor(self, number):
7+
a, b = 1, 1
8+
for i in range(number):
9+
a, b = b, a+b
10+
return a
11+
12+
# 方法二：递归
13+
class Solution:
14+
def jumpFloor(self, number):
15+
a = [0, 1, 2]
16+
if number in a:
17+
return a[number]
18+
return self.jumpFloor(number-1) + self.jumpFloor(number-2)

‎剑指Offer/09.变态跳台阶.py

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
# f(1)=1 f(2)=2 f(3)=4 f(4)=8
2+
# f(n)=2的n-1次方
3+
class Solution:
4+
def jumpFloorII(self, number):
5+
if number <= 0:
6+
return 0
7+
return pow(2, number-1)

‎剑指Offer/10.矩形覆盖.py

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
# 类似斐波那契数列：f(1)=1 f(2)=2 f(3)=3 f(4)=5
2+
class Solution:
3+
def rectCover(self, number):
4+
if number == 0:
5+
return 0
6+
a, b = 0, 1
7+
for i in range(number):
8+
a, b = b, a+b
9+
return b

0 commit comments

Comments
 (0)