Zako's Blog

題目網址：https://leetcode.cn/problems/count-of-range-sum/ 題意：給一整數 array nums 以及兩個整數 lower 和 upper。求 nums 中, 值位於 [lower, upper] 之區間和個數。 區間和 S(i, j) 表示在 nums 中, idx 從 i 到 j 中的區間之和, 包含 i 和 j（i ≤ j）。 Solution： 想法：利用 Prefix Sum + Binary Search + Merge Sort, 類似 303. Range Sum Query - Immutable。presum[0] 必須為 0, 若我們想求一區間和 S(i, j) 可看做是 prefix[j + 1] - prefix[i] 我們先考慮以下的問題: 給兩個升序的 array n1 和 n2, 找出所有 (i, j) 滿足 : n2[j] - n2[i] ∈ [lower,upper] 我們在 n2 中使用兩個 ptr left 和 right, 初始皆為 n2 的起始位置。 考慮 n1 的第一個元素 將 lef ...

題目網址：https://leetcode.cn/problems/minimum-number-of-k-consecutive-bit-flips/ 題意：給一 binary array nums 和一整數 k。 k-bit flip 指的是從 nums 中選擇一長度為 k 的 subarray, 並把 subarray 中的每一個 bit 進行反轉。 返回 nums 中不存在 0 所需的最小 k-bit flip 次數。若不可能, 則返回 -1。 subarray 指的是 array 的連續部分。 Solution 1：（TLE 無法通過） 想法：利用 Greedy, 因為對於每個位置而言, 只有初始狀態和 flip 次數決定了自己最終的狀態。每一個長度為 k 的區間, 最多只會被 flip 一次, 因為 flip 兩次對最終結果沒有影響。 因此, 我們由左向右遍歷 nums, 一旦 nums[i] 為 0, 則將其做為 sliding window 的開頭往後取 k - 1 個元素進行 flip 若 i + k - 1 ≥ n, 代表無法將最後幾個 0 反轉, 故返回 ...

題目網址：https://leetcode.cn/problems/count-unique-characters-of-all-substrings-of-a-given-string/ 題意：定義一函數 countUniqueChars(s) 返回 string s 中只出現一次的 char 之個數。 e.g. s = "LEETCODE", 其中 L、T、C、O、D 皆只出現過一次, 因此 countUniqueChars(s) = 5。 今給一 string s, 返回 countUniqueChars(t) 的總和, 其中 t 是 s 的 substring。 注意： 有些 substring 是會重複的, 計算時也必須算上這些重複的 substring（也就是說, 統計 s 所有 substring 中只出現一次的 char）。 s 僅由大寫英文所組成。 Solution 1： 想法：與其計算所有 substring 中的 unique char 個數, 不如計算單一 char 在哪些 substring 是 unique char, 最後做加 ...

題目網址：https://leetcode.cn/problems/substring-with-concatenation-of-all-words/ 題意：給一 string s 和一些長度相同的單字 words。返回 s 中恰好可以由 words 中所有單字串聯而成的 substring 之起始位置。 注意：substring 要與 words 中的單字完全相同, 中間不可參雜其他 char, 而單字串聯的順序可以是任意的。 Solution： 想法：利用 Sliding Window 由於單字串聯的順序可以是任意的, 故利用 freqs 來記錄 words 中每個單字的出現次數 以 i 為起點, 往後取 wordsNum 個單字 用 cur 來記錄當前 substring 中每種單字的出現次數 每個 word 的開頭 = i + j * wordLen, 其中 j 表示以 i 為起點目前取到第幾個單字 若 word 不存在於 freqs 中, 則代表當前 substring 不符合 ➔ 故 i 往下一個嘗試 若 word 在 cur 中的次數 > 該 ...

題目網址：https://leetcode.cn/problems/rearrange-string-k-distance-apart/ 題意：給一 string s 和一整數 k, 重新排列 s 使得相同 char 位置間隔距離至少為 k。若無法做到, 則返回 ""。 Solution： 想法：利用 Greedy 和 Heap, 類似 621. Task Scheduler 和 767. Reorganize String, 要相同 char 之間距離為 k, 可想成是若每一輪能取出不同 k 個 char, 則每一輪相同 char 之間距離一定 ≥ k, 要記得考慮不滿 k 個 char 的情況 class Solution {public: string rearrangeString(string s, int k) { // 在沒有限制間隔距離的情況下, 直接返回 s if (k == 0) { return s; } // 計 ...