题目列表
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 long
- for(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 为结尾的最大总得分,dp = max(dp[k]+(i-k)*nums[k]),然后取dp中的最大值返回,时间复杂度为O(n^2),显然是过不了的,而且我们也无法优化,如何做?当我们dp做不出的时候,我们可以取想想贪婪。
那么如何贪婪呢?我们来观察这个式子 (j - i) * nums,我们可以从柱状图的方式去思考这个式子
(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[i]); // 取前缀最大值 加入 ans
- ans += 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;
- }
- };
复制代码 免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。 |