1. 圆形赛道上经过次数最多的扇区

给出一个圆形赛道,共被分为 n 段区域。再给出一个数组 rounds ,代表马拉松的各个阶段。n|rounds| 数据范围都为 1e2

例如 rounds=[1,3,1,2] 代表:赛道共分为 4 段,赛程共分为 3 段,第一段是 [1,3] , 第二段是 [4,1] ,第三段是 [2,2]

以数组形式返回经过次数最多扇区,并按升序排列。

题解

暴力统计每段赛道区域被访问的次数。

class Solution {
public:
    vector<int> mostVisited(int n, vector<int>& rounds) {
        int cnt[105]; memset(cnt, 0, sizeof(cnt));
        int m = rounds.size();
        
        // 将数据由 [1,n] 调整至 [0, n-1] 方便取模
        for(int i=0; i<m; i++) rounds[i]--;

        // 统计赛道每个阶段被访问的次数
        for(int i=0; i<m-1; i++) {
            int x = rounds[i], y = rounds[i+1];
            if(y < x) y += n; // 处理 y < x 即跑到第二圈的开始这种情况 
            for(int j=x; j<=y; j++) cnt[j % n]++; // 统计
            rounds[i+1] = (rounds[i+1] + 1) % n; // 下一段的开头为当前结尾的下一段
        }

        // 求访问次数最大值
        int mx = 0;
        for(int i=0; i<n; i++) mx = max(mx, cnt[i]);

        // 统计访问次数达到最大值的区域
        vector<int> ans;
        for(int i=0; i<n; i++) if(cnt[i] == mx) ans.push_back(i+1);
        
        return ans;
    }
};

2. 你可以获得的最大硬币数目

3n 堆硬币,每次可以拿三堆。三堆中,数量最多和最少的分给 Alice 和 Bob ,剩下的一堆留给自己。

数据范围, n1e5 。求自己最多能获得的硬币数目。

题解

简单贪心。将 3n 堆硬币排序后,应该是前 n 堆分给 Bob, 后 2n 堆分给Alice和自己。并且在Alice必须每一次都拿到比我多的一堆的前提下,为了保证最优,应该是我和 Alice 间隔着从排好序的 2n 堆中拿。

class Solution {
public:
    int maxCoins(vector<int>& piles) {
        sort(piles.begin(), piles.end());
        int n = piles.size(), ans = 0;
        for(int i=n/3; i<n; i+=2) ans += piles[i];
        return ans;
    }
};

3. 查找大小为 M 的最新分组

给出一个数组 arr ,设其长度为 n 。初始化一个长度为 n 的二进制串 s[1...n] ,每一位 s[i] 都为 0

接下来共 n 个步骤,第 i 个步骤将 s[arr[i]] 置为 1

现在给出一个数 m ,求二进制串 s 中含有长度恰好为 m 的纯 1 串的最后一个步骤。

题解

并查集。是否存在纯 1 串的长度为 m ,本质就是求 arr 中是否存在连续数字的长度为 m

const int MAXN = 1e5 + 5;
int fa[MAXN]; 
bool vis[MAXN];
int fa_cnt[MAXN]; // fa_cnt[i] = 以 i 为父节点的连续数字串长度
int check[MAXN]; // check[i] = 长度为 i 的连续数字串的个数

class Solution {
public:
    int find(int x) {
        if(fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }
    void merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if(fx == fy) return;
        
        // 将合并之前 check 中记录的两个长度删除
        check[fa_cnt[fx]]--; 
        check[fa_cnt[fy]]--;
        
        // 合并
        fa[fy] = fx;

        // 计算合并之后的长度,并添加至 check 中
        fa_cnt[fx] += fa_cnt[fy];
        check[fa_cnt[fx]]++;
    }
    int findLatestStep(vector<int>& arr, int m) {
        int n = arr.size(), ans = -1;
        for(int i=1; i<=n; i++) vis[i] = false, fa[i] = i, fa_cnt[i] = 0, check[i] = 0; // 初始化
        
        for(int i=0; i<n; i++) {
            vis[arr[i]] = true;
            fa_cnt[arr[i]] = 1; check[1]++; // 将当前数字的长度初始化为 1
            if(arr[i] > 1 && vis[arr[i]-1]) merge(arr[i], arr[i]-1); // 与 arr[i] - 1 合并
            if(arr[i] < n && vis[arr[i]+1]) merge(arr[i], arr[i]+1); // 与 arr[i] + 1 合并   
            if(check[m] != 0) ans = i + 1; // 如果存在长度为 m 的连续串,记录下来
        }
        return ans;
    }
};

4. 石子游戏 V

给出一个 stoneValue 数组代表一行石子,每一次将该行石子分为左右两部分(不可空)。 |stoneValue| 范围为 1e5

每一次分割后, Alice 将会得到累加和更少的那一部分,并将和加入得分。如果两部分的和一样,Alice任取一部分。如果只剩一个石子,游戏结束。

求 Alice 能够获得的最大得分。

题解

比较裸的区间 dp , dp[i][j] 表示 [i,j] 区间内 Alice 能够获得的最大得分。

int dp[505][505]; 
class Solution {
public:
    // 记忆化搜索
    int dfs(int l, int r, vector<int>& stoneValue) {
        if(l == r) return 0; // 只剩一个石子,游戏结束

        if(dp[l][r] != -1) return dp[l][r]; // 记忆化

        int tot = 0; // tot 表示 [l, r] 的石子总和
        for(int i=l; i<=r; i++) tot += stoneValue[i];

        int cur = 0, mx = 0;
        for(int k=l; k<r; k++) { // 枚举分割点
            cur += stoneValue[k];

            int now = 0;
            if(cur < tot - cur) now = cur + dfs(l, k, stoneValue); // 如果 [l, k] 比较少
            else if(cur > tot - cur) now = tot - cur + dfs(k+1, r, stoneValue); // 如果 [k+1, r] 比较少
            else now = cur + max(dfs(l, k, stoneValue), dfs(k+1, r, stoneValue)); // 如果两边一样多

            mx = max(mx, now);
        }
        return dp[l][r] = mx;
    }

    int stoneGameV(vector<int>& stoneValue) {
        int n = stoneValue.size();
        for(int i=0; i<n; i++) for(int j=0; j<n; j++) dp[i][j] = -1;
        return dfs(0, n-1, stoneValue);
    }
};
最后修改:2020 年 08 月 23 日 03 : 32 PM
如果觉得我的文章对你有用,请随意赞赏