[leetcode]Count of Smaller Numbers After Self

用BST加count就可以解决

public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        LinkedList<Integer> result = new LinkedList<Integer>();
        BinarySearchTree tree = new BinarySearchTree();
        for(int i = nums.length-1; i >= 0; i--){
            result.addFirst(tree.add(nums[i]));
        }
        return result;
    }
}

class BinarySearchTree{
    BSTNode root;
    int add(int value){
        BSTNode visit = root;
        int count = 0;
        if (root == null) root = new BSTNode(value);

        while (visit != null){
            if (visit.value == value){
                visit.dupCount++;
                count += visit.leftCount;
                break;
            }else if (visit.value < value){
                count += (visit.dupCount+visit.leftCount);
                if (visit.right == null){
                    visit.right = new BSTNode(value);
                    break;
                }
                visit = visit.right;
            }else{
                visit.leftCount++;  
                if (visit.left == null){
                    visit.left = new BSTNode(value);
                    break;
                }
                visit = visit.left;
            }
        }
        return count;
    }
}

class BSTNode{
    int dupCount = 1;
    int leftCount;
    int value;
    BSTNode left, right;
    BSTNode(int value){
        this.value = value;
    }
}

[leetcode] Kth Largest Element in an Array

用Quick Select...其实可以在原array上修改...不过可能code会复杂点。。 直接straight forward 建立新array做

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

public class Solution { public int findKthLargest(int[] nums, int k) { List<Integer> numsList = new LinkedList<Integer>(); for (int i = 0; i < nums.length; i++) numsList.add(nums[i]); return findKthRec(numsList, k); } private int findKthRec(List<Integer> nums, int k){ int pivot = nums.get(0); int numPivot = 0; LinkedList<Integer> left = new LinkedList<Integer>(); LinkedList<Integer> right = new LinkedList<Integer>(); while (!nums.isEmpty()){ int current = nums.remove(0); if (current < pivot) right.add(current); else if (current > pivot) left.add(current); else numPivot++; } if (left.size() >= k) return findKthRec(left, k); else if (left.size()+numPivot >= k) return pivot; return findKthRec(right, k-left.size()-numPivot); } }

[leetcode]Different Ways to add parentheses

divide and conquer, 总是分成两半...

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

public class Solution { public List<Integer> diffWaysToCompute(String input) { if (input.equals("")) return new LinkedList<Integer>(); String operand = ""; List<Integer> result = new LinkedList<Integer>(); for (int i = 0; i < input.length(); i++){ if (!Character.isDigit(input.charAt(i))){ List<Integer> rightSide = diffWaysToCompute(input.substring(i+1)); List<Integer> leftSide = diffWaysToCompute(input.substring(0, i)); char operator = input.charAt(i); for (Integer left:leftSide){ for (Integer right:rightSide){ result.add(eval(operator, left, right)); } } }else{ operand+=input.charAt(i); } } if (result.size() == 0) result.add(Integer.valueOf(operand)); return result; } int eval(char operator, int operand1, int operand2){ if (operator == '*') return operand1*operand2; else if (operator == '+') return operand1+operand2; return operand1-operand2; } }

[leetcode]Search a 2D Matrix II

不知是否最优 。。。 从右上角开始搜 大于 向右走 小于向下走

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

public class Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0){ return false; } int row = 0; int col = matrix[0].length-1; while (row >= 0 && row < matrix.length && col >= 0 && col < matrix[0].length){ if (matrix[row][col] == target) return true; if (matrix[row][col] > target) col--; else row++; } return false; } }

[leetcode] Word Ladder

直接BFS..... 有一处搞了很久 发现原来return是转换过程有多少个word... 而不是换了多少个字母

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 int ladderLength(String beginWord, String endWord, Set<String> wordList) { HashSet<String> notVisited = new HashSet<String>(wordList); boolean found = false; HashSet<String> nextLevel = new HashSet<String>(); HashSet<String> curLevel = new HashSet<String>(); curLevel.add(beginWord); notVisited.remove(beginWord); int level = 1; while (!found && !curLevel.isEmpty()){ if (curLevel.contains(endWord)){ found = true; }else{ level++; } for (String cur:curLevel){ getNextWords(nextLevel, notVisited, cur); } HashSet<String> inter = nextLevel; nextLevel = curLevel; curLevel = inter; nextLevel.clear(); } return found?level:0; } public void getNextWords(HashSet<String> nextWord, HashSet<String>notVisited, String current){ char []possible = current.toCharArray(); for (int i = 0; i < possible.length; i++){ char origin = possible[i]; for (char a = 'a'; a <= 'z'; a++){ if (a != origin){ possible[i] = a; String temp = String.valueOf(possible); if (notVisited.contains(temp)){ nextWord.add(temp); notVisited.remove(temp); } } } possible[i] = origin; } } }

[leetcode]Word Ladder II

这是条难题（base on time and memory limit) 大概思路就是记录每个字的parents.. 还有用hashset来装next level这样可以避免重复 当整个next level都生成完毕之后...就可以把notVisited里面的next level word 去掉 一举两得..既可以避免重复visit又可以满足同一个word有multiple parents的情况... **有个地方就是注意同样字母的时候 不应该算进possible

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 57 58 59 60 61 62 63 64 65 66

public class Solution { List<List<String>> result = new ArrayList<List<String>>(); public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) { HashMap<String, List<String>> parents = new HashMap<String, List<String>>(); HashSet<String> notVisited = new HashSet<String>(wordList); boolean found = false; HashSet<String> nextLevel = new HashSet<String>(); HashSet<String> curLevel = new HashSet<String>(); curLevel.add(beginWord); notVisited.remove(beginWord); while (!found && !curLevel.isEmpty()){ for (String cur:curLevel){ getNextWords(parents, nextLevel, notVisited, cur); } for (String next:nextLevel){ notVisited.remove(next); } if (nextLevel.contains(endWord)) found = true; HashSet<String> inter = nextLevel; nextLevel = curLevel; curLevel = inter; nextLevel.clear(); } if (!parents.containsKey(endWord)) return new ArrayList<List<String>>(); generateResult(parents, beginWord, endWord, new LinkedList<String>()); return result; } public void generateResult(HashMap<String, List<String>> parents, String start, String end, List<String> fromPrev){ if (start == end){ LinkedList<String> temp = new LinkedList<String>(fromPrev); temp.addFirst(start); result.add(temp); return; } List<String> parent = parents.get(end); ((LinkedList<String>) fromPrev).addFirst(end); for (String upper:parent){ generateResult(parents, start, upper, fromPrev); } ((LinkedList<String>) fromPrev).removeFirst(); } public void getNextWords(HashMap<String, List<String>> parents, HashSet<String> nextWord, HashSet<String>notVisited, String current){ char []possible = current.toCharArray(); for (int i = 0; i < possible.length; i++){ char origin = possible[i]; for (char a = 'a'; a <= 'z'; a++){ if (a != origin){ possible[i] = a; String temp = String.valueOf(possible); if (notVisited.contains(temp)) { nextWord.add(temp); List<String> parent = parents.containsKey(temp)?parents.get(temp):new ArrayList<String>(); parent.add(current); parents.put(temp, parent); } } } possible[i] = origin; } } }

next topic

divide and conquer

Backtracking

[leetcode]Surrounded Regions

这题leetcode设的memory好紧... 最后把recursion换成iterative做才过.. 还有BFS忘了track visited loop 搞了很久 

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 void solve(char[][] board) { if (board == null || board.length == 0 || board[0].length == 0) return; for (int i = 0; i < board.length; i++){ if (board[i][0] == 'O') filpEdgeRegionToOne(board, i, 0); if (board[i][board[0].length-1] == 'O') filpEdgeRegionToOne(board, i, board[0].length-1); } for (int i = 0; i < board[0].length; i++){ if (board[0][i] == 'O') filpEdgeRegionToOne(board, 0, i); if (board[board.length-1][i] == 'O') filpEdgeRegionToOne(board, board.length-1, i); } for (int i = 0; i < board.length; i++){ for (int j = 0; j < board[0].length; j++){ if (board[i][j] == 'O') board[i][j] = 'X'; else if (board[i][j] == '1') board[i][j] = 'O'; } } } void filpEdgeRegionToOne(char[][]board, int i, int j){ int dirs[][] = {{1,0},{-1,0},{0,1},{0,-1}}; Queue<int[]> queue = new LinkedList<int[]>(); queue.add(new int[]{i,j}); while (!queue.isEmpty()){ int []location = queue.poll(); if (board[location[0]][location[1]] == 'O'){ board[location[0]][location[1]] = '1'; for (int k = 0; k < dirs.length; k++){ int x = location[0]+dirs[k][0]; int y = location[1]+dirs[k][1]; if (checkValid(board, x, y)) queue.add(new int[]{x,y}); } } } } boolean checkValid(char[][] board, int i, int j){ return !(i < 0 || i >= board.length || j < 0 || j >= board[i].length || board[i][j] == 'X' || board[i][j] == '1'); } }

[leetcode] Course Schedule II

貌似这是Topological sorting...上网看了下Topological的解释 思路就清晰了....

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

public class Solution { public int[] findOrder(int numCourses, int[][] prerequisites) { int[] inDegree = new int[numCourses]; List<HashSet<Integer>> out = new ArrayList<HashSet<Integer>>(); for (int i = 0; i < numCourses; i++){ out.add(new HashSet<Integer>()); } for (int i = 0; i < prerequisites.length; i++){ if (!out.get(prerequisites[i][1]).contains(prerequisites[i][0])){ inDegree[prerequisites[i][0]]++; out.get(prerequisites[i][1]).add(prerequisites[i][0]); } } Queue<Integer> queue = new LinkedList<Integer>(); for (int i = 0; i < inDegree.length; i++){ if (inDegree[i] == 0) queue.add(i); } int result[] = new int[numCourses]; int curPtr = 0; while (!queue.isEmpty()){ int current = queue.poll(); result[curPtr++] = current; HashSet<Integer> outCourses = out.get(current); for (Integer temp:outCourses){ inDegree[temp]--; out.get(temp).remove(current); if (inDegree[temp] == 0) queue.add(temp); } } if (curPtr != numCourses) return new int[0]; return result; } }

[leetcode]Minimum Height Trees

这条题考的就是对graph和tree的熟悉程度... 记着tree maximum只可能有2个nodes能成为最短path的root... 围绕着这个做文章.. 不停地删leaf..剩下的（小于等于2）的结果就是所要的结果了..

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

public class Solution { public List<Integer> findMinHeightTrees(int n, int[][] edges) { int degree[] = new int[n]; HashMap<Integer, List<Integer>> nodes = new HashMap<Integer, List<Integer>>(); for (int i = 0; i < edges.length; i++){ int a = edges[i][0]; int b = edges[i][1]; List<Integer> listA = nodes.containsKey(a)?nodes.get(a):new ArrayList<Integer>(); List<Integer> listB = nodes.containsKey(b)?nodes.get(b):new ArrayList<Integer>(); listA.add(b); listB.add(a); nodes.put(a, listA); nodes.put(b, listB); degree[a]++; degree[b]++; } int remain = n; Queue<Integer> queue = new LinkedList<Integer>(); for (int i = 0; i < n; i++){ if(degree[i] == 1) queue.add(i); } while (remain > 2){ int size = queue.size(); for (int i = 0; i < size; i++){ int leaf = queue.poll(); remain--; degree[leaf]--; for (Integer neighbor:nodes.get(leaf)){ degree[neighbor]--; if (degree[neighbor] == 1) queue.add(neighbor); } } } List<Integer> result = new ArrayList<Integer>(queue); if (n == 1) result.add(0); return result; } }

TO-DO 12/20/2015

REVIEW:
 Dijstra and Bellman-ford algorithm, RIP algorithm
Floyd最短路算法 还有max flow这些基础图论的东西

fibonacci number matrix calculation

http://www.gocalf.com/blog/calc-fibonacci.html

[leetcode] Clone Graph

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

/** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * List<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * }; */ public class Solution { public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if (node == null) return null; HashMap<UndirectedGraphNode, UndirectedGraphNode> cloneNodes = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); mapClone(node, cloneNodes); UndirectedGraphNode[] allNodes = cloneNodes.keySet() .toArray(new UndirectedGraphNode[cloneNodes.size()]); for (int i = 0; i < allNodes.length; i++){ UndirectedGraphNode copyNode = cloneNodes.get(allNodes[i]); List<UndirectedGraphNode> neighbors = allNodes[i].neighbors; for (int j = 0; j < neighbors.size(); j++){ copyNode.neighbors.add(cloneNodes.get(neighbors.get(j))); } } return cloneNodes.get(node); } public void mapClone(UndirectedGraphNode node, HashMap<UndirectedGraphNode, UndirectedGraphNode> cloneNodes){ if (cloneNodes.containsKey(node)) return; cloneNodes.put(node, new UndirectedGraphNode(node.label)); List<UndirectedGraphNode> neighbors = node.neighbors; for (int i = 0; i < neighbors.size(); i++){ mapClone(neighbors.get(i), cloneNodes); } } }

[leetcode]Course Schedule

就是建立有向图 查有没有cycle

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

public class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { HashMap<Integer, Node> lookup = new HashMap<Integer, Node>(); for (int i = 0; i < prerequisites.length; i++){ Node temp = lookup.containsKey(prerequisites[i][0])? lookup.get(prerequisites[i][0]):new Node(prerequisites[i][0]); Node next = lookup.containsKey(prerequisites[i][1])? lookup.get(prerequisites[i][1]):new Node(prerequisites[i][1]); temp.addNext(next); lookup.put(prerequisites[i][0], temp); lookup.put(prerequisites[i][1], next); } Integer[]nodes = (Integer[])lookup.keySet().toArray(new Integer[lookup.size()]); for (int i = 0; i < nodes.length; i++){ if (!lookup.get(nodes[i]).checked && hasCycle(lookup, new HashSet<Integer>(), nodes[i].intValue())){ return false; } } return true; } public boolean hasCycle(HashMap<Integer, Node> lookup, HashSet<Integer> visited, int current){ Node curNode = lookup.get(current); curNode.checked = true; visited.add(current); List<Node> neighbors = curNode.nexts; for (int i = 0; i < neighbors.size(); i++){ if (visited.contains(neighbors.get(i).classNum) || hasCycle(lookup, visited, neighbors.get(i).classNum)){ return true; } } visited.remove(current); return false; } } class Node{ int classNum; boolean checked; List<Node> nexts = new ArrayList<Node>(); Node(int classNum){this.classNum = classNum;} void addNext(Node next){nexts.add(next);} }

[leetcode]Graph Valid Tree

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

public class Solution { public boolean validTree(int n, int[][] edges) { if (n == 1) return true; HashMap<Integer, List<Integer>> lookup = new HashMap<Integer, List<Integer>>(); for (int i = 0; i < edges.length; i++){ List<Integer> neighbors = lookup.containsKey(edges[i][0])? lookup.get(edges[i][0]):new ArrayList<Integer>(); neighbors.add(edges[i][1]); List<Integer> neighbors2 = lookup.containsKey(edges[i][1])? lookup.get(edges[i][1]):new ArrayList<Integer>(); neighbors2.add(edges[i][0]); lookup.put(edges[i][0], neighbors); lookup.put(edges[i][1], neighbors2); } if (lookup.size() != n) return false; boolean visited[] = new boolean[n]; if (hasCycle(lookup, visited, -1, 0)) return false; for (int i = 0; i < visited.length; i++){ if (!visited[i]) return false; } return true; } public boolean hasCycle(HashMap<Integer, List<Integer>> neighbors, boolean[] visited, int parent, int current){ if (visited[current]) return true; visited[current] = true; List<Integer> neighbor = neighbors.get(current); for (int i = 0; i < neighbor.size(); i++){ if (neighbor.get(i) != parent && hasCycle(neighbors, visited, current, neighbor.get(i))){ return true; } } return false; } }

[leetcode]Remove Invalid Parentheses

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

public class Solution { public List<String> removeInvalidParentheses(String s) { List<String> result = new ArrayList<String>(); HashSet<String> lookup = new HashSet<String>(); Queue<String> queue = new LinkedList<String>(); queue.add(s); queue.add(null); while (!queue.isEmpty()){ String current = queue.poll(); if (current == null){ if (result.size() != 0) break; queue.add(null); } if (current != null && !lookup.contains(current)){ lookup.add(current); if (isValid(current)) result.add(current); else{ for (int i = 0; i < current.length(); i++){ char temp = current.charAt(i); if (temp == '(' || temp == ')'){ queue.add(current.substring(0,i)+current.substring(i+1)); } } } } } return result; } private boolean isValid(String s){ int count = 0; for (int i = 0; i < s.length(); i++){ char current = s.charAt(i); if (current == '(') count++; else if (current == ')') count--; if (count < 0) return false; } return count == 0; } }

QuickSelection

http://marswork.logdown.com/posts/285570-algorithm-quick-select

[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; } }

[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"; } }