讨论/题目交流/🏆 第 157 场力扣周赛/
🏆 第 157 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

玩筹码
最长定差子序列
黄金矿工
统计元音字母序列的数目

展开讨论

第一题 玩筹码

比较奇数位置的筹码多,还是偶数位置的筹码多。
因为奇数位置的筹码可以以 0 代价 移动到任意奇数位置,以 1 代价 移动到任意偶数位置,偶数位置的代码也类似。

    int minCostToMoveChips(vector<int>& chips) {
        int cnt[2] = {0, 0};
        for (auto c: chips) ++cnt[c & 1];
        return min(cnt[0], cnt[1]);
    }

第二题 最长定差子序列

dp[i] 代表以 i 为结尾时,子序列能形成的最大长度。
例如,当前 diff2,且当前遍历到了 5,此时 5 最多可以和之前的 3(5-2) 连到一起,
去查找之前以 3 为结尾的最大值 + 1 和 以 5 为结尾的最大值进行比较,然后比较一下即可。

    int longestSubsequence(vector<int>& arr, int diff) {
        int res = 1;
        unordered_map<int, int> has;
        for(auto it : arr) {
            has[it] = max(has[it], has[it - diff] + 1);
            res = max(res, has[it]);
        }
        return res;
    }

第三题 黄金矿工

进阶版的 DFS

class Solution {
public:
    vector<int> dx{1, -1, 0, 0};
    vector<int> dy{0, 0, 1, -1};
    void dfs(vector<vector<int>>& grid, vector<vector<bool>>& used, int &res, int i, int j, int tem) {
        // 搜索到空就停止搜索
        if(grid[i][j] == 0) return ;
        res = max(res, tem += grid[i][j]);
        // 把当前搜索标志置为 true
        used[i][j] = true;
        for(int k=0; k<4; k++) {
        	int x = i + dx[k], y = j + dy[k];
                // 下一个点是否越界以及为空, 以及是否搜索过
        	if(x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size()) continue;
        	if(grid[x][y] == 0 || used[x][y]) continue;
        	dfs(grid, used, res, x, y, tem);
        } // 当前点的深度搜索都已完成, 再把标志清除, 不妨碍下次搜索
        used[i][j] = false;
    }
    int getMaximumGold(vector<vector<int>>& grid) {
    	int m = grid.size(), n = grid[0].size(), res = 0;
        vector<vector<bool>> used(m, vector<bool>(n, false));
        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++)
                if(grid[i][j] != 0)
                    dfs(grid, used, res, i, j, 0);
        return res;
    }
};

第四题 统计元音字母序列的数目

求出来对应的次序然后直接计算就行
根据题意可画出对应的转移图, 然后根据对应关系进行转移即可

image.png

    int countVowelPermutation(int n) {
        long long a = 1, e = 1, i = 1, o = 1, u = 1;
        long long res = 0, mod = 1e9+7;
        for(int j=1; j<n; j++) {
            long long a1, e1, i1, o1, u1;
            a1 = (e + i + u) % mod;
            e1 = (a + i) % mod;
            i1 = (e + o) % mod;
            o1 = i;
            u1 = (i + o) % mod;
            a = a1, e = e1, i = i1, o = o1, u = u1;
        }
        res = (a + e + i + o + u) % mod;
        return res;
    }

这个题数据量再大一些就应该采用 矩阵来做运算,并可以通过矩阵快速幂来加速运算
下面是通过矩阵进行运算的算法:

    int countVowelPermutation(int n) {
        // 矩阵的公式
        int mode = 1e9 + 7;
        vector<vector<int>> grid{{0,1,0,0,0}, {1,0,1,0,0}, {1,1,0,1,1}, {0,0,1,0,1}, {1,0,0,0,0} };
        vector<long long> arr(5, 1);
        for(int i=1; i<n; i++) {
            vector<long long> tem(5, 0);
            for(int j=0; j<5; j++)
                for(int k=0; k<5; k++)
                    tem[j] = (tem[j] + grid[j][k] * arr[k]) % mode;
            swap(tem, arr);
        }
        for(int i=1; i<5; i++) arr[i] += arr[i-1];
        return arr.back() % mode;
    }

矩阵快速幂的代码比较长, 写到题解里面了, 里面的矩阵相乘 multiply 以及矩阵幂运算 pow 函数是封装好的
碰到类似的问题, 可以直接套用
矩阵快速幂的解法

27
展开全部 14 讨论