这是悦乐书的第251次更新,第264篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第118题(顺位题号是520)。给定一个单词,你需要判断其中大写字母的使用是否正确。当下列情况之一成立时,我们将单词中大写字母的用法定义为正确:
这个单词中的所有字母都是大写字母,如“USA”。
这个单词中的所有字母都不是大写字母,如“leetcode”。
如果它有多个字母,只有首字母是大写字母,如“Google”。
否则,我们定义该单词不以正确的方式使用大写字母。例如:
输入:“USA”
输出:true
输入:“FlaG”
输出:false
注意:输入将是一个非空单词,由大写和小写字母组成。
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
a-z的ASCII值是从97到122, A-Z的ASCII值是从65到90,取第一个字符来判断是大写还是小写,首字母是大写分为两种情况,一是全大写,二是首字母大写,后面的字母小写,然后依次使用循环进行判断,只要出现不符合的情况字符,可以直接返回false。
此解法的时间复杂度是(n),空间复杂度是O(1)。
public boolean detectCapitalUse(String word) {
int res = word.charAt(0)-'a';
if (res < 0) {
// 首字母大写,后面的字母小写
if (word.length() >= 2 && word.charAt(1)-'a' >= 0) {
for (int i=1; i<word.length(); i++) {
if (word.charAt(i) - 'a' < 0) {
return false;
}
}
} else {
// 全部大写
for (char c : word.toCharArray()) {
if (c - 'a' >= 0) {
return false;
}
}
}
} else {
// 全部小写
for (char c : word.toCharArray()) {
if (c - 'a' < 0) {
return false;
}
}
}
return true;
}
03 第二种解法
使用一个变量记数,遍历该单词中每一个字符,如果最后count等于0或者等于单词的长度,说明该单词是全大写或全小写字母组成,如果等于1并且首字母大写,说明其符合第三条的条件。
此解法的时间复杂度是(n),空间复杂度是O(1)。
public boolean detectCapitalUse2(String word) {
int count = 0;
for (char c : word.toCharArray()) {
if (c - 'a' < 0) {
count++;
}
}
if (count == word.length() || count == 0) {
return true;
}
return count == 1 && word.charAt(0)-'a' < 0;
}
04 第三种解法
还可以一行代码搞定。如果是全大写,那么该单词一定和其被转为全大写的单词相等。如果全小写或者首字母除外的小写,那么其从第二位开始的子串一定和该子串全转为小写后相等。
public boolean detectCapitalUse3(String word) {
return word.substring(1).equals(word.substring(1).toLowerCase()) ||
word.equals(word.toUpperCase());
}
05 小结
算法专题目前已日更超过三个月,算法题文章118+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。
以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!