Belous

2.7万

Yoship

GetALife

someone

123go

yxc
rhf

cosycosy

cmz

JQW

Belous
13天前

### 标准模块 re



### 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()))


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)