Hello World
type: channel
link: https://www.ronie.ren/
description: Your description here.
items: redis 限流
items: Nginx 配置文件注释
items: 复杂sql记录
items: docker compose kafka
items: docker-compose-redis
items: LeetCode（2024-01-12）
items: LeetCode（2024-01-11）
items: LeetCode（2024-01-10）
items: LeetCode（2024-01-09）
items: LeetCode（2024-01-08）

redis 限流
type: item
date: 2025-12-31T09:34:21+00:00
description: redis 限流redis 令牌桶限流@dataclass(frozen=True) class RateLimitResult: allowed: bool remaining_tokens: float retry_after_seconds: float now_ms: int class RedisTokenBucketRateLimiter: _TOKEN_BUCKET_LUA = r""" local key = KEYS[1] -- 令牌桶状态存储的 Redis Key（Hash） local capacity = tonumber(ARGV[1]) -- 桶容量：最多可累积的令牌数 local rate = tonumber(ARGV[2]) -- 补充速率：每秒补充多少令牌（tokens/s） local requested = tonumber(ARGV[3]) -- 本次请求要消耗的令牌数 local ttl_ms = tonumber(ARGV[4]) -- 令牌桶 Key 的过期时间（毫秒），用于回收冷 Key local t = redis.call('TIME') -- 读取 Redis 服务器时间：{秒, 微秒} local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000) -- 服务器时间换算为毫秒时间戳 local data = redis.call('HMGET', key, 'tokens', 'ts') -- 读取当前令牌数(tokens)与上次更新时间(ts) local tokens = tonumber(data[1]) -- 当前令牌数（可能为 nil） local ts = tonumber(data[2]) -- 上次更新时间戳（毫秒，可能为 nil） if tokens == nil then tokens = capacity end -- 初始化：若不存在，则认为桶是满的 if ts == nil then ts = now end -- 初始化：若不存在，则将上次更新时间设为当前 if now < ts then ts = now end -- 防御：若时钟回拨导致 now < ts，则强制对齐 local delta_ms = now - ts -- 距离上次更新过去了多少毫秒 local refill = (delta_ms / 1000.0) * rate -- 这段时间应补充的令牌数量（可为小数） tokens = math.min(capacity, tokens + refill) -- 将令牌补充后并截断到容量上限 local allowed = 0 -- 是否允许：0/1（Lua 没有布尔返回给 Python 的统一类型） local retry_after_ms = 0 -- 如果不允许，建议等待多少毫秒再试 if tokens >= requested then -- 若令牌充足 allowed = 1 -- 标记允许 tokens = tokens - requested -- 扣除本次消耗 else -- 否则令牌不足 allowed = 0 -- 标记拒绝 if rate > 0 then -- 若补充速率 > 0，可计算需要等待的时间 local missing = requested - tokens -- 还差多少令牌 retry_after_ms = math.ceil((missing / rate) * 1000) -- 差额按速率换算为等待毫秒数（向上取整） else -- 若 rate=0，则永远补不回令牌 retry_after_ms = -1 -- 用 -1 表示无法通过等待获得令牌 end -- 结束 rate>0 分支 end -- 结束 tokens>=requested 分支 redis.call('HMSET', key, 'tokens', tokens, 'ts', now) -- 写回最新 tokens 与 ts（原子更新） if ttl_ms ~= nil and ttl_ms > 0 then -- 若配置了过期时间且 >0 redis.call('PEXPIRE', key, ttl_ms) -- 给令牌桶 Key 设置过期（毫秒） end -- 结束 ttl 分支 return {allowed, tokens, retry_after_ms, now} -- 返回：是否允许、剩余令牌、建议等待(ms)、当前时间(ms) """ def __init__( self, redis: Optional[AsyncRedis…

Nginx 配置文件注释
type: item
date: 2025-03-27T07:00:49+00:00
description: user nobody; # Nginx worker进程运行的用户及用户组 worker_processes 4; # 在master/worker运行方式下，定义worker进程的个数; 可以为auto worker_rlimit_nofile 65535; # 设置 Nginx worker 进程可以打开的最大文件描述符数量。这个指令通常用于确保 Nginx 能够处理大量并发连接，因为每个连接通常会占用一个文件描述符。 worker_rlimit_core 1m; # 通过worker_rlimit_core配置可以限制core文件的大小 working_directory /usr/local/lighthouse/softwares/nginx/coredump; # 设置coredump文件所放置的目录 daemon on; # 是否以守护进程方式运行Nginx master_process on; # 是否以 master/worker 方式工作 worker_cpu_affinity 1000 0100 0010 0001; # 绑定worker进程到指定的CPU内核 error_log logs/error.log notice; # error_log/path/file level; timer_resolution 100ms; # 每次内核的事件调用（如epoll、select、poll、kqueue等）返回时，都会执行一次gettimeofday，实现用内核的时钟来更新Nginx中的缓存时钟。 events { # 处理网络连接设置的核心部分 debug_connection 10.224.66.14; # 仅仅来自以上IP地址的请求才会输出debug级别的日志 debug_connection 10.224.57.0/24; # 其他请求仍然沿用error_log中配置的日志级别 accept_mutex on; # 负载均衡锁 accept锁默认是打开的，如果关闭它，那么建立TCP连接的耗时会更短，但worker进程之间的负载会非常不均衡 accept_mutex_delay 500ms; # 使用accept锁后，同一时间只有一个worker进程能够取到accept锁。这个accept锁不是阻塞锁，如果取不到会立刻返回。 如果有一个worker进程试图取accept锁而没有取到，它至少要等accept_mutex_delay定义的时间间隔后才能再次试图取锁。 multi_accept off; # 当事件模型通知有新连接时，尽可能地对本次调度中客户端发起的所有TCP请求都建立连接。 use epoll; # 事件驱动模型 worker_connections 8192; # 每个worker进程可以同时处理的最大连接数。 } http { include mime.types; default_type application/octet-stream; log_format combinedio '$remote_addr - $remote_user [$time_local] ' '"$request" $status $body_bytes_sent ' '"$http_referer" "$http_user_agent" $request_length $request_time $upstream_response_time'; access_log logs/access.log combinedio; sendfile on; # 硬盘 >> kernel buffer >> user buffer>> kernel socket buffer >>协议栈 | 硬盘 >> kernel buffer (快速拷贝到kernelsocket buffer) >>协议栈 gzip on; # 压缩响应内容 tcp_nopush on; # 数据量达到一定值后发送 tcp_nodelay on; # 对keepalive连接是否使用TCP_NODELAY选项。# 应用程序每产生一次操作就会发送一个包, delay 会等待数据，因此操作后它不会发送一个数据包，而是将这段时间内的数据打成一个大的包 keepalive_timeout 0; # 一个keepalive连接在闲置超过一定时间后,服务器关闭这个连接。 client_body_timeout 10; # second HTTP包体 client_header_timeout 10; # second 客户端与服务器建立连接后将开始接收HTTP头部，在这个过程中，如果在一个时间间隔（超时时间）内没有读取到客户端发来的字节，则认为超…

复杂sql记录
type: item
date: 2025-03-27T06:43:41+00:00
description: 字段存储，设计必须这么存fieldis_showis_dup_keyxxx00xxx10xxx01sql查询时压缩，c_rule_md5与业务表关联，这是query1SELECT c_rule_md5, field_id, MAX(is_show) AS is_show, MAX(is_dup_key) AS is_dup_key FROM t_rel_complicated_rules_fields trcrf WHERE trcrf.is_dup_key != 1字段信息和字段表和表基本信息表连接查询，获取字段所属表名称，字段名称，字段中文名等，这是query5SELECT ttf.column_name_cn, ttf.column_name, ttbi.table_name, ttbi.table_schema, ttbi.table_schema_cn, ttbi.table_name_cn, query1.c_rule_md5, query1.is_show, query1.is_dup_key, ttf.id AS field_id FROM ( SELECT c_rule_md5, field_id, MAX( is_show ) AS is_show, MAX( is_dup_key ) AS is_dup_key FROM t_rel_complicated_rules_fields trcrf WHERE trcrf.is_dup_key != 1 GROUP BY c_rule_md5, field_id ) query1 LEFT JOIN t_table_field ttf ON query1.field_id = ttf.id LEFT JOIN t_table_base_info ttbi ON ttbi.table_schema = ttf.table_schema AND ttbi.table_name = ttf.table_name WHERE ttbi.table_schema = 'db_enterprise' AND ttbi.table_name = 't_address' AND query1.field_id = 396 )查最新一条报告，这是query3SELECT tcrr.id, tcrr.rule_md5, tcrr.is_alarming, tcrr.create_time AS last_execute_time FROM t_complicated_rule_report tcrr JOIN ( SELECT rule_md5, MAX( create_time ) AS max_create_time FROM t_complicated_rule_report GROUP BY rule_md5 ) query2 ON tcrr.rule_md5 = query2.rule_md5 AND tcrr.create_time = query2.max_create_time最新一条报告和主表连接，tcrc与query3左连接，生成query4SELECT tcrc.id AS id, tcrc.rule_name, tcrc.rule_md5, tcrc.rule_type_id AS rule_type_id, tcrc.create_user, tcrc.create_time, tcrc.cron_type, tcrc.rule_status AS is_online, tcrc.rule_update_time, tcrc.online_approve_id, query3.is_alarming AS is_alarming, query3.last_execute_time, tcrc.try_running_percent FROM t_complicated_rule_config tcrc LEFT JOIN ( SELECT tcrr.id, tcrr.rule_md5, tcrr.is_alarming, tcrr.create_time AS last_execute_time FROM t_complicated_rule_report tcrr JOIN ( SELECT rule_md5, MAX( create_time ) AS max_create_time FROM t_complicated_rule_report GROUP BY rule_md5 ) query2 ON tcrr.rule_md5 = query2.rule_md5 AND tcrr.create_time = query2.max_create_t…

docker compose kafka
type: item
date: 2025-02-24T08:59:00+00:00
description: docker kafka 配置文件version: '3.8' name: "kafka-service" # https://docs.docker.com/compose/how-tos/project-name/ services: kafka-server0: image: bitnami/kafka:latest hostname: kafka0 container_name: kafka0 ports: - "9092:9094" environment: KAFKA_CFG_NODE_ID: 0 KAFKA_CFG_BROKER_ID: 0 KAFKA_CFG_LISTENERS: PLAINTEXT://:9092,CONTROLLER://:9093,EXTERNAL://0.0.0.0:9094 KAFKA_CFG_ADVERTISED_LISTENERS: PLAINTEXT://kafka0:9092,EXTERNAL://192.168.60.134:9092 KAFKA_CFG_LISTENER_SECURITY_PROTOCOL_MAP: CONTROLLER:PLAINTEXT,EXTERNAL:PLAINTEXT,PLAINTEXT:PLAINTEXT KAFKA_CFG_CONTROLLER_QUORUM_VOTERS: 1@kafka1:9093,2@kafka2:9093,0@kafka0:9093 KAFKA_CFG_PROCESS_ROLES: broker,controller # KAFKA_CFG_LOG_DIRS: /var/lib/kafka/data KAFKA_CFG_OFFSETS_TOPIC_REPLICATION_FACTOR: 3 KAFKA_CFG_TRANSACTION_STATE_LOG_REPLICATION_FACTOR: 3 KAFKA_CFG_TRANSACTION_STATE_LOG_MIN_ISR: 2 KAFKA_CFG_MIN_INSYNC_REPLICAS: 1 KAFKA_CFG_AUTO_CREATE_TOPICS_ENABLE: true KAFKA_CFG_CONTROLLER_LISTENER_NAMES: CONTROLLER KAFKA_KRAFT_CLUSTER_ID: d6c6ea9d1bfe423ebdc74579b10c61f0 networks: kafka: ipv4_address: 172.16.0.2 volumes: - ~/kafka-data/0:/bitnami/kafka kafka-server1: image: bitnami/kafka:latest hostname: kafka1 container_name: kafka1 ports: - "9094:9094" environment: KAFKA_CFG_NODE_ID: 1 KAFKA_CFG_BROKER_ID: 1 KAFKA_CFG_LISTENERS: PLAINTEXT://:9092,CONTROLLER://:9093,EXTERNAL://0.0.0.0:9094 KAFKA_CFG_ADVERTISED_LISTENERS: PLAINTEXT://kafka1:9092,EXTERNAL://192.168.60.134:9094 KAFKA_CFG_LISTENER_SECURITY_PROTOCOL_MAP: CONTROLLER:PLAINTEXT,EXTERNAL:PLAINTEXT,PLAINTEXT:PLAINTEXT KAFKA_CFG_CONTROLLER_QUORUM_VOTERS: 1@kafka1:9093,2@kafka2:9093,0@kafka0:9093 KAFKA_CFG_PROCESS_ROLES: broker,controller # KAFKA_CFG_LOG_DIRS: /var/lib/kafka/data KAFKA_CFG_OFFSETS_TOPIC_REPLICATION_FACTOR: 3 KAFKA_CFG_TRANSACTION_STATE_LOG_REPLICATION_FACTOR: 3 KAFKA_CFG_TRANSACTION_STATE_LOG_MIN_ISR: 2 KAFKA_CFG_MIN_INSYNC_REPLICAS: 1 KAFKA_CFG_AUTO_CREATE_TOPICS_ENABLE: true KAFKA_CFG_CONTROLLER_LISTENER_NAMES: CONTROLLER KAFKA_KRAFT_CLUSTE…

docker-compose-redis
type: item
date: 2025-02-24T08:57:56+00:00
description: RedisRedis-Server通过bitnami/redis:7.4.1实现 redis 主从集群version: '3.8' name: 'redis-service' services: redis-master: image: 'bitnami/redis:7.4.1' container_name: redis-master hostname: redis-master expose: - '6379' environment: - REDIS_REPLICATION_MODE=master - REDIS_PASSWORD=OeLFo2b3GVXKj0Ren1Dh - REDIS_MASTER_PORT_NUMBER=6379 networks: redis: ipv4_address: 192.168.0.2 redis-replica: image: 'bitnami/redis:7.4.1' deploy: replicas: 2 depends_on: - redis-master environment: - REDIS_REPLICATION_MODE=slave - REDIS_MASTER_HOST=192.168.0.2 - REDIS_MASTER_PORT_NUMBER=6379 - REDIS_MASTER_PASSWORD=OeLFo2b3GVXKj0Ren1Dh - REDIS_PASSWORD=OeLFo2b3GVXKj0Ren1Dh networks: redis: networks: redis: driver: bridge name: redis-net ipam: config: - subnet: 192.168.0.0/24 gateway: 192.168.0.1 Redis-Sentinel为保证redis集群高可用，添加redis sentinel监控master节点。version: '3.8' name: 'redis-sentinel-cluster' services: redis-sentinel: image: 'bitnami/redis-sentinel:6.2.16' deploy: replicas: 3 environment: REDIS_SENTINEL_PORT_NUMBER: '26379' REDIS_MASTER_HOST: '192.168.0.2' REDIS_MASTER_PORT_NUMBER: '6379' REDIS_SENTINEL_QUORUM: '2' # 在进行故障转移之前，必须同意主节点失效的 Sentinel 实例的最小数量。 REDIS_MASTER_PASSWORD: 'OeLFo2b3GVXKj0Ren1Dh' REDIS_SENTINEL_DOWN_AFTER_MILLISECONDS: '5000' REDIS_SENTINEL_FAILOVER_TIMEOUT: '5000' REDIS_MASTER_SET: 'mymaster' networks: - redis networks: redis: name: 'redis-net' external: true测试后发现，redis sentinel 能在master节点失效后选举新master节点，但是在docker-compose中只暴露了master节点的6379端口。于是在redis-net网络中添加nginx反代。nginx反代（不可用）nginx-reverse-proxy: image: 'bitnami/nginx:1.27' volumes: - ./nginx.conf:/opt/bitnami/nginx/conf/stream_server_blocks/my_server_block.conf environment: NGINX_ENABLE_STREAM: yes ports: - '6379:6379' networks: redis: depends_on: - redis-replica添加反代后，发现slave节点不能向master节点转发命令（记错了，这个是redis分片集群的功能，分片节点计算键的插槽，该插槽不归该节点管就转发给该管这个插槽的节点）。放弃反代，直接将测试代码接入redis-net网络。问题发现容器内无法访问外部网络(.venv) ronie@ronie:~/PycharmProjects/evilbox$ docker attach 81 / # ping www.baidu.com PING www.baidu.com (180.101.50.188): 56 data bytes…

LeetCode（2024-01-12）
type: item
date: 2024-01-12T09:49:52+00:00
description: 2645. 构造有效字符串的最少插入数2645. 构造有效字符串的最少插入数class Solution: def addMinimum(self, word: str) -> int: res = ord(word[0]) - ord(word[-1]) + 2 for i in range(1, len(word)): res += (ord(word[i]) - ord(word[i - 1]) + 2) % 3 return res1020. 飞地的数量1020. 飞地的数量from typing import List class UnionFindSet: def __init__(self): self.father = {} def find(self, val): if val not in self.father: self.father[val] = val if self.father[val] != val: self.father[val] = self.find(self.father[val]) return self.father[val] def union(self, val1, val2): root_val1 = self.find(val1) root_val2 = self.find(val2) self.father[root_val2] = root_val1 class Solution: def __init__(self): self.direction = [[-1, 0], [1, 0], [0, -1], [0, 1]] def numEnclaves(self, grid: List[List[int]]) -> int: uf = UnionFindSet() for i in (0, len(grid) - 1): for j in range(len(grid[i])): self.set_zero(grid, i, j) for i in range(len(grid)): for j in (0, len(grid[i]) - 1): self.set_zero(grid, i, j) for i in range(1, len(grid) - 1): for j in range(1, len(grid[i]) - 1): if grid[i][j] == 1: uf.find((i, j)) grid[i][j] = 2 for x, y in self.direction: if grid[i + x][j + y] == 1: uf.union((i, j), (i + x, j + y)) return len(uf.father) def set_zero(self, grid, x, y): if grid[x][y] == 0: return grid[x][y] = 0 for i, j in self.direction: if x + i < 0 or x + i >= len(grid) or y + j < 0 or y + j >= len(grid[x + i]): continue self.set_zero(grid, x + i, y + j) 1559. 二维网格图中探测环1559. 二维网格图中探测环from typing import List class UnionFindSet: def __init__(self): self.father = {} def find(self, val): if val not in self.father: self.father[val] = val if self.father[val] != val: self.father[val] = self.find(self.father[val]) return self.father[val] def union(self, val1, val2): root_val1 = self.find(val1) root_val2 = self.find(val2) if root_val1 == root_val2: return True self.father[root_val1] = self.find(root_val2) return False class Solution: def __init__(self): self.direction = [[-1, 0], [1, 0], [0, -1], [0, 1]] def containsCycle(self, grid: List[List[str]])…

LeetCode（2024-01-11）
type: item
date: 2024-01-11T10:10:50+00:00
description: 735. 小行星碰撞735. 小行星碰撞class Solution: def asteroidCollision(self, asteroids: List[int]) -> List[int]: stack = [asteroids[0]] for i in range(1, len(asteroids)): if stack and stack[-1] < 0: stack.append(asteroids[i]) elif stack and asteroids[i] < 0: while stack and -asteroids[i] > stack[-1] > 0: stack.pop() if stack and -asteroids[i] == stack[-1]: stack.pop() continue if stack and -asteroids[i] < stack[-1]: continue stack.append(asteroids[i]) else: stack.append(asteroids[i]) return stack895. 最大频率栈895. 最大频率栈优先队列，时间复杂度$O(nlogn)$；题解将栈序列分解成为多个频率不同的栈序列，时间复杂度$O(1)$。from collections import defaultdict from typing import Dict import heapq class FreqStack: def __init__(self): self.frequency: Dict[int, int] = defaultdict(int) self.heap = [] self.index = 0 def push(self, val: int) -> None: self.frequency[val] += 1 self.index -= 1 heapq.heappush(self.heap, (-self.frequency[val], self.index, val)) def pop(self) -> int: freq, index, val = heapq.heappop(self.heap) self.frequency[val] -= 1 return val1319. 连通网络的操作次数1319. 连通网络的操作次数深度优先搜索，还可使用并查集from typing import List, Dict from collections import defaultdict class Solution: def makeConnected(self, n: int, connections: List[List[int]]) -> int: if len(connections) < n - 1: return -1 conn: Dict[int, list] = defaultdict(list) for src, dst in connections: conn[src].append(dst) conn[dst].append(src) checked = set() ans = 0 for i in range(n): if i not in checked: self.dfs(conn, i, checked) ans += 1 return ans - 1 def dfs(self, conn, start, checked): checked.add(start) for computer in conn[start]: if computer in checked: continue self.dfs(conn, computer, checked)LCR 066. 键值映射LCR 066. 键值映射字典树class Node: __slots__ = ["child", 'char', 'val'] def __init__(self, c, val=0): self.child = {} self.char = c self.val = val class MapSum: def __init__(self): """ Initialize your data structure here. """ self.tree = Node(None) def insert(self, key: str, val: int) -> None: node = self.tree for c in key: if c in node.child: node = node.child[c] else: new_node =…

LeetCode（2024-01-10）
type: item
date: 2024-01-10T06:44:43+00:00
description: 2696. 删除子串后的字符串最小长度2696. 删除子串后的字符串最小长度class Solution: def minLength(self, s: str) -> int: while True: tmp_s = s s = s.replace('AB', '').replace('CD', '') if tmp_s == s: break return len(s)787. K 站中转内最便宜的航班787. K 站中转内最便宜的航班from typing import List, Dict from collections import defaultdict import heapq class Solution: def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: edges = flights flights: Dict[int, list] = defaultdict(list) for s, d, c in edges: flights[s].append((c, d)) priority_queue = [(0, src, 0, [])] arrived_airport = set() while priority_queue: cost, airport, transfer_cnt, path = heapq.heappop(priority_queue) arrived_airport.add(airport) if airport == dst: return cost if transfer_cnt == k + 1: for item in path: arrived_airport.discard(item) continue for c, d in flights[airport]: if d in arrived_airport: continue path.append(d) heapq.heappush(priority_queue, (cost + c, d, transfer_cnt + 1, path[:])) path.pop() return -1 LCP 67. 装饰树LCP 67. 装饰树class Solution: def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: self.dfs(root) return root def dfs(self, node: Optional[TreeNode]): if node.left: insert_node = TreeNode(-1) insert_node.left = node.left node.left = insert_node self.dfs(insert_node.left) if node.right: insert_node = TreeNode(-1) insert_node.right = node.right node.right = insert_node self.dfs(insert_node.right)236. 二叉树的最近公共祖先236. 二叉树的最近公共祖先class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': p_path = [] self.dfs(root, p, p_path) q_path = [] self.dfs(root, q, q_path) index = 0 while index < len(p_path) and index < len(q_path): if p_path[index].val != q_path[index].val: return p_path[index - 1] index += 1 return p_path[-1] if len(p_path) < len(q_path) else q_path[-1] def dfs(self, node, search_node, path: list): if node.val == search_node.val: path.append(node) return True path.append(node) if node.left and self.dfs(node.left, sea…

LeetCode（2024-01-09）
type: item
date: 2024-01-10T06:44:13+00:00
description: 2707. 字符串中的额外字符2707. 字符串中的额外字符class Solution: def minExtraChar(self, s: str, dictionary: List[str]) -> int: dictionary = set(dictionary) dp = [0 for i in range(len(s) + 1)] for i in range(1, len(s) + 1): dp[i] = dp[i - 1] + 1 for j in range(i - 1, -1, -1): if s[j:i] in dictionary: dp[i] = min(dp[i], dp[j]) return dp[-1]841. 钥匙和房间841. 钥匙和房间class Solution: def canVisitAllRooms(self, rooms: List[List[int]]) -> bool: need_enter = {i for i in range(len(rooms))} have_keys = {0} while have_keys: key = have_keys.pop() if key in need_enter: need_enter.discard(key) have_keys.update(set(rooms[key])) return not bool(need_enter)1261. 在受污染的二叉树中查找元素1261. 在受污染的二叉树中查找元素from typing import List, Optional from tools import treeGenerate import json # Definition for a binary tree node. class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right from collections import deque class FindElements: def __init__(self, root: Optional[TreeNode]): root.val = 0 self.root = self.recover(root) def recover(self, node: Optional[TreeNode]): if node.left: node.left.val = 2 * node.val + 1 self.recover(node.left) if node.right: node.right.val = 2 * node.val + 2 self.recover(node.right) return node def find(self, target: int) -> bool: path = deque() while target != 0: path.appendleft(target) target = (target - 1) // 2 node = self.root while path: val = path.popleft() if node.val * 2 + 1 == val and node.left: node = node.left elif node.val * 2 + 2 == val and node.right: node = node.right else: return False return True 1905. 统计子岛屿1905. 统计子岛屿class Solution: def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int: m = len(grid1) n = len(grid1[0]) not_check_island = set() for i in range(m): for j in range(n): if grid1[i][j] == 0 and grid2[i][j] == 1: not_check_island.add((i, j)) island = [] for i in range(len(grid2)): for j in range(len(grid2[i])): if grid2[i][j] == 1: island_area = set() ret = self.dfs(grid2, i, j, island_area, n…

LeetCode（2024-01-08）
type: item
date: 2024-01-08T09:48:19+00:00
description: 764. 最大加号标志764. 最大加号标志class Solution: def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int: dp = [[[0, 0, 0, 0] for i in range(n)] for j in range(n)] mines = set(list(map(tuple, mines))) for i in range(n): for j in range(n): if (i, j) in mines: dp[i][j][0] = 0 dp[i][j][1] = 0 else: dp[i][j][0] = dp[i - 1][j][0] + 1 if i - 1 >= 0 else 1 dp[i][j][1] = dp[i][j - 1][1] + 1 if j - 1 >= 0 else 1 for i in range(n - 1, -1, -1): for j in range(n - 1, -1, -1): if (i, j) in mines: dp[i][j][2] = 0 dp[i][j][3] = 0 else: dp[i][j][2] = dp[i + 1][j][2] + 1 if i + 1 < n else 1 dp[i][j][3] = dp[i][j + 1][3] + 1 if j + 1 < n else 1 ans = 0 for i in range(n): for j in range(n): ans = max(ans, min(dp[i][j])) return ans1944. 队列中可以看到的人数1944. 队列中可以看到的人数class Solution: def canSeePersonsCount(self, heights: List[int]) -> List[int]: stack = [] ans = [0 for i in range(len(heights))] for i in range(len(heights) - 1, -1, -1): while stack and heights[i] > stack[-1]: ans[i] += 1 stack.pop() if stack: ans[i] += 1 stack.append(heights[i]) return ans2439. 最小化数组中的最大值2439. 最小化数组中的最大值使用二分法检查数class Solution: def minimizeArrayValue(self, nums: List[int]) -> int: right = 10 ** 9 left = 0 while left < right: mid = left + (right - left) // 2 if self.check(mid, nums): right = mid else: left = mid + 1 return left def check(self, k, nums): num = 0 for i in range(len(nums)): if nums[i] < k: num += k - nums[i] else: if num < (nums[i] - k): return False else: num -= nums[i] - k return TrueLCR 009. 乘积小于 K 的子数组LCR 009. 乘积小于 K 的子数组class Solution: def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int: cnt = 0 mul = 1 p0 = 0 for p1 in range(len(nums)): mul *= nums[p1] while p0 <= p1 and mul >= k: mul //= nums[p0] p0 += 1 cnt += p1 - p0 + 1 return cnt 966. 元音拼写检查器966. 元音拼写检查器class Solution: def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]: words_set = set(wordlist) words_lower = {wordlist[i].lower(): wordlist[i] for i in range(len(wordlist) - 1, -1, -1)} wor…