蔚来的题，偏思维，有点意思！
蔚来汽车联名力扣周赛的题目涉及的算法都很常见，但是都带了一点思维，作为头脑风暴是个不错的选择。
设计知识点：模拟、前缀和、双指针、贪心
5963. 反转两次的数字
给定一个正整数
，把它翻转两次，判断是否还等于
，每次反转要去除前导零
题解
可以直接模拟
//cpp 11
class Solution {
public:
int rever(int num) {
string s;
int x = num;
while (x) {
s += x % 10 + '0'; x /= 10;
}
const char* str= s.c_str();
return atoi(str);
}
bool isSameAfterReversals(int num) {
return num == rever(rever(num));
}
};
另一种办法，只要尾巴有
，反转的时候就会丢失，因此判断是否是
的倍数即可，特判一下
// cpp
class Solution {
public:
bool isSameAfterReversals(int num) {
return num == 0 || num % 10 != 0;
}
};
5964. 执行所有后缀指令
给定一个网格，给定一个指令字符串，机器人按照指令行动，如果越界或者指令结束，机器人停止行动
现在机器人根据指令字符串的每一个后缀指令行动，计算机器人停止时执行的指令个数
题解
直接模拟，暴力梭哈
// cpp11
class Solution {
public:
vector<int> executeInstructions(int n, vector<int>& st, string s) {
vector<int> ans;
for (int i = 0; i < s.length(); ++i) {
int cnt = 0;
int x = st[0], y = st[1];
for (int j = i; j < s.length(); ++j) {
if (s[j] == 'L') y--;
else if (s[j] == 'R') y++;
else if (s[j] == 'U') x--;
else if (s[j] == 'D') x++;
if (x >= 0 && x < n && y >= 0 && y < n) cnt++;
else break;
}
ans.push_back(cnt);
}
return ans;
}
};
5965. 相同元素的间隔之和
给定一个数组
，对于元素
，我们定义他们的距离为
现在对每个位置
，我们先找出所有与
相等的元素，然后计算他们到
的距离之和
数据规定
，其中
为数组
的长度
题解
比赛的时候想了个推式子的方法，思维量比较大
可以用哈希表划分等价类，以值为代表元，为每个集合维护一个
考虑子问题，给定一个下标数组
，如何计算距离之和
可以先利用差分数组
计算出两两之间的距离
对于每个位置
，考虑距离出现的次数，于是可以列出如下式子
考虑到
是
的前缀和，我们再用
维护
的前缀和，于是可以化简为
于是可以
计算每个位置的距离和，总的时间复杂度为
// cpp11
class Solution {
public:
vector<long long> getDistances(vector<int>& a) {
typedef long long LL;
map<LL, vector<int>> mp;
for (int i = 0; i < a.size(); ++i) {
LL key = a[i];
mp[key].push_back(i);
}
vector<LL> ans(a.size());
for (auto& i: mp) {
auto vec = i.second;
int n = vec.size();
vector<LL> dif(n), pre(n);
dif[0] = vec[0];
pre[0] = 0;
for (int i = 1; i < n; ++i) {
dif[i] = vec[i] - vec[i - 1];
}
for (int i = 1; i < n; ++i) {
pre[i] = 1LL * i * dif[i] + pre[i - 1];
}
for (int i = 0; i < n; ++i) {
ans[vec[i]] = 2LL * pre[i] - pre[n - 1] + 1LL * n * (vec[n - 1] - vec[i]);
}
}
return ans;
}
};
5966. 还原原数组
从前 alice 有一个数组 a，她任取了一个正整数 k
她对于每一个位置 i，都构造出了 a[i] - k, a[i] + k 两个元素，并放入了 l, h 数组的对应位置
现在 l, h 数组被合并成了一个新数组 arr，并随机做了一个排列，之前的数组 a，正整数 k 也消失了，希望你可以帮忙还原出原数组 a
数据规定
，其中
为数组
的长度
题解
将
排序，那么
一定是
我们从
枚举
中所有位置，并判断该位置成为
的可行性
不妨设
，如果已经有
满足
，那么之后满足
的
一定满足
，这是由
的单调性保证的
所以可以用两个单调指针去扫描
，维护成立的
个数，根据个数是否等于
来判断可行性
时间复杂度
// cpp11
class Solution {
public:
vector<int> recoverArray(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<int> ans;
for (int i = 1; i < n; ++i) {
int dif = nums[i] - nums[0]; // 可能的 dif
if (dif == 0 || dif % 2) continue; // dif 是正偶数
int l = 0, r = 1; // 双指针扫描
vector<int> vis(n);
while (r < n) {
while (l < r && vis[l]) l++; // 跳过重复的元素
while (r < n && nums[r] != nums[l] + dif) r++; // 右指针向右拓展
if (r == n) break;
// cout << l << ' ' << r << ' ' << dif << endl;
ans.push_back((nums[r] + nums[l]) / 2);
vis[r++] = true, vis[l++] = true;
}
if (ans.size() != n / 2) ans.clear();
else break;
}
return ans;
}
};