Kadane's algorithm

昨天練習的題目是 3381. Maximum Subarray Sum With Length Divisible by K，題目的最佳解是利用 Kadane's algorithm，我覺得比較容易理解的方式是先計算前面 k-1 個 kSum 之後，再往後面用 Kadane's algorithm 來解。

如果是寫 C++ 是這樣：

class Solution {
public:
    long long maxSubarraySum(vector< int>& nums, int k) {
        const int n = nums.size();
        vector< long long> kSum(k, 0);
        long long maxSum = numeric_limits< long long>::min(), prefixSum = 0;
        for (int i = 0; i < k - 1; ++i) {
            prefixSum += nums[i];
            kSum[i] = prefixSum;
        }
        for (int i = k - 1; i < n; ++i) {
            prefixSum += nums[i];
            int r = i % k;
            maxSum = max(maxSum, prefixSum - kSum[r]);
            kSum[r] = min(kSum[r], prefixSum);
        }
        return maxSum;
    }
};

寫 Python3 是這樣：

class Solution:
    def maxSubarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        kSum = [0] * k
        prefixSum = 0
        maxSum = float("-inf")
        for i in range(k - 1):
            prefixSum += nums[i]
            kSum[i] = prefixSum
        for i in range(k - 1, n):
            prefixSum += nums[i]
            r = i % k
            maxSum = max(maxSum, prefixSum - kSum[r])
            kSum[r] = min(kSum[r], prefixSum)
        return maxSum

寫 Go 是這樣，這邊要注意即便是使用 math.MinInt64 還是要用 int64() 明確轉型，不然預設會用 int 然後就會跟後面的 int64 衝突。

func maxSubarraySum(nums []int, k int) int64 {
	n := len(nums)
	kSum := make([]int64, k)
	prefixSum, maxSum := int64(0), int64(math.MinInt64)
	for i := range n {
		prefixSum += int64(nums[i])
		if i < k-1 {
			kSum[i] = prefixSum
			continue
		}
		r := i % k
		maxSum = max(maxSum, prefixSum-kSum[r])
		kSum[r] = min(kSum[r], prefixSum)
	}
	return maxSum
}

寫 Rust 是這樣，沒什麼特別要注意的地方，反正寫錯時編譯器會提醒你該如何修正。 :-P

impl Solution {
    pub fn max_subarray_sum(nums: Vec< i32>, k: i32) -> i64 {
        let k = k as usize;
        let n = nums.len();
        let mut kSum = vec![0i64; k];
        let mut prefixSum = 0i64;
        let mut maxSum = i64::MIN;
        for i in 0..(k-1) {
            prefixSum += nums[i] as i64;
            kSum[i] = prefixSum;
        }
        for i in (k-1)..n {
            prefixSum += nums[i] as i64;
            let r = i % k;
            maxSum = maxSum.max(prefixSum - kSum[r]);
            kSum[r] = kSum[r].min(prefixSum);
        }
        maxSum
    }
}

不曉得為何，寫 Rust 有最愉快的感覺。 :-P

Binary Search

今日練習的題目是 300. Longest Increasing Subsequence 主要是需要使用到 Binary Search

首先是 C++ 的 lower_bound

class Solution {
public:
    int lengthOfLIS(vector< int>& nums) {
        vector< int> arr;
        arr.reserve(nums.size());
        for (auto& num : nums) {
            auto ptr = ranges::lower_bound(arr.begin(), arr.end(), num);
            if (ptr == arr.end()) {
                arr.push_back(num);
            } else {
                *ptr = num;
            }
        }
        return arr.size();
    }
};

然後是 Python 的 bisect.bisect_left()

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        arr = []
        for num in nums:
            i = bisect.bisect_left(arr, num)
            if i == len(arr):
                arr.append(num)
            else:
                arr[i] = num
        return len(arr)

然後是 Go 的 sort.Search()

func lengthOfLIS(nums []int) int {
	arr := make([]int, 0, len(nums))
	for _, num := range nums {
		idx := sort.Search(len(arr), func(i int) bool {
			return arr[i] >= num
		})
		if idx == len(arr) {
			arr = append(arr, num)
		} else {
			arr[idx] = num
		}
	}
	return len(arr)
}

最後是 Rust 的 binary_search

impl Solution {
    pub fn length_of_lis(nums: Vec< i32>) -> i32 {
        let mut arr = Vec::with_capacity(nums.len());
        for num in nums {
            let i = match arr.binary_search(&num) {
                Ok(index) => index,
                Err(index) => index,
            };
            if i == arr.len() {
                arr.push(num);
            } else {
                arr[i] = num;
            }
        }
        arr.len() as i32
    }
}

每種程式語言使用方式都有所不同。

Gray code

今天練習的題目是 1611. Minimum One Bit Operations to Make Integers Zero，後來自己想出解法後去看官方解答才發現是在考 Gray code 的轉換。

我自己列出 16 轉換到 0 的所有 bits 的表現方式，然後仔細觀察後發現有某種規律，於是就猜想了一個方程式出來試試看，結果還真的可以解答，先聲明一下這不是最有效的方法，只是眾多解法中的其中一種而已。

設 $p_1, p_2, \dots, p_j$ 為 $n$ 的二進位中所有 1 的 0-based 索引，且 $p_1 > p_2 > \dots > p_j$ ($p_1$ 是 MSB)。
$$f(n) = \sum_{i=1}^{j} (-1)^{i-1} \cdot (2^{p_i+1} - 1)$$

這是我初始第一個版本

class Solution {
public:
    int minimumOneBitOperations(int n) {
        if (n == 0)
            return 0;
        int k = 32 - __builtin_clz(n);
        int ans = 0;
        bitset<30> arr(n);
        int sign = 1;
        for (int i = k; i > 0; --i) {
            if (arr[i - 1]) {
                ans += sign * ((1 << i) - 1);
                sign *= -1;
            }
        }
        return ans;
    }
};

簡化後的第二個版本

class Solution {
public:
    int minimumOneBitOperations(int n) {
        if (n == 0)
            return 0;
        int k = 32 - __builtin_clz(n);
        int ans = 0;
        int sign = 1;
        for (int i = k; i > 0; --i) {
            if (n & (1 << (i - 1))) {
                ans += sign * ((1 << i) - 1);
                sign *= -1;
            }
        }
        return ans;
    }
};

再進一步簡化後的第三個版本

class Solution {
public:
    int minimumOneBitOperations(int n) {
        if (n == 0)
            return 0;
        int ans = 0;
        int sign = 1;
        while (n) {
            int k = 32 - __builtin_clz(n);
            ans += sign * ((1 << k) - 1);
            sign *= -1;
            n ^= (1 << (k-1));
        }
        return ans;
    }
};

有用 Gemini AI 幫忙寫了一份解答分享在 LeetCode 上面 Using a Math Formula 這樣