Re: [閒聊] LeetCode Weekly Contest 411

看板Marginalman作者DJYOMIYAHINA (通通打死)時間1年前 (2024/08/18 20:20)推噓3(3推 0噓 0→)

留言3則, 3人參與討論串3/3 (看更多)

好羨慕你板人的智商我自己是都想到卡住就沒動筆了 Q3我應該跟大部分人一樣都是一個一個想但就想到mod 7就卡住還去偷估狗7的倍數判斷方法但都沒想法 Q4我也是先記下每個index為結尾的subarray的左邊界但沒有想法當這個左邊界超出query_l該怎麼辦硬掃的話每次query就要O(N) 感覺就不行不過我看解答好像有人這樣過== 我有想到也可以記下每個index當開頭的subarray的右界這個方向但也不知道怎麼使用他看答案才知道 -- 針對每個index記下: 1. 以這個index為開頭的subarray最遠可以往右到哪裡 → right_bound[index] 2. 以這個index為為結尾的subarray最遠可以往左到哪裡 → left_bound[index] 針對每個query，分兩種情況 1. 若right_bound[l] >= r 代表nums[l:r]所有subarray都符合條件，所以直接append(len*(len+1)/2) 2. 若right_bound[l] < r 就可以把這個query分兩段第一段nums[l:right_bound[l]] → 這一段subarray同第一種情況，所有都符合，所以先加len*(len+1)/2 第二段nums[right_bound[l]+1:r] → 其實可以反推出left_bound[right_bound[l]+1]一定>l 因nums[l:right_bound[l]+1]已經不符合條件了，所以以right_bound[l]+1為結尾且符合條件的subarray的左邊界一定>l 所以這邊就可以以right_bound[l]+1 ~ r為subarray結尾，加總subarray的個數因為左邊界一定>l，所以也不用擔心這些subarray超出邊界l 就直接用prefix_sum的方式可以快速query def countKConstraintSubstrings(self, s: str, k: int, queries: List[List[int]]) -> List[int]: n = len(s) right_bound = [0 for _ in range(n)] left_bound = [0 for _ in range(n)] #calculate right r, one_cnt, zero_cnt = 0, 0, 0 for l in range(n): while r<n: one_cnt += (s[r] == '1') zero_cnt += (s[r] == '0') if one_cnt>k and zero_cnt>k: one_cnt -= (s[r] == '1') zero_cnt -= (s[r] == '0') break r += 1 right_bound[l] = min(n-1, r-1) one_cnt -= (s[l] == '1') zero_cnt -= (s[l] == '0') #calculate left l, one_cnt, zero_cnt = n-1, 0, 0 for r in range(n-1, -1, -1): while l>=0: one_cnt += (s[l] == '1') zero_cnt += (s[l] == '0') if one_cnt>k and zero_cnt>k: one_cnt -= (s[l] == '1') zero_cnt -= (s[l] == '0') break l -= 1 left_bound[r] = max(0, l+1) one_cnt -= (s[r] == '1') zero_cnt -= (s[r] == '0') #prefix_sum of left prefix_sum_of_left_length = list(accumulate([r-left_bound[r]+1 for r in range(n)])) ans = [] for l,r in queries: if right_bound[l] >= r: length = r-l+1 ans.append(length*(length+1)//2) else: ans_cur = 0 length = right_bound[l]-l+1 ans_cur += length*(length+1)//2 ans_cur += prefix_sum_of_left_length[r] - prefix_sum_of_left_length[right_bound[l]] ans.append(ans_cur) return ans -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.37.69 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723983641.A.879.html

推

sustainer123

08/18 20:21, 1年前 , 1^F

08/18 20:21, 1^F

推

oin1104

08/18 20:23, 1年前 , 2^F

08/18 20:23, 2^F

推

dont

08/18 20:25, 1年前 , 3^F

08/18 20:25, 3^F