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

‎剑指Offer/11.二进制中1的个数.py

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
# 使用右移运算符，逐位跟1进行'与'运算
2+
class Solution:
3+
def NumberOf1(self, n):
4+
return sum([(n>>i & 1) for i in range(32)])

‎剑指Offer/12.数值的整数次方.py

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
# 方法一：累乘
2+
class Solution:
3+
def Power(self, base, exponent):
4+
if base == 0:
5+
return False
6+
if exponent == 0:
7+
return 1
8+
res = 1
9+
for i in range(abs(exponent)):
10+
res *= base
11+
if exponent < 0:
12+
return 1/res
13+
return res
14+
15+
# 方法二：使用pow()函数
16+
class Solution:
17+
def Power(self, base, exponent):
18+
return pow(base, exponent)

‎剑指Offer/13.调整数组顺序使奇数位于偶数前面.py

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
# 方法一：使用一个数组
2+
class Solution:
3+
def reOrderArray(self, array):
4+
l = []
5+
for i in range(len(array)):
6+
# 逆序访问，是奇数则插到数组第一位
7+
if array[-1-i]%2 != 0:
8+
l.insert(0, array[-1-i])
9+
# 顺序访问，是偶数则追加到数组后面
10+
if array[i]%2 == 0:
11+
l.append(array[i])
12+
return l
13+
14+
# 方法二：使用两个数组，分别存放奇数和偶数
15+
class Solution:
16+
def reOrderArray(self, array):
17+
a = [x for x in array if x%2]
18+
b = [x for x in array if not x%2]
19+
return a+b

‎剑指Offer/14.链表中倒数第k个结点.py

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
# 方法一：数组存储链表结点值
2+
class Solution:
3+
def FindKthToTail(self, head, k):
4+
l = []
5+
while head:
6+
l.append(head)
7+
head = head.next
8+
if k>len(l) or k<1:
9+
return None
10+
return l[-k]
11+
12+
# 方法二：使用两个指针
13+
# 两个指针指向head，第一个指针先走k步。然后两个指针同时往后移，当第一个指针到达末尾时，第二个指针即在倒数第k个结点
14+
class Solution:
15+
def FindKthToTail(self, head, k):
16+
front, later = head, head
17+
for i in range(k):
18+
if not front:
19+
return
20+
if not front.next and i==k-1:
21+
return head
22+
front = front.next
23+
while front.next:
24+
front = front.next
25+
later = later.next
26+
return later.next

‎剑指Offer/15.反转链表.py

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
# pre指向已反序的最后一个结点，pHead指向正在反序的结点，after指向下一个要反序的结点
2+
class Solution:
3+
def ReverseList(self, pHead):
4+
if not pHead or not pHead.next:
5+
return pHead
6+
pre, after = None, None
7+
while pHead:
8+
after = pHead.next
9+
pHead.next = pre
10+
pre = pHead
11+
pHead = after
12+
return pre

‎剑指Offer/16.合并两个排序的链表.py

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
# 递归
2+
class Solution:
3+
# 方法作用：比较两个节点的值，合并较小者到链表
4+
def Merge(self, pHead1, pHead2):
5+
head = None
6+
# 终止条件是一个链表为空，处理方法是返回另一个链表
7+
if not pHead1:
8+
return pHead2
9+
if not pHead2:
10+
return pHead1
11+
else:
12+
if pHead1.val <= pHead2.val:
13+
head = pHead1
14+
# 提取重复逻辑
15+
head.next = self.Merge(pHead1.next, pHead2)
16+
else:
17+
head = pHead2
18+
head.next = self.Merge(pHead1, pHead2.next)
19+
return head

‎剑指Offer/17.树的子结构.py

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
# 递归：寻找相同结点需要递归，判断是否为子结构也需要递归
2+
3+
class Solution:
4+
# 方法作用：A中寻找与B根结点相同的节点，并判断B是否为A的子结构
5+
def HasSubtree(self, pRoot1, pRoot2):
6+
# 终止条件：A或B的根节点为空
7+
if not pRoot1 or not pRoot2:
8+
# 处理方法
9+
return False
10+
# 提取重复逻辑
11+
return self.is_subtree(pRoot1, pRoot2) or self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)
12+
13+
# 方法作用：判断两个结点是否相同
14+
def is_subtree(self, A, B):
15+
# 终止条件：B先遍历完则返回ture
16+
if not B:
17+
return True
18+
# 终止条件：A先遍历完或AB的值不相等，说明不是子结构
19+
if not A or A.val != B.val:
20+
return False
21+
# 提取重复逻辑。否则两值相等，再递归判断左右子树的值
22+
return self.is_subtree(A.left, B.left) and self.is_subtree(A.right, B.right)

‎剑指Offer/18.二叉树镜像.py

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
class Solution:
2+
# 方法作用：交换左右子树
3+
def Mirror(self, root):
4+
if root:
5+
root.left, root.right = root.right, root.left
6+
self.Mirror(root.left)
7+
self.Mirror(root.right)

0 commit comments

Comments
 (0)