[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