[leetcode]Two Sum III

two sum问题一直ignore的一个细节就是要check target-value[i]是不是map向同一个数字..而这个数字是否只存在一个...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

public class TwoSum { HashMap<Integer, Integer>lookup = new HashMap<Integer, Integer>(); ArrayList<Integer> numbers = new ArrayList<Integer>(); public void add(int number) { int count = 1; if (lookup.containsKey(number)) count += lookup.get(number); lookup.put(number, count); numbers.add(number); } public boolean find(int value) { for (int i = 0; i < numbers.size(); i++){ int target = value-numbers.get(i); if (target == numbers.get(i)){ if (lookup.containsKey(target) && lookup.get(target) >= 2){ return true; } }else if (lookup.containsKey(target)) return true; } return false; } }

[leetcode]Bull and Cows

有时候要再三审视思路...因为未必是对的.. 最好先弄个小test case 想好思路想一想. 思路分两步走 先找matched 顺便把不match的入hash, 然后再找不match 还有一个更高效的方法是用counter...下次记得用

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

public class Solution { public String getHint(String secret, String guess) { HashMap<Character, Integer> lookup = new HashMap<Character, Integer>(); int matched = 0; int hasNum = 0; for (int i = 0; i < secret.length(); i++){ char sechar = secret.charAt(i); char guchar = guess.charAt(i); if (sechar == guchar) matched++; else{ int count = 1; if (lookup.containsKey(sechar)){ count += lookup.get(sechar); } lookup.put(sechar, count); } } for (int i = 0; i < guess.length(); i++){ char guchar = guess.charAt(i); char sechar = secret.charAt(i); if (guchar != sechar && lookup.containsKey(guchar)){ int count = lookup.get(guchar)-1; if (count == 0) lookup.remove(guchar); else lookup.put(guchar, count); if (guchar == sechar) matched++; else hasNum++; } } return matched+"A"+hasNum+"B"; } }

[leetcode]Word Pattern

最重要捉住1 to 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

public class Solution { public boolean wordPattern(String pattern, String str) { if (pattern.length() == 0 || str.length() == 0) return false; String[] array = str.split(" "); if (array.length != pattern.length()) return false; HashMap<String, Character> lookup = new HashMap<String, Character>(); HashMap<Character, String> reverseLookup = new HashMap<Character, String>(); String result = ""; for (int i = 0; i < array.length; i++){ if(reverseLookup.containsKey(pattern.charAt(i)) && !reverseLookup.get(pattern.charAt(i)).equals(array[i])){ return false; }else{ reverseLookup.put(pattern.charAt(i), array[i]); } if(lookup.containsKey(array[i]) && lookup.get(array[i]) != pattern.charAt(i)){ return false; }else{ lookup.put(array[i], pattern.charAt(i)); } } return true; } }

[leetcode]H-index

这题有点绕啊 别想太多 就用wiki的方法 sort好 从大到小看... 假如有index >= collection[index]的 那就return index, 最后return size

1 2 3 4 5 6 7 8 9 10 11

public class Solution { public int hIndex(int[] citations) { if (citations == null || citations.length == 0) return 0; int[] copy = Arrays.copyOf(citations, citations.length); Arrays.sort(copy); for (int i = copy.length-1, j = 0; i >=0; i--, j++){ if (j>=copy[i]) return j; } return copy.length; } }

[leetcode]Isomorphic Strings

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

public class Solution { public boolean isIsomorphic(String s, String t) { if (s.length() != t.length()) return false; HashMap<Character, Character>lookup = new HashMap<Character, Character>(); HashMap<Character, Character>lookup2 = new HashMap<Character, Character>(); for (int i = 0; i < s.length(); i++){ char c1 = s.charAt(i); char c2 = t.charAt(i); if (lookup.containsKey(c1) && lookup.get(c1) != c2) return false; if (lookup2.containsKey(c2) && lookup2.get(c2) != c1) return false; lookup.put(c1, c2); lookup2.put(c2,c1); } return true; } }

[leetcode]Valid Sudoku

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

public class Solution { public boolean isValidSudoku(char[][] board) { if (board == null || board.length != 9 || board[0].length != 9) return false; boolean lookup[]; boolean lookCol[]; for (int i = 0; i < 9; i++){ lookup = new boolean[9]; lookCol = new boolean[9]; for (int j = 0; j < 9; j++){ if (board[i][j] != '.'){ int index = board[i][j] - '0'-1; if (lookup[index]) return false; lookup[index] = true; } if (board[j][i] != '.'){ int index2 = board[j][i] -'0'-1; if (lookCol[index2]) return false; lookCol[index2] = true; } } } for (int i = 0; i < 9; i+=3){ for (int j = 0; j < 9; j+=3){ lookup = new boolean[9]; lookCol = new boolean[9]; for (int k = i; k < i+3; k++){ for (int q = j; q < j+3; q++){ if (board[k][q] != '.'){ int index = board[k][q] - '0'-1; if (lookup[index]) return false; lookup[index] = true; } if (board[q][k] != '.'){ int index2 = board[q][k] -'0'-1; if (lookCol[index2]) return false; lookCol[index2] = true; } } } } } return true; } }

[leetcode]Strobogrammatic Number

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

public class Solution { boolean rightMapping(char c1, char c2){ if (c1 > c2) return rightMapping(c2,c1); if (c1 == '0') return c2 == '0'; if (c1 == '1') return c2 == '1'; if (c1 == '6') return c2 == '9'; if (c1 == '8') return c2 == '8'; return false; } public boolean isStrobogrammatic(String num) { char[] arr = num.toCharArray(); int left = 0; int right = arr.length-1; while (left <= right){ if (!rightMapping(arr[left++], arr[right--])) return false; } return true; } }