一切move on

没事，给自己几个关于cs career 的目标
1. leetcode
2. system design
3. aws certificate

非常不开心

我忍不住了，在这里我做的根本就是没用功。。。杀虫用牛刀。。。 我要忍着，要发泄就这里发泄。争取加速换工作

总结03.02

1. 之前 有一些烦恼，不应该庸人自扰，什么事是对的 什么事是错的 要清楚，
不能让emotion和冲动战胜理智。要忍和斩断不好的念头。
2. 工作里面 要耐心听讲和不要太agressive, 要感恩别人对自己的帮助 和 耐心

[leetcode]Find Minimum in Rotated Sorted Array II

这种题off by one error太容易出了.. 到目前为止除了仔细检查和写好run code找error和记code之外没找到好办法

public class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        while (left < right){
         int mid = (left+right)/2;
            if (nums[right] > nums[mid]){
          right = mid;
         }else if (nums[right] < nums[mid]){
          left = mid+1;
         }else{
          right--;
         }
        }
        return nums[left];
    }
}

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