【力扣周赛】第394场周赛

本文主要是介绍【力扣周赛】第394场周赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.统计特殊字母的数量

题目链接

• 🍎该题涉及的小技巧：🐥
  🐧①大写字母和对应的小写字母低5位都是相等的；
  🐧②大写字母ASCII二进制第 6 位是0，对应的小写字母第 6 位是1；
  

🐧③位运算小技巧：🐥

• 解题思路:
  🐧①将 word 中的字母都取出来各自放入一个大写🔠字母的集合，和一个小写🔡字母的集合；
  
  🐧②再对两个集合求交集就可以求出同时出现大小写字母的个数；
  
  🐧③用到的位运算小技巧：
  (ch >> 5) & 1，表示取出该字母的ASCII第6位，如果是 0 表示大写字母，1 表示小写字母；
  
  1<<(ch&31);，可以将该字母转换成为得到一个唯一的 8个字节32个 比特位数中的一位数字 1，其他的31位都是 0，这样 26个字母每个字母对应的映射都不一样；(例如： 假如 ch 字符是小写字母 c的话，此时1<<(ch&31) )的结果为十进制 8（0000 0000 0000 1000），所以这样看每个字母都有自己对应不同的二进制表示
  
  🐧④mask[0] & mask[1]表示求交集；
  
  🐧⑤集合的大小：__builtin_popcount(s)

• 代码实现

class Solution {
public:int numberOfSpecialChars(string word) {int mask[2] = {0};// 注意：大写字母的ASCII二进制第 6 位是 0，小写字母第 6 位是 1for(auto ch : word){mask[(ch >> 5) & 1] |= 1<<(ch&31);}// 求集合的大小：__builtin_popcount(s)return __builtin_popcount(mask[0] & mask[1]);}
};

2.使矩阵满足条件的最少操作次数

题目链接

• 解题思路:
  🐧①逆向思维：求最少操作的次数，那我们可以反过来取求最多保留多少个数字🔢；🎈
  
  🐧②我们从后往前来求每一列最多保留多少个数字🔢；
  
  🐧③必须记录前一列填的数字（要保证相邻列数字不同）
  
  🐧④注意❗：必须用一个数组记录每一列用某一个数字的时候的结果，并且及时更新；
  

• 解题代码

class Solution {int n, m;
int cnt[1010][15] = {0};
int vis[1010][15] = {0};
int ans = 0;public:int minimumOperations(vector<vector<int>>& grid) {n = grid.size(), m = grid[0].size();memset(vis, -1, sizeof(vis));for (int i = 0; i < m; i ++){for (int j = 0; j < n; j ++){int x = grid[j][i];cnt[i][x] ++;   // 第 i 列中，0 ~ 9 的个数}}//从最后一列开始往前搜索int res = dfs(m - 1, 10);// 注意：我们用了逆向思维，求的是最多保留数据的个数return n * m - res;}// 表示搜索第 i 列中，最多保留的个数，前一列为 jint dfs(int i, int j){// 递归出口if (i < 0)return 0;auto& ans = vis[i][j]; // 注意这里是引用if (ans != -1)return ans;ans = 0;for (int k = 0; k <= 9; k ++){if (k != j){ans = max(ans, dfs(i - 1, k) + cnt[i][k]);}}return ans;}
};

这篇关于【力扣周赛】第394场周赛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---