【力扣周赛】第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 位是 1
        for(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 列中，最多保留的个数，前一列为 j
    int 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;
    }
};