陣列與字串 — Array 操作技巧與字串處理完整指南 | 資料結構與演算法

let s = "hello";
s[0] = "H";      // 靜默失敗！字串不可變
console.log(s);  // 仍然輸出 "hello"

// 若要修改，需建立新字串
s = "H" + s.slice(1);  // 產生新字串 "Hello"

// 陣列基本操作與對應複雜度
const arr: number[] = [10, 20, 30, 40, 50];

// O(1) 隨機存取
console.log(arr[2]);        // 30 — 直接定址

// O(1) 尾端 push / pop（動態陣列攤銷）
arr.push(60);               // [10, 20, 30, 40, 50, 60]
arr.pop();                  // [10, 20, 30, 40, 50]

// O(n) 頭端 unshift / shift（需搬移所有元素）
arr.unshift(0);             // [0, 10, 20, 30, 40, 50]
arr.shift();                // [10, 20, 30, 40, 50]

// O(n) 中間插入（splice）
arr.splice(2, 0, 99);       // [10, 20, 99, 30, 40, 50]

// O(n) 搜尋（未排序）
const idx = arr.indexOf(99); // 2

// O(k) 切片（建立副本）
const sub = arr.slice(1, 4); // [20, 99, 30]

// O(n log n) 排序（TimSort）
arr.sort((a, b) => a - b);

// prefix-sum.ts
// 核心思想：預計算累積和，使區間查詢從 O(n) 降至 O(1)

class PrefixSum {
  private prefix: number[];

  constructor(nums: number[]) {
    // prefix[i] = nums[0] + nums[1] + ... + nums[i-1]
    // 索引偏移一位，讓 prefix[0] = 0，簡化邊界處理（無需特判 left = 0）
    this.prefix = new Array(nums.length + 1).fill(0);
    for (let i = 0; i < nums.length; i++) {
      this.prefix[i + 1] = this.prefix[i] + nums[i];
    }
  }

  // 查詢 [left, right] 閉區間的元素總和，O(1)
  rangeSum(left: number, right: number): number {
    return this.prefix[right + 1] - this.prefix[left];
    // 公式推導：
    // prefix[right+1] = sum(0..right)
    // prefix[left]    = sum(0..left-1)
    // 差值            = sum(left..right) ✓
  }
}

// 使用範例
const nums = [3, -2, 4, 1, -5, 8, 2];
const ps = new PrefixSum(nums);
console.log(ps.rangeSum(1, 4));  // -2+4+1+(-5) = -2
console.log(ps.rangeSum(0, 6));  // 全部 = 11
console.log(ps.rangeSum(5, 6));  // 8+2 = 10

// 二維前綴和（矩形區域求和）
class PrefixSum2D {
  private prefix: number[][];

  constructor(matrix: number[][]) {
    const m = matrix.length, n = matrix[0].length;
    // prefix[i][j] = 左上角 (0,0) 到 (i-1,j-1) 的矩形總和
    this.prefix = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
      for (let j = 1; j <= n; j++) {
        this.prefix[i][j] = matrix[i-1][j-1]
          + this.prefix[i-1][j]   // 上方矩形
          + this.prefix[i][j-1]   // 左方矩形
          - this.prefix[i-1][j-1]; // 容斥原理消除重複計算
      }
    }
  }

  // 查詢 (r1,c1) 到 (r2,c2) 的矩形區域總和，O(1)
  regionSum(r1: number, c1: number, r2: number, c2: number): number {
    return this.prefix[r2+1][c2+1]
      - this.prefix[r1][c2+1]   // 扣除上方
      - this.prefix[r2+1][c1]   // 扣除左方
      + this.prefix[r1][c1];    // 容斥原理補回多扣的部分
  }
}

// difference-array.ts
// 核心思想：將「區間加值」操作從 O(n) 降至 O(1)，還原時 O(n)

class DifferenceArray {
  private diff: number[];

  constructor(nums: number[]) {
    const n = nums.length;
    // diff[i] = nums[i] - nums[i-1]（記錄相鄰差值）
    this.diff = new Array(n).fill(0);
    this.diff[0] = nums[0];
    for (let i = 1; i < n; i++) {
      this.diff[i] = nums[i] - nums[i - 1];
    }
  }

  // 對 [left, right] 區間的每個元素加上 val，O(1)
  rangeAdd(left: number, right: number, val: number): void {
    this.diff[left] += val;                  // 從 left 開始「啟動」加值效果
    if (right + 1 < this.diff.length) {
      this.diff[right + 1] -= val;           // 從 right+1 開始「取消」加值效果
    }
    // 原理：還原時做前綴和，left 之前不受影響，right+1 之後被抵消
  }

  // 還原為實際陣列，O(n)
  toArray(): number[] {
    const result = new Array(this.diff.length);
    result[0] = this.diff[0];
    for (let i = 1; i < this.diff.length; i++) {
      result[i] = result[i - 1] + this.diff[i]; // 前綴和還原
    }
    return result;
  }
}

// 使用範例：多次區間加值後一次還原
const da = new DifferenceArray([0, 0, 0, 0, 0]);
da.rangeAdd(1, 3, 5);  // 對索引 1~3 各加 5 → [0, 5, 5, 5, 0]
da.rangeAdd(0, 2, 2);  // 對索引 0~2 各加 2 → [2, 7, 7, 5, 0]
da.rangeAdd(2, 4, -1); // 對索引 2~4 各減 1 → [2, 7, 6, 4, -1]
console.log(da.toArray()); // [2, 7, 6, 4, -1]
// k 次區間加值：O(k)，若用暴力法為 O(k·n)

// kadane.ts
// 核心思想：局部最優 → 全域最優（Greedy / DP 交匯）

function maxSubArray(nums: number[]): number {
  // currentSum：以 nums[i] 結尾的最大子陣列和
  // maxSum：全域最大值
  let currentSum = nums[0];
  let maxSum = nums[0];

  for (let i = 1; i < nums.length; i++) {
    // 決策：繼承前段（currentSum + nums[i]）or 重新開始（nums[i]）
    // 若前段和為負，拋棄它不如從 nums[i] 重新開始
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
  return maxSum;
}

console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
// 輸出：6（子陣列 [4, -1, 2, 1]）

// string-tricks.ts

// ✓ 正確：用陣列收集後一次 join，O(n)
function buildString(words: string[]): string {
  const parts: string[] = [];
  for (const word of words) {
    parts.push(word.toUpperCase());
  }
  return parts.join(', '); // 內部使用 StringBuilder 模式，只複製一次
}

// 字串轉陣列 → 修改 → 轉回字串（處理需要「修改」字串的場景）
function reverseString(s: string): string {
  return s.split('').reverse().join('');
  // split('')  → string[] ← 可以修改
  // reverse()  → 原地反轉
  // join('')   → 轉回 string
}

// 字元頻率計數（用於同字母異序詞問題）
function charFrequency(s: string): Map<string, number> {
  const freq = new Map<string, number>();
  for (const ch of s) {
    freq.set(ch, (freq.get(ch) ?? 0) + 1); // ?? 0 處理第一次出現
  }
  return freq;
}

// 判斷兩字串是否為同字母異序詞（Anagram）
function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  const freq = charFrequency(s);
  for (const ch of t) {
    const count = freq.get(ch) ?? 0;
    if (count === 0) return false; // t 中有 s 沒有的字元
    freq.set(ch, count - 1);
  }
  return true;
}

console.log(isAnagram("anagram", "nagaram")); // true
console.log(isAnagram("rat", "car"));         // false

// array_comparison.cpp
// 編譯：g++ -O2 -std=c++20 array_comparison.cpp -o array_comparison
#include <array>
#include <iostream>
#include <numeric>
#include <vector>

// ── C-style array：固定大小，堆疊分配 ──────────────────────
// 優點：零開銷，直接對應硬體記憶體模型
// 缺點：無大小資訊，容易越界，不可複製賦值
void cStyleDemo() {
  int arr[5] = {1, 2, 3, 4, 5};
  // sizeof(arr) / sizeof(arr[0]) 才能得到長度，容易忘記
  std::cout << "C-style size: " << sizeof(arr)/sizeof(arr[0]) << "\n"; // 5
}

// ── std::array：固定大小，堆疊分配，型別安全 ────────────────
// 優點：size() 方法、範圍 for、at() 越界檢查、可複製
// 缺點：大小必須是編譯期常數
void stdArrayDemo() {
  std::array<int, 5> arr = {1, 2, 3, 4, 5};
  std::cout << "std::array size: " << arr.size() << "\n"; // 5

  // STL 算法可直接使用
  int sum = std::accumulate(arr.begin(), arr.end(), 0);
  std::cout << "sum: " << sum << "\n"; // 15

  // at() 提供越界檢查（丟出 std::out_of_range）
  try {
    arr.at(10); // 越界存取
  } catch (const std::out_of_range& e) {
    std::cout << "越界：" << e.what() << "\n";
  }
}

// ── std::vector：動態大小，堆積分配 ─────────────────────────
// 優點：動態調整大小，攤銷 O(1) push_back，豐富 STL 方法
// 缺點：堆積分配有額外開銷，cache 效能略低於固定陣列
void stdVectorDemo() {
  std::vector<int> v;
  v.reserve(10); // 預先分配，避免多次 realloc

  for (int i = 0; i < 5; i++) v.push_back(i * 2); // 0 2 4 6 8
  std::cout << "size=" << v.size() << " capacity=" << v.capacity() << "\n";

  v.emplace_back(10); // 直接在容器內構造，比 push_back 少一次複製

  // 刪除中間元素（O(n)，後續元素左移）
  v.erase(v.begin() + 2);

  for (int x : v) std::cout << x << " ";
  std::cout << "\n"; // 0 2 6 8 10
}

// prefix_diff.cpp
#include <iostream>
#include <vector>

// 前綴和
struct PrefixSum {
  std::vector<long long> prefix;

  explicit PrefixSum(const std::vector<int>& nums)
      : prefix(nums.size() + 1, 0) {
    for (std::size_t i = 0; i < nums.size(); ++i) {
      prefix[i + 1] = prefix[i] + nums[i];
    }
  }

  // O(1) 區間查詢
  long long rangeSum(int left, int right) const {
    return prefix[right + 1] - prefix[left];
  }
};

// 差分陣列
struct DiffArray {
  std::vector<long long> diff;

  explicit DiffArray(const std::vector<int>& nums)
      : diff(nums.size(), 0) {
    diff[0] = nums[0];
    for (std::size_t i = 1; i < nums.size(); ++i) {
      diff[i] = nums[i] - nums[i - 1];
    }
  }

  // O(1) 區間加值
  void rangeAdd(int left, int right, long long val) {
    diff[left] += val;
    if (right + 1 < static_cast<int>(diff.size())) {
      diff[right + 1] -= val;
    }
  }

  // O(n) 還原
  std::vector<long long> toVector() const {
    std::vector<long long> result(diff.size());
    result[0] = diff[0];
    for (std::size_t i = 1; i < diff.size(); ++i) {
      result[i] = result[i - 1] + diff[i];
    }
    return result;
  }
};

int main() {
  std::vector<int> nums = {3, -2, 4, 1, -5, 8, 2};
  PrefixSum ps(nums);
  std::cout << ps.rangeSum(1, 4) << "\n"; // -2

  std::vector<int> base = {0, 0, 0, 0, 0};
  DiffArray da(base);
  da.rangeAdd(1, 3, 5);
  da.rangeAdd(0, 2, 2);
  auto result = da.toVector();
  for (auto x : result) std::cout << x << " ";
  std::cout << "\n"; // 2 7 7 5 0
  return 0;
}

#include <string>
#include <string_view>
#include <iostream>

void stringVsStringView() {
  std::string s = "Hello, World! This is a long string.";

  // std::string：擁有資料，substr 複製 → O(k) 時間 + O(k) 空間
  std::string sub = s.substr(7, 5); // 複製 "World"
  std::cout << "substr (copy): " << sub << "\n";

  // std::string_view：非擁有的視圖，O(1) 切片，零複製
  // 注意：string_view 的生命週期不能超過底層 string！
  std::string_view sv(s);
  std::string_view sv_sub = sv.substr(7, 5); // 零複製，只移動指標
  std::cout << "string_view (no copy): " << sv_sub << "\n";
}

// 語言差異對照表
// ┌──────────────────┬──────────────────┬──────────────────────────┐
// │ 特性             │ JavaScript       │ C++                      │
// ├──────────────────┼──────────────────┼──────────────────────────┤
// │ 字串可變性       │ 不可變           │ std::string 可變          │
// │ 零複製切片       │ 無原生支援       │ std::string_view          │
// │ 動態陣列         │ Array（內建）    │ std::vector<T>            │
// │ 固定大小陣列     │ TypedArray       │ std::array<T,N>           │
// │ 越界存取         │ 回傳 undefined   │ 未定義行為（UB）          │
// └──────────────────┴──────────────────┴──────────────────────────┘

// circular-array.ts
class CircularQueue<T> {
  private data: (T | undefined)[];
  private head: number = 0; // 讀取指標
  private tail: number = 0; // 寫入指標
  private _size: number = 0;

  constructor(private capacity: number) {
    this.data = new Array(capacity);
  }

  enqueue(item: T): boolean {
    if (this._size === this.capacity) return false; // 已滿
    this.data[this.tail] = item;
    this.tail = (this.tail + 1) % this.capacity; // 環形前進
    this._size++;
    return true;
  }

  dequeue(): T | undefined {
    if (this._size === 0) return undefined; // 已空
    const item = this.data[this.head];
    this.data[this.head] = undefined;
    this.head = (this.head + 1) % this.capacity; // 環形前進
    this._size--;
    return item;
  }

  get size(): number { return this._size; }
}

const q = new CircularQueue<number>(3);
q.enqueue(1); q.enqueue(2); q.enqueue(3);
console.log(q.dequeue()); // 1
q.enqueue(4);             // 環繞回到索引 0
console.log(q.size);      // 3

// sparse-array.ts
class SparseArray<T> {
  private store = new Map<number, T>();
  constructor(public readonly length: number, private defaultValue: T) {}

  get(index: number): T {
    return this.store.get(index) ?? this.defaultValue;
  }

  set(index: number, value: T): void {
    if (value === this.defaultValue) {
      this.store.delete(index); // 等於預設值就不儲存
    } else {
      this.store.set(index, value);
    }
  }

  get memoryUsage(): number { return this.store.size; }
}

// 應用：1,000,000 格的矩陣，只有 2 格非零
const sparse = new SparseArray<number>(1_000_000, 0);
sparse.set(42, 99);
sparse.set(999_999, 7);
console.log(sparse.memoryUsage); // 2（只儲存 2 個非零值）
console.log(sparse.get(42));     // 99
console.log(sparse.get(100));    // 0（預設值）

// 二維陣列初始化（常見陷阱）
const m = 3, n = 4;

// ❌ 錯誤：所有列共享同一個陣列參考
const wrongGrid = new Array(m).fill(new Array(n).fill(0));
wrongGrid[0][0] = 99;
console.log(wrongGrid[1][0]); // 99！— 意外修改了所有列

// ✓ 正確：使用 Array.from 為每列建立獨立陣列
const grid = Array.from({ length: m }, () => new Array(n).fill(0));
grid[0][0] = 99;
console.log(grid[1][0]); // 0 — 正確獨立

// 時間：O(n)，空間：O(1)（輸出陣列不計入額外空間）
function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const result = new Array(n).fill(1);

  // 第一次掃描：result[i] = i 左邊所有元素的積
  let prefixProduct = 1;
  for (let i = 0; i < n; i++) {
    result[i] = prefixProduct;
    prefixProduct *= nums[i]; // 為下一位置更新前綴積
  }

  // 第二次掃描（從右到左）：乘上 i 右邊所有元素的積
  let suffixProduct = 1;
  for (let i = n - 1; i >= 0; i--) {
    result[i] *= suffixProduct;
    suffixProduct *= nums[i]; // 為下一位置更新後綴積
  }

  return result;
}

// 追蹤過程（nums = [1, 2, 3, 4]）：
// 前綴積後 result: [1, 1, 2, 6]
//                   ^           (result[0] 左邊無元素 → 1)
// 後綴積後 result: [24, 12, 8, 6]  ← 正確答案
console.log(productExceptSelf([1, 2, 3, 4])); // [24, 12, 8, 6]

// 時間：O(n)，空間：O(n)
function subarraySum(nums: number[], k: number): number {
  // prefixCountMap[s] = 前綴和等於 s 的出現次數
  const prefixCountMap = new Map<number, number>();
  prefixCountMap.set(0, 1); // 空子陣列的基底情況（前綴和為 0 出現一次）

  let currentPrefix = 0;
  let count = 0;

  for (const num of nums) {
    currentPrefix += num;

    // 若 (currentPrefix - k) 曾出現過，代表存在對應的有效子陣列
    const complement = currentPrefix - k;
    count += prefixCountMap.get(complement) ?? 0;

    // 記錄當前前綴和
    prefixCountMap.set(currentPrefix, (prefixCountMap.get(currentPrefix) ?? 0) + 1);
  }

  return count;
}

// 追蹤過程（nums = [1, 1, 1], k = 2）：
// i=0: prefix=1, complement=-1（未找到）, map={0:1, 1:1}
// i=1: prefix=2, complement=0（找到！+1）, map={0:1, 1:1, 2:1}
// i=2: prefix=3, complement=1（找到！+1）, map={0:1, 1:1, 2:1, 3:1}
// count = 2 ✓
console.log(subarraySum([1, 1, 1], 2)); // 2
console.log(subarraySum([1, 2, 3], 3)); // 2（[1,2] 和 [3]）

// ❌ 錯誤：l = 0 時需要特判，容易出錯
function rangeSumBad(prefix: number[], l: number, r: number): number {
  return l > 0 ? prefix[r] - prefix[l - 1] : prefix[r]; // 特判！
}

// ✓ 正確：宣告時多一個哨兵位 prefix[0] = 0，統一公式
function rangeSumGood(prefix: number[], l: number, r: number): number {
  // prefix 長度為 n+1，prefix[i+1] = sum(0..i)
  return prefix[r + 1] - prefix[l]; // 永遠不需要特判
}

// ❌ 錯誤：每次 += 建立新字串，累積 O(n²)
function joinBad(words: string[]): string {
  let result = '';
  for (const word of words) {
    result += word + ','; // 每次產生全新完整字串並複製！
  }
  return result;
}

// ✓ 正確：用陣列收集後一次 join，O(n)
function joinGood(words: string[]): string {
  return words.join(',');
}

// ❌ 錯誤：fill 共享同一個陣列參考
const wrong = new Array(3).fill(new Array(4).fill(0));
wrong[0][0] = 99;
console.log(wrong[1][0]); // 99！— 不是預期的 0

// ✓ 正確：Array.from 為每列建立獨立陣列
const correct = Array.from({ length: 3 }, () => new Array(4).fill(0));
correct[0][0] = 99;
console.log(correct[1][0]); // 0 — 正確