Skip to content

Commit d8f41d9

Browse files
Xuu666Xuu666
committed
week09 assignment
1 parent 3bce7fb commit d8f41d9

18 files changed

Lines changed: 406 additions & 1 deletion

‎Week_09/#115 不同的子序列.py‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
#!/usr/bin/env python
2+
# coding: utf-8
3+
4+
# In[ ]:
5+
6+
7+
class Solution(object):
8+
def numDistinct(self, s, t):
9+
"""
10+
:type s: str
11+
:type t: str
12+
:rtype: int
13+
"""
14+
m, n = len(s), len(t)
15+
dp = [[0] * (m+1) for _ in range(n+1)]
16+
for i in range(m+1):
17+
dp[0][i] = 1
18+
for i in range(1,n+1):
19+
for j in range(1,m+1):
20+
if s[j-1] == t[i-1]:
21+
dp[i][j] = dp[i-1][j-1] + dp[i][j-1]
22+
else:
23+
dp[i][j] = dp[i][j-1]
24+
25+
return dp[-1][-1]
26+

‎Week_09/#151 翻转字符串里的单词.py‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
#!/usr/bin/env python
2+
# coding: utf-8
3+
4+
# In[ ]:
5+
6+
7+
class Solution(object):
8+
def reverseWords(self, s):
9+
"""
10+
:type s: str
11+
:rtype: str
12+
"""
13+
return ' '.join(s.strip().split()[::-1])
14+

‎Week_09/#205 同构字符串.py‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
#!/usr/bin/env python
2+
# coding: utf-8
3+
4+
# In[ ]:
5+
6+
7+
class Solution(object):
8+
def isIsomorphic(self, s, t):
9+
"""
10+
:type s: str
11+
:type t: str
12+
:rtype: bool
13+
"""
14+
return all(s.index(s[i]) == t.index(t[i]) for i in range(len(s)))
15+

‎Week_09/#300 最长递增子序列.py‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
#!/usr/bin/env python
2+
# coding: utf-8
3+
4+
# In[ ]:
5+
6+
7+
class Solution(object):
8+
def lengthOfLIS(self, nums):
9+
"""
10+
:type nums: List[int]
11+
:rtype: int
12+
"""
13+
if not nums: return 0
14+
dp = [1] * len(nums)
15+
for i in range(len(nums)):
16+
for j in range(i):
17+
if nums[i] > nums[j]:
18+
dp[i] = max(dp[i], dp[j] + 1)
19+
return max(dp)
20+

‎Week_09/#32最长有效括号.py‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
#!/usr/bin/env python
2+
# coding: utf-8
3+
4+
# In[ ]:
5+
6+
7+
class Solution(object):
8+
def longestValidParentheses(self, s):
9+
"""
10+
:type s: str
11+
:rtype: int
12+
"""
13+
n = len(s)
14+
if n == 0: return 0
15+
res, dp = 0, [0]*n
16+
for i in range(n):
17+
if i >0 and s[i] == ')':
18+
if s[i-1] == '(':
19+
dp[i] = dp[i-2] +2
20+
elif s[i-1] ==')' and i-dp[i-1]-1>=0 and s[i-dp[i-1]-1] == '(':
21+
dp[i] = dp[i-1]+2+dp[i-dp[i-1]-2]
22+
if dp[i]>res: res = dp[i]
23+
return res
24+

‎Week_09/#387 字符串中的第一个唯一字符.py‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
#!/usr/bin/env python
2+
# coding: utf-8
3+
4+
# In[ ]:
5+
6+
7+
class Solution(object):
8+
def firstUniqChar(self, s):
9+
"""
10+
:type s: str
11+
:rtype: int
12+
"""
13+
dic = {}
14+
for ch in s:
15+
dic[ch] = dic.get(ch,0) + 1
16+
for i in range(len(s)):
17+
if dic[s[i]] == 1:
18+
return i
19+
break
20+
return -1
21+

‎Week_09/#438 找到字符串中所有字母异位词.py‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
#!/usr/bin/env python
2+
# coding: utf-8
3+
4+
# In[ ]:
5+
6+
7+
class Solution(object):
8+
def findAnagrams(self, s, p):
9+
"""
10+
:type s: str
11+
:type p: str
12+
:rtype: List[int]
13+
"""
14+
res = []
15+
window, needs = {}, {}
16+
for pi in p: needs[pi] = needs.get(pi,0) +1
17+
18+
length, limit = len(p), len(s)
19+
left = right = 0
20+
21+
while right < limit:
22+
c = s[right]
23+
if c not in needs:
24+
window.clear()
25+
left = right = right +1
26+
else:
27+
window[c] = window.get(c,0) +1
28+
if right - left + 1 == length:
29+
if window == needs: res.append(left)
30+
window[s[left]] -= 1
31+
left += 1
32+
right += 1
33+
return res
34+

‎Week_09/#44 通配符匹配.py‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
#!/usr/bin/env python
2+
# coding: utf-8
3+
4+
# In[ ]:
5+
6+
7+
class Solution(object):
8+
def isMatch(self, s, p):
9+
"""
10+
:type s: str
11+
:type p: str
12+
:rtype: bool
13+
"""
14+
pn, sn = len(p) + 1, len(s) + 1
15+
dp = [[False] * pn for _ in range(sn)]
16+
print(pn,sn)
17+
print(dp)
18+
dp[0][0] = True
19+
for k in range(1,pn):
20+
if p[k-1] == "*":
21+
dp[0][k] = dp[0][k-1]
22+
for m in range(1,sn):
23+
for n in range(1,pn):
24+
if s[m-1] == p[n-1] or p[n-1] == "?":
25+
dp[m][n] = dp[m-1][n-1]
26+
elif p[n-1] == "*":
27+
dp[m][n] = dp[m-1][n] or dp[m][n-1]
28+
return dp[-1][-1]
29+

‎Week_09/#5 最长回文子串.py‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
#!/usr/bin/env python
2+
# coding: utf-8
3+
4+
# In[ ]:
5+
6+
7+
class Solution(object):
8+
def longestPalindrome(self, s):
9+
"""
10+
:type s: str
11+
:rtype: str
12+
"""
13+
14+
size=len(s)
15+
if len(s)<2: return s
16+
dp=[[False for _ in range(size)] for _ in range(size)]
17+
max_len=1
18+
start=0
19+
for i in range(size):
20+
dp[i][i]=True
21+
22+
for j in range(1,size):
23+
for i in range(0,j):
24+
if s[i]==s[j]:
25+
if j-i<3:
26+
dp[i][j]=True
27+
else:
28+
dp[i][j]=dp[i+1][j-1]
29+
else:
30+
dp[i][j]=False
31+
32+
if dp[i][j]:
33+
cur_len=j-i+1
34+
if cur_len>max_len:
35+
max_len=cur_len
36+
start=i
37+
print(start)
38+
return s[start:start+max_len]
39+

‎Week_09/#541反转字符串2.py‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
#!/usr/bin/env python
2+
# coding: utf-8
3+
4+
# In[ ]:
5+
6+
7+
class Solution(object):
8+
def reverseStr(self, s, k):
9+
"""
10+
:type s: str
11+
:type k: int
12+
:rtype: str
13+
"""
14+
res, flag = "", True
15+
for i in range(0, len(s), k):
16+
res += s[i:i+k][:: -1] if flag else s[i:i+k]
17+
flag = not flag
18+
return res
19+

0 commit comments

Comments
 (0)