【Android开发】算法题合集（八）键盘行和检测大写字母

Android面试题算法篇，由本人整理汇总，后续将继续推出系列篇，如果喜欢请持续关注和推荐，更多精彩内容可以扫描文末二维码加v获得更多咨询~

上接：
【Android面试】算法题合集（一）二叉树和反转字符串
【Android开发】算法题合集（二）相对名次和反转字符串中的元音字母
【Android开发】算法题合集（三）赎金信和字符串中的第一个唯一字符
【Android开发】算法题合集（四）找不同和判断子序列
【Android开发】算法题合集（五）最长回文串和Fizz Buzz
【Android开发】算法题合集（六）字符串相加和字符串中的单词数
【Android开发】算法题合集（七）重复的子字符串和字符串中的单词数

在这里插入图片描述

🌲真题一：键盘行

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

美式键盘中：

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-V0cesFXc-1657075973361)(https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/c64e05d394de413cb30bfce7dbb5cfa6~tplv-k3u1fbpfcp-zoom-in-crop-mark:1956:0:0:0.image)]

示例1:

输入：words = ["Hello","Alaska","Dad","Peace"]
输出：["Alaska","Dad"]

示例2:

输入：words = ["omk"]
输出：[]

示例3:

输入：words = ["adsdf","sfd"]
输出：["adsdf","sfd"]

提示：

1 <= words.length <= 20
1 <= words[i].length <= 100
words[i] 由英文字母（小写和大写字母）组成

🌻C#方法：排序遍历

我们为每一个英文字母标记其对应键盘上的行号，然后检测字符串中所有字符对应的行号是否相同。

我们可以预处理计算出每个字符对应的行号。
遍历字符串时，统一将大写字母转化为小写字母方便计算。

代码：

public class Solution {
    public string[] FindWords(string[] words) {
        IList<string> list = new List<string>();
        string rowIdx = "12210111011122000010020202";
        foreach (string word in words) {
            bool isValid = true;
            char idx = rowIdx[char.ToLower(word[0]) - 'a'];
            for (int i = 1; i < word.Length; ++i) {
                if (rowIdx[char.ToLower(word[i]) - 'a'] != idx) {
                    isValid = false;
                    break;
                }
            }
            if (isValid) {
                list.Add(word);
            }
        }

        string[] ans = new string[list.Count];
        for (int i = 0; i < list.Count; ++i) {
            ans[i] = list[i];
        }
        return ans;
    }
}

执行结果

通过
执行用时：152 ms，在所有 C# 提交中击败了49.50%的用户
内存消耗：41.4 MB，在所有 C# 提交中击败了24.90%的用户

🌻Java 方法：计数

思路解析 我们为每一个英文字母标记其对应键盘上的行号，然后检测字符串中所有字符对应的行号是否相同。

我们可以预处理计算出每个字符对应的行号。
遍历字符串时，统一将大写字母转化为小写字母方便计算。

代码：

class Solution {    
    public String[] findWords(String[] words) {
        List<String> list = new ArrayList<String>();
        String rowIdx = "12210111011122000010020202";
        for (String word : words) {
            boolean isValid = true;
            char idx = rowIdx.charAt(Character.toLowerCase(word.charAt(0)) - 'a');
            for (int i = 1; i < word.length(); ++i) {
                if (rowIdx.charAt(Character.toLowerCase(word.charAt(i)) - 'a') != idx) {
                    isValid = false;
                    break;
                }
            }
            if (isValid) {
                list.add(word);
            }
        }
        String[] ans = new String[list.size()];
        for (int i = 0; i < list.size(); ++i) {
            ans[i] = list.get(i);
        }
        return ans;
    }
}

执行结果

通过
执行用时：0 ms，在所有 Java  提交中击败了100.76%的用户
内存消耗：36.4 MB，在所有 Java 提交中击败了89.40%的用户

🌲真题二：检测大写字母

我们定义，在以下情况时，单词的大写用法是正确的：

全部字母都是大写，比如 “USA” 。
单词中所有字母都不是大写，比如 “leetcode” 。
如果单词不只含有一个字母，只有首字母大写，比如 “Google” 。

给你一个字符串 word 。如果大写用法正确，返回 true ；否则，返回 false 。

示例1:

输入：word = "USA"
输出：true

示例2:

输入：word = "FlaG"
输出：false

提示：

1 <= word.length <= 100
word 由小写和大写英文字母组成

🌻C#方法：排序遍历

根据题目要求，若单词的大写用法正确，则需要满足：

若第 1 个字母为大写，则其他字母必须均为大写或均为小写，即其他字母必须与第 2 个字母的大小写相同；
若第 1 个字母为小写，则其他字母必须均为小写。

根据以上规则，可以整理得到以下更简单的判断规则：

无论第 1 个字母是否大写，其他字母必须与第 2 个字母的大小写相同；
若第 1 个字母为小写，则需额外判断第 2 个字母是否为小写。

代码：

public class Solution {
    public bool DetectCapitalUse(string word) {
        // 若第 1 个字母为小写，则需额外判断第 2 个字母是否为小写
        if (word.Length >= 2 && char.IsLower(word[0]) && char.IsUpper(word[1])) {
            return false;
        }
        
        // 无论第 1 个字母是否大写，其他字母必须与第 2 个字母的大小写相同
        for (int i = 2; i < word.Length; ++i) {
            if (char.IsLower(word[i]) ^ char.IsLower(word[1])) {
                return false;
            }
        }
        return true;
    }
}

执行结果

通过
执行用时：108 ms，在所有 C# 提交中击败了8.50%的用户
内存消耗：37.4 MB，在所有 C# 提交中击败了67.90%的用户

🌻Java 方法：计数

思路解析 根据题目要求，若单词的大写用法正确，则需要满足：

若第 1 个字母为大写，则其他字母必须均为大写或均为小写，即其他字母必须与第 2 个字母的大小写相同；
若第 1 个字母为小写，则其他字母必须均为小写。

根据以上规则，可以整理得到以下更简单的判断规则：

无论第 1 个字母是否大写，其他字母必须与第 2 个字母的大小写相同；
若第 1 个字母为小写，则需额外判断第 2 个字母是否为小写。

代码：

class Solution {
    public boolean detectCapitalUse(String word) {
        // 若第 1 个字母为小写，则需额外判断第 2 个字母是否为小写
        if (word.length() >= 2 && Character.isLowerCase(word.charAt(0)) && Character.isUpperCase(word.charAt(1))) {
            return false;
        }
        
        // 无论第 1 个字母是否大写，其他字母必须与第 2 个字母的大小写相同
        for (int i = 2; i < word.length(); ++i) {
            if (Character.isLowerCase(word.charAt(i)) ^ Character.isLowerCase(word.charAt(1))) {
                return false;
            }
        }
        return true;
    }
}

执行结果

通过
执行用时：1 ms，在所有 Java  提交中击败了94.76%的用户
内存消耗：36.8 MB，在所有 Java 提交中击败了26.40%的用户

复杂度分析

时间复杂度：O( n )
空间复杂度：O(1)

💬总结

文章采用 C# 和 Java 两种编程语言进行解题。一些方法也是参考力扣大神写的，也是边学习边分享，希望能够尽可能的帮助Android开发的伙伴们，大家一起学习，共同进步！！
今天的算法题分享到此结束，这里附上上述的面试题相关的几十套字节跳动，京东，小米，腾讯、头条、阿里、美团等公司19年的面试题。把技术点整理成了视频和PDF（实际上比预期多花了不少精力），包含知识脉络 + 诸多细节。
详细可扫描下方二维码，免费领取资料。