Re: [取暖] 週賽

我來試著把我寫題目的當下在想什麼講出來試試 因為這樣字數會比較多 P幣也會比較多 第一題： 看到 1-indexed 會覺得不太尋常，因為 LeetCode 的習慣是 0-indexed 接著看到 special 的定義是 n % i == 0 之後覺得合理，因為 i 不能是 0 然後剩下就是當 n % i == 0 時把 nums[i] 平方加起來 標準的第一題 第二題： 看到 operation, 先看他是不是無限次，這題是每個 index 最多一次 然後因為是問 subsequence, nums[i] 能變的值是 [nums[i] - k, nums[i] + k] 也只和自己本身的值有關 所以知道位置不重要，可以無腦 sort (LeetCode 基本上不會出現 O(nlogn) 過不了但 O(n) 能過的題目) sort 完之後會發現，答案一定是把 nums 的一段 subarray 都變成同一個值 不可能跳，因為假如 nums[i] 和 nums[j] 都變成 x 則 nums[i], ..., nums[j] 中間的所有人也都一定能變成 x (真的嗎？) 所以假如考慮以 index 結尾的所有 subarray 我們只要找到第一個 nums[start] 且 他們兩個可以變成同一個值就好 條件是 nums[index] - nums[start] <= 2k 因為 nums 遞增，所以隨著 index 增加，第一個合法的 start 也只會跟著增加 所以可以用 two-pointer 這題以第二題來說稍微偏難 第三題： 看到 dominant 的定義是 freq(x) * 2 > m 第一感想到的是「比其他加起來都多」(freq(x) > m - freq(x)) 然後他要我們切成左右兩邊，兩邊都要有一樣的 dominant 可以很簡單的知道一定得是原本的 dominant 然後左右都是 dominant 代表和其他人的差距兩邊都必須 >= 1 也就是總共的差距 >= 2 如果總共的差距是 1 的話就會失敗 接著在心理就出現「累計差距」的圖 橫軸是 index, 縱軸是考慮 nums[0, ..., index] 時 dominant 和其他人的差距 這個差距從 0 開始，如果遇到 dominant 就加一，否則減一 最後抵達 freq(x) - (m - freq(x)) 因為我們知道 freq(x) - (m - freq(x)) >= 2 又每次一定只能 +-1, 所以一定有某一刻會通過「1」(真的嗎？) 此時左半邊的差距是 1, 右半邊的差距 >= (2 - 1) > 0 所以就會合法 至於為什麼會浮現這個圖 因為 LeetCode 有類似的題目 第四題： 看到很多字串的 matching, 第一念頭是該不會要寫 Trie 吧好麻煩喔 不過接著看到長度 <= 10 且總數 <= 10^5 所以直接用 set 硬幹也不會有什麼問題 然後題目說要找最長又不包含禁字的 substring 想像中會是這樣 <---------------- word -----------------------> <-xxxxxx-> <-xxxxxx-> <-yyyyyyy-> <-zzzzzzz-> 其中 xxxxxx, yyyyyy, zzzzzz 是禁字 思考一下能不能找出「以 index 為結尾的最長合法 substring」 發現可以，因為非法的條件是完整的包住一個禁字 對於 index, 我們只要找出所有結尾在 index 之前的禁字區間 然後我們的起始點不能比他們任一個人的開頭還要前面，否則就包住他了 反之就不會有任何人被我們包住 所以只要一直更新最大的、我們的開頭不能包含的起始點就可以 index | a b c | d <---------------- word -----------------------> <-xxxxxx-> <-xxxxxx-> <-yyyyyyy-> <-zzzzzzz-> 在上面那張圖裡，以 index 結尾時，ab 是我們不能超過的 cd 可以 c 可以是因為第二個 xxxxxx 的結尾是在 index 之後的，不管怎樣都不會包住他 剩下就只是對每個 index, 把結尾在 index 之前的禁字區間加進來 （看 word[index,...,index], ..., word[index-9,...,index] 有沒有禁字） 並更新起始最大值就好 今天的題目還蠻標準的 應該算是刷久了就會的題目 -- https://i.imgur.com/tLHo8xr.png --
※ 批踢踢實業坊(ptt.cc), 來自: 203.77.61.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1689483142.A.405.html