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
直接調(diào)用String類的toLowerCase函數(shù)，效率不高，只能擊敗20%的提交
Approach 2
使用StringBuilder和char與int的自動(dòng)轉(zhuǎn)換，擊敗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%的提交
時(shí)間復(fù)雜度O(S)，S為words中單詞的個(gè)數(shù)
空間復(fù)雜度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();
}
}
上面的程序可以改進(jìn)，字符串拼接時(shí)，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();
}
}
改進(jìn)之后，擊敗51.52%的提交，看了其他答案，基本大同小異，那么為什么只能擊敗51.52%呢？
分析之下，認(rèn)為和dict的定義有關(guān)，如果改為String[] dict 改為static String[] dict，修改之后，發(fā)現(xiàn)有時(shí)能達(dá)到100%，有時(shí)51.52%，有時(shí)29.15%，具體原因目前不清，需要繼續(xù)嘗試分析
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();
}
}
還有一種寫法，發(fā)現(xiàn)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();
}
}
知識(shí)點(diǎn)
StringBUilder
HashSet
static變量和動(dòng)態(tài)變量的性能比較
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;
}
}
}
