Code School - Git Real

Level 2: Staging & Remotes

Undo Commit Commands

1. git reset --soft HEAD^

Undo last commit (the changes will be keep in staging)

2. git commit --amend -m "new message"

Change the last commit

3. git reset --hard HEAD^

Undo last commit and all changes (hard reset will not keep the change)

4. git reset --hard HEAD^^

Undo last 2 commits and all changes

Adding a remote

git remote add origin https://github.com/name/git-real.git

    new remote   name of the remote                 address

kind of like bookmark, means 'origin' referring the above url address

git remote -v

Show all remote repositories

Change commit with one command

git commit --amend -m "change last commit with one command"

Check out file with current branch?

git checkout -- filename.fileext

=============================================================

Level 3: Cloning & Branching

Clone a repository

git clone

Clone a repository

git remote -v

list all the remotes ?

Checkout branch

1. git branch newBranch

create a new branch

2. git checkout newBranch

checkout the new branch

(same as)

1. git checkout -b newBranch

create a new branch and checkout

Merge branch

step 1: git checkout master

switch back to the main branch u want ur change to goes in

step 2: git merge branchToMerge

merge the temp branch to be merged

step 3: git branch -d branchToMerge

remove the temp branch

=============================================================

Level 4: Collaboration Basics

About pull

1. git pull

get latest code and update local code

(same as)

1. git fetch

get latest code from remote branch

2. git merge origin/master

merge remote master into local branch (update local code)

=============================================================

Level 5: Branching

Pulling New Branches

1. git branch -r

show all remote branches

2. git checkout remoteBranchName

checkout remote branch, already automatic link this local branch to the remote branch?

Removing a Branch

1. git push origin :remoteBranch

delete remote branch

2. git branch -d localBranch

delete local branch (if has uncommitted change, will get error)

3. git branch -D localBranch

force delete local branch

Manage remote branches

1. git remote show origin

show all remote and local branches, and their status (may have the ref to deleted remote branch)

2. git remote prune origin

to clean up deleted remote branches

Tagging (version)

1. git tag

list all tags

2. git tab -a v0.0.2 -m "version 0.0.2"

create a new tag

3. git push --tags

push new tags

4. git checkout v1.0.1

checkout or retrieve a previous version tag

=============================================================

Level 6: Rebase Belong to us

Rebase

1. git fetch

get(retrieve) remote changes

2. git rebase targetBranch

(get change from the current branch and put on top of the targetBranch?)

move all changes to master which are not in origin/master to a temp area

run all origin/master commits

run all commits in the temp area, one at a time (redo commits one by one)

2.1. git rebase --continue

if has conflict, fix the conflict then continue rebase

2.2. git rebase --abort

if want to stop rebase

3. git merge fromBranch

merge the fromBranch(just rebased) to targetBranch?

=============================================================

Level 7: History and Configuration

Config display

git config --global color.ui true

turn on colorizing the log

Output log with format

git log --pretty=oneline

display one commit in one line

git log --pretty=format:"%h %ad- %s [%an]"

%ad : author date

%an : author name

%h : SHA hash

%s : subject

%d : ref names

git log --oneline -p

patch the change with history

git log --oneline --stat

show how many changes (number)

git log --oneline --graph

show commits history with graph (simple)

git log --until=1.minute.ago

git log --until=1.day.ago

git log --until=1.hour.ago

git log --since=1.month.ago --until=2.weeks.ago

git log --since=2000-01-01 --until=2000-02-02

show log within date range

Show diff with format

git diff

(same as)

git diff HEAD

git diff HEAD^

git diff HEAD ^^

git diff HEAD~5

git diff HEAD^..HEAD 

compare second most recent commit with most resent commit

git diff SHAShashNum1..SHAShashNum2

Show diff with format

git diff branch1 branch2

git diff --since=time1 --until=time2

Blame

git blame file.ext --date short

Untracking Files

git rm --cashed file.ext

use when u want to untracking the file without remove it

See all local config

git config --list

Setup Aliases

1. 
git config --global alias.mylog \
"log --pretty=format:'%h %s [%an]'" --graph
2.
git mylog

pre-set log format for easy use later


1. git config --global alias.st status
2. git st
(same as)
git status

LeetCode - Evaluate Reverse Polish Notation

Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Solution:

public class Solution {
    public int evalRPN(String[] tokens) {
        int res = 0;
        if(tokens.length == 0) return res;
        
        // build a stack for this kind of problem
        String operators = "+-*/";
        Stack<string> stack = new Stack<string>();
        
        for(String s : tokens) {
            // if s is not an valid operator, then s is a num, push in stack
            if(!operators.contains(s)) {
                stack.push(s);
            } 
            // if s is an valid operator, pop two nums, calculate, push back
            else {
                int a = Integer.valueOf(stack.pop());
                int b = Integer.valueOf(stack.pop());
                
                // caculate
                switch(s) {
                    case "+" : stack.push(String.valueOf(a + b)); break;
                    case "-" : stack.push(String.valueOf(b - a)); break;
                    case "*" : stack.push(String.valueOf(a * b)); break;
                    case "/" : stack.push(String.valueOf(b / a)); break;
                }
            }
        }
        
        // after loop, pop the last num as res
        res = Integer.valueOf(stack.pop());
        
        return res;
    }
}

Thanks to: http://www.programcreek.com/2012/12/leetcode-evaluate-reverse-polish-notation/

==========================

The hardest part is not about solving the problem, but to keep learning and last forever... 

Leetcode - Reverse Words in a String

Reverse Words in a String

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

click to show clarification.

Clarification:

• What constitutes a word?
  A sequence of non-space characters constitutes a word.
• Could the input string contain leading or trailing spaces?
  Yes. However, your reversed string should not contain leading or trailing spaces.
• How about multiple spaces between two words?
  Reduce them to a single space in the reversed string.

Solution:

public class Solution {
    public String reverseWords(String s) {
        if(s.isEmpty() || s.length() == 0)   return s;
        
        StringBuffer res = new StringBuffer();
        
        int t, h;
        for(int i = s.length() - 1; i >= 0; i--) {
            while(i >= 0 && s.charAt(i) == ' ') i--;
            
            // set tail pointer
            if(i < 0) break;
            t = i;
            h = t;
            
            // set head pointer
            while(i >= 0 && s.charAt(i) != ' ') { h = i; i--; }
            
            // append this word (append a space if find more than two words)
            if(h <= t && res.length() > 0) res.append(' ');
            for(int j = h; j <= t; j++) {
                res.append(s.charAt(j));
            }
        }
        
        return res.toString();
    }
}

-------------------------------------
OK, finally i'm back! second round, go~

Leetcode - Unique Paths

Unique Paths

 

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Solution #1: (Recursive, O(n^2), Time Limit Exceeded...)

// recursive
public class Solution {
    public int uniquePaths(int m, int n) {
        return backtrack(0, 0, m, n);
    }
    
    private int backtrack(int row, int col, int m, int n) {
        // to the target
        if(row == m - 1 && col == n - 1)
            return 1;
        // out of range
        if(row > m - 1 || col > n - 1)
            return 0;
            
        // move down + move right
        return backtrack(row + 1, col, m, n) + backtrack(row, col + 1, m, n);
    }
}

Solution #2: loop, O(n^2) space & time

// loop, similar as min path sum, O(n^2) time & space
public class Solution {
    public int uniquePaths(int m, int n) {
        int[][] res = new int[m][n];
        
        // init left
        for(int i = 0; i < m; i++) {
            res[i][0] = 1;
        }
        // init top
        for(int j = 0; j < n; j++) {
            res[0][j] = 1;
        }
        
        // add values
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                res[i][j] = res[i - 1][j] + res[i][j - 1];
            }
        }
        
        return res[m - 1][n - 1];
    }
}

Solution #3: loop, O(n^2) time, O(n) space

// loop, similar as min path sum, O(n^2) time, O(n) space
public class Solution {
    public int uniquePaths(int m, int n) {
        int[] res = new int[n];
        
        // init array
        for(int j = 0; j < n; j++) {
            res[j] = 1;
        }
        
        // add values
        for(int i = 1; i < m; i++) {
            // reset the head to 1 (simulate the next row head)
            // similar to set all left most elements in a 2D array to 1
            res[0] = 1;
            for(int j = 1; j < n; j++) {
                res[j] = res[j - 1] + res[j];
            }
        }
        
        return res[n - 1];
    }
}

Many thanks to:
http://cuijing.org/interview/leetcode/summary-of-dynamic-programming-in-leetcode.html
&
http://yucoding.blogspot.com/2013/04/leetcode-question-116-unique-path-i.html

Leetcode - Minimum Path Sum

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

Solution #1:

// DP, O(n^2) time, O(n^2) space
public class Solution {
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        
        int[][] res = new int[row][col];
        // init
        res[0][0] = grid[0][0];
        
        // left
        for(int i = 1; i < row; i++) {
            res[i][0] = res[i - 1][0] + grid[i][0];
        }
        // top
        for(int j = 1; j < col; j++) {
            res[0][j] = res[0][j - 1] + grid[0][j];
        }
        
        // rest elements
        for(int i = 1; i < row; i++) {
            for(int j = 1; j < col; j++) {
                res[i][j] = grid[i][j] + Math.min(res[i - 1][j], res[i][j - 1]);
            }
        }
        
        return res[row - 1][col - 1];
    }
}

Solution #2:

// DP, O(n^2) time, O(n) space
public class Solution {
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        
        int[] res = new int[col];
        // init
        Arrays.fill(res, Integer.MAX_VALUE);
        res[0] = 0;
        
        // rest elements
        for(int i = 0; i < row; i++) {
            // init the 0th sum = old 0th element + the new 0th element
            // just init the 0th column every time dynamically
            res[0] = res[0] + grid[i][0];
            
            // loop through each element of each row
            for(int j = 1; j < col; j++) {
                res[j] = grid[i][j] + Math.min(res[j], res[j - 1]);
            }
        }
        
        return res[col - 1];
    }
}

Many thanks to: http://fisherlei.blogspot.com/2012/12/leetcode-minimum-path-sum.html

Leetcode - Maximum Subarray

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

click to show more practice.

More practice: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

 1. Solution #1, O(n)
Just simply loop from left to right and return the max val.

// O(n)
public class Solution {
    public int maxSubArray(int[] A) {
        int sum = 0;
        int maxSum = Integer.MIN_VALUE;
        for(int i = 0; i < A.length; i++) {
            sum += A[i];
            maxSum = Math.max(maxSum, sum);
            // re-set sum when < 0 (no need to keep neg value)
            if(sum < 0) sum = 0;
        }
        return maxSum;
    }
}

2. Solution #2, Divide and conquer, O(n) also?
The max range can be in the left half, or in the right half, or across the mid of the array, so we just divide it to tree parts and recursive until we get the max value of each part, and then get the largest value.

// Devide and Conquer
public class Solution {
    public int maxSubArray(int[] A) {
        int maxSum = Integer.MIN_VALUE;
        return findMaxSub(A, 0, A.length - 1, maxSum);
    }
    
    // recursive to find max sum 
    // may appear on the left or right part, or across mid(from left to right)
    public int findMaxSub(int[] A, int left, int right, int maxSum) {
        if(left > right)    return Integer.MIN_VALUE;
        
        // get max sub sum from both left and right cases
        int mid = (left + right) / 2;
        int leftMax = findMaxSub(A, left, mid - 1, maxSum);
        int rightMax = findMaxSub(A, mid + 1, right, maxSum);
        maxSum = Math.max(maxSum, Math.max(leftMax, rightMax));
        
        // get max sum of this range (case: across mid)
        // so need to expend to both left and right using mid as center
        // mid -> left
        int sum = 0, midLeftMax = 0;
        for(int i = mid - 1; i >= left; i--) {
            sum += A[i];
            if(sum > midLeftMax)    midLeftMax = sum;
        }
        // mid -> right
        int midRightMax = 0; sum = 0;
        for(int i = mid + 1; i <= right; i++) {
            sum += A[i];
            if(sum > midRightMax)    midRightMax = sum;
        }
        
        // get the max value from the left, right and across mid
        maxSum = Math.max(maxSum, midLeftMax + midRightMax + A[mid]);
        
        return maxSum;
    }
}

Thanks to : http://fisherlei.blogspot.com/2012/12/leetcode-maximum-subarray.html

Leetcode - Rotate Image

Rotate Image

You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?

public class Solution {
    public void rotate(int[][] matrix) {
        if(matrix == null)  return;
        int n = matrix.length;
        // n * n matrix
        //int w = matrix[0].length;
        if(n < 2) return;
        
        // rule: i = j'; j = n-1 - i';
        // that is: i' = n-1 -j; j' = i;
        // loop through 1/4 of the matrix
        // a | b
        // c | d
        // four parts
        // Math.ceil : returns the smallest integer >= a number.
        for(int i = 0; i < n/2; i++) {
            for(int j = 0; j < Math.ceil(((double)n)/2.0); j++) {
                int tmp = matrix[i][j];
                
                // c -> a
                matrix[i][j] = matrix[n-1 - j][i];
                // d -> c
                matrix[n-1 - j][i] = matrix[n-1 - i][n-1 - j];
                // b -> d
                matrix[n-1 - i][n-1 - j] = matrix[j][n-1 - i];
                // a -> b (tmp -> b)
                matrix[j][n-1 - i] = tmp;
            }
        }
    }
}