当前位置：首页 > news >正文

LeetCode --- 414周赛

news 来源：原创 2024/9/18 17:37:34

题目列表

3280. 将日期转换为二进制表示

3281. 范围内整数的最大得分

3282. 到达数组末尾的最大得分

3283. 吃掉所有兵需要的最多移动次数

一、将日期转换成二进制表示

题目本质就是将数字转成二进制字符串，可以类比将十进制数字的每一位拆开拼成字符串，直接模拟即可，代码如下

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));}
};

二、范围内整数的最大得分

看到最大最小，就要想到二分，然后我们来判断这题能否用二分来写，即判断是否具有单调性。(当然不是所有的最大最小题都能用二分来解决，只是二分对于大部分的这类题目有奇效)

得分越大 => 相邻两个数之间的距离就越远，而范围是固定的，则越难找到满足要求的整数。满足单调性，可以二分，接下来，我们只要考虑 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[0]; // 注意：pre可能会超int范围，要用long longfor(int i = 1; i < n; i++){if(pre + k <= start[i])pre = start[i];else if(pre + k <= start[i] + d)pre += k;else return false;}return true;};int l = 0, r = (start.back() + d - start[0]) / (n - 1) + 1;while(l <= r){int mid = l + (r - l)/2;if(check(mid)) l = mid + 1;else r = mid - 1;}return r;}
};

三、到达数组末尾的最大得分

这题很容易让人想到动态规划，状态定义为 dp[i] 以 i 为结尾的最大总得分，dp[i] = max(dp[k]+(i-k)*nums[k])，然后取dp中的最大值返回，时间复杂度为O(n^2)，显然是过不了的，而且我们也无法优化，如何做？当我们dp做不出的时候，我们可以取想想贪心。

那么如何贪心呢？我们来观察这个式子 (j - i) * nums[i]，我们可以从柱状图的方式去思考这个式子

(j - i) * nums[i] 的本质就是长 * 宽，即让我们选择尽可能大的nums[i]作为矩阵的边长，让单个矩阵的面积最大，从而让面积之和最大。代码如下

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[i]); // 取前缀最大值 加入 ansans += mx;}return ans;}
};

四、吃掉所有兵需要的最多移动步数

思路：首先，我们要预处理得到马在任意位置到达每个兵的最小步数，这里我们也可以反向考虑，假设马在兵的位置上时，到达任意位置的最小步数，可以用bfs解决，然后我们就能dfs暴力的枚举Alice和Bob吃哪一个兵能使得个自的策略最优，代码如下

class Solution {const int dir[8][2]={-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[n][50][50];memset(f, -1, sizeof(f));for(int i = 0; i < n; i++){int x0 = positions[i][0], y0 = positions[i][1];queue<pair<int,int>> q;q.emplace(x0, y0);f[i][x0][y0] = 0;while(q.size()){auto [x, y] = q.front(); q.pop(); // cout << x << " " << y << endl;for(int j = 0; j < 8; j++){int dx = x + dir[j][0];int dy = y + dir[j][1];if(dx < 0 || dx >= 50 || dy < 0 || dy >= 50 || f[i][dx][dy] >= 0)continue;f[i][dx][dy] = f[i][x][y] + 1;q.emplace(dx, dy);}}}int memo[n][1<<n];memset(memo, -1, sizeof(memo));function<int(int,int)> dfs = [&](int i, int mask)->int{if(mask == (1 << n) - 1) return 0;if(memo[i][mask] != -1) return memo[i][mask];int cnt0 = __builtin_popcount(mask);int res = cnt0 & 1 ? INT_MAX : 0;int x0 = positions[i][0], y0 = positions[i][1];for(int j = 0; j < n; j++){if(mask >> j & 1) continue;    int x = positions[i][0], y = positions[i][1];if(cnt0 & 1){res = min(res, dfs(j, mask | 1 << j) + f[j][x][y]);}else{res = max(res, dfs(j, mask | 1 << j) + f[j][x][y]);}}return memo[i][mask] = res;};int ans = 0;for(int i = 0; i < n; i++){ans = max(ans, dfs(i, 1 << i) + f[i][kx][ky]);}return ans;}
};