Archive for August 14th, 2013
- In: CC150 | leetcode
- Leave a Comment
这个题好像就没一次做对过。实在是，太绕了太绕了太绕了。二维数组的上下左右index能把人活活烦死。出现的多次失误：
- 只转了四个角（主要在于i的物理意义没弄清）
- 每个边转了整个长度而不是长度-1（这样四角就会一直转来转去）
- 没搞清left, right, up, bottom怎么用layer和index表示。一个检查写的对不对的方法：记住
- upper说明i不变（depend on constant layer）， j在从小到大变动（从左往右）
- left说明j不变（一直是最小值，因为靠左），i在从大到小的变动（从下往上）
- bottom说明i不变（一直是最大的），j在从大到小变动（从右往左）
- right说明j不变（一直是最大的），i在从大到小变动（从上往下）
public void rotate(int[][] matrix) {
int len = matrix[0].length;
for (int layer = 0; layer < len / 2; layer++) {
for (int i = layer; i < len - 1 - layer; i++) {
// save upper
int temp = matrix[layer][i];
// upper = left
matrix[layer][i] = matrix[len - 1 - i][layer];
// left = bottom
matrix[len - 1 - i][layer] = matrix[len - 1 - layer][len - 1 - i];
// bottom = right
matrix[len - 1 - layer][len - 1 - i] = matrix[i][len - 1 - layer];
// right = up
matrix[i][len - 1 - layer] = temp;
}
}
}
十月份重做，还是没做出来。不知道为什么大家都觉得这个题简单，我个人认为这是CC150最难的3道题之一。别的难题都是理解了下次就做出来了，这题是理解了再做5遍还是做不出来。
和spiral matrix的区别：那道题是大大卷那种，spiral的，这个是一层一层的，上一层和这一层没关系。
看了看别人的答案，他们是利用了罗马数字的概念：从左往右，每次加上当前字母的面值就好了。如果前一个字母面值<后一个字母，说明当前字母是4，9的第二个字符。这个时候就减去两次前一个字母面值（因为前一步已经加一次了，这里发现其实是需要减，所以要减两次）。最后无论如何都要加上当前字母的面值。比如XIV(14)，后一个字母是V时，发现>I，但此时result已经是10 + 1了，所以要-2，再+5。
public int romanToInt(String s) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
map.put('I', 1);
map.put('V', 5);
map.put('X', 10);
map.put('L', 50);
map.put('C', 100);
map.put('D', 500);
map.put('M', 1000);
char[] arr = s.toCharArray();
int res = map.get(arr[0]);
for (int i = 1; i < arr.length; i++) {
if (map.get(arr[i]) > map.get(arr[i - 1])) {
res -= 2 * map.get(arr[i - 1]);
}
res += map.get(arr[i]);
}
return res;
}
Tags: math
这题是和amazon wiki上的做法一致，即每次取最右面的single digit，根据当前位数（个位十位之类的）和这个数字本身来算出它的罗马数字（用pattern matching)；然后prepend到string builder前面。这题好多做法，但是pattern matching的做法不用考虑4呀9呀之类的，比较清晰。
public String intToRoman(int num) {
Map<Integer, Tri> weiToTri = new HashMap<Integer, Tri>();
weiToTri.put(1, new Tri('I', 'V', 'X'));
weiToTri.put(2, new Tri('X', 'L', 'C'));
weiToTri.put(3, new Tri('C', 'D', 'M'));
weiToTri.put(4, new Tri('M', 'F', 'F'));
StringBuilder result = new StringBuilder();
int wei = 1;
while (num != 0) {
int digit = num % 10;
result.insert(0, getRomanForDigit(digit, wei, weiToTri));
num /= 10;
wei++;
}
return result.toString();
}
private String getRomanForDigit(int digit, int wei, Map<Integer, Tri> weiToTri) {
Tri tri = weiToTri.get(wei);
String[] patterns = {"", "a", "aa", "aaa", "ab", "b", "ba", "baa", "baaa", "ac"};
String pattern = patterns[digit].replace('a', tri.one).replace('b', tri.five).replace('c', tri.ten);
return pattern;
}
Tags: math
Lexi's Leetcode solutions 