一个月刷完cc150

3.2 Stack Min (leetcode 155. Min Stack)
Problem:
How would you design a stack which, in addition to push and pop, has a function min which returns the minimum element? Push, pop and min should all operate in 0(1) time.

Analysis:
We should maintain the minimum value. When the state rolls back to previous state, minimum value also rolls back to previous state. So we keep a roll of all minimum states. When we pop out the minimum value, we delete it from minimum stack to roll back to previous minimum state.

Code:
class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> min;
    /** initialize your data structure here. */
    /**
   
    5
    */
    public MinStack() {
        stack=new Stack<>();
        min=new Stack<>();
    }
   
    public void push(int x) {
        stack.push(x);
        if(x<=getMin()){
            min.push(x);
        }
        
    }
   
    public void pop() {
        if(getMin()==stack.pop()){
            min.pop();
        }
    }
   
    public int top() {
        return stack.peek();
    }
   
    public int getMin() {
        if(min.size()==0){
            return Integer.MAX_VALUE;
        }else{
            return min.peek();
        }
    }
}

/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/

4.10 (leetcode 110. Balanced Binary Tree)
Problem:
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Analysis:
We determine through calculating height from bottom up each node’s subtree’s balance.

Code:
public boolean isBalanced(TreeNode root) {
        return height(root)==-1? false: true;
}
   
   
public int height(TreeNode root){
        if(root==null)return 0;
        int left=height(root.left);
        if(left==-1)return -1;
        int right=height(root.right);
        if(right==-1)return -1;
        if(Math.abs(left-right)>1)return -1;
        return Math.max(left,right)+1;
}

cc150 4.2 Minimal Tree
Problem:
Given a sorted (increasing order) array with unique integer elements, write an algo-rithm to create a binary search tree with minimal height.

Analysis:
To make the search tree minimal height, we have to make the root middle value. So the left sub tree get the smaller half, and the right sub tree get the larger half. We use in-order traversal and recursion to allocate each node.

Code:
Public Node minTree(int[] nums){
    Return helper(mums, 0, mums.length-1);
}

Public Node helper(int[] nums, int start, int end){
    If(start > end){return null;}
    Int mid = start+(end-start)/2;
    Node root=new Node(mums[mid]);
    Root.left=helper(nums, start, mid-1);
    Root.right=helper(nums,mid+1,end);
    Return root;
}

楼主加油

之前ctci刷得差不多了，现在还剩第16章和第17章，从今天开始补刷一下

16.1
Problem:
Write a function to swap a number in place (that is, without temporary variables).

Analysis:
This problem could be solved by saving their difference in one of the variable(so no temporary).
a = b-a
Firstly store diference in a.
b = b-a
Secondly reduce difference in b, so b is storing value a.
a = b+a
Lastly add back difference in a so a is storing value b. Now both numbers are swapped.
(Mathematical: a1=b-a, b1=b-a1=b-(b-a)=a, a2=b1+a1=a+(b-a)=b)

Code:
public void swap(int a, int b){
    a=b-a;
    b=b-a;
    a=b+a;
}

16.2

Problem:
Design a method to find the frequency of occurrences of any given word in a book. What if we were running this algorithm multiple times?

Analysis:
This question is actually asking 2 circumstances. One is one time calculate issue, the other is re-usable calculation. For one time we can do iteration, for usable one we can do preprocess with has table.

Code:
1.One Time
public int findFreqOfWord(String word, String[] book){
    if(word==null || book==null){return -1;}
    int count=0;
    word=word.trim().toLowerCases();
    for(String s:book){
        if(word.trim().toLowerCases().equals(s)){
            count++;
        }
    }
    return count;
}

2.Re-usable
private Map<String,Integer> setDictionary(String[] book){
    if(book==null){return -1;}
    Map<String,Integer> dict=New HashMap<>();
    for(String word:book){
        word=word.trim().toLowerCases();
        dict.set(word,dict.getOrDefault(word,0)+1);
    }
    return dict;
}

public int getFreqFromDict(String word,Map<String,Integer> dict){
    if(book==null||dict==null){return -1;}
    return dict.getOrDefault(word.trim().toLowerCases(),0);
}

16.3
Problem:
Given two straight line segments (represented as a start point and an end point), compute the point of intersection, if any.

Analysis:
Basically we can think of the straight lines as infinite lines, and if the intersection of the infinite lines are within the straight lines, there is an intersection.
If the 2 lines are parallel: 1)start of second line is between first line start and end points, there is intersection which is second line start point. 2)else there’s no intersection

Code:
public Point getIntersection(Point start1,Point end1,Point start2,Point end2){
    Line l1,l2;
    setLinesOrder(start1,end1,start2,end2);
    //check if parallel
    if(l1.slope==l2.slope){
        if(inBetween(start1,start2,end1)){
            return start2;
        |else{
            return null;
        }
    }

    //not parallel, get intersection of infinite lines
    int interX=(l2.yintercept-l1.yintercept)/(l1.slope-l2.slope);
    int interY=l1.slope*interX+l1.yintercept;
    Point intersection=new Point(interX,interY);
    //check if intersection is between the points of 2 lines
    if(inBetween(start1,intersection,end1)&&inBetween(start2,intersection,end2)){
        return intersection;
    }
    return null;
}

public boolean inBetween(Point lo,Point mid,Point hi){
    if(lo.x<mid.x&&midx<hi.x){return true;}
    return false;
}

public void setLinesOrder(Point start1,Point end1,Point start2,Point end2){
    if(start1.x>end1.x){
        swap(start1,end1);
    }
    if(start2.x>end2.x){
        swap(start2,end2);
    }
    if(start1.x>start2.x){
        swap(start1,start2);
        swap(end1,end2);
    }
    l1=new Line(start1,end1);
    l2=new Line(start2,end2);
}

public void swap(Point p1,Point p2){
    int tmpX=p2.x,tmpY=p2.y;
    p2.setLocation(p1.x,p1.y);
    p1.setLocation(tmpX,tmpY);
}

public class Point{
    int x,y;

    public Point(int x, int y){
        this.x=x;
        this.y=y;
    }

    public setLocation(int x,int y){
        this.x=x;
        this.y=y;
    }
}

public class Line{
    int slope,yintercept;
   
    public Line(Point start,Point end){
        slope=(start.y-end.y)/(start.x-end.x);
        yintercept=end.y-slope*end.x;
    }
}

16.4
Problem:
Design an algorithm to figure out if someone has won a game of tic-tac-toe.

Analysis:
This problem could be 4 scenarios: 1)we use this method multiple times: we can store all possible boards and winner as int value using base-3 and boolean key-value set in hash table to look up. 2)we use this method one time: we can either check all 8 lines of winning scenario which is not scalable, or 3) look up all rows/columns/diagonals. 4)we use this method on N*N board: we can expand 3*3 board second method with iterator or directions passed to check.

Code:
enum Piece {Empty,Red,Blue};
1)multiple times:
public int boardToInt(Piece[][] board){
    int res=0;
    for(int row=0;row<board.length;row++){
        for(int col=0;col<board[0].length;col++){
            int p=board[row][col]==Piece.Empty?0:(board[row][col]==Piece.Red?1:2);
            res=res*3+p;
        }
    }
    return res;
}

2)one time with last move:
public Piece isWinner(Piece[][] board,int row,int col){
    Piece p=board[row][col];
    if(p==Piece.Empty){return Piece.Empty;}
    //if column/row is wining
    if(colWin(col,board)||rowWin(row,board)){return p;}

    //if diagonal is winning
    if(col==row&&diaWin(p,board,1)){return p;}
    if(col==board[0].length-1&&diaWin(p,board,-1)){return p;}

    return Piece.Empty;
}

public boolean diaWin(Piece p,Piece[][] board,int direction){
    int row=0,col=direction==1?0:board[0].length-1;
    while(row<board.length){
        if(board[row][col]!=board[p.row][p.col]){return false;}
        col+=direction;         
        row++;     
    }
    return true;
}

public boolean colWin(int col,Piece[][] board){
    for(int row=1;row<board.length;row++){
        if(board[row][col]!=board[0][col]){return false;}
    }
    return true;
}

public boolean rowWin(int row,Piece[][] board){
    for(int col=1;col<board[0].length;col++){
        if(board[row][col]!=board[row][0]){return false;}
    }
    return true;
}

3)one time without last move look up all rows/columns/diagonals
4)for N*N board
public Piece isWinner(Piece[][] board){
    int len=board.length;
    List<Direction> directions=new ArrayList<>();

    setUpDirections(len,directions);
    for(Direction direction:directions){
        Piece winner=check(board,direction);
        if(winner!=Piece.Empty){return winner;}
    }
}

public Piece check(Piece[][] board,Direction direction){
    Piece p=board[0][0];
    for(int row=direction.row,col=direction.col;row<board.length&&col<board[0].length&&row>=0&&col>=0;row+=direction.rowInc,col+=direction.colInc){
        if(board[row][col]!=p){return Piece.Empty;}
    }
    return p;
}

public void setUpDirections(int len,List<Direction> directions){
    //set up checker for rows and columns
    for(int i=0;i<len;i++){
        directions.add(new Direction(i,0,0,1));
        directions.add(new Direction(0,i,1,0));
    }
    //set up checker for diagonals
    directions.add(new Direction(0,0,1,1));
    directions.add(new Direction(0,len-1,1,-1));
}

public class Direction{
    int row,col,rowInc,colInc;

    public Direction(int row,int col,int rowInc,int colInc){
        this.row=row;
        this.col=col;
        this.rowInc=rowInc;
        this.colInc=colInc;
    }
}
   

16.5
Problem:
Write an algorithm which computes the number of trailing zeros in n factorial.

Analysis:
As known trailing zeros are decided by 10 factors, so we only need to know how many 10s are in the factors. As 10=2*5, basically we need to know how many (2,5) pairs are formed. As in factorial 2s are much more than 5s, so basically we need to know how many 5s are in the factors. The trick here is 25 has two 5s, and 125 has three 5s, etc.
So when counting 5s, first check for 5:the quotient is how many 5s are in the factors, add 1 for each; Then check for 25:the quotient is how many 25s are in the factors, we should add 2 for each but we already added 1 when counting 5, so add 1 for each; Then check for 125, the quotient is how many 125s are in factors, we should add 3 for each but we already added 2 when counting 25, so add 1 for each, etc.

Code:
public int trailingZeros(int num){
    int ans=0;
    for(int n=0;num/n>1;n*=5){
        int count=num/n;
        ans+=count*1;
    }   
    return ans;
}