第 398 场 LeetCode 周赛题解

本文主要是介绍第 398 场 LeetCode 周赛题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A 特殊数组 I

模拟：遍历数组判断是否是一个特殊数组

class Solution {
public:bool isArraySpecial(vector<int>& nums) {int r = 0;while (r + 1 < nums.size() && nums[r + 1] % 2 != nums[r] % 2)r++;return r == nums.size() - 1;}
};

B 特殊数组 II

查表：遍历 $n u m s$ ，将 $n u m s$ 划分为若干个最大的特殊数组，并记录各元素所在的特殊数组，然后遍历 $q u r i es$ ，判断 $from_i$ 和 $to_i$ 是否在同一个特殊数组

class Solution {
public:vector<bool> isArraySpecial(vector<int>& nums,vector<vector<int>>& queries) {int n = nums.size();vector<int> id(n);for (int l = 0, r = 0; l < n; l = ++r) {id[l] = l;//nums[l]所在的特殊数组的左端点为lwhile (r + 1 < n && nums[r + 1] % 2 != nums[r] % 2)id[++r] = l;//nums[++r]所在的特殊数组的左端点为l}vector<bool> res;for (auto& qi : queries)res.push_back(id[qi[0]] == id[qi[1]]);return res;}
};

C 所有数对中数位不同之和

计数：记录每个数位上各数字的出现次数，然后枚举数组中各元素的各个数位

class Solution {
public:using ll = long long;long long sumDigitDifferences(vector<int>& nums) {int n = nums.size();int m = to_string(nums[0]).size();int cnt[m][10]; // cnt[j][v]:数位j上v数字的出现次数memset(cnt, 0, sizeof(cnt));for (auto v : nums) {auto s = to_string(v);for (int j = 0; j < m; j++)cnt[j][s[j] - '0']++;}ll res = 0;for (auto v : nums) {auto sv = to_string(v);for (int j = 0; j < m; j++)res += (ll)(n - cnt[j][sv[j] - '0']);}return res / 2;//题目计数方法中数对是无序的，所以res/2}
};

D 到达第 K 级台阶的方案数

记忆化搜索：需要维护三个状态信息：当前所在台阶 $c u r$ ，上一次操作(如果有)是否是下台阶 $last\_back$ ，当前 $j u m p$ 值。可以将 $cur,last\_back,jump)$ 用一个 long long 类型数表示，从而用哈希表来实习记忆化搜索

class Solution {
public:using ll = long long;ll enc(int cur, int last_back, int jump) {//状态编码 (cur,last_back,jump) -> maskreturn ((ll)cur << 6LL) | (last_back << 5) | jump;}tuple<int, int, int> dec(ll mask) {//状态解码 mask -> (cur,last_back,jump)return {mask >> 6, mask >> 5 & 1, mask & 31};}int waysToReachStair(int k) {unordered_map<ll, ll> cnt;function<ll(ll)> get = [&](ll mask) {//记忆化搜索if (cnt.count(mask))return cnt[mask];auto [cur, last_back, jump] = dec(mask);if (cur > k + 1)return 0LL;if (cur == k)cnt[mask] = 1;cnt[mask] += get(enc(cur + (1LL << (ll)jump), 0, jump + 1));if (last_back == 0)//不能连续下台阶cnt[mask] += get(enc(cur - 1, 1, jump));return cnt[mask];};return get(enc(1, 0, 0));}
};