前端工程師的 LeetCode 之旅 -- 周賽 201

01

整理字元串

題目描述【Easy】

給你一個由大小寫英文字母組成的字元串 s 。

一個整理好的字元串中，兩個相鄰字元 s[i] 和 s[i + 1] 不會同時滿足下述條件：

0 <= i <= s.length - 2

s[i] 是小寫字元，但 s[i + 1] 是相同的大寫字元；反之亦然 。

請你将字元串整理好，每次你都可以從字元串中選出滿足上述條件的 兩個相鄰 字元并删除，直到字元串整理好為止。

請傳回整理好的 字元串 。題目保證在給出的限制條件下，測試樣例對應的答案是唯一的。

注意：空字元串也屬于整理好的字元串，盡管其中沒有任何字元。

示例：

輸入：s = 'leEeetcode'

輸出：'leetcode'

解釋：無論你是選擇 i = 1 或者 i = 2，s 都會縮減為 'leetcode'

本題主要考察以下兩點：

• 資料結構 -- 棧
• 利用 charCode 的內插補點來判斷相鄰兩字元是否互為大小寫字元

時間複雜度 O(n)，空間複雜度 O(n)。

  const makeGood = function(s) {
    const stack = [];
    let startIndex = 0;
    while (startIndex < s.length) {
      const currentItem = s[startIndex];
      if (stack.length && Math.abs(currentItem.charCodeAt(0) - stack[stack.length - 1].charCodeAt(0)) === 32) {
        stack.pop();
      } else {
        stack.push(currentItem);
      }
      startIndex++;
    }

    return stack.join('');
  };
           

02

        找出第N個字元串中的第K位

題目描述【Medium】

給你兩個正整數 n 和 k，二進制字元串  Sn 的形成規則如下：

S1 = "0"

當 i > 1 時，Si = Si-1 + "1" + reverse(invert(Si-1))

其中 + 表示串聯操作，reverse(x) 傳回反轉 x 後得到的字元串，而 invert(x) 則會翻轉 x 中的每一位（0 變為 1，而 1 變為 0）

例如，符合上述描述的序列的前 4 個字元串依次是：

S1 = "0"

S2 = "011"

S3 = "0111001"

S4 = "011100110110001"

請你傳回  Sn 的 第 k 位字元 ，題目資料保證 k 一定在 Sn 長度範圍以内。

示例：

輸入：n = 3，k = 1

輸出：'0'

解釋：s3 為 '0111001'，其第一位為 '0'。

讀完本題之後，應該能夠發現以下規律：

• 每一行的字元串的長度為 2^n - 1
• 後一行與前一行是存在遞推關系
• 每一行的左右兩部分存在翻轉關系

根據以上規律，可以計算出由第一行演變到第 n 行的過程中，第 k 位字元經曆了多少次翻轉，進而得出最終結果。

時間複雜度 O(n)，空間複雜度 O(1)。

  const findKthBit = function(n, k) {
    let current = n;
    let reverseCount = 0;
    if (n === 1) {
      return '0'
    }
    while (current > 1) {
      const total = 2 ** current - 1;
      const mid = Math.ceil(total / 2);
      if (k === mid) {
        if (reverseCount % 2 === 0) {
          return '1';
        }
        return '0';
      }
      if (k > mid) {
        reverseCount++;
        k = mid * 2 - k;
      }
      current--;
    }
    if (reverseCount % 2 === 0) {
      return '0';
    }
    return '1';
  };
           

03

        最大數目不重疊非空子數組

題目描述【Medium】

給你數組 nums 和一個整數 target。

請你傳回非空不重疊子數組的最大數目，且每一個子數組的元素和為 target。

示例：

輸入：nums = [1,1,1,1,1]，target = 2

輸出：2

解釋：總共有兩個不重疊子數組 [1,1] 和 [1,1]。

求解本題需要考慮以下兩個問題：

• 子數組目标和值
• 子數組不重疊

求解子數組目标和值最樸素的方式：兩次循環。采用字首和的方式可以通過空間換時間的方式，将複雜度降低到 O(n)。

但是本題需要確定子數組不重疊，那麼就需要在字首和的基礎上進行一定的改造：尋找到滿足條件的子數組之後，重置目前的字首和狀态。

時間複雜度 O(n)，空間複雜度 O(n)。

  const maxNonOverlapping = function(nums, target) {
    let record = new Set();
    record.add(0);
    let ans = 0;
    let currentSum = 0;
    for (let i = 0; i < nums.length; i++) {
      currentSum += nums[i];
      if (record.has(currentSum - target)) {
        ans++;
        record.clear();
        record.add(0);
        currentSum = 0;
      } else {
        record.add(currentSum);
      }
    }
    return ans;
  };
           

04

 切棍子的最小成本

題目描述【Hard】

有一根長度為 n 個機關的木棍，棍上從 0 到 n 标記了若幹個位置。

你可以按順序完成切割，也可以根據需要更改切割的順序。

每次切割的成本都是目前要切割的棍子的長度，切棍子的總成本是曆次切割成本的總和。對棍子進行切割将會把一根木棍分成兩根較小的木棍（這兩根木棍的長度和就是切割前木棍的長度）。請參閱第一個示例以獲得更直覺的解釋。

傳回切棍子的 最小總成本 。

示例：

輸入：n = 7, cuts = [1, 3, 4, 5]

輸出：16

這是一道尋找最優解的題型，比較容易想到的思路就是周遊所有方案得到最優方案。

針對本道題，那麼就可以嘗試 [0, n] 之間的分割點，每次分割的最小成本由以下三部分組成：

• 目前棍子的長度
• 分割後左半部分棍子後續切割的成本
• 分割後右半部分棍子後續切割的成本

是不是一眼就看出來這是一個遞歸的關系，另外千萬不要忘記遞歸枚舉的過程中一定要利用記憶化來減少重複子問題的計算。

  const minCost = function(n, cuts) {
    const cache = new Map();
    return help(0, n, cuts, cache);
  };

  function help(left, right, cuts, cache) {
    const cacheKey = `${left}-${right}`;
    if (cache.has(cacheKey)) {
      return cache.get(cacheKey);
    }
    let min = Number.MAX_SAFE_INTEGER;
    for (let i = 0; i < cuts.length; i++) {
      if (cuts[i] > left && cuts[i] < right) {
        let cost = help(left, cuts[i], cuts, cache) + help(cuts[i], right, cuts, cache);
        min = Math.min(min, cost);
      }
    }
    if (min === Number.MAX_SAFE_INTEGER) {
      min = 0
    } else {
      min += right - left;
    }
    cache.set(cacheKey, min);
    return min;
  }
           

本道題提示條件中，cuts 數組的長度遠遠小于 n ，是以上述解法還有優化的空間。

優化的解法中可以從 cuts 數組中擷取枚舉的下标，但是題目中給出的 cuts 數組需要做出如下改造：

• cuts 數組是無序的，導緻在周遊的過程中很難判斷目前的切割點是否在合法的區間内。
• cuts 不包含首尾下标，導緻在遞歸過程中沒有起止邊界。

優化後的代碼如下：

  const minCost = function(n, cuts) {
    const record = new Map();
    cuts.sort((a, b) => a - b);
    cuts.unshift(0);
    cuts.push(n);
    const maxIndex = cuts.length - 1;
    return help(0, maxIndex, cuts, record);
  };

  function help(leftIndex, rightIndex, cuts, record) {
    const cacheKey = `${leftIndex}-${rightIndex}`
    if (record.has(cacheKey)) {
      return record.get(cacheKey);
    }
    const left = cuts[leftIndex];
    const right = cuts[rightIndex];

    let min = Number.MAX_SAFE_INTEGER;
    for (let i = leftIndex + 1; i < rightIndex; i++) {
      const cost = help(leftIndex, i, cuts, record) + help(i, rightIndex, cuts, record);
      min = Math.min(cost, min);
    }

    if (min === Number.MAX_SAFE_INTEGER) {
      min = 0;
    } else {
      min += right - left;
    }
    record.set(cacheKey, min);
    return min;
  }
           

05

 往期精彩回顧

• 前端工程師的 LeetCode 之旅 -- 周賽 200
• 前端工程師的 LeetCode 之旅 -- 周賽 185
• 前端工程師的 LeetCode 之旅 -- 周賽 184
• 前端工程師的 LeetCode 之旅 -- 周賽 183

你點的每個贊，我都認真當成了喜歡