[leetcode]Filp Game II

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

public class Solution { char[] sChar; public boolean canWin(String s) { sChar = s.toCharArray(); return canWin(); } private boolean canWin(){ for (int i = 0; i < sChar.length-1; i++){ if (sChar[i] == '+' && sChar[i+1] == '+'){ sChar[i] = '-'; sChar[i+1] = '-'; boolean win = canWin(); sChar[i] = '+'; sChar[i+1] = '+'; if (!win) return true; } } return false; } }

[leetcode]Meeting Room II

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

public class Solution { public int minMeetingRooms(Interval[] intervals) { if (intervals == null || intervals.length == 0){ return 0; } PriorityQueue<int[]> queue = new PriorityQueue<int[]>(1, new Comparator<int[]>(){ public int compare(int[] o1, int[] o2){ if (o1[0] == o2[0]) return o1[1]-o2[1]; return o1[0]-o2[0]; } }); for (int i = 0; i < intervals.length; i++){ queue.add(new int[]{intervals[i].start, 1}); queue.add(new int[]{intervals[i].end, -1}); } int maxSameTime = 0; int count = 0; while (!queue.isEmpty()){ int[] time = queue.poll(); count += time[1]; maxSameTime = Math.max(maxSameTime, count); } return maxSameTime; } }

[leetcode]Walls and Gates

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

public class Solution { public void wallsAndGates(int[][] rooms) { int INF = 2147483647; LinkedList<int[]> queue = new LinkedList<int[]>(); for (int i = 0; i < rooms.length; i++){ for (int j = 0; j < rooms[i].length; j++){ if (rooms[i][j] == 0) queue.add(new int[]{i,j}); } } int directions[][] = {{-1,0},{1,0},{0,1},{0,-1}}; while (!queue.isEmpty()){ int[] current = queue.poll(); for (int i = 0; i < 4; i++){ int newRow = current[0]+directions[i][0]; int newCol = current[1]+directions[i][1]; if (newRow >= 0 && newRow < rooms.length && newCol >= 0 && newCol < rooms[0].length &&rooms[newRow][newCol] == INF){ rooms[newRow][newCol] = rooms[current[0]][current[1]]+1; queue.add(new int[]{newRow, newCol}); } } } } }

[leetcode] find prime

不是第一次做这个题了.. 最优方法就是从2开始 把凡是2的倍数去掉..然后advance到下一个...下一个不是prime的话 继续 遇到prime继续往后灭 ..note:从2 到sqrt(n)就可以了 ..2.内部loop直接找下一个倍数 不要逐个逐个找

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

public class Solution { public int countPrimes(int n) { if (n <= 2) return 0; boolean notPrime[] = new boolean[n]; int k = (int)Math.sqrt(n); int count = 0; for (int i = 2; i <= k+2 && i < n; i++){ if (!notPrime[i]){ int multi = i*2; while (multi < n){ if (!notPrime[multi]){ notPrime[multi] = true; count++; } multi += i; } } } return n-2-count; } }

[leetcode] meeting room

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

/** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */ public class Solution { public boolean canAttendMeetings(Interval[] intervals) { if (intervals.length <= 1) return true; PriorityQueue<Interval> queue = new PriorityQueue<Interval>(intervals.length, new Comparator<Interval>(){ public int compare(Interval i, Interval k){ return i.start-k.start; } }); queue.addAll(Arrays.asList(intervals)); Interval prev = queue.poll(); while (!queue.isEmpty()){ Interval temp = queue.poll(); if(isOverlap(temp, prev)) return false; prev = temp; } return true; } boolean isOverlap (Interval i, Interval b){ return !(i.start >= b.end || b.start >= i.end); } }

[leetcode]Repeated DNA Sequences

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

public class Solution { public List<String> findRepeatedDnaSequences(String s) { List<String> result = new ArrayList<String>(); HashMap<Integer, Integer> lookup = new HashMap<Integer, Integer>(); String current = ""; int sum = 0; for (int i = 0; i < s.length(); i++){ sum = ((sum << 2)+getMap(s.charAt(i))) & 0xFFFFF; current += s.charAt(i); if (current.length() == 10){ if (lookup.containsKey(sum)){ if (lookup.get(sum) == 1){ result.add(current); lookup.put(sum,2); } }else{ lookup.put(sum,1); } current = current.substring(1,10); } } return result; } int getMap(char a){ if (a == 'A') return 0; if (a == 'C') return 1; if (a == 'G') return 2; return 3; } }

[leetcode] Sudoku solver

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 46 47 48 49 50 51 52 53 54 55 56

public class Solution { public void solveSudoku(char[][] board) { dfs(board, 0, 0); } private boolean dfs(char[][] board, int row, int col){ if (row >= 9) return true; int nextCol = (col+1)%9; int nextRow = row+(col+1)/9; if (board[row][col] != '.') return dfs(board, nextRow, nextCol); else{ for (int i = 0; i < 9; i++){ board[row][col] = (char)(i+'1'); if (isValid(board, row, col) && dfs(board, nextRow, nextCol)) return true; board[row][col] = '.'; } } return false; } private boolean isValid(char[][] board, int row, int col){ boolean lookup[] = new boolean[9]; //check row for (int i = 0; i < 9; i ++){ if (board[row][i] != '.'){ int index = board[row][i] - '0' -1; if (lookup[index]) return false; lookup[index] = true; } } //check column lookup = new boolean[9]; for (int i = 0; i < 9; i++){ if (board[i][col] != '.'){ int index = board[i][col] - '0' - 1; if(lookup[index]) return false; lookup[index] = true; } } //check box int startingRow = (row/3)*3; int startingCol = (col/3)*3; lookup = new boolean[9]; for (int i = startingRow; i < startingRow+3; i++){ for (int j = startingCol; j < startingCol+3; j++){ if (board[i][j] != '.'){ int index = board[i][j] - '0' - 1; if (lookup[index]) return false; lookup[index] = true; } } } return true; } }