本文共 2953 字，大约阅读时间需要 9 分钟。

• ：一堂课不合格的条件是：两次及以上的缺席（‘A‘）或连续三次的迟到（‘L‘），给定一个字符串，求该学生是否合格，Easy

class Solution(object):    def checkRecord(self, s):        """        :type s: str        :rtype: bool        """        countA = 0        for i in range(len(s)):            if s[i]=='A':                countA+=1                if countA>1:                    return False            if i>1 and s[i]=='L' and s[i-1] == 'L' and s[i-2]=='L':                return False        return True

• ：求n长满足学生出勤合格的字符串的总个数，Hard

设dp[k][x][y] 为长度为k的有x个A和以y个L结尾的个数

dp[n][0][0] = sum(dp[n-1][0]) 即结尾增加一个P

dp[n][0][1] = dp[n-1][0][0] 即结尾增加一个L

dp[n][0][2] = dp[n-1][0][1] 即结尾增加一个L

dp[n][1][0] = sum(dp[n-1][0]) + sum(dp[n-1][1]）前者增加一个A后者增加一个P

dp[n][1][1] = dp[n-1][1][0] 即结尾增加一个L

dp[n][1][2] = dp[n-1][1][1] 即结尾增加一个L

由于dp[n] 只和dp[n-1]有关，所以可以采用滚动数组，该思路参考

class Solution(object):    def checkRecord(self, n):        """        :type n: int        :rtype: int        """        MOD = 1000000007        dp = [[1,1,0],[1,0,0]]        for i in range(2,n+1):            tmp = sum(dp[0]) % MOD            dp[0][2] = dp[0][1]            dp[0][1] = dp[0][0]            dp[0][0] = tmp            tmp = (dp[0][0] + sum(dp[1]))%MOD            dp[1][2] = dp[1][1]            dp[1][1] = dp[1][0]            dp[1][0] = tmp        return (sum(dp[0])+sum(dp[1]))%MOD

• ：求一个整数的7进制表达，Easy

注意正负号和0的特殊处理

class Solution(object):    def convertToBase7(self, num):        """        :type num: int        :rtype: str        """        ret,flag = '',1        if num<0:            flag = 0            num = -num        while(num):            ret = str(num % 7)+ret            num = num/7        if ret == '':            return '0'        if flag: return ret        else:            return '-'+ret

• ：判断words列表中有多少个word能够扩展成S, Medium

能够扩展的条件是 单词连续个数大于3

先统计S中单词的个数 query 如heeellooo -> [(h,1),(e,3),(l,2),(o,3)]

对于每一个word来说，也统计word中单词的个数，candidate 如 hello -> [(h,1),(e,1),(l,2),(o,1)]

检查 len(query) == len(candidate) ?

检查 query[i][0] == candidate[i][0] ?

检查 query[i][1] >= candidate[i][1] 且如果> 成立的话 ，需要检查query[i][1]>=3 ?

class Solution(object):    def expressiveWords(self, S, words):        """        :type S: str        :type words: List[str]        :rtype: int        """        def countLetters(word):            cnt,last,ans = 0,'',[]            for c in word:                if c == last:                    cnt+=1                else:                    if cnt: ans.append((last,cnt))                    cnt,last = 1,c            if cnt: ans.append((last,cnt))            return ans        def check(query,candidate):            if len(query)!=len(candidate): return 0            for c,w in zip(query,candidate):                if  c[0] != w[0]: return 0                if  c[1] < w[1]: return 0                if  c[1] > w[1] and c[1]<3: return 0            return 1        query = countLetters(S)        ans = 0        for word in words:            candidate = countLetters(word)            ans+=check(query,candidate)        return ans

转载地址：http://vbqmi.baihongyu.com/