10.其他
# 01.青蛙跳&爬楼梯
# 1.1 题目描述
- 一只青蛙一次可以跳上1级台阶,也可以跳上2级。
- 求该青蛙跳上一个n级的台阶总共有多少种跳法
# 1.2 实现思路
- 思路
# 1、n=1 时只有一种方法
f(1) = 1
# 2、n=2 时当第一次跳一个台阶时,有一种方法,当第一次跳两个台阶时有一种方法
f(2) = 1+1 = 2
# 3、n=3 倒推最后一跳跳一步有f(n-1)种方法 最后一跳跳两步f(n-2)
f(3) = f(2) + f(1) = 3
# 4、n>2 以此类推
f(n) = f(n-1)+f(n-2)
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
- 二级台阶
- 当为1级台阶: 剩n−1 个台阶,此情况共有 f(n-1)种跳法
- 当为2级台阶: 剩 n-2个台阶,此情况共有 f(n-2)种跳法。
# 1.2.1 python
#! /usr/bin/env python
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(1000000000) #设置系统最大递归深度
def fib(n):
if n <= 2:
return n
else:
return fib(n-1) + fib(n-2)
print(fib(4)) # 5
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 1.2.2 golang
package main
import (
"fmt"
)
var mapData = make(map[int]int, 0)
func climbStairs(n int) int {
if n <= 2 {
return n
}
if _, ok := mapData[n]; !ok {
mapData[n] = climbStairs(n-1) + climbStairs(n-2)
}
return mapData[n] // 如果有缓存,可以直接取出来,避免重复计算
}
func main() {
v := climbStairs(4) // 5
fmt.Println(v)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 1.3 n级台阶问题
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。
求该青蛙跳上一个n级的台阶总共有多少种跳法
思路
#! /usr/bin/env python
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(1000000000) #设置系统最大递归深度
def fib(n):
if n <= 2:
return n
else:
return 2 * fib(n - 1)
print(fib(4)) # 8
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
- n级台阶推演
# 1、n=1 时只有一种方法
f(1) = 1
# 2、n=2 时当第一次跳一个台阶时,有一种方法,当第一次跳两个台阶时有一种方法
f(n) = 1+1 = 2
# 3、n=3 时当第一次跳一个台阶时有f(3-1)中方法,当第一次跳两个台阶时有f(3-2)中方法,当第一次跳3个台阶时有f(3-3)种跳法
f(n) = 2+1 = 3
# 4、n>2 以此类推
f(n) = f(n-1)+f(n-2)+......f(0)
'''
f(n) = f(n-1)+f(n-2)+......f(0)种跳法
f(n-1) = f(n-2)+f(n-3)+.....f(0)
f(n)-f(n-1)=f(n-1)
所以f(n) = 2*f(n-1)
'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 1.4 三级台阶问题
#! /usr/bin/env python
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(1000000000) #设置系统最大递归深度
def fib(n):
if n <= 2:
return n
elif n == 3:
return 4
else:
return fib(n-1) + fib(n-2) + fib(n-3)
print(fib(4)) # 7
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 02.用两个栈实现队列
请实现它的两个函数 appendTail 和 deleteHead
分别完成在队列尾部插入整数
在队列头部删除整数的功能。
(若队列中没有元素,deleteHead 操作返回 -1 )
class CQueue:
def __init__(self):
self.stack_in = []
self.stack_out = []
def appendTail(self, value):
self.stack_in.append(value)
def deleteHead(self):
if not self.stack_out:
if not self.stack_in: # 都为空
return -1
else: # 把in栈中的东西全部倒入out栈中
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
return self.stack_out.pop()
if __name__ == '__main__':
cq = CQueue() # 1 ->2 ->3 ->4
cq.appendTail(1)
cq.appendTail(2)
cq.appendTail(3)
cq.appendTail(4)
print( cq.deleteHead() ) # 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 03.最小栈
# 3.1 题目描述
- 设计一个支持
push
,pop
,top
操作,并能在常数时间内检索到最小元素的栈 - push(x) —— 将元素 x 推入栈中。
- pop() —— 删除栈顶的元素。
- top() —— 获取栈顶元素。
- getMin() —— 检索栈中的最小元素。
pop
、top
和getMin
操作总是在 非空栈 上调用。
# 3.2 解题思路
- 在每个元素
a
入栈时把当前栈的最小值m
存储起来。在这之后无论何时,如果栈顶元素是a
,我们就可以直接返回存储的最小值m
。 - 题目要求在常数时间内获得栈中的最小值,因此不能在 getMin() 的时候再去计算最小值
- 最好应该在 push 或者 pop 的时候就已经计算好了当前栈中的最小值。
- 即每次新元素
x
入栈的时候保存一个元组:(当前值 x,栈内最小值)top()
函数是获取栈顶的当前值,即栈顶元组的第一个值getMin()
函数是获取栈内最小值,即栈顶元组的第二个值pop()
函数时删除栈顶的元组。
class MinStack(object):
def __init__(self):
self.stack = []
def push(self, x):
# 每次新元素 `x` 入栈的时候保存一个元组:(当前值 x,栈内最小值)
if not self.stack:
self.stack.append((x, x))
else:
# self.stack[-1][1] 是栈顶元素中最小值
self.stack.append((x, min(x, self.stack[-1][1])))
def pop(self):
self.stack.pop()
def top(self):
return self.stack[-1][0]
def getMin(self):
return self.stack[-1][1]
obj = MinStack()
obj.push(3) # [(3,3)]
obj.push(2) # [(3,3),(2,2)]
obj.push(4) # [(3,3),(2,2),(4,2)]
print( obj.top() ) # 4
print( obj.getMin() ) # 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 04.斐波那契数列
# 4.1 斐波拉契01
- 输入
n
,求斐波那契数列的第n
项(即F(N)
)
def fib(n):
a, b = 0, 1
for i in range(n): # 求斐波拉契中第n个数的值
a, b = b, a + b
return a % 1000000007
print( fib(10) ) # 55
1
2
3
4
5
6
7
2
3
4
5
6
7
- golang
package main
import (
"fmt"
)
// 斐波那契数列的第 n 项(即 F(N))
func fib(n int) int {
a, b := 0, 1
for i := 0; i < n; i++ {
a, b = b, a + b
a = a % 1000000007
}
return a
}
func main() {
v := fib(95) // 55
fmt.Println(v)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 4.2 斐波拉契02
- 输入n,求斐波拉契中n以内的所有数
def fib(max_num):
a,b = 0,1
while a < max_num:
yield b
a,b=b,a+b
g = fib(10)
print(list(g)) #生成一个生成器:[1,2, 3, 5, 8, 13]
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
- golang
package main
import (
"fmt"
)
// 斐波那契数列的第 n 项(即 F(N))
func fib(n int) []int {
vals := []int{}
a,b := 0,1
for a < n {
vals = append(vals, b)
a,b =b, a+b
}
return vals
}
func main() {
v := fib(10) // 55
fmt.Println(v) // [1 1 2 3 5 8 13]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 05.遍历文件夹
import os
def gci(filepath):
files = os.listdir(filepath) # 遍历filepath下所有文件,包括子目录
for fi in files:
fi_d = os.path.join(filepath, fi)
if os.path.isdir(fi_d):
gci(fi_d)
else:
print(os.path.join(filepath, fi_d))
gci('C:\Go') # 递归遍历/root目录下所有文件
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 06.读取大文件
def read_big_file_v(fname):
block_size = 1024 * 8
with open(fname,encoding="utf8") as fp:
while True:
chunk = fp.read(block_size)
# 当文件没有更多内容时,read 调用将会返回空字符串 ''
if not chunk:
break
print(chunk)
path = r'C:\aaa\luting\edc-backend\tttt.py'
read_big_file_v(path)
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 07.大文件拆分处理
# 7.1 创建100万测试数据
import random
with open('test.txt', 'w') as f:
for i in range(1000000):
n = random.randint(1, 100)
f.write('www.example.com%s\n'%n)
1
2
3
4
5
2
3
4
5
# 7.2 50亿数据中找出相同的URL
- 题目1:从两个文件50亿数据中找出相同的URL
import os,threading
# 将大文件url根据 hash值 拆分到 10 个文件中
def hash_split(fromfile,todir):
with open(fromfile) as f:
url = f.readline()
while url:
count = count + 1
h_hash = hash(url) % 10
filename = os.path.join(todir,str(h_hash)+".txt")
fileobj = open(filename,'a')#make partfile
fileobj.write(url) #write data into partfile
fileobj.close()
url = f.readline()
# 使用多线程,分别去处理
def read_data(path_dir):
pash_list = os.listdir(todir)
for file_name in pash_list:
file_path = path_dir + "\\" + file_name
t = threading.Thread(target=handle_per_file, args=(file_path,))
t.start()
# 处理文件的方法
def handle_per_file(file_path):
d = {}
with open(file_path,'r') as f:
for line in f.readlines():
d[line] = d.get(line,0) + 1
print(d) # 这里已经可以将一个file变成字典
# 后面只需要打开 file_path2,依次读取和字典进行比较即可
'''
{'www.example.com31\n': 10042,
{'www.example.com100\n': 9991,
{'www.example.com2\n': 9838, '
{'www.example.com28\n': 10110,
'''
if __name__ == "__main__":
todir = r"C:\tmp\celery_test\data"
fromfile = r"C:\tmp\celery_test\data\test.txt"
hash_split(fromfile, todir)
read_data(todir)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# 7.3 50亿条数据排序
分治——根据数据存在文件中的位置分裂文件到批量小文件中
因为数据量太大了!我们不得不将大事化小,小事化了。
这里我们的做法是每次读取待排序文件的10000个数据,把这10000个数据进行快速排序
再写到一个小文件bigdata.part.i.sorted中。这样我们就得到了50000个已排序好的小文件了。
有已排序小文件的基础上,我只要每次拿到这些文件中当前位置的最小值就OK了。
再把这些值依次写入bigdata.sorted中。
# 08.装饰器
# 8.1 手写普通装饰器
def outer_wrapper(func):
def wrapper(*args, **kwargs):
print('---->')
res = func(*args, **kwargs)
return wrapper
@outer_wrapper
def home():
print("welcome to home page")
return "from home"
home()
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 8.2 装饰器计算运行时间
import time
def timer(func): #timer(test1) func=test1
def deco(*args,**kwargs):
start_time = time.time()
func(*args,**kwargs) #run test1
stop_time = time.time()
print("running time is %s"%(stop_time-start_time))
return deco
@timer # test1=timer(test1)
def test1():
time.sleep(3)
print("in the test1")
test1()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 8.3 三级装饰器
def auth(auth_type):
def outer_wrapper(func):
def wrapper(*args, **kwargs):
print("---->", auth_type)
res = func(*args, **kwargs)
return wrapper
return outer_wrapper
@auth(auth_type="local") # home = wrapper()
def home():
print("welcome to home page")
return "from home"
home()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 09.单例模式
- 1、单例模式:永远用一个对象得实例,避免新建太多实例浪费资源
- 2、实质:使用__new__方法新建类对象时先判断是否已经建立过,如果建过就使用已有的对象
- 3、使用场景:如果每个对象内部封装的值都相同就可以用单例模式
# 9.1 单例模式01
class Foo(object):
instance = None
def __init__(self):
self.name = 'alex'
def __new__(cls, *args, **kwargs):
if Foo.instance:
return Foo.instance
else:
Foo.instance = object.__new__(cls,*args,**kwargs)
return Foo.instance
obj1 = Foo() # obj1和obj2获取的就是__new__方法返回的内容
obj2 = Foo()
print(obj1,obj2) # 运行结果: <__main__.Foo object at 0x00D3B450> <__main__.Foo object at 0x00D3B450>
# 运行结果说明:
# 这可以看到我们新建的两个Foo()对象内存地址相同,说明使用的•同一个类,没有重复建立类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 9.2 单例模式02
class Singleton(object):
def __new__(cls, *args, **kwargs): #new方法最后返回的是一个实例
if not hasattr(cls, "_instance"): #如果没有这个字段就调用父类创建
cls._instance = super(Singleton, cls).__new__(cls)
return cls._instance #永远返回的就是第一次创建的对象
obj1 = Singleton()
obj2= Singleton()
print(obj1,obj2)
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 10.LRU 缓存机制
# 10.1 题目说明
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key)
- 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
void put(int key, int value)
- 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。
- 当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。
# 10.2 答案
1)使用三个数据标识这个缓存系统
- self.cache = {} # cache模拟所有缓存系统中数据 key: val
- self.keys = [] # keys只存放cache字典中的 key
- self.size = size # size 来定义这个缓存系统最大容量
2)模拟数据加入缓存(set)
- 1.如果缓存为达到最大长度,新数据key插入到 keys列表头部,将key:val存入字典
- 2.如果达到最大长度,先删除最后列表keys最后一个元素,将这个key:val 从cache字典中删除
3)模拟获取缓存数据(get)
- 1.判断获取的key是否在 cache字典中,如果在就从列表keys中先删除原有key,然后将key插入到列表最前面,并返回val
- 2.如果key不在cache字典中,直接返回None即可
#!/usr/bin/env python
# -*- coding:utf-8 -*-
class LRUcache:
def __init__(self, size=3):
self.cache = {} # cache模拟所有缓存系统中数据 key: val
self.keys = [] # keys只存放cache字典中的 key
self.size = size # size 来定义这个缓存系统最大容量
def get(self, key):
if key in self.cache:
self.keys.remove(key)
self.keys.insert(0, key)
return self.cache[key]
else:
return None
def set(self, key, value):
if key in self.cache:
self.keys.remove(key)
self.keys.insert(0, key)
self.cache[key] = value
elif len(self.keys) == self.size:
old = self.keys.pop()
self.cache.pop(old)
self.keys.insert(0, key)
self.cache[key] = value
else:
self.keys.insert(0, key)
self.cache[key] = value
if __name__ == '__main__':
test = LRUcache()
test.set('a', 1)
test.set('b', 2)
test.set('c', 3)
test.set('d', 4)
print(test.keys) # ['d', 'c', 'b']
print(test.cache) # {'c': 3, 'b': 2, 'd': 4}
print(test.get('a')) # None 当d=4加入缓存是,缓存到达上线3,所以把a从缓存中移除了
print(test.get('b')) # 2
print(test.get('c')) # 3
print(test.get('d')) # 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
编辑 (opens new window)
上次更新: 2024/3/13 15:35:10