yyyying的blog

好好学习 天天向上

0%

力扣每日

发表于 更新于 分类于 Valine：
本文字数： 1.7k 阅读时长 ≈ 2 分钟

力扣每日刷题

551.学生出勤记录

2021.8.17 简单题目 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def checkRecord(self, s):
        """
        :type s: str
        :rtype: bool
        """
        absent = 0
        late = 0
        for i in s:
            if i == 'L':
                late += 1
            else:
                late = 0
                if i == 'A':
                    absent += 1
            if late >= 3:
                return False
        return absent < 2

552.学生出勤记录II

题目链接

题目描述：

可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：
‘A’：Absent，缺勤
‘L’：Late，迟到
‘P’：Present，到场
如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：
按 总出勤 计，学生缺勤（’A’）严格 少于两天。
学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（’L’）记录。
给你一个整数 n ，表示出勤记录的长度（次数）。请你返回记录长度为 n 时，可能获得出勤奖励的记录情况 数量 。答案可能很大，所以返回对 109 + 7 取余 的结果。

此题数据规模较大，个人思路尝试动态规划解题，后参考题解使用矩阵快速幂可以时间复杂度由O(n)降为O(log n)，下边是我的程序

程序 
1
2
3
4
5
6
7
8
9
10
a,b,c,d,e,f = 1,1,0,1,0,0
for i in range(n-1):
    a,b,c,d,e,f = a+b+c,a,b,a+b+c+d+e+f,d,e
    a %= (10**9+7)
        b %= (10**9+7)
        c %= (10**9+7)
        d %= (10**9+7)
        e %= (10**9+7)
        f %= (10**9+7)
return (a+b+c+d+e+f)%(10**9+7)
程序分析

程序分析：使用动态规划，此题一共六种情况：无A结尾无L,无A结尾一个L,无A结尾两个L,一个A结尾无L,一个A结尾一个L,一个A结尾两个L，每一天结果相互转化，起始第一天为（1,1,0,1,0,0)，之后每一天一次转换:

前一天 今天
无A结尾无L a a+b+c
无A结尾一个L b a
无A结尾两个L c b
一个A结尾无L d a+b+c+d
一个A结尾一个L e d
一个A结尾两个L f e

345.反转字符串中的元音字母

简单 双指针遍历即可 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def reverseVowels(self, s: str) -> str:
        n = len(s)
        buf = list(s)
        i = 0
        j = n-1
        while i<j:
            while i<n and not ( buf[i] in 'AEIOUaeiou'):
                i += 1
            while j>0 and not (buf[j] in 'AEIOUaeiou'):
                j -= 1
            if i < j:
                buf[i], buf[j] = buf[j], buf[i]
                i += 1
                j -= 1
        return ''.join(buf)

541.反转字符串 II

简单 循环没2k 翻转k个字母 官方解答更简洁，所以这里用官方程序 
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        t = list(s)
        for i in range(0, len(t), 2 * k):
            t[i: i + k] = reversed(t[i: i + k])
        return "".join(t)

#作者：LeetCode-Solution
#链接：https://leetcode-cn.com/problems/reverse-string-ii/solution/fan-zhuan-zi-fu-chuan-ii-by-leetcode-sol-ua7s/
#来源：力扣（LeetCode）
#著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。