键盘行LeetCode（打表 + 位运算） /水博客

写LeetCode遇到一个简单题，想到了一些清奇的思路，用于分类汇总的位运算

先附上原题链接：500. 键盘行 - 力扣（LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/keyboard-row/

500、键盘行

给你一个字符串数组 words ，只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。

美式键盘 中：

第一行由字符 "qwertyuiop" 组成。
第二行由字符 "asdfghjkl" 组成。
第三行由字符 "zxcvbnm" 组成。

class Solution {
public:
    vector<string> findWords(vector<string>& words) {

    }
};

我们需要对一个字符串进行判断是否所有字母都处在同一行，由于所有字母都是以不明规则排布的，所以我们先进行一个分类打表 ，判断每个字母的行数

        int dic[26] = {2, 4, 4, 2, 1, 2, 2, 2, 1, 2, 2, 2, 4, 4, 1, 1, 1, 1, 2, 1, 1, 4, 1, 4, 1, 4};

为什么要用 1，2，4 来给字母进行编号而不是用 0，1，2 呢？

这里就要说到位运算了

我们用二进制给每个字母分一下类，则

第一行字母：001

第二行字母：010

第三行字母：100

再通过对字符串的位或运算就能轻松得出字符串横跨了几行字母

        int pos = 0;
        for(auto ch:word) {
            if(ch >= 'A' && ch <= 'Z') ch -= 'A'-'a'; 
            // 在阅读题解时发现了一个tolower的函数，略显鸡肋（）
            pos |= dic[ch-'a'];
        }

如果字符串的字母均处于一行，那么 pos 自然就是 1，2，4 其中一个

于是我们便可以得到这道题的完整代码

class Solution {
public:
    vector<string> findWords(vector<string>& words) {
        int dic[26] = {2, 4, 4, 2, 1, 2, 2, 2, 1, 2, 2, 2, 4, 4, 1, 1, 1, 1, 2, 1, 1, 4, 1, 4, 1, 4};
        vector<string> ans;
        for(auto &word:words){
            int pos = 0;
            for(auto ch:word) {
                if(ch >= 'A' && ch <= 'Z') ch -= 'A'-'a';
                pos |= dic[ch-'a'];
            }
            if(pos == 1 || pos == 2 || pos == 4) ans.push_back(word);
        }
        return ans;
    }
};

自从打开了位运算的大门，发现这个用来分类汇总还是十分好用的（相比于定义好几个变量再通过不停的 if 和 else if 要方便得多）

另外：如果不用手动打表，这次的题目就需用并查集或是哈希表来打一个表，这样的操作常规且简单，也不是本篇重点，就不在这里赘述啦

好，这次的水博客到此结束     \ 完结撒花 /