1. git branch [-a] look at the branches you’ve visited
2. git branch create a new branch from the current commit version
3. git checkout -b
4. git -d branch_name
5. git merge
6. git stash
7. git push -f
8. git checkout
9. git checkout -b new_master
10. git branch -d master

Question:

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given “25525511135”,

return [“255.255.11.135”, “255.255.111.35”]. (Order does not matter)

Thinking:

Valid IP address is between 0 and 255, so we can once detect one to three digits of the string. What’s more, it’s not valid if there is number like “001”. Use bactracing select one to three digits once, and go farther until all the substrings are selected and there are four parts of the result. Then put the result in the list. We should also detect the length of the String because if the length is not between 4 and 12, it’s invalid.

Solution:

public List<String> restoreIpAddresses(String s) {
    List<String> res = new ArrayList<String>();

    if (s.length() < 4)
        return res;
    if (s.length() > 12)
        return res;

    backtracing(s, 0, new ArrayList<String>(), res);

    return res;
}

public void backtracing(String s, int start, List<String> tempres, List<String> res){
    if (start == s.length()){
        if (tempres.size() == 4){
            String tempstr = "";
            tempstr = tempres.get(0) + "." + tempres.get(1) + "." + tempres.get(2) + "." + tempres.get(3);
            res.add(tempstr);
        }
        else{
            return;
        }
    }

    for (int i = start+1; i <= s.length(); i++){
        if (s.charAt(start) == '0' && i != start+1)
            continue;
        if (i - start > 3)
            break;
        int num = Integer.parseInt(s.substring(start, i));
        if (num > 255)
            break;
        else{
            tempres.add(s.substring(start, i));
            backtracing(s, i, tempres, res);
            tempres.remove(tempres.size() - 1);
        }
    }
}

Question:

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

Thinking:

We should use backtracing to trace all the possible answers. In order to remove duplicate, there are two methods. One is to use hashset, the other is to build a visited array, if the same value is not visited, then don’t visit the value. And there two ways to backtracing, one is to use the return value, and the other is to pass the fucntion value.

Solution1:

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);
    return backtracing(candidates, target, 0);
}

public List<List<Integer>> backtracing(int [] candidates, int target, int left){
    HashSet<List<Integer>> tres = new HashSet<List<Integer>>();
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    int right = candidates.length-1;

    if (left > right){
        return res;
    }
    if (target < candidates[left]){
        return res;
    }
    if (target == candidates[left]){
        List<Integer> list = new ArrayList<Integer>();
        list.add(candidates[left]);
        res.add(list);
        return res;
    }
    if (left == right){
        return res;
    }

    for (int i = left; i <= right; i++){
        for (List<Integer> list: backtracing(candidates, target-candidates[i], i+1)){
            list.add(0, candidates[i]);
            tres.add(list);
        }
        for (List<Integer> list: backtracing(candidates, target, i+1)){
            tres.add(list);
        }
    }

    res.addAll(tres);
    return res;
}

Solution2:

public static ArrayList<List<Integer>> combinationSum2(int[] candidates, int target) {  
    ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();  
    ArrayList<Integer> item = new ArrayList<Integer>();
    if(candidates == null || candidates.length==0)  
        return res; 

    Arrays.sort(candidates);  
    boolean [] visited = new boolean[candidates.length];
    helper(candidates,target, 0, item ,res, visited);  
    return res;  
}  

private static void helper(int[] candidates, int target, int start, List<Integer> item,   
ArrayList<List<Integer>> res, boolean[] visited){  
    if(target<0)  
        return;  
    if(target==0){  
        res.add(new ArrayList<Integer>(item));  
        return;
    }

    for(int i=start;i<candidates.length;i++){
        if(!visited[i]){
            if(i>0 && candidates[i] == candidates[i-1] && visited[i-1]==false)//deal with dupicate
                continue;  
            item.add(candidates[i]);
            visited[i]=true;
            int newtarget = target - candidates[i];
            helper(candidates,newtarget,i+1,item,res,visited);  
            visited[i]=false;
            item.remove(item.size()-1);  
        }
    }  
}

Question:

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

Thinking:

It’s similar with Reverse Linked List, only thing different is to limit the range. So we should to find the start of the reversed linked list and record its previous node. Also, we should add a dummy node for easily operator with the first node. Then use three points as usual pre, cur and next to operate and change the nodes’ next pointers.

Solution:

public ListNode reverseBetween(ListNode head, int m, int n) {
    if (m == n)
        return head;
    ListNode prehead = new ListNode(0);//dummy
    prehead.next = head;
    ListNode pre = prehead;
    ListNode cur = head;
    int idx = 1;

    while (idx < m) {
        pre = cur;
        cur = cur.next;
        idx++;
    }
    ListNode prerever = pre;
    ListNode next = null;
    pre = cur;
    cur = cur.next;
    while (idx < n) {
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
        idx++;
    }
    prerever.next.next = cur;
    prerever.next = pre;


    return prehead.next;
}

Question:

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:
nums = [1, 3], n = 6
Return 1.

Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

Example 2:
nums = [1, 5, 10], n = 20
Return 2.
The two patches can be [2, 4].

Example 3:
nums = [1, 2, 2], n = 5
Return 0.

Thinking:

The first range we can cover of an array is total, then if we add a new element to this array and this element add <= total, then the new range is [1, add+total). We should also care about the java maxint value, so if we use bit manipulation, it means it is bigger than maxint if total is smaller than zero.

Solution:

public int minPatches(int[] nums, int n) {
    int total = 1; //total is the upper bound of the sum
    int count = 0;
    int index = 0;
    int len = nums.length;

    while (total <= n) {
        if (index < len && nums[index] <= total){
            total += nums[index++];
        }
        else{
            total <<= 1;
            count++;
            if (total < 0)
                break;
        }
    }


    return count;
}