LeetCode --- 414周赛
题目列表3280. 将日期转换为二进制表现
3281. 范围内整数的最大得分
3282. 到达数组末了的最大得分
3283. 吃掉所有兵需要的最多移动次数
一、将日期转换成二进制表现
https://i-blog.csdnimg.cn/direct/9e8954583d08448ea514c627280b2ff9.png
题目本质就是将数字转成二进制字符串，可以类比将十进制数字的每一位拆开拼成字符串，直接模拟即可，代码如下
class Solution {
string get(string s){
int x = stoi(s);
string ans;
while(x){
ans += (x & 1) + '0';
x >>= 1;
}
reverse(ans.begin(),ans.end());
return ans;
}
public:
string convertDateToBinary(string date) {
// int pos1 = date.find('-');
// int pos2 = date.rfind('-');
// return get(date.substr(0, pos1)) + '-'
// + get(date.substr(pos1+1,pos2-pos1-1)) + '-'
// + get(date.substr(pos2+1));
// 当然我们也可以直接观察字符串的格式，对字符串进行切割
return get(date.substr(0, 4)) + '-'
+ get(date.substr(5, 2)) + '-'
+ get(date.substr(8));
}
}; 二、范围内整数的最大得分
https://i-blog.csdnimg.cn/direct/ee12befe6ba243b6811752c794ea601b.png
看到最大最小，就要想到二分，然后我们来判断这题能否用二分来写，即判断是否具有单调性。(当然不是所有的最大最小题都能用二分来解决，只是二分对于大部门的这类题目有奇效)
得分越大 => 相邻两个数之间的距离就越远，而范围是固定的，则越难找到满足要求的整数。满足单调性，可以二分，接下来，我们只要考虑 check 函数如何写，即判断一个得分是否能有正当的方案实现 --- 我们可以贪婪的去考虑每一个整数的选取：对于每一个区间，我们尽可能的去区间的左边选数，给背面的区间留下尽可能大的范围去举行选择，看是否每一个区间都能选择出一个数，代码如下
class Solution {
public:
int maxPossibleScore(vector<int>& start, int d) {
int n = start.size();
ranges::sort(start);
auto check = [&](int k)->bool{
long long pre = start; // 注意：pre可能会超int范围，要用long long
for(int i = 1; i < n; i++){
if(pre + k <= start)
pre = start;
else if(pre + k <= start + d)
pre += k;
else
return false;
}
return true;
};
int l = 0, r = (start.back() + d - start) / (n - 1) + 1;
while(l <= r){
int mid = l + (r - l)/2;
if(check(mid)) l = mid + 1;
else r = mid - 1;
}
return r;
}
}; 三、到达数组末了的最大得分
https://i-blog.csdnimg.cn/direct/672d7f37450e4b21a9aaad74e81a39bc.png
这题很容易让人想到动态规划，状态界说为 dp 以 i 为结尾的最大总得分，dp = max(dp+(i-k)*nums)，然后取dp中的最大值返回，时间复杂度为O(n^2)，显然是过不了的，而且我们也无法优化，如何做？当我们dp做不出的时候，我们可以取想想贪婪。
那么如何贪婪呢？我们来观察这个式子 (j - i) * nums，我们可以从柱状图的方式去思考这个式子
https://i-blog.csdnimg.cn/direct/f3a8e30b96f14e38b6d40f69b723d4cd.png
(j - i) * nums 的本质就是 长 * 宽，即让我们选择尽可能大的nums作为矩阵的边长，让单个矩阵的面积最大，从而让面积之和最大。代码如下
class Solution {
using LL = long long;
public:
long long findMaximumScore(vector<int>& nums) {
int n = nums.size();
LL ans = 0;
int mx = 0;
for(int i = 0; i < n - 1; i++){
mx = max(mx, nums); // 取前缀最大值 加入 ans
ans += mx;
}
return ans;
}
}; 四、吃掉所有兵需要的最多移动步数
https://i-blog.csdnimg.cn/direct/861057170f844d65b9c935b5eebfc23f.png
思路：首先，我们要预处置处罚得到马在恣意位置到达每个兵的最小步数，这里我们也可以反向考虑，假设马在兵的位置上时，到达恣意位置的最小步数，可以用bfs解决，然后我们就能dfs暴力的枚举Alice和Bob吃哪一个兵能使得个自的策略最优，代码如下
class Solution {
const int dir={-2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1};
public:
int maxMoves(int kx, int ky, vector<vector<int>>& positions) {
int n = positions.size();
int f;
memset(f, -1, sizeof(f));
for(int i = 0; i < n; i++){
int x0 = positions, y0 = positions;
queue<pair<int,int>> q;
q.emplace(x0, y0);
f = 0;
while(q.size()){
auto = q.front(); q.pop();
// cout << x << " " << y << endl;
for(int j = 0; j < 8; j++){
int dx = x + dir;
int dy = y + dir;
if(dx < 0 || dx >= 50 || dy < 0 || dy >= 50 || f >= 0)
continue;
f = f + 1;
q.emplace(dx, dy);
}
}
}
int memo;
memset(memo, -1, sizeof(memo));
function<int(int,int)> dfs = [&](int i, int mask)->int{
if(mask == (1 << n) - 1) return 0;
if(memo != -1) return memo;
int cnt0 = __builtin_popcount(mask);
int res = cnt0 & 1 ? INT_MAX : 0;
int x0 = positions, y0 = positions;
for(int j = 0; j < n; j++){
if(mask >> j & 1) continue;
int x = positions, y = positions;
if(cnt0 & 1){
res = min(res, dfs(j, mask | 1 << j) + f);
}else{
res = max(res, dfs(j, mask | 1 << j) + f);
}
}
return memo = res;
};
int ans = 0;
for(int i = 0; i < n; i++){
ans = max(ans, dfs(i, 1 << i) + f);
}
return ans;
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]