第 2 场双周赛
A.
模拟
class Solution {
public:
int sumOfDigits(vector<int>& nums) {
sort(nums.begin(), nums.end());
int t = nums.front();
int sum = 0;
while(t) {
sum += t % 10;
t /= 10;
}
return !(sum & 1);
}
};
B.
模拟，排序/优先队列。
可以做到
O
(
n
)
O(n)
O(n)，及时更新前五大数即可。
class Solution {
public:
vector<vector<int>> highFive(vector<vector<int>>& items) {
vector<vector<int>> res;
vector<vector<int>> temp(1001, vector<int>());
for(auto u : items)
temp[u[0]].push_back(u[1]);
for(int i = 1; i <= 1000; ++i) {
if(!temp[i].empty()) {
sort(temp[i].begin(), temp[i].end(), greater<int>());
int sum = 0;
for(int j = 0; j < 5; ++j)
sum += temp[i][j];
res.push_back({i, sum / 5});
}
}
return res;
}
};
C.
先对字符串进行展开成数组，然后dfs枚举即可
class Solution {
public:
vector<string> expand(string s) {
vector<vector<char>> vec;
for(int i = 0; i < s.size(); ++i) {
if(s[i] == '{') {
vector<char> temp;
int j = i + 1;
while(j < s.size() && s[j] != '}') {
if(isalpha(s[j])) {
temp.push_back(s[j]);
}
j += 1;
}
sort(temp.begin(), temp.end());
vec.push_back(temp);
i = j - 1;
} else {
if(isalpha(s[i])) vec.push_back({s[i]});
}
}
res.clear();
cur = "";
dfs(0, vec);
return res;
}
private:
vector<string> res;
string cur;
void dfs(int u, vector<vector<char>>& vec) {
if(u == vec.size()) {
res.push_back(cur);
return ;
}
for(auto v : vec[u]) {
cur += v;
dfs(u + 1, vec);
cur.pop_back();
}
}
};
D.
先数位
d
p
dp
dp求出来所有不含
2
、
3
、
4
、
5
、
7
2、3、4、5、7
2、3、4、5、7的数
然后考虑翻转180°后相同的情况，将这些数减去：
-
1
、
0
、
8
1、0、8
1、0、8翻转后相同
- 对于处理回文位置上的数，如果一个为
6
6
6，一个为
9
9
9，翻转后仍然相同。例如：
69
→
69
69→69
69→69，
609
→
609
609→609
609→609
- 这里需要注意
0
0
0不能放首位，否则翻转后必然相同与原数值不同。
- 同时
6
6
6和
9
9
9不能放到奇长度回文数的中间，否则翻转后必然与原数值相同。
- 这块可以直接暴搜，因为考虑到长度最多为
10
10
10，枚举回文只需要枚举到一半，那么
10
×
5
5
=
31250
10\times 5^5=31250
10×55=31250，可以通过。
class Solution {
public:
int confusingNumberII(int n) {
int res = dp(n);
string str = to_string(n);
int m = str.size();
for(int i = 1; i <= m; ++i) {
res -= dfs2(1, i, n);
}
return res;
}
private:
int f[40];
int digit[40];
int dp(int x) {
if(x == 0) return 0;
memset(f, -1, sizeof f);
int g = 0;
while(x) digit[++g] = x % 10, x /= 10;
return dfs1(false, true, g);
}
// 不含2,3,4,5,7的数的个数
int dfs1(bool lead, bool limit, int dep) {
if(dep == 0) return lead ? 1 : 0;
if(lead && !limit && ~f[dep]) return f[dep];
int last = limit ? digit[dep] : 9;
int res = 0;
for(int i = 0; i <= last; ++i)
if(i != 2 && i != 3 && i != 4 && i != 5 && i != 7)
res += dfs1(lead | i, limit && i == digit[dep], dep - 1);
if(lead && !limit) f[dep] = res;
return res;
}
// 计算不同长度的不含1,0,8构成的回文数
int nums[40];
int dfs2(int u, int len, int n) {
if(u * 2 - 1 > len) {
long long sum = 0;
for(int i = 1; i <= len; ++i)
sum = sum * 10 + nums[i];
return sum <= n;
}
int ans = 0;
nums[u] = nums[len - u + 1] = 1;
ans += dfs2(u + 1, len, n);
nums[u] = nums[len - u + 1] = 8;
ans += dfs2(u + 1, len, n);
if(u > 1) {
nums[u] = nums[len - u + 1] = 0;
ans += dfs2(u + 1, len, n);
}
if(u * 2 - 1 != len) {
nums[u] = 6, nums[len - u + 1] = 9;
ans += dfs2(u + 1, len, n);
nums[u] = 9, nums[len - u + 1] = 6;
ans += dfs2(u + 1, len, n);
}
return ans;
}
};
