LeetCode演算法題-Detect Capital(Java實現)
這是悅樂書的第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 +篇,公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞,獲取系列文章合集。
以上就是全部內容,如果大家有什麼好的解法思路、建議或者其他問題,可以下方留言交流,點贊、留言、轉發就是對我最大的回報和支援!