Leetcode 第 398 場周賽題解

題目1：3151. 特殊數組 I

思路

遍歷數組 nums，依次比較相鄰元素是否奇偶性不同即可。

代碼

class Solution {
public:bool isArraySpecial(vector<int>& nums) {if (nums.size() == 1)return true;int n = nums.size();for (int i = 0; i < n - 1; i++)if (!different(nums[i], nums[i + 1]))return false;return true;}bool different(int a, int b) { return abs(a - b) % 2; }
};

復雜度分析

時間復雜度：O(n)，其中 n 是數組 nums 的長度。

空間復雜度：O(1)。

題目2：3152. 特殊數組 II

思路

預處理 + 前綴和。

定義一個長為 n?1 的數組 a，其中 a[i] = nums[i] % 2 == nums[i+1] % 2，那么 a 的從 to-1 到 from 的子數組和等于 0，就說明詢問的子數組是特殊數組。

計算 a 的前綴和 preSum，可以快速判斷子數組和是否為 0。

代碼

/** @lc app=leetcode.cn id=3152 lang=cpp** [3152] 特殊數組 II*/// @lc code=start
class Solution
{
public:vector<bool> isArraySpecial(vector<int> &nums, vector<vector<int>> &queries){int n = nums.size();// 定義一個長為 n?1 的數組 a，其中 a[i] = nums[i] % 2 == nums[i+1] % 2// 那么 a 的從 to-1 到 from 的子數組和等于 0，就說明詢問的子數組是特殊數組。// 計算 a 的前綴和 preSum，可以快速判斷子數組和是否為 0vector<int> preSum(n, 0);for (int i = 1; i < n; i++){// 相鄰兩數的異或和的最低位取反int a = !((nums[i] ^ nums[i - 1]) & 1);preSum[i] = preSum[i - 1] + a;}int m = queries.size();vector<bool> ans(m);for (int i = 0; i < m; i++){int from = queries[i][0], to = queries[i][1];ans[i] = preSum[to] - preSum[from] == 0;}return ans;}
};
// @lc code=end

復雜度分析

時間復雜度：O(n+m)，其中 n 是數組 nums 的長度，m 是數組 queries 的長度。

空間復雜度：O(n)，其中 n 是數組 nums 的長度。

題目3：3153. 所有數對中數位不同之和

思路

遍歷數組 nums， 對每一位的數字進行計數并保存在數組 cnt 中。

遍歷完數組得到 cnt 后，cnt[i][j] 表示在第 i 位，數字為 j 的數的個數，那么在第 i 位，數字不為 j 的數的個數為 n?cnt[i][j]，其中 n 為數組 nums 的長度。根據乘法原理可以知道，在第 i 位，一共有 cnt[i][j]?(n?cnt[i][j])/2 對數在該位的數字不相同。累加每一位數字不相同的數對數量，即可得到所需要的答案。

代碼

/** @lc app=leetcode.cn id=3153 lang=cpp** [3153] 所有數對中數位不同之和*/// @lc code=start
class Solution
{
public:long long sumDigitDifferences(vector<int> &nums){int n = nums.size();int cnt[9][10];memset(cnt, 0, sizeof(cnt));for (int num : nums){int i = 0;while (num){cnt[i][num % 10]++;i++;num /= 10;}}long long ans = 0LL;for (int i = 0; i < 9; i++)for (int j = 0; j < 10; j++)ans += cnt[i][j] * (n - cnt[i][j]);return ans >> 1;}
};
// @lc code=end

復雜度分析

時間復雜度：O(l*n+l*d)，其中 n 為數組 nums 的長度，l 為數組 nums 中數據的十進制位數，l 的最大值為 9，d 為從 0 到 9 共 10 個數字。

空間復雜度：O(l*d)，其中 l 為數組 nums 中數據的十進制位數，l 的最大值為 9，d 為從 0 到 9 共 10 個數字。

題目4：3154. 到達第 K 級臺階的方案數

思路

記憶化搜索。

定義 dfs(int i, int jump, bool preDown) 表示當前位于臺階 i，已經使用了 jump 次第二種操作，preDown：上一次操作是否為操作一時，到達臺階 k 的方案數。

枚舉當前使用哪個操作：

1. 使用操作一：前提是 i != 0 && preDown == false。使用操作一后，要解決的子問題是 dfs(i - 1, jump, true)，加入返回值中。
2. 使用操作二：要解決的子問題是 dfs(i + (1 << jump), jump + 1, false)，加入返回值中。
3. 此外，如果 i=k，可以把返回值加一。

遞歸邊界：如果 i>k+1，由于操作一不能連續使用，無法到達 k，返回 0。

遞歸入口：dfs(1,0,false)，即答案。

代碼

/** @lc app=leetcode.cn id=3154 lang=cpp** [3154] 到達第 K 級臺階的方案數*/// @lc code=start
class Solution
{
private:unordered_map<long long, int> memo;public:int waysToReachStair(int k){// 當前位于臺階 i，已經使用了 jump 次第二種操作，preDown：上一次操作是否為操作一function<int(int, int, bool)> dfs = [&](int i, int jump, bool preDown) -> int{if (i > k + 1)return 0;long long state = (long long)i << 32 | jump << 1 | preDown;if (memo.contains(state))return memo[state];int res = 0;if (i == k)res++;if (i != 0 && preDown == false){ // 操作一res += dfs(i - 1, jump, true);}res += dfs(i + (1 << jump), jump + 1, false); // 操作二memo[state] = res; // 記憶化return res;};// 從臺階 1 開始，一開始 jump 為 0，前一次操作不為操作二return dfs(1, 0, false);}
};
// @lc code=end

復雜度分析

時間復雜度：O(log²k)。

空間復雜度：O(log²k)。