重點

• 每天至少練習一題
• 一題可能有兩個解法，通常是「解不出來」之後，看別人的更優解，自己再寫一遍的結果。

題目 — 分享 3 組練習

RotateString

題目

Given two strings s and goal, return true if and only if s can become goal after some number of shifts on s.

A shift on s consists of moving the leftmost character of s to the rightmost position.

For example, if s = "abcde", then it will be "bcdea" after one shift.

解法

• 遍歷從 0 開始找到 n-1，只要找到從 goal 的 index 切分，重新組裝一下就會變成原本的 s 字串，就代表是可以 s 可以通過操作變成 goal。
• 意即從切分的 index 查找，往前的部分是屬於 s 的一部分，且往後切分的字串也是 s 的一部分，代表 goal 是可以從原字串 shift 之後產生的。

Code

package com.leetcode;

public class Solution {
    public boolean rotateString(String s, String goal) {
        if (s.length() != goal.length()) {
            return false;
        }
        for (int i = 0; i < goal.length(); i++) {
            if (s.contains(goal.substring(i)) && s.contains(goal.substring(0, i))) {
                return true;
            }
        }
        return false;
    }
}

test

package com.leetcode;

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

public class RotateStringTest {
    @Test
    public void testRotateString() {
        Solution rotateString = new Solution();
        assertTrue(rotateString.rotateString("abcde", "cdeab"));
    }

    @Test
    public void shouldReturnFalseIfGoalIsNotRotationOfS() {
        Solution rotateString = new Solution();
        assertFalse(rotateString.rotateString("abcde", "decba"));
    }

    @Test
    public void shouldReturnFalseIfLengthOfSAndGoalIsNotEqual() {
        Solution rotateString = new Solution();
        assertFalse(rotateString.rotateString("abcde", "decbaa"));
    }
}

3163. String Compression III

題目

給定一個 string word，使用以下演算法對其進行壓縮：

• 以空字串開頭compword為

  。當 word 不為空時，請使用以下操作：

  • 刪除由最多重複9 次的單一字元word c組成的最大長度前綴。
  • 將前綴的長度附加c 到 comp

返回字串comp。

解法

1. 初始設置
   • 建立 StringBuilder 存儲結果
   • 取得第一個字符作為 currentChar
   • 設置計數器 count = 1
2. 遍歷字串中的每個字符
   • 比較當前字符是否與前一個相同
   • 如果相同且計數 < 9，則計數加 1
   • 如果不同，則將「數字+字符」加入結果中
3. 重置處理
   • 更新當前字符為新字符
   • 重置計數器為 1
4. 完成處理
   • 處理最後一組字符
   • 輸出壓縮後的結果

Code

package com.leetcode;

class CompressedString {
    public String compressedString(String word) {
        StringBuilder compressed = new StringBuilder();
        char currentChar = word.charAt(0);
        int count = 1;

        for (int i = 1; i < word.length(); i++) {
            char character = word.charAt(i);
            if (currentChar == character && count < 9) {
                count++;
            } else {
                compressed.append(count).append(currentChar);
                currentChar = character;
                count = 1;
            }
        }
        compressed.append(count).append(currentChar);
        return compressed.toString();
    }
}

test cases

package com.leetcode;

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

public class CompressedStringTest {

    @Test
    void allNotSame() {
        CompressedString compressedString = new CompressedString();
        assertEquals("1a1b1c1d1e", compressedString.compressedString("abcde"));
    }

    @Test
    void testCompressedStringWithRepeatedCharacters() {
        CompressedString compressedString = new CompressedString();
        assertEquals("9a2a2b", compressedString.compressedString("aaaaaaaaaaabb"));
    }
}

974. Subarray Sums Divisible by K

題目

給定一個整數數組nums和一個整數k，傳回總和可被 整除的非空子數組k的數量。

子數組會是數組之中的連續部分數組**。**

解法

• 用一個 prefix sum 把每次 for loop 的加總存起來。
• 接著拿 sum 去跟 k 除得餘數，若這個餘數「重複出現」數次，代表上一個有這餘數的值，與這個值有「同樣的間隔」，可以用 k 來做整除。
  • 4, 5, 0 — % 5→ 4 % 5 = 4（一次）, 9 % 5 = 4（二次）, 9 % 5 = 4（三次）
  • 然後第一次的出現不算，所以是 0 + 1 + 2 總共 3 個 sub arrays（[5], [5, 0], [0]）

Code

public class SubArraysDivByK {
    public int subarraysDivByK(int[] nums, int k) {
        int count = 0;
        int prefixSum = 0;
        int[] modCount = new int[k];
        modCount[0] = 1; // 初始化整除的數量，整除的只要被找到，必定就會先 + 1

        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i];
            int mod = (prefixSum % k + k) % k;
            count += modCount[mod]; // 若是第一次出現該餘數（除了餘數為0），則啥都沒有，但第二次出現後，代表「在上次和這次」之間，會有 sum 可被 k 整除的 sub array。
            modCount[mod]++;
        }
        return count;
    }
}

js 版本

function devideByK(arr = [1, 2, 3], k = 2) {
    let count = 0;
    let modMap = { 0: 1, };
    let sum = 0;
    for (let i = 0; i < arr.length; i++) {
        sum += arr[i];
        const mod = (sum % k + k) % k;
        count += modMap[mod] || 0;
        modMap[mod] = (modMap[mod] || 0) + 1;
    }

    return count;
}

package com.leetcode;

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

public class SubArraysDivByKTest {
    @Test
    public void testSubarraysDivByK() {
        SubArraysDivByK subArraysDivByK = new SubArraysDivByK();
        assertEquals(7, subArraysDivByK.subarraysDivByK(new int[] { 4, 5, 0, -2, -3, 1 }, 5));
    }

    @Test
    public void testSubarraysDivByKWithNegativeNumbers() {
        SubArraysDivByK subArraysDivByK = new SubArraysDivByK();
        assertEquals(0, subArraysDivByK.subarraysDivByK(new int[] { 5 }, 9));
    }

    @Test
    public void testSubarraysDivByKWithAllSameNumbers() {
        SubArraysDivByK subArraysDivByK = new SubArraysDivByK();
        assertEquals(1, subArraysDivByK.subarraysDivByK(new int[] { -5 }, 5));
    }
}