2024.04.30_学习日记

Posted on In Views:

天气：中雨
学习地点：宿舍
学习时长：10h

学习内容

  1. 算法题
    alt text
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    from collections import defaultdict  # 导入defaultdict模块
    while True:
        try:
            n = int(input())  # 接收输入，表示接下来有几组测试数据
            for i in range(n):  # 对每组测试数据进行处理
                strs = input()  # 接收输入的字符串
                hashmap = defaultdict(int)  # 创建一个默认值为0的字典
                cnt = 0  # 记录字符串中重复字符的数量
                for c in strs:  # 遍历字符串中的每个字符
                    if hashmap[c] == 1:  # 如果当前字符已经出现过一次
                        cnt += 1  # 则重复字符数量加1
                        hashmap[c] = 0  # 并将该字符的计数归零，表示不再重复
                    else:
                        hashmap[c] += 1  # 否则，将该字符的计数加1
                if len(strs) - cnt <= 26:  # 如果去除重复字符后的长度不超过26
                    print(cnt)  # 则输出重复字符数量
                else:
                    print(len(strs) - 26)  # 否则，输出超过26个字符的部分
        except:  # 捕获所有异常
            break  # 如果出现异常，则结束循环
  2. 动态规划
    alt text
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    while True:
        try:
            n = int(input())  # 接收输入，表示接下来有几组测试数据
            for i in range(n):  # 对每组测试数据进行处理
                nums = list(map(int, input().strip()[1:-1].split(',')))  # 输入一个列表，去除首尾的方括号，然后按逗号分割成数字列表
                dp = [1]*(len(nums)+1)  # 初始化动态规划数组，长度比nums多1，初始值都为1
                # dp[i]表示前i个数的最长递增子序列的长度
                res = 1  # 初始化结果为1
                for i in range(1, len(nums)):  # 遍历nums中的每个数字，从第2个数字开始
                    for j in range(i):  # 遍历nums中当前数字之前的每个数字
                        if nums[i] > nums[j]:  # 如果当前数字大于前面的数字
                            dp[i] = max(dp[i], dp[j]+1)  # 更新dp[i]，取当前dp[i]和dp[j]+1的较大值
                    res = max(res, dp[i])  # 更新结果为当前res和dp[i]的较大值
                print(res)  # 输出结果
        except:  # 捕获所有异常
            break  # 如果出现异常，则结束循环