今日算法记录
字符串hash
P1
U461211 字符串 Hash（数据加强）
https://www.luogu.com.cn/problem/U461211
#include <iostream>
#include <string>
#include <vector>
int main() {
long long n;
std::cin >> n;
std::vector<std::string> s(n + 1);
long long dangqian_hash = 0;
// long long hash_list = 0;
// std::vector<int> hash_list(n + 1);
long long base = 2017; // prime > jinzhi
long long p = 457281707330443ll;
// long long p = 1e9 + 7; // prime > base^max_len
long long pp = 1e6;
std::vector<std::vector<long long>> hash_list(pp + 1);
for (long long i = 0; i < n; i++) {
std::cin >> s[i];
dangqian_hash = 1;
for (int j = 0; j < s[i].length(); j ++) {
dangqian_hash = (dangqian_hash * base + s[i][j]) % p;
}
bool find_ = false;
for (int j = 0; j < hash_list[dangqian_hash % pp].size(); j ++) {
if (dangqian_hash == hash_list[dangqian_hash % pp][j]) {
find_ = true;
}
}
if (!find_) {
hash_list[dangqian_hash % pp].push_back(dangqian_hash);
}
}
int sum_len = 0;
for (int i = 0; i < hash_list.size(); i ++) {
sum_len += hash_list[i].size();
}
std::cout << sum_len;
return 0;
}
P2
49. 字母异位词分组
https://leetcode.cn/problems/group-anagrams/?envType=study-plan-v2&envId=top-100-liked
没用标准字符串哈希来做，也没用 Set，Set 是 log 级别的复杂度
创建个随机值映射，防止被 b, b, a, c 这样的数据 hack
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
ans_dict = defaultdict(list)
temp_dict = {}
for i in range(ord('a'), ord('z') + 1):
temp = i + random.randint(10000000, 100000000)
temp_dict[i] = temp
for i in strs:
this_ans = 0
for j in i:
# print(ord(j))
this_ans += temp_dict[ord(j)]
ans_dict[this_ans].append(i)
return list(ans_dict.values())
DP
划分子问题，DP数组作缓存（当然也可以递归 + @cache）
P1
P1048 [NOIP 2005 普及组] 采药
https://www.luogu.com.cn/problem/P1048
from functools import cache
import sys
# #input
# 70 3
# 71 100
# 69 1
# 1 2
# T, M = map(int, input().split())
M = 0
pairs = []
@cache
def digui(index, bag_yu):
if index >= M:
return 0
# 放入
val = 0
if bag_yu >= pairs[index][0]:
val = digui(index + 1, bag_yu - pairs[index][0]) + pairs[index][1]
pass
return max(val, digui(index + 1, bag_yu))
def solve():
global T, M
input = sys.stdin.read().splitlines()
# ptr = 0
# T = int(input[ptr])
# ptr += 1
# for _ in range(T):
# a, b = map(int, input[ptr:ptr+2])
# ptr += 2
# print(a + b)
T, M = map(int, input[0].split())
for i in range(1, M + 1):
# 体积, 价值
a, b = map(int, input[i].split())
pairs.append((a, b))
# print(pairs)
print(digui(0, T))
if __name__ == "__main__":
solve()
P2
70. 爬楼梯
https://leetcode.cn/problems/climbing-stairs/description/?envType=study-plan-v2&envId=top-100-liked
class Solution:
@cache
def climbStairs(self, n: int) -> int:
if n <= 1:
return 1
# 先爬1
ans = self.climbStairs(n - 1)
# 先爬2
ans += self.climbStairs(n - 2)
return ans
栈
P1
20. 有效的括号
https://leetcode.cn/problems/valid-parentheses/description/?envType=study-plan-v2&envId=top-100-liked
class Solution:
def isValid(self, s: str) -> bool:
stack = []
# for i in s:
yingshe = {
'{': '}',
'[': ']',
'(': ')'
}
for i in range(len(s)):
if s[i] in '{[(':
stack.append(s[i])
# for i in range(len(s)):
# else if s[i] in ')}]':
else:
if stack != [] and yingshe[stack[-1]] == s[i]:
stack.pop()
else:
return False
# for i in s:
if stack == []:
return True
else:
return False
P2
https://leetcode.cn/problems/decode-string/description/?envType=study-plan-v2&envId=top-100-liked
正在做
2025.05.23 做完了，update Solution
from curses.ascii import isdigit
class Solution:
def decodeString(self, s: str) -> str:
stack = []
current_num = 0
current_str = ''
# for i in range(len(s)):
# if s[i] in '[':
# # stack.append(s[i - 1])
# # stack.append(s[i])
# # stack.append(i - 1)
# stack.append(i)
# elif s[i] in ']':
# temp = stack.pop()
# new_s += s[temp + 1: i] * int(s[temp - 1])
# return new_s
for char in s:
if char.isdigit():
current_num = current_num * 10 + int(char)
elif char == '[':
stack.append(current_str)
stack.append(current_num)
current_str = ''
current_num = 0
elif char == ']':
num = stack.pop()
prev_str = stack.pop()
current_str = prev_str + current_str * num
else:
current_str += char
return current_str
