thảo luận Leetcode contest, đường tới Guardian
- Người tạo chủ đề freedom.9
- Ngày bắt đầu
- Trạng thái
lilleboybk
Senior Member
Em nhớ có contest gần đây cũng dùng Z function. LC để điểm các bài làm kha khá người tưởng contest lần này ngon ăn.Tính ra ý tưởng câu 4 dùng Z function quá đơn giản để nghĩ ra, mà lún hơi sâu vô cái Rabin Karp vì nghĩ nó pass
Q3 khó tiếp cận hơn nhiều, đọc đề xong ko có 1 ý tưởng gì luôn mà đánh Medium. Constrain cao vãi đái chắc chỉ có Greedy mới ăn.
freedom.9
Senior Member
Contest lần này coi như bỏ, hên mình cũng ko bị trừ điểm. Code ẩu ăn 1 cái bug Q2 ko thì cũng có điểm mang về rồi
freedom.9
Senior Member
Cuối cùng cũng sửa lại cho nó accepted được, ngu quá đi tính cái powerBase cho từng index nên TLE sml.
Python:
class Solution:
def minStartingIndex(self, s: str, pattern: str) -> int:
base = 31
MOD = 10**14 + 7
n = len(pattern)
lastBase = pow(base, n - 1, MOD)
if len(s) < n:
return -1
def calculateHash(target):
currentHash = 0
for i in range(n):
currentHash = (currentHash * base + (ord(target[i]) - ord('a'))) % MOD
return currentHash
def getHashList(pattern):
hashResult = set()
currentHash = calculateHash(pattern)
currentBase = 1
for i in range(n - 1, - 1, -1):
order = ord(pattern[i]) - ord('a')
originalContribution = (order * currentBase) % MOD
newHash = (currentHash - originalContribution + MOD) % MOD
for j in range(26):
modifiedHash = (j * currentBase) % MOD
modifiedHash = (modifiedHash + currentHash - originalContribution)%MOD
hashResult.add(modifiedHash)
currentBase*=base
currentBase%=MOD
return hashResult
patternHashes = getHashList(pattern)
h2 = calculateHash(s[:n])
if h2 in patternHashes:
return 0
left = 0
for i in range(n, len(s)):
h2 = (h2 - (ord(s[left]) - ord('a')) * lastBase) % MOD
h2 = (h2 * base + (ord(s[i]) - ord('a'))) % MOD
left += 1
if h2 < 0:
h2 += MOD
if h2 in patternHashes:
return left
return -1
Sửa lần cuối:
thangkc89
Senior Member
Q4 mình dùng BS để tìm longest prefix O(NlogN) nhưng TLE 
Mình optimize bằng cách dùng sliding window để đếm tổng số lượng ký tự khác nhau, nếu 2 xâu được khác nhau nhiều nhất 1 ký tự thì tổng ký tự khác nhau phải <= 2
Mình optimize bằng cách dùng sliding window để đếm tổng số lượng ký tự khác nhau, nếu 2 xâu được khác nhau nhiều nhất 1 ký tự thì tổng ký tự khác nhau phải <= 2
Mã:
class Solution:
def minStartingIndex(self, s: str, pattern: str) -> int:
MOD = 10**9 + 7
base = 31
ord_a = ord('a')
d1 = defaultdict(int)
d2 = defaultdict(int)
p = [0] * (max(len(s), len(pattern)) + 1)
p[0] = 1
for i in range(1, len(p)):
p[i] = (p[i-1] * base) % MOD
hash1 = [0] * (len(s) + 1)
for i in range(len(s)):
hash1[i+1] = ((hash1[i] * base) + ord(s[i]) - ord_a) % MOD
hash2 = [0] * (len(pattern) + 1)
for i in range(len(pattern)):
hash2[i+1] = ((hash2[i] * base) + ord(pattern[i]) - ord_a) % MOD
d2[pattern[i]] += 1
def get_hash(hash_array, l, r):
return (hash_array[r+1] - hash_array[l] * p[r-l+1] + MOD * MOD) % MOD
diff = 0
for i in range(len(pattern) - 1):
d1[s[i]] += 1
for j in range(0, 26):
c = chr(j + ord('a'))
if d1[c] != d2[c]:
# print(c, d1[c], d2[c])
diff += abs(d1[c] - d2[c])
for i in range(len(s)):
if i + len(pattern) > len(s):
break
diff -= abs(d1[s[i+len(pattern)-1]] - d2[s[i+len(pattern)-1]])
d1[s[i+len(pattern)-1]] += 1
diff += abs(d1[s[i+len(pattern)-1]] - d2[s[i+len(pattern)-1]])
if i > 0:
diff -= abs(d1[s[i-1]] - d2[s[i-1]])
d1[s[i-1]] -= 1
diff += abs(d1[s[i-1]] - d2[s[i-1]])
if diff > 2:
continue
inf = 1
suf = len(pattern)
k = 0
while inf <= suf:
mid = (inf + suf) // 2
if get_hash(hash1, i, i+mid-1) == get_hash(hash2, 0, mid-1):
k = mid
inf = mid + 1
else:
suf = mid - 1
if k == len(pattern) or k == len(pattern) - 1:
return i
if get_hash(hash1, i+k+1, i+len(pattern)-1) == get_hash(hash2, k+1, len(pattern)-1):
return i
return -1
garanphomai
Member
Như thường lệ, stuck q2, nay thêm con bọ q1 nữa
TLE_WA
Junior Member
Q4 em thấy còn dễ hơn Q3
freedom.9
Senior Member
Ngồi mãi ko có ý tưởng gì rồi, greedy hay là dp nhỉ. Nhiều người giải đc quá chắc trick lỏ gì rồi mà ko nhìn raQ4 em thấy còn dễ hơn Q3
TLE_WA
Junior Member
chỉ là quy luật thôi anh, ở bước thứ i thì độ dài của chuỗi luôn là 2 ^ i, so sánh xem trong chuỗi đó thì k ở nửa dưới hay nửa trên (nói cách khác tại bước i thì k là bản gốc hay là bản sao)
lovelyly
Senior Member
T thì không giỏi giải thích, nhưng ý tưởng nó như thế này.
Mã:
- Giảm k đi 1 đơn vị
- Nếu bit thứ i (đếm từ phải qua) của k là 1 => word[k] chịu ảnh hưởng từ operations[i]
- Đếm xem có bao nhiêu lần word[k] chịu ảnh hưởng của operation = 1freedom.9
Senior Member
anh nhìn ra là ở mỗi bước k*2 thì char sẽ bằng k nếu operation = 0 hoặc là char + 1 nếu operation = 1
Còn đếm tới k thì ko có ý tưởng gì, mấy bài thiên về observations kém quá, hình như CF nó có cái tag constructive algorithm mấy bài dạng này để luyện thử.
Q3 làm nhanh gọn mà tới q4 bưa quá
TLE_WA
Junior Member
sol q4:
tại bước thứ i của operation (tính theo 1-index) thì chuỗi có độ dài là L = 2^i, nếu k > L / 2 thì k nằm ở nửa trên, tức k là bản sao, nói cách khác bản gốc của word[k] là word[k-L/2]
=> Nếu operation == 1 thì số lần shift cộng thêm 1, nếu là 0 thì số lần shift giữ nguyên.
Cứ như thế truy vết về bản chính gốc + số lần shift là ra
tại bước thứ i của operation (tính theo 1-index) thì chuỗi có độ dài là L = 2^i, nếu k > L / 2 thì k nằm ở nửa trên, tức k là bản sao, nói cách khác bản gốc của word[k] là word[k-L/2]
=> Nếu operation == 1 thì số lần shift cộng thêm 1, nếu là 0 thì số lần shift giữ nguyên.
Cứ như thế truy vết về bản chính gốc + số lần shift là ra
Mã:
func kthCharacter(k int64, operations []int) byte {
shift := 0
for i := min(48, len(operations)); i >= 0; i-- {
L := int64(1 << (i + 1))
if k > L / 2 {
k -= L / 2
shift += operations[i]
}
}
return byte('a' + shift % 26)
}lilleboybk
Senior Member
Q3 đến lúc còn 4p em mới accepted. Như mấy bác trên nói thì Q4 code khá ngắn nhỉ.anh nhìn ra là ở mỗi bước k*2 thì char sẽ bằng k nếu operation = 0 hoặc là char + 1 nếu operation = 1
Còn đếm tới k thì ko có ý tưởng gì, mấy bài thiên về observations kém quá, hình như CF nó có cái tag constructive algorithm mấy bài dạng này để luyện thử.
Q3 làm nhanh gọn mà tới q4 bưa quá
freedom.9
Senior Member
Bài 3 ý tưởng dùng sliding windows, khi mà có 1 valid window với vowels = 5 và consonents >= k thì shrink windows xuống để tìm 1 valid substring, tổng số substring sẽ là n - dp với dp chứa last consonent index, vì nếu như thêm 1 consonent nữa thì các substring phía sau sẽ invalid. Bản nâng cao của Q3 Q4 bữa trước, còn khó hơn Q4 bữa trước.
Python:
class Solution:
def countOfSubstrings(self, word: str, k: int) -> int:
n = len(word)
dp = [0] * n
lastConsonantIndex = n
for i in range(n-1, -1, -1):
dp[i] = lastConsonantIndex
if word[i] not in 'aeiou':
lastConsonantIndex = i
countVowels = defaultdict(int)
totalConsonants = 0
left = 0
ans = 0
for right in range(n):
idx = ord(word[right]) - ord('a')
if word[right] in 'aeiou':
countVowels[word[right]] += 1
else:
totalConsonants += 1
while len(countVowels) == 5 and totalConsonants >= k:
if totalConsonants == k:
ans += dp[right] - right
if word[left] in 'aeiou':
countVowels[word[left]] -= 1
if countVowels[word[left]] == 0:
countVowels.pop(word[left])
else:
totalConsonants -= 1
left += 1
return ans
Sửa lần cuối:
garanphomai
Member
E làm slide y chang luôn nhưng k biết cách tính số substring -.-
freedom.9
Senior Member
Phải biết cách đếm substring mới ăn đc dạng bài này, thường có 1 valid window thì phải biết cách đếm xem có bao nhiêu substrings cắt cái window đấy thôi fence.
via theNEXTvoz for iPhone
- Trạng thái
Chủ đề tương tự
