Leetcode第 414 场周赛题解

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

给你一个字符串 date，它的格式为 yyyy-mm-dd，表示一个公历日期。

date 可以重写为二进制表示，只需要将年、月、日分别转换为对应的二进制表示（不带前导零）并遵循 year-month-day 的格式。

返回 date 的 二进制 表示。

解法：STL一步到胃

class Solution {
public:
    string convertDateToBinary(string date) {
        // 提取年、月、日
        string year_str = date.substr(0, 4);
        string month_str = date.substr(5, 2);
        string day_str = date.substr(8, 2);
        
        // 将字符串转换为整数
        int year = stoi(year_str);
        int month = stoi(month_str);
        int day = stoi(day_str);
        
        // 将整数转换为二进制字符串
        string year_bin = bitset<12>(year).to_string(); // 年份最多12位二进制
        string month_bin = bitset<4>(month).to_string(); // 月份最多4位二进制
        string day_bin = bitset<5>(day).to_string(); // 日期最多5位二进制
        
        // 去除前导零
        year_bin = year_bin.substr(year_bin.find('1'));
        month_bin = month_bin.substr(month_bin.find('1'));
        day_bin = day_bin.substr(day_bin.find('1'));
        
        // 拼接结果
        return year_bin + "-" + month_bin + "-" + day_bin;
    }
};

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

给你一个整数数组 start 和一个整数 d，代表 n 个区间 [start[i], start[i] + d]。

你需要选择 n 个整数，其中第 i 个整数必须属于第 i 个区间。所选整数的 得分 定义为所选整数两两之间的 最小 绝对差。

返回所选整数的 最大可能得分 。

解法：二分答案

先对整数数组进行排序，这样最小绝对差值一定是由相邻区间的所选整数来提供的

• 因为区间相邻越远，差值肯定会更大

接下来在【0 ~ \(2 * 10^9\)】的区间内二分最小绝对差值

• check函数从前往后遍历整数数组，判断相邻区间是否能够满足该差值

class Solution {
public:
    using ll = long long;
    int maxPossibleScore(vector<int>& start, int d) {
        sort(start.begin(), start.end());
        
        auto check = [&](ll x) -> bool {
            //pre记录上一个区间所取整数，从start[0]开始最优
            ll pre = start[0];
            for (int i = 1; i < start.size(); i++) {
                if (start[i] + d - pre < x) {
                    return false;
                }
                pre = max((ll)start[i], pre + x);
            }
            return true;
        };
        
		ll l = 0, r = 2 * 1e9;
        while (l < r) {
            ll mid = l + r + 1 >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};

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

给你一个长度为 n 的整数数组 nums 。

你的目标是从下标 0 出发，到达下标 n - 1 处。每次你只能移动到 更大 的下标处。

从下标 i 跳到下标 j 的得分为 (j - i) * nums[i] 。

请你返回你到达最后一个下标处能得到的 最大总得分 。

解法：

当身处nums[i]时只需要跳到下一个比nums[i]大的位置处即可

只需要维护一个前缀最大元素的集合，最后将【最后一个元素之外】的所有元素相加即可

class Solution {
public:
    long long findMaximumScore(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 0);
        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i] = max(dp[i - 1], nums[i]);
        }
        long long res = 0;
        for (int i = 0; i < n - 1; i++) {
            res += dp[i];
        }
        return res;
    }
};

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

给你一个 50 x 50 的国际象棋棋盘，棋盘上有 一个 马和一些兵。给你两个整数 kx 和 ky ，其中 (kx, ky) 表示马所在的位置，同时还有一个二维数组 positions ，其中 positions[i] = [xi, yi] 表示第 i 个兵在棋盘上的位置。

Alice 和 Bob 玩一个回合制游戏，Alice 先手。玩家的一次操作中，可以执行以下操作：

• 玩家选择一个仍然在棋盘上的兵，然后移动马，通过 最少 的 步数 吃掉这个兵。注意 ，玩家可以选择 任意 一个兵，不一定 要选择从马的位置出发 最少 移动步数的兵。
• 在马吃兵的过程中，马 可能 会经过一些其他兵的位置，但这些兵 不会 被吃掉。只有 选中的兵在这个回合中被吃掉。

Alice 的目标是 最大化 两名玩家的 总 移动次数，直到棋盘上不再存在兵，而 Bob 的目标是 最小化 总移动次数。

假设两名玩家都采用 最优 策略，请你返回 Alice 可以达到的 最大 总移动次数。

在一次 移动 中，如下图所示，马有 8 个可以移动到的位置，每个移动位置都是沿着坐标轴的一个方向前进 2 格，然后沿着垂直的方向前进 1 格。

解法：bfs 状压DP

我们可以将kx，ky也看成一个有一个兵，加入positions集合中（作为初始状态）

BFS：

先对positions中的每个兵都进行一次bfs，这样我们就可以快速得到图中每个点到任何一个兵的最短距离

状态转移：

dp[mask][i]：当前马在第i个兵的位置，已经被吃了的兵的集合为mask，继续游戏，两名玩家的总移动次数的最大值

• mask：已经被吃掉的兵的集合
• i：当前马在第i个兵的位置

我们假设：

• next = mask | (1 << j)（也就是选择吃j的之后的集合）

• x = positions[j][0] y = positions[j][1]，也就是第j个兵的位置

• distance[i][x][y]：从[x, y]到第i个兵的最短距离

如果当前是Alice操作，则：

\[dp[mask][i] = max\{dp[next][j]\}\ +\ distance[i][x][y] \]

如果当前是Bob操作，则：

\[dp[mask][i] = min\{dp[next][j]\}\ +\ distance[i][x][y] \]

判断当前是谁操作：

通过__builtin_popcount(mask)，得到当前mask中有几个1（也就是现在吃了几个兵）

• 如果当前已经吃了奇数个兵：那么下一步由Alice操作
• 如果当前已经吃了偶数个兵：那么下一步由Bob操作

记住，因为我们将{kx, ky}也看成了一个兵，作为初始状态，最初已经被吃了

递归入口：dp[1 << n - 1][n - 1]

• 因为一开始positions.push_back({kx, ky})，所以这里相当于从初始位置开始

class Solution {
public:
    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {
        //先将[kx, ky]加入集合中
        positions.push_back({kx, ky});
        int n = positions.size();
        vector<vector<vector<int>>> d(16, vector<vector<int>>(50, vector<int>(50, -1)));
        int dx[8] = {1, -1, 1, -1, 2, -2, 2, -2}, dy[8] = {2, -2, -2, 2, 1, -1, -1, 1};
        auto bfs = [&](pair<int, int> st, int idx) {
            queue<pair<int, int>> q;
            q.push({st.first, st.second});
            d[idx][st.first][st.second] = 0;
            while (q.size()) {
                auto t = q.front(); q.pop();
                int a = t.first, b = t.second;
                for (int i = 0; i < 8; i++) {
                    int aa = a + dx[i], bb = b + dy[i];
                    if (aa >= 0 && aa < 50 && bb >= 0 && bb < 50 && d[idx][aa][bb] == -1) {
                        d[idx][aa][bb] = d[idx][a][b] + 1;
                        q.push({aa, bb});
                    }
                }
            }
        };
        //对每个兵都bfs一遍
        for (int i = 0; i < n; i ++) {
            bfs({positions[i][0], positions[i][1]}, i);
        }
        //接下来进行状压DP
        vector<vector<int>> f(1 << n, vector<int>(n, -1));
        function<int(int, int)> dp = [&](int msk, int lst) -> int {
            if (msk == (1 << n) - 1) return 0;
            if (f[msk][lst] >= 0) return f[msk][lst];
            //cnt：已经吃了多少个兵
            int cnt = __builtin_popcount(msk);
            int res = (cnt & 1 ? -1e9 : 1e9);
            for (int i = 0; i < n; i++) {
                if ((msk >> i & 1 ^ 1)) {//如果当前第i个兵还没有被吃
                    int t = dp(msk | (1 << i), i) + d[lst][positions[i][0]][positions[i][1]];
                    if (cnt & 1) res = max(res, t);//Alice操作
                    else res = min(res, t);//Bob操作
                }
            }
            f[msk][lst] = res;
            return res;
        };
        return dp(1 << (n - 1), n - 1);
    }
};