709.To Lower Case

Description

Implement function ToLowerCase() that has a string parameter str, and returns the same string in lowercase.

Example 1:

Input: "Hello"Output: "hello"

Solution

Approach 1

直接调用String类的toLowerCase函数，效率不高，只能击败20%的提交

Approach 2

使用StringBuilder和char与int的自动转换，击败100%提交

class Solution {
    public String toLowerCase(String str) {
        if (str == null || str.length() == 0) {
            return str;
        }

        StringBuilder sb = new StringBuilder();
        for(char c:str.toCharArray()){
            if('A' <= c &&  c <= 'Z'){
                c = (char)(c+32);
            }
            sb.append(c);
        }

        return sb.toString();

        // 效率不高
        //return str.toLowerCase();
    }
}

804. Unique Morse Code Words

Description

International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows: "a" maps to ".-", "b" maps to "-...", "c" maps to "-.-.", and so on.

For convenience, the full table for the 26 letters of the English alphabet is given below:

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
Now, given a list of words, each word can be written as a concatenation of the Morse code of each letter. For example, "cab" can be written as "-.-.-....-", (which is the concatenation "-.-." + "-..." + ".-"). We'll call such a concatenation, the transformation of a word.

Return the number of different transformations among all words we have.

Example:
Input: words = ["gin", "zen", "gig", "msg"]
Output: 2
Explanation:
The transformation of each word is:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."

There are 2 different transformations, "--...-." and "--...--.".

Note:

The length of words will be at most 100.
Each words[i] will have length in range [1, 12].
words[i] will only consist of lowercase letters.

Solution

Approach 1

最容易想到的方法，击败19.09%的提交
时间复杂度O(S)，S为words中单词的个数
空间复杂度O(S)

class Solution {
    String[] dict = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};

    public int uniqueMorseRepresentations(String[] words) {
        HashSet<String> set = new HashSet<String>();
        for (String word : words) {
            String morse = "";
            for (char c : word.toCharArray()) {
                int index = c - 'a';
                morse += dict[index];
            }
            set.add(morse);
        }
        
        return set.size();
    }
}

上面的程序可以改进，字符串拼接时，StringBuilder效率较高，程序修改如下：

class Solution {
    String[] dict = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
    
    public int uniqueMorseRepresentations(String[] words) {
        HashSet<String> set = new HashSet<String>();
        for (String word : words) {
            StringBuilder code = new StringBuilder();
            for (char c : word.toCharArray()) {
                code.append(dict[c - 'a']);
            }
            set.add(code.toString());
        }
        
        return set.size();
    }
}

改进之后，击败51.52%的提交，看了其他答案，基本大同小异，那么为什么只能击败51.52%呢？
分析之下，认为和dict的定义有关，如果改为String[] dict 改为static String[] dict，修改之后，发现有时能达到100%，有时51.52%，有时29.15%，具体原因目前不清，需要继续尝试分析

class Solution {
    private final static String[] dict = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
    
    public int uniqueMorseRepresentations(String[] words) {
        HashSet<String> set = new HashSet<String>();
        for (String word : words) {
            StringBuilder code = new StringBuilder();
            for (char c : word.toCharArray()) {
                code.append(dict[c - 'a']);
            }
            set.add(code.toString());
        }
        
        return set.size();
    }
}

还有一种写法，发现beat100%的概率比较大

class Solution {
    static String[] morseCode = { ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.",
                "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.." };

    public int uniqueMorseRepresentations(String[] words) {
        HashSet<String> hashSet = new HashSet<>();
        for (String w : words) {
            hashSet.add(getCode(w));
        }

        return hashSet.size();
    }

    private String getCode(String w) {
        // TODO Auto-generated method stub
        StringBuilder stringBuilder = new StringBuilder();
        for (char c : w.toCharArray()) {
            stringBuilder.append(morseCode[c - 'a']);
        }
        return stringBuilder.toString();
    }
}

知识点

StringBUilder
HashSet
static变量和动态变量的性能比较

657. Robot Return to Origin

Description

There is a robot starting at position (0, 0), the origin, on a 2D plane. Given a sequence of its moves, judge if this robot ends up at (0, 0) after it completes its moves.

The move sequence is represented by a string, and the character moves[i] represents its ith move. Valid moves are R (right), L (left), U (up), and D (down). If the robot returns to the origin after it finishes all of its moves, return true. Otherwise, return false.

Note: The way that the robot is "facing" is irrelevant. "R" will always make the robot move to the right once, "L" will always make it move left, etc. Also, assume that the magnitude of the robot's movement is the same for each move.
Example 1:

Input: "UD"
Output: true
Explanation: The robot moves up once, and then down once. All moves have the same magnitude, so it ended up at the origin where it started. Therefore, we return true.
Example 2:

Input: "LL"
Output: false
Explanation: The robot moves left twice. It ends up two "moves" to the left of the origin. We return false because it is not at the origin at the end of its moves.

Solution

class Solution {
    public boolean judgeCircle(String moves) {
        if (moves == null || moves.length() == 0) {
            return true;
        }

//         int up = 0;
//         int down = 0;
//         int left = 0;
//         int right = 0;

//         for (int i = 0; i < moves.length(); i++) {
//             switch (moves.charAt(i)) {
//                 case 'U':
//                     up++;
//                     break;
//                 case 'D':
//                     down++;
//                     break;
//                 case 'L':
//                     left++;
//                     break;
//                 case 'R':
//                     right++;
//                     break;
//                 default:
//                     break;
//             }
//         }

//         if (up == down && left == right) {
//             return true;
//         } else {
//             return false;
//         }
        
         // 方法二
        int x = 0, y = 0;
        for (char move : moves.toCharArray()) {
            switch (move) {
                case 'U':
                    y++;
                    break;
                case 'D':
                    y--;
                    break;
                case 'L':
                    x--;
                    break;
                case 'R':
                    x++;
                    break;
                default:
                    break;
            }
        }

        if (x == 0 && y == 0) {
            return true;
        } else {
            return false;
        }
    }
}