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

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

image.png

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

展开讨论
共 14 个讨论

第一题 玩筹码

比较奇数位置的筹码多,还是偶数位置的筹码多。
因为奇数位置的筹码可以以 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

欢迎提意见和建议

12

先占坑,详细题解稍晚来:

  • 玩筹码
    题目意思转化一下就是奇数位可以无代价到奇数位,偶数位可以无代价到偶数位,但是奇数位和偶数位到达代价是 1 ,于是统计奇数位和偶数位的筹码数,将少的挪到多的位置就可以了。

  • 最长定差子序列
    遍历数组,每访问到一个数看看前面有没有可以和他构成等差数列的数,同时维护前面的等差数列最长长度。可以用 dict 来保持以每个数结尾的最长等差数列长度,总体时间复杂度为 O(n)O(n)

  • 黄金矿工
    有两种做法,第一种是无脑搜索,注意维护棋盘状态就可以了,这题时限较宽松可过。第二种做法是用状态压缩DP,dp[x,y,s]dp[x,y,s],表示当前在 (x,y)(x,y) 点,状态为 ss 是否可达,状态 ss 是一个 2525 位的二进制数,每一位表示当前格子的黄金是否已经被拿走。这样时间复杂度为 O(n2n)O(n*2^n) ,其中 nn 为黄金点数量。

  • 统计元音字母序列的数目
    其实是一道很简单的题目,不要被hard吓到了。dp[i,0 4]dp[i,0~4] 表示当前在第i位,最后一个字母是 aua-u (对应 040-4 )的可行序列总数,然后按照题目给的限制进行 dp[i+1]dp[i+1] 的转移就可以了。时间复杂度 O(n5)=O(n)O(n*5)=O(n)
    PS: 这道题 nn 可以给到 101810^{18},还存在更好的解法。

5

5213. 玩筹码

原题链接

移动 2 位是无代价的,移动 1 位是有代价的,因此:

  • 奇数位移动到奇数位 或 偶数位移动到偶数位 是无代价移动
  • 偶数位移动到奇数位 或 奇数位移动到偶数位 需要花费代价 1

所以只要统计奇数位的筹码数和偶数位的筹码数,将少的一方移到多的一方即可。

class Solution:
    def minCostToMoveChips(self, chips: List[int]) -> int:
        odd = 0
        even = 0
        
        for chip in chips:
            if chip % 2 == 0:
                even += 1
            else:
                odd += 1
        
        return min(odd, even)

5214. 最长定差子序列

原题链接

把每一个数当前位置能构成的最长定差子序列长度用字典 dp 记录下来,遍历 arr 时,根据 difference 求出在定差子序列中该数的前一个数 pre = a - difference,若 pre 存在 dp 中(已能构成定差子序列),则有 dp[a] = max(dp[a], dp[pre] + 1),否则令 dp[a] = 1

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp = dict()
        for a in arr:
            pre = a - difference
            if pre in dp:
                dp[a] = max(dp.get(a, 0), dp[pre] + 1)
            else:
                dp[a] = 1
        return max([x for _, x in dp.items()])

5215. 黄金矿工

原题链接

DFS 暴力挖矿。对挖过的格子进行标记,走到一个格子后,判断该格子四个方向的格子是否满足要求:

  1. 不超过 grid 边界
  2. 黄金数目不为 0
  3. 没有被挖过

如果满足上述条件就继续 DFS 挖下去。

伪代码大概长这样:

dfs(v) // v 可以是 grid 的一个坑v 上打访问标记
  for u in v 的四个相邻坑位
    if (u 没有越界) and (u 有黄金) and (u 没有被挖过) then
      dfs(i)

具体实现:

class Solution:
    
    ans = 0
    
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        
        n = len(grid)
        m = len(grid[0])
        
        """
        获取方向
        """
        def get_directions(i, j, mark):
            directions = []
            if i - 1 >= 0 and grid[i - 1][j] != 0 and (not mark[i - 1][j]):
                directions.append([i - 1, j])
            if i + 1 < n and grid[i + 1][j] != 0 and (not mark[i + 1][j]):
                directions.append([i + 1, j])
            if j - 1 >= 0 and grid[i][j - 1] != 0 and (not mark[i][j - 1]):
                directions.append([i, j - 1])
            if j + 1 < m and grid[i][j + 1] != 0 and (not mark[i][j + 1]):
                directions.append([i, j + 1])
                
            return directions
        
        """
        DFS
        """
        def dfs(i, j, mark, count):
            # 打上访问标记
            mark[i][j] = True
            # 获得可走方向
            directions = get_directions(i, j, mark)
            # 无路可走时返回
            if len(directions) == 0:
                self.ans = max(self.ans, count)
                return
            # 遍历方向
            for direction in directions:
                dfs(direction[0], direction[1], [x[:] for x in mark], count + grid[direction[0]][direction[1]]) # dfs
                    
        for i in range(n):
            for j in range(m):
                # 任意一个有黄金的单元格出发
                if grid[i][j] != 0:
                    mark = [[False for _ in range(m)] for _ in range(n)]
                    dfs(i, j, mark, grid[i][j])

        return self.ans

5216. 统计元音字母序列的数目

原题链接

长度为 x 的字符串是由长度为 x - 1 的合法字符串,根据其最后一个字母,追加一个符合规则的字母构成的。

因此,如果我们要求长度为 x 的字符串个数,只需要知道长度为 x - 1 的字符串中所有字符串最后一个字母的情况,从 n = 1 开始一直推算到 n = x

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        
        if n == 1:
            return 5
        
        map_dict = {"a": ["e"], "e": ["a", "i"], "i": ["a", "e", "o", "u"], "o": ["i", "u"], "u": ["a"]}
        index = {"a": 0, "e": 1, "i": 2, "o": 3, "u": 4}
        c = {0: "a", 1: "e", 2: "i", 3: "o", 4: "u"}
        
        # aeiou 对应的个数
        pre = [1, 1, 1, 1, 1]
        
        res = 0
        
        for i in range(2, n + 1):
            cur = [0 for _ in range(5)]
            for j in range(len(pre)):
                cur_c = c[j] # 当前字母
                cur_c_count = pre[j] # 当前字母数量
                for map_c in map_dict[cur_c]: # 遍历可以跟随的字母
                    map_c_index = index[map_c]
                    cur[map_c_index] += cur_c_count
            pre = cur
            
        res = sum(cur)
        
        return res % (10**9 + 7)
5

第四题 构造邻接矩阵+矩阵快速幂 应该是蛮有意思的一个方法(离散数学终于派上用场。。

3

第四题矩阵快速幂要注意矩阵运算中取模……

2

前排还是大佬

1

请问第一题的第二个样例肿么理解呀?
为啥不能这样跳呢? 1号位移动到3号位(代价0), 5号位移动到3号位(代价0), 4号位移动到2号位(代价0), 3号位移动到2号位(代价1)
是我理解错了咩, 求大佬指点
tmp.png

请问大佬C语言写超时了,有什么办法没

第二题的题目怎么理解?
[3,0,-3,4,-4,7,6]
3
样例的答案怎么是2,不是4吗?