支持removerandom的hashtable

class RandomHashTable{
    private List<Object> list = new ArrayList<Object>();
    private Map<Object, Object> table = new Hashtable<Object, Object>();
    
    public void put(Object k, Object v){
        table.put(k,v);
        if(!table.containsKey(k))
            list.add(k);
    }
    public Object removeKey(Object k){
        list.remove(k);
        return table.remove(k);
    }
    public Object get(Object k){
        return table.get(k);
    }
    public Object removeRandom(){
        Object k = getRandom();
        return removeKey(k);
    }
    public Object getRandom(){
        if(table.size()==0) return null;
        Random ran = new Random();
        return list.get(ran.nextInt(list.size()));
    }  
}
//put、get、remove、random均为O(1), 不一定是hashtable
class RandomClass{
    private List<Object> list = new ArrayList<Object>();
    private Map<Object, Integer> table = new Hashtable<Object, Integer>();
    public void put(Object k){
        list.add(k);
        table.put(k, list.size()-1);
    }
    public void remove(Object k){
        int index = table.get(k);
        table.remove(k);
        list.set(index, list.get(list.size()-1));
        table.put(list.get(index), index);
        list.remove(list.size()-1);
    }
    public Object getRandom(){
        if(list.size()==0) return null;
        Random ran = new Random();
        return list.get(ran.nextInt(list.size()));
    }
}

实现hashmap

若是thread-safe，用synchronized就ok了

class Entry<K, V>{
    private final K key;
    private V value;
    Entry<K,V> next;
    
    Entry(K k, V v){
        key = k;
        value = v;
    }
    public K getKey(){
        return key;
    }
    public V getValue(){
        return value;
    }
    public V setValue(V v){
        V old = value;
        value = v;
        return old;
    }
    public boolean equals(Object o){
        if(!(o instanceof Entry))
                return false;
        Entry<K,V> e = (Entry<K,V>) o;
        return (this.getKey()==null ? e.getKey()==null : this.getKey().equals(e.getKey())) && (this.getValue()==null ? e.getValue()==null : e.getValue().equals(e.getValue()));  
    }
    public final int hashCode() {
        return (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode());
    }
}


class HashMap<K, V>{
    private static final int size = 16;
    private Entry[] table ;
    
    public HashMap(){
        table = new Entry[size];
    }
 
    public int getIndex(int hashcode, int length){
        return hashcode % length;
    }
    
    public V get(K k){
        int i = getIndex(k.hashCode(), size);
        Entry<K, V> e = table[i];
        while(e!=null){
            if(e.getKey().equals(k))
                return e.getValue();
            e = e.next;
        }
        return null;
    }
    
    public V put(K k, V v){
        int i = getIndex(k.hashCode(), size);
        Entry<K, V> e = table[i];
        if(e!=null){
            if(e.getKey().equals(k)){
                V old = e.getValue();
                e.setValue(v);
                return old;
            }else{
                while(e.next!=null)
                    e = e.next;
                Entry<K, V> newEntry = new Entry<K, V>(k, v);
                e.next = newEntry;
            }
        }else{
            table[i] = new Entry<K,V>(k,v);
        }
        return null;
    }
}

Leetcode - Valid Sudoku && Sudoku Solver

I: Valid Sudoku
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

[Thoughts]:

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                if(board[i][j]=='.')
                    continue;
                else if(!isValid(board, i, j))
                    return false;
            }
        }
        return true;
    }
    
    public boolean isValid(char[][] board, int x, int y){
        for(int i=0; i<9; i++){
            if(i!=x && board[i][y]==board[x][y])
                return false;
            if(i!=y && board[x][i]==board[x][y])
                return false;
        }
        //这一题的重点就是check小框框里的是否是数独
        for(int i=3*(x/3); i<3*(x/3+1); i++){
            for(int j=3*(y/3); j<3*(y/3+1); j++){
                if(i!=x && j!=y && board[i][j]==board[x][y])
                    return false;
            }
        }
        return true;
    }
}

II: Write a program to solve a Sudoku puzzle by filling the empty cells.
[Thoughts]:

public class Solution {
    public void solveSudoku(char[][] board) {
        solver(board);
    }
    public boolean solver(char[][] board){
        for(int i=0; i<9;  i++){
            for(int j=0; j<9; j++){
               //上面的两个for只是在找下一个‘.‘的位置，并不会起到迭代作用，下面的if要么返回true，要么false 
                if(board[i][j]=='.'){
                    for(char num='1'; num<='9'; num++){
                        board[i][j] = num;
                        if(isValid(board, i, j) && solver(board))//solver递归，
                            return true;
                        board[i][j] = '.';
                    }
                    return false;
                }
            }
        }
        return true;
    }
    public boolean isValid(char[][] board, int x, int y){
        for(int i=0; i<9; i++)
            if(i!=x && board[i][y]==board[x][y])
                return false;
        for(int i=0; i<9; i++)
            if(i!=y && board[x][i]==board[x][y])
                return false;
        for(int i=3*(x/3); i<3*(x/3+1); i++){
            for(int j=3*(y/3); j<3*(y/3+1); j++){
                if(i!=x && j!=y && board[i][j]==board[x][y])
                    return false;
            }
        }
        
        return true;
    }
}

Leetcode - Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

[Thoughts]:对于任意位置i， 计算这一点左边最高和右边最高， 小的那个减去i位置，就是i位置应该有的存水量

public class Solution {
    public int trap(int[] A) {
        if(A.length < 2)  return 0;  

        int[] left = new int[A.length];  
        int[] right = new int[A.length];  
          
        left[0] = A[0];  
        for(int i=1; i<A.length; i++)
            left[i] = Math.max(left[i-1], A[i]);  
          
        right[A.length-1] = A[A.length-1];  
        for(int i=A.length-2; i>=0; i--)
            right[i] = Math.max(right[i+1], A[i]);  
          
        int sum = 0;  
        for(int i=1; i<A.length-1; i++)
            sum += Math.min(left[i], right[i]) - A[i];  
          
        return sum;  
    }
}

Best Time to Buy and Sell Stock I && II && III

Say you have an array for which the ith element is the price of a given stock on day i.
I: If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
[Thoughts]: 从左往右遍历最大的price减去最小的price就是最大的profit。

public class Solution {
    public int maxProfit(int[] prices) {
        int min = Integer.MAX_VALUE;
        int max = 0, diff = 0;
        
        for(int i : prices){
            if(i<min)
                min = i;
            max = Math.max(max, i-min);
        }    
        return max;
    }
}

II: Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

public class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        
        for(int i=1; i<prices.length; i++)
            profit += prices[i]-prices[i-1] > 0 ? prices[i]-prices[i-1] : 0;
            
        return profit;

    }
}

III: Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
[Thoughts]: 
create两个数组，left 和right。计算left和right的过程和题I一样。
left[i] = i左边(inclusive i）若只完成一次交易能够获得的最大profit。
right[i] = i右边（inclusive i）若只完成一次交易能够获得的最大profit。
left[i] + right[i]便是完成两次交易获得的最大profit。

public class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if(len==0) return 0;
        
        int[] left = new int[len];
        int[] right = new int[len];
        
        calculatePro(left, right, prices);
        
        int max = Integer.MIN_VALUE;
        for(int i=0; i<len; i++)
            max = Math.max(max, left[i]+right[i]);
        return max;
    }
    
    public void calculatePro(int[] left, int[] right, int[] p){
        left[0] = 0;
        int min = p[0];
        for(int i=1; i<p.length; i++){
            left[i] = Math.max(left[i-1], p[i]-min);
            min = Math.min(p[i], min);
        }
        
        right[p.length-1] = 0;
        int max = p[p.length-1];
        for(int i=p.length-2; i>=0; i--){
            right[i] = Math.max(max-p[i], right[i+1]);
            max = Math.max(p[i], max);
        }
    }
}

Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

log(n^2)的方法是比较容易想到的，每个点都试一下能不能通过，但肯定是通不过大数据的。
1，计算所有gas[i]-cost[i]的和，如果大约0，那么必然有一点可以保证从那点出发有足够的油可以走一圈。
2，知道1之后，我们可以不断更新start

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if(gas.length==0 || cost.length==0 || gas.length!=cost.length)
            return -1;
            
        int start = 0, left = 0, sum = 0;

        for(int i=0; i<gas.length; i++){
            sum += gas[i]-cost[i];
            left += gas[i]-cost[i];

            if(left<0){//如果小于0，start点不满足，start被更新为i+1
                start = i+1;
                left = 0;
            }
        }
        return sum>=0 ? start : -1;     
    }
}

Candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

不知道这种题意义何在， 数学基础 or 数组操作？
1，每个小孩先一人分一个糖；
2，从左往右走一遍，右边比左边大的多给一块（Math.max(candy[i], candy[i-1]+1));
3，从右往左走一遍，左边比右边大的多给一块；
4，计算给的candy总数。

第三步和第四步可和到一个循环。  不晓得有没有一个循环的方法....

public class Solution {
    public int candy(int[] ratings) {
        if(ratings.length==0) return 0;
        int[] candy = new int[ratings.length];
        Arrays.fill(candy, 1);//note1
        
        for(int i=1; i<ratings.length; i++){//note2
            if(ratings[i]>ratings[i-1])
                candy[i] = Math.max(candy[i], candy[i-1]+1);
        }
        
        int sum = candy[ratings.length-1];
        for(int i=ratings.length-2; i>=0; i--){//note3
            if(ratings[i]>ratings[i+1])
                candy[i] = Math.max(candy[i], candy[i+1]+1);
            sum +=candy[i];//note4
        }
    
        return sum;
    }
}

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

[Note]:
1, 建立两个数组，left和right， left[i]代表i位置左边最大的值，right[i]代表i位置右边最大的值。
2, 分别从左往右扫一遍，和从右往左扫一遍，更新left和right数组。
3, 从头到尾扫数组，Math.min(left[i], right[i]) - A[i]便是i位置可以存的水量。

public class Solution {
    public int trap(int[] A) {
        if(A.length < 2)  return 0;  

        int[] left = new int[A.length];  
        int[] right = new int[A.length];  
          
        left[0] = A[0];  
        for(int i=1; i<A.length; i++)//note1
            left[i] = Math.max(left[i-1], A[i]);  
          
        right[A.length-1] = A[A.length-1];  
        for(int i=A.length-2; i>=0; i--)//note2
            right[i] = Math.max(right[i+1], A[i]);  
          
        int sum = 0;  
        for(int i=1; i<A.length-1; i++)//note3
            sum += Math.min(left[i], right[i]) - A[i];  
          
        return sum;  
    }
}