網易首頁 > 網易號 > 正文申請入駐

2026-04-27：使子字符串變交替的最少刪除次數。用go語言，給定一個只含字符 A 和 B 的字符串 s，長度為 n。隨后會有若干操作查詢 queries

2026-04-27 00:09:38　來源: moonfdd

北京舉報

分享至

2026-04-27：使子字符串變交替的最少刪除次數。用go語言，給定一個只含字符 A 和 B 的字符串 s，長度為 n。隨后會有若干操作查詢 queries，總數為 q。每條查詢可能是兩種形式之一：
1.[1, j]：把字符串中位置 j 的字符翻轉（A ? B）。該操作會改變字符串 s，并影響后續所有查詢。
2.[2, l, r]：在不修改字符串 s 的前提下，針對區間 [l, r] 的子串，求讓它變為“交替字符串”所需的最少刪除字符數。

? “交替字符串”指子串中任意相鄰兩個字符都不相同。長度為 1 的子串天然滿足該條件。
? 區間查詢不會改變整體字符串長度 n。

請為所有類型 [2, l, r] 的查詢依次計算結果，并把這些結果按順序組成數組 answer 返回，其中 answer[i] 對應第 i 個區間查詢的最小刪除數。

1 <= n == s.length <= 100000。

s[i] 要么是 'A'，要么是 'B'。

1 <= q == queries.length <= 100000。

queries[i].length == 2 或 3。

queries[i] == [1, j] 或

queries[i] == [2, l, r]。

0 <= j <= n - 1。

0 <= l <= r <= n - 1。

輸入：s = "ABA", queries = [[2,1,2],[1,1],[2,0,2]]。

輸出：[0,2]。

解釋：

queries[i]

查詢前的 s

s[l..r]

結果

答案

[2, 1, 2]

"ABA"

"BA"

已經是交替字符串

[1, 1]

"ABA"

將 s[1] 從 'B' 反轉為 'A'

[2, 0, 2]

"AAA"

刪除任意兩個 'A' 以得到 "A"

因此，答案是 [0, 2]。

題目來自力扣3777。

代碼執行過程詳細分步解析

我們結合輸入示例：s = "ABA"（長度n=3），queries = [[2,1,2],[1,1],[2,0,2]]，分步驟拆解整個邏輯，全程不寫代碼，只講核心流程。

前置知識鋪墊

1.交替字符串：相鄰字符不能相同，比如BA是交替，AAA不是；
2.核心規律：一個子串要變成交替字符串，最少刪除次數 = 子串中相鄰重復字符的總個數
例：BA無相鄰重復，刪除數=0；AAA有2組相鄰重復（位置0-1、1-2），刪除數=2；
3.樹狀數組（Fenwick Tree）：專門用來快速記錄、更新、查詢區間內相鄰重復字符的總數，支持O(logn)的單點修改和區間查詢。

第一步：初始化數據結構

1. 確定字符串長度n=3，創建一個長度適配的樹狀數組，專門存儲相鄰重復字符的標記；
2. 遍歷原字符串ABA，檢查每一組相鄰字符：

? 位置0和1：A和B→ 不重復，不標記；
? 位置1和2：B和A→ 不重復，不標記；

3. 最終樹狀數組中沒有任何標記值，代表原字符串沒有相鄰重復的字符。

第二步：處理第一條查詢 [2, 1, 2]（類型2：區間查詢）

1. 解析查詢：查詢子串區間[1,2]（對應原字符串BA）；
2. 核心邏輯：調用樹狀數組查詢這個區間內相鄰重復字符的總數；
3. 結果：區間內沒有相鄰重復字符，總數=0；
4. 輸出：將0加入答案數組，此時答案數組為[0]。

第三步：處理第二條查詢 [1, 1]（類型1：字符翻轉）

1. 解析查詢：翻轉字符串位置1的字符（原字符是B，翻轉后變成A）；
2. 關鍵操作：翻轉字符會影響它左邊和右邊的相鄰關系，需要同步更新樹狀數組：

? 位置1的左側是位置0（原字符A）：翻轉后A和A重復 → 給樹狀數組標記+1；
? 位置1的右側是位置2（原字符A）：翻轉后A和A重復 → 給樹狀數組標記+1；

3. 最終字符串變為AAA，樹狀數組記錄了2個相鄰重復標記；

4. 無輸出結果，僅修改字符串和樹狀數組。

第四步：處理第三條查詢 [2, 0, 2]（類型2：區間查詢）

1. 解析查詢：查詢子串區間[0,2]（對應修改后的字符串AAA）；
2. 核心邏輯：調用樹狀數組查詢這個區間內相鄰重復字符的總數；
3. 結果：區間內有2組相鄰重復字符，總數=2；
4. 輸出：將2加入答案數組，最終答案數組為[0, 2]。

完整流程總結

1. 初始化：用樹狀數組記錄原字符串所有相鄰重復字符的位置；
2. 遍歷所有查詢：

? 遇到類型2查詢：直接用樹狀數組查詢目標區間的相鄰重復總數，就是最少刪除數，加入答案；
? 遇到類型1查詢：翻轉指定位置的字符，同時更新該字符左右兩側的相鄰關系（修改樹狀數組的標記）；

3. 所有查詢處理完畢，返回答案數組。

時間復雜度與空間復雜度分析 1. 總時間復雜度

? 樹狀數組的單點更新和區間查詢操作，時間復雜度都是O(logn)；
? 初始化遍歷字符串：O(n)；
? 總共有 q 條查詢，每條查詢最多執行2次樹狀數組操作（類型1）或1次（類型2）；
? 總時間復雜度：O(n + q·logn)。
（完全適配題目中n和q最大1e5的要求，高效無超時）

2. 總額外空間復雜度

? 樹狀數組占用空間：O(n)；
? 存儲原字符串的字節數組：O(n)；
? 答案數組：最多O(q)；
? 總額外空間復雜度：O(n + q)。
（屬于線性空間，符合大數據量的內存要求）

總結

1. 核心思路：最少刪除次數 = 子串內相鄰重復字符的個數；
2. 核心工具：樹狀數組實現快速修改+快速查詢，適配1e5級別的大數據量；
3. 時間復雜度：O(n + q·logn)，空間復雜度：O(n + q)。

Go完整代碼如下：

package main

 import (
    "fmt"
)

 type fenwick []int

 func newFenwickTree(n int) fenwick {
    returnmake(fenwick, n+1) // 使用下標 1 到 n
}

 // a[i] 增加 val
// 1 <= i <= n
// 時間復雜度 O(log n)
func (f fenwick) update(i int, val int) {
    for ; i < len(f); i += i & -i {
        f[i] += val
    }
}

 // 求前綴和 a[1] + ... + a[i]
// 1 <= i <= n
// 時間復雜度 O(log n)
func (f fenwick) pre(i int) (res int) {
    for ; i > 0; i &= i - 1 {
        res += f[i]
    }
    return
}

 // 求區間和 a[l] + ... + a[r]
// 1 <= l <= r <= n
// 時間復雜度 O(log n)
func (f fenwick) query(l, r int) int {
    if r < l {
        return0
    }
    return f.pre(r) - f.pre(l-1)
}

 func minDeletions(s string, queries [][]int) (ans []int) {
    n := len(s)
    t := newFenwickTree(n - 1)
    for i := 1; i < n; i++ {
        if s[i-1] == s[i] { // 刪除 i
            t.update(i, 1)
        }
    }

     bs := []byte(s)
    for _, q := range queries {
        if q[0] == 2 {
            ans = append(ans, t.query(q[1]+1, q[2]))
            continue
        }

         i := q[1]

         if i > 0 {
            val := 1
            if bs[i-1] == bs[i] {
                val = -1
            }
            t.update(i, val)
        }

         if i < n-1 {
            val := 1
            if bs[i] == bs[i+1] {
                val = -1
            }
            t.update(i+1, val)
        }

         bs[i] ^= 'A' ^ 'B'// A 變成 B，B 變成 A
    }
    return
}

 func main() {
    s := "ABA"
    queries := [][]int{{2, 1, 2}, {1, 1}, {2, 0, 2}}
    result := minDeletions(s, queries)
    fmt.Println(result)
}

Python完整代碼如下：

# -*-coding:utf-8-*-

 class Fenwick:
    def __init__(self, n: int):
        self.n = n
        self.bit = [0] * (n + 1)  # 使用下標 1 到 n

     # a[i] 增加 val
    # 1 <= i <= n
    # 時間復雜度 O(log n)
    def update(self, i: int, val: int) -> None:
        while i < len(self.bit):
            self.bit[i] += val
            i += i & -i

     # 求前綴和 a[1] + ... + a[i]
    # 1 <= i <= n
    # 時間復雜度 O(log n)
    def pre(self, i: int) -> int:
        res = 0
        while i > 0:
            res += self.bit[i]
            i &= i - 1
        return res

     # 求區間和 a[l] + ... + a[r]
    # 1 <= l <= r <= n
    # 時間復雜度 O(log n)
    def query(self, l: int, r: int) -> int:
        if r < l:
            return0
        return self.pre(r) - self.pre(l - 1)

 def min_deletions(s: str, queries: list) -> list:
    n = len(s)
    tree = Fenwick(n - 1)

     # 初始化樹狀數組，標記需要刪除的位置
    for i in range(1, n):
        if s[i - 1] == s[i]:  # 刪除 i
            tree.update(i, 1)

     bs = list(s)
    ans = []

     for q in queries:
        if q[0] == 2:
            # 區間查詢
            ans.append(tree.query(q[1] + 1, q[2]))
            continue

         # 更新操作 q[0] == 1
        i = q[1]

         if i > 0:
            val = 1
            if bs[i - 1] == bs[i]:
                val = -1
            tree.update(i, val)

         if i < n - 1:
            val = 1
            if bs[i] == bs[i + 1]:
                val = -1
            tree.update(i + 1, val)

         # 翻轉字符 A <-> B
        bs[i] = chr(ord('A') + ord('B') - ord(bs[i]))

     return ans

 def main():
    s = "ABA"
    queries = [[2, 1, 2], [1, 1], [2, 0, 2]]
    result = min_deletions(s, queries)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代碼如下：

  

  


 using namespace std;

 class Fenwick {
private:
    vector bit;
    int n;

 public:
    Fenwick(int n) : n(n) {
        bit.resize(n + 1, 0); // 使用下標 1 到 n
    }

     // a[i] 增加 val
    // 1 <= i <= n
    // 時間復雜度 O(log n)
    void update(int i, int val) {
        for (; i < bit.size(); i += i & -i) {
            bit[i] += val;
        }
    }

     // 求前綴和 a[1] + ... + a[i]
    // 1 <= i <= n
    // 時間復雜度 O(log n)
    int pre(int i) {
        int res = 0;
        for (; i > 0; i &= i - 1) {
            res += bit[i];
        }
        return res;
    }

     // 求區間和 a[l] + ... + a[r]
    // 1 <= l <= r <= n
    // 時間復雜度 O(log n)
    int query(int l, int r) {
        if (r < l) {
            return0;
        }
        return pre(r) - pre(l - 1);
    }
};

 vector minDeletions(string s, vector 
 
 int 
 >>& queries) { 
 
 
      
 int 
  n = s.size(); 
 
 
     Fenwick tree(n -  
 1 
 ); 
 
 
 
 
      
 // 初始化樹狀數組，標記需要刪除的位置 
 
 
      
 for 
  ( 
 int 
  i =  
 1 
 ; i < n; i++) { 
 
 
          
 if 
  (s[i -  
 1 
 ] == s[i]) {  
 // 刪除 i 
 
 
             tree.update(i,  
 1 
 ); 
 
 
         } 
 
 
     } 
 
 
 
 
     vector 
 
 bs(s.begin(), s.end()); 
 
 
 
     vector< 
 int 
 > ans; 
 
 
 
 
      
 for 
  (auto& q : queries) { 
 
 
          
 if 
  (q[ 
 0 
 ] ==  
 2 
 ) { 
 
 
              
 // 區間查詢 
 
 
             ans.push_back(tree.query(q[ 
 1 
 ] +  
 1 
 , q[ 
 2 
 ])); 
 
 
              
 continue 
 ; 
 
 
         } 
 
 
 
 
          
 // 更新操作 q[0] == 1 
 
 
          
 int 
  i = q[ 
 1 
 ]; 
 
 
 
 
          
 if 
  (i >  
 0 
 ) { 
 
 
              
 int 
  val =  
 1 
 ; 
 
 
              
 if 
  (bs[i -  
 1 
 ] == bs[i]) { 
 
 
                 val =  
 -1 
 ; 
 
 
             } 
 
 
             tree.update(i, val); 
 
 
         } 
 
 
 
 
          
 if 
  (i < n -  
 1 
 ) { 
 
 
              
 int 
  val =  
 1 
 ; 
 
 
              
 if 
  (bs[i] == bs[i +  
 1 
 ]) { 
 
 
                 val =  
 -1 
 ; 
 
 
             } 
 
 
             tree.update(i +  
 1 
 , val); 
 
 
         } 
 
 
 
 
          
 // 翻轉字符 A <-> B 
 
 
          
 // 'A' ^ 'B' 在 C++ 中是 1，因為 'A' 是 65，'B' 是 66，異或結果為 1 
 
 
          
 // 所以 bs[i] ^= 1 可以實現 A(65) 變成 B(66)，B(66) 變成 A(65) 
 
 
         bs[i] ^=  
 1 
 ; 
 
 
     } 
 
 
 
 
      
 return 
  ans; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
      
 string 
  s =  
 "ABA" 
 ; 
 
 
     vector 
 
 int 
 >> queries = {{ 
 2 
 ,  
 1 
 ,  
 2 
 }, { 
 1 
 ,  
 1 
 }, { 
 2 
 ,  
 0 
 ,  
 2 
 }}; 
 
 
     vector< 
 int 
 > result = minDeletions(s, queries); 
 
 
 
 
     cout <<  
 "[" 
 ; 
 
 
      
 for 
  (size_t i =  
 0 
 ; i < result.size(); i++) { 
 
 
          
 if 
  (i >  
 0 
 ) cout <<  
 " " 
 ; 
 
 
         cout << result[i]; 
 
 
     } 
 
 
     cout <<  
 "]" 
  << endl; 
 
 
 
 
      
 return 
 0 
 ; 
 
 
 }

我們相信人工智能為普通人提供了一種“增強工具”，并致力于分享全方位的AI知識。在這里，您可以找到最新的AI科普文章、工具評測、提升效率的秘籍以及行業洞察。歡迎關注“福大大架構師每日一題”，發消息可獲得面試資料，讓AI助力您的未來發展。

特別聲明：以上內容(如有圖片或視頻亦包括在內)為自媒體平臺“網易號”用戶上傳并發布，本平臺僅提供信息存儲服務。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.