头像

Belous

兰州交通大学




离线:1天前


最近来访(81)
用户头像
Yoship
用户头像
人菜瘾又大
用户头像
七酱
用户头像
GetALife
用户头像
志秋世
用户头像
someone
用户头像
斩月
用户头像
弈剑观星
用户头像
岁末的秋天
用户头像
123go
用户头像
一个小蒟蒻
用户头像
yxc
用户头像
rhf
用户头像
夜白丶
用户头像
cosycosy
用户头像
乐天知命故不忧
用户头像
cmz
用户头像
樹上的男爵
用户头像
JQW
用户头像
Softsndad


Belous
13天前

标准模块 re

补上’$’,确保match函数用p匹配整个s.

import re
class Solution(object):
    def isMatch(self, s, p):
        return re.match(p+'$',s)

DFS

class Solution(object):
    def isMatch(self, s, p):
        sd, pd = len(s), len(p)

        def dfs(si, pi):
            if pi == pd:
                return si == sd  # 正则串结束时, 匹配串也要结束
            match = si < sd and (s[si] == p[pi] or p[pi]
                                 == '.')  # 匹配串还有, 且当前位置两串字符相同
            if pi+1 < pd and p[pi+1] == '*':  # 是否存在*
                return dfs(si, pi+2) or (match and dfs(si+1, pi))  # 不匹配 or 匹配
            return match and dfs(si+1, pi+1)

        return dfs(0, 0)

DP

dp[i][j] : s[:i]与p[:j]是否匹配.

  • 初始化
    因为 s[:0] == p[:0] == ‘’ , 必定匹配, 所以 dp[0][0] = True .
    由于 ‘*‘ 的存在, s[:0]==’‘ 可能与 p[:j] 匹配, 因为 ‘*‘ 出现在首位没有意义, 所以 j 从 2 开始.

  • 状态转移

    • if p[j-1] == s[i-1] or p[j-1] == ‘.’
      匹配成功, dp[i][j] = dp[i-1][j-1] .
    • elif p[j-1] == ‘*‘
      出现元字符 ‘*‘
      • if p[j-2] == s[i-1] or p[j-2] == ‘.’
        匹配0个时: dp[i][j] = dp[i][j-2]
        匹配1~n个时: dp[i][j] = dp[i-1][j]
      • else
        匹配0个时: dp[i][j] = dp[i][j-2]
class Solution(object):
    def isMatch(self, s, p):
        def isMatch(self, s, p):
        dp = [[False]*(len(p)+1) for _ in range(len(s)+1)]
        dp[0][0] = True
        for j in range(2, len(p)+1):
            if p[j-1] == '*':
                dp[0][j] = dp[0][j-2]
        for i in range(1, len(s)+1):
            for j in range(1, len(p)+1):
                if p[j-1] == s[i-1] or p[j-1] == '.':
                    dp[i][j] = dp[i-1][j-1]
                elif p[j-1] == '*':
                    dp[i][j] = dp[i][j-2]
                    if p[j-2] == s[i-1] or p[j-2] == '.':
                        dp[i][j] |= dp[i-1][j]
        return dp[-1][-1]



Belous
13天前
#! python3.9-64 -bb -O
# -*- coding: utf-8 -*-
"""
CreateTime: 2021-11-22 16:42:17
Author: Belous
"""


def main():
    n, m = map(int, input().split())
    matrix = [[0]*m for i in range(n)]
    direct = ((0, 1), (1, 0), (0, -1), (-1, 0))
    num, mi, mj, di = 1, 0, 0, 0
    while num <= n*m:
        matrix[mi][mj] = num
        if not (0 <= mi+direct[di][0] < n and 0 <= mj+direct[di][1] < m) or matrix[mi+direct[di][0]][mj+direct[di][1]]:
            di = (di+1) % 4
        num, mi, mj = num+1, mi+direct[di][0], mj+direct[di][1]
    [print(*i) for i in matrix]


if __name__ == '__main__':
    main()



Belous
15天前
#! python3.9-64 -bb -O
# -*- coding: utf-8 -*-
"""
CreateTime: 2021-11-20 21:00:34
Author: Belous
"""
import string


def main():
    s, d = input(), {c: [0, -1] for c in string.ascii_lowercase}
    for idx, c in enumerate(s):
        d[c][0], d[c][1] = max(d[c][0], idx-d[c][1]), idx
    for val in d.values():
        val[0] = max(val[0], len(s)-val[1])
    print(min(d.values())[0])


if __name__ == '__main__':
    main()



Belous
15天前
#! python3.9-64 -bb -O
# -*- coding: utf-8 -*-
"""
CreateTime: 2021-11-20 20:52:45
Author: Belous
"""


if __name__ == '__main__':
    book = {'A': 1, '0': 0, '1': 10}
    book.update({str(i): i for i in range(2, 10)})
    print(sum(book[c] for c in input()))



Belous
18天前
#python3.9
# -*- coding: utf-8 -*-
"""
CreateTime: 2021-11-12 05:05:50
Author: Belous
"""

def manacher(s):
    s = '?#'+'#'.join(s)+'#!'
    p = [1]*(len(s)-1)
    mid, r = 1, 1
    for i in range(2, len(s)-1):
        if i < r-1:
            p[i] = min(p[mid*2-i], r-i)
        while s[i-p[i]] == s[i+p[i]]:
            p[i] += 1
        if i+p[i] > r:
            mid, r = i, i+p[i]
    return max(p)-1

if __name__ == '__main__':
    print(manacher(input()))


活动打卡代码 AcWing 4073. 找规律输出

Belous
22天前
# -*- coding: utf-8 -*-
"""
Created on %(date)s
@author: %Belous
"""


print(' that '.join(['I love' if i % 2 else 'I hate' for i in range(int(input()))])+' it')




Belous
22天前
# -*- coding: utf-8 -*-
"""
CreateTime: 2021-11-13 20:33:14
Author: Belous
"""


if __name__ == '__main__':
    print(' that '.join(['I love' if i % 2 else 'I hate' for i in range(int(input()))])+' it')



Belous
23天前

orz




Belous
30天前

方法一: 内置pow函数.

a,b,p=map(int,input().split())
print(pow(a,b,p))

方法二: 快速幂.

a,b,p=map(int,input().split())
s=1%p
while(b):
    if b&1: s=s*a%p
    a=a*a%p
    b>>=1
print(s)



Belous
1个月前
datas=[sum(map(int,input().split())) for i in range(7)]
print(datas.index(max(datas))+1 if max(datas)>8 else 0)