01.青蛙跳&爬楼梯

1、爬楼梯

• 70.爬楼梯 (opens new window)

• 假设你正在爬楼梯需要 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级台阶： 剩n−1 个台阶，此情况共有 f(n-1)种跳法
  • 当为2级台阶： 剩 n-2个台阶，此情况共有 f(n-2)种跳法
• 状态定义： 设 dp 为一维数组，其中 dp[i] 的值代表斐波那契数列的第 i 个数字
• 转移方程： dp[i+1]=dp[i]+dp[i−1] ，即对应数列定义 f(n+1)=f(n)+f(n−1)
• 初始状态： dp[0]=1, dp[1]=1 ，即初始化前两个数字
• 返回值： dp[n] ，即斐波那契数列的第 n 个数字

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        else:
            return self.climbStairs(n-1) + self.climbStairs(n-2)

2、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

• 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)
'''

3、三级台阶问题

#! /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

02.图书整理II

• LCR 125.图书整理 II (opens new window)

• 读者来到图书馆排队借还书，图书管理员使用两个书车来完成整理借还书的任务

• 书车中的书从下往上叠加存放，图书管理员每次只能拿取书车顶部的书

• 排队的读者会有两种操作：

  • push(bookID)：把借阅的书籍还到图书馆
  • pop()：从图书馆中借出书籍

• 为了保持图书的顺序，图书管理员每次取出供读者借阅的书籍是 最早 归还到图书馆的书籍

• 你需要返回 每次读者借出书的值

• 如果没有归还的书可以取出，返回 -1

1、Python

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

04.斐波那契数列

• LCR 126. 斐波那契数 (opens new window)

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

• 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)
}

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]

• 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]
}

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目录下所有文件

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)

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)

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)

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()

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()

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()

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()对象内存地址相同，说明使用的•同一个类，没有重复建立类

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)

10.LRU 缓存机制

• 146.LRU 缓存机制 (opens new window)

• LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存

• int get(int key)

  • 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1

• void put(int key, int value)

  • 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」
  • 当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间

1、Python

• 核心思想: 淘汰最久未使用的缓存项
• 驱动原则: 基于时间维度的“最近使用”
• 工作原理:
  • LRU 维护一个有序的结构（如双向链表或队列），记录每个缓存项的访问顺序
  • 当一个缓存项被访问时，将其移动到队首
  • 每次缓存满时，移除队尾的元素（即最久未使用的缓存项）

# -*- coding:utf-8 -*-
class LRUCache:
    def __init__(self, size=3):
        self.cache = {}  # 缓存系统中的数据 (key: val)
        self.keys = []   # 用于存放缓存中数据的key
        self.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 -1  # 如果键不存在，返回-1

    def put(self, key, value):
        if key in self.cache:
            # 如果键已存在，更新值并将键移到列表头部
            self.keys.remove(key)
            self.keys.insert(0, key)
            self.cache[key] = value
        else:
            if len(self.keys) >= self.size:
                # 如果缓存已满，移除最久未使用的键值对
                old_key = self.keys.pop()  # 从列表尾部移除最久未使用的键
                del self.cache[old_key]  # 从字典中删除对应的值
            
            # 插入新的键值对
            self.keys.insert(0, key)  # 将新键插入到列表头部
            self.cache[key] = value  # 更新字典

# 示例使用
# cache = LRUCache(2)
# cache.put(1, 1)
# cache.put(2, 2)
# print(cache.get(1))  # 返回 1
# cache.put(3, 3)      # 该操作会使得关键

11.用栈实现队列

• 232.用栈实现队列 (opens new window)

• 请你仅使用两个栈实现先入先出队列

• 队列应当支持一般队列支持的所有操作（push、pop、peek、empty）

• void push(int x) 将元素 x 推到队列的末尾

• int pop() 从队列的开头移除并返回元素

• int peek() 返回队列开头的元素

• boolean empty() 如果队列为空，返回 true ；否则，返回 false

1、Python

class MyQueue:

    def __init__(self):
        # 初始化两个栈
        self.stack_in = []
        self.stack_out = []

    def push(self, x: int) -> None:
        # 将元素推入 stack_in
        self.stack_in.append(x)

    def pop(self) -> int:
        # 如果 stack_out 为空，将 stack_in 中的元素倒入 stack_out
        self._move_in_to_out()
        # 从 stack_out 中弹出并返回元素
        return self.stack_out.pop()

    def peek(self) -> int:
        # 如果 stack_out 为空，将 stack_in 中的元素倒入 stack_out
        self._move_in_to_out()
        # 返回 stack_out 的顶部元素
        return self.stack_out[-1]

    def empty(self) -> bool:
        # 如果两个栈都为空，则队列为空
        return not self.stack_in and not self.stack_out

    def _move_in_to_out(self) -> None:
        # 将 stack_in 中的元素全部移动到 stack_out
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())

12.最小栈

• 155.最小栈 (opens new window)
• 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈

1、Python

• 通过使用两个栈来实现 MinStack 类，一个栈用于存储所有的元素，另一个栈用于存储当前的最小值
• 这样可以在常数时间内检索到最小元素

class MinStack:

    def __init__(self):
        # 初始化两个栈
        self.stack = []
        self.minStack = []

    def push(self, val):
        # 将元素推入主栈
        self.stack.append(val)
        # 如果辅助栈为空，或者当前值小于等于辅助栈栈顶值，则将该值推入辅助栈
        if not self.minStack or val <= self.minStack[-1]:
            self.minStack.append(val)

    def pop(self):
        # 弹出主栈栈顶元素
        top = self.stack.pop()
        # 如果弹出的元素等于辅助栈栈顶元素，则辅助栈也弹出
        if top == self.minStack[-1]:
            self.minStack.pop()

    def top(self):
        # 获取主栈栈顶元素
        return self.stack[-1]

    def getMin(self):
        # 获取辅助栈栈顶元素，即最小元素
        return self.minStack[-1]

13.用 Rand70 实现 Rand10()

• 470.用 Rand70 实现 Rand10() (opens new window)

• 给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数

输入: 3
输出: [3,8,10]

1、Python

• rand7() 函数生成 [1, 7] 范围内的均匀随机整数

• 使用 (rand7() - 1) * 7 + rand7() 生成一个范围是 [1, 49] 的均匀随机整数

• 如果生成的数在 [1, 40] 范围内，则可以通过 num % 10 + 1 将其映射到 [1, 10] 范围

• 如果生成的数在 [41, 49] 范围内，则丢弃重新生成，直到生成的数落在 [1, 40] 范围内为止

• 通过这种方法，生成的 [1,10] 范围内的整数是均匀分布的

import random

class Solution:
    def rand7(self):
        return random.randint(1, 7)

    def rand10(self):
        while True:
            # 生成一个范围是 [1,49] 的随机数
            num = (self.rand7() - 1) * 7 + self.rand7()
            # 如果随机数在 [1,40] 范围内，则映射到 [1,10]
            if num <= 40:
                return num % 10 + 1

14.LFU 缓存

• 460.LFU 缓存 (opens new window)

• 核心思想: 淘汰访问频率最低的缓存项。

• 驱动原则: 基于访问次数的“使用频率”。

• 工作原理:

  • LFU 维护每个缓存项的访问计数器，每当缓存项被访问时，计数器加一
  • 当缓存满时，移除访问次数最少的缓存项
  • 如果多个缓存项的计数相同，可以进一步使用 LRU 原则决定淘汰哪一个

1、Python

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity  # 缓存的最大容量
        self.min_freq = 0  # 当前缓存中最小的使用频率
        self.key_to_val_freq = {}  # 用于存储 key -> (value, freq)
        self.freq_to_keys = {}  # 用于存储 freq -> [keys]，每个频率对应的 keys 列表

    def _update_freq(self, key: int):
        """更新键的使用频率，并调整相应的结构"""
        value, freq = self.key_to_val_freq[key]

        # 从当前频率的列表中移除该 key
        self.freq_to_keys[freq].remove(key)

        # 如果当前频率列表为空且该频率是最小频率，更新最小频率
        if not self.freq_to_keys[freq]:
            del self.freq_to_keys[freq]
            if self.min_freq == freq:
                self.min_freq += 1

        # 更新 key 的频率并插入到新的频率列表中
        new_freq = freq + 1
        self.key_to_val_freq[key] = (value, new_freq)
        if new_freq not in self.freq_to_keys:
            self.freq_to_keys[new_freq] = []
        self.freq_to_keys[new_freq].append(key)

    def get(self, key: int) -> int:
        if key not in self.key_to_val_freq:
            return -1  # 如果 key 不存在，返回 -1

        # 更新该 key 的频率并返回其值
        self._update_freq(key)
        return self.key_to_val_freq[key][0]

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return  # 容量为 0 时，直接返回

        if key in self.key_to_val_freq:
            # 如果 key 已存在，更新其值和频率
            self.key_to_val_freq[key] = (value, self.key_to_val_freq[key][1])
            self._update_freq(key)
        else:
            # 如果 key 不存在且缓存已满，移除最不经常使用的键
            if len(self.key_to_val_freq) >= self.capacity:
                # 从最小频率列表中移除最先插入的 key
                least_freq_keys = self.freq_to_keys[self.min_freq]
                evict_key = least_freq_keys.pop(0)
                if not least_freq_keys:
                    del self.freq_to_keys[self.min_freq]
                del self.key_to_val_freq[evict_key]

            # 插入新 key 和 value，并设置初始频率为 1
            self.key_to_val_freq[key] = (value, 1)
            if 1 not in self.freq_to_keys:
                self.freq_to_keys[1] = []
            self.freq_to_keys[1].append(key)
            self.min_freq = 1  # 新插入的 key 频率为 1，更新 min_freq

15.连通图拷贝

• 给你无向 连通图 中一个节点的引用，请你返回该图的 深拷贝（克隆）

• 图中的每个节点都包含它的值 int val 和其邻居的列表List<Node>

• 邻接表 neighbors 描述了图中节点的邻居集

======= 原图 ========  
         1
       /   \
      4     3
     /       \
    4 ------- 6
======= 深拷贝 =======
          1'
        /   \
       4'    3'
      /       \
     4' ------ 6'

1、Python

class Node:
    def __init__(self, val: int, neighbors):
        self.val = val  # 当前节点的值
        # 邻居列表，若未提供则初始化为空列表
        self.neighbors = neighbors if neighbors is not None else []

class Solution:
    def deepCopy(self, root):
        if not root:      # 如果原始图为空，返回 None
            return None
        node_dic = {}     # 哈希表，用于记录已经克隆过的节点，避免重复克隆和死循环

        def dfs(node):
            if node in node_dic:         # 如果该节点已经被克隆过，直接返回克隆结果
                return node_dic[node]

            clone = Node(node.val)       # 创建当前节点的克隆对象（此时还没有邻居）
            node_dic[node] = clone       # 把克隆节点存入哈希表，防止后续重复克隆

            # 遍历当前节点的邻居列表，递归克隆邻居并加入克隆节点的邻居列表中
            for neighbor in node.neighbors:
                clone.neighbors.append(dfs(neighbor))

            return clone     # 返回当前节点的克隆对象

        return dfs(root)     # 从原始图的 root 节点开始克隆整个图