5.21 今日算法记录

#牛客AI配图神器#

字符串hash

P1

U461211 字符串 Hash（数据加强）

此题卡 python

#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. 字母异位词分组

没用标准字符串哈希来做，也没用 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 普及组] 采药

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. 爬楼梯

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. 有效的括号

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