剑指Offer边读边记

public boolean Find(int target, int [][] array) {
    if(array == null || array.length == 0 || array[0].length == 0)    return false;
    int rowLen = array.length;
    int colLen = array[0].length;
    for(int i=0;i<rowLen;++i){
        if(target == array[i][0] || target == array[i][colLen - 1])
            return true;
        else if(target < array[i][0])
            return false;
        else if(target > array[i][colLen - 1])
            continue;
        else{
            if(binarySearch(target,array[i]))
                return true;
        }
    }
    return false;
}
    
private boolean binarySearch(int target,int [] arr){
    int low = 0,high = arr.length - 1;
    while(low <= high){
        int mid = low + (high - low)/2;
        if(arr[mid] == target){
            return true;
        }else if(arr[mid] < target){
            low = mid + 1;
        }else if(arr[mid] > target){
            high = mid - 1;
        }
    }
    return false;
}

public void reOrderArray(int [] array) {
    int length = array.length;
    if(array == null || length <= 1)    return ;
    for(int i = 0;i < length;++i){
        int j = i+1;
        if((array[i]&0x1) == 0){//第一个偶数
            while((array[j]&0x1) == 0){//找到下一个奇数
                if(j == length - 1){
                    return;
                }
                j++;
            }
            int cnt = j - i - 1;
            int temp = array[i];
            array[i] = array[j];
            while(cnt>0){
                array[i+cnt+1] = array[i+cnt];
                cnt--;
            }
            array[i+1] = temp;
        }
    }
}

import java.util.ArrayList;

public ArrayList<Integer> printMatrix(int [][] matrix) {
    ArrayList<Integer> res = new ArrayList<>();
    if(matrix == null || matrix.length == 0 || matrix[0].length == 0)    return res;
    
    int rowLen = matrix.length,colLen = matrix[0].length;
    int sum = (Math.min(rowLen,colLen)+1)/2;
    for(int cnt = 0;cnt<sum;cnt++){
        for(int i = cnt;i<colLen-cnt;i++){
            res.add(matrix[cnt][i]);
        }
        for(int i = cnt + 1;i<rowLen-cnt;i++){
            res.add(matrix[i][colLen - 1 - cnt]);
        }
        for(int i=(colLen-1)-(cnt+1);i>=cnt&&(rowLen - 1 - cnt)!=cnt;i--){
            res.add(matrix[rowLen-1-cnt][i]);
        }for(int i=(rowLen-1)-(cnt+1);i>=cnt+1 && (colLen - 1 - cnt)!=cnt;i--){
            res.add(matrix[i][cnt]);
        }
    }
    return res;
}

public int MoreThanHalfNum_Solution(int [] array) {
    if(array == null || array.length == 0)    return 0;
    int pre = array[0];
    int count = 1;
    //找到可能的备选数
    for(int i = 0;i < array.length;++i){
        if(array[i] == pre)
            count ++;
        else{
            count --;
            if(count == 0){
                pre = array[i];
                count = 1;
            }
        }
    }
    //判断是否满足出现次数超过一半
    int num = 0;
    for(int i = 0;i<array.length;++i){
        if(array[i] == pre)
            num++;
    }
    return (num > array.length/2) ? pre : 0;
}

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
    ArrayList<Integer> result = new ArrayList<>();
    if(input == null || input.length == 0 || k <=0 || k > input.length) return result;
    Arrays.sort(input);
    for(int i = 0 ;i<k;i++){
        result.add(input[i]);
    }
    return result;
}

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
    ArrayList<Integer> result = new ArrayList<>();
    if(input == null || k <= 0 || k > input.length)   return result;
    int start = 0, end = input.length - 1;
    int index = partition(input,start,end);
    while(index != k - 1){
        if(index < k - 1){
            start = index + 1;
            index = partition(input,start,end);
        }else{
            end = index - 1;
            index = partition(input,start,end);
        }
    }
    for(int i = 0;i<k;++i){
        result.add(input[i]);
    }
    return result;
}

private int partition(int []arr,int low,int high){
    int pivot = arr[low];
    while(low < high){
        while(low < high && arr[high] >= pivot)
            --high;
        arr[low] = arr[high];
        while(low < high && arr[low] <= pivot)
            ++low;
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}
//https://www.cnblogs.com/yongh/p/9944155.html

public int FindGreatestSumOfSubArray(int[] array) {
    if(array == null || array.length == 0)    return 0;
    int[] dp = new int[array.length];

    int max = array[0];
    dp[0] = array[0];
    for(int i = 1;i<array.length;i++){
        dp[i] = Math.max(dp[i-1] + array[i],array[i]);
        max = Math.max(max,dp[i]);
    }
    return max;
}

public String PrintMinNumber(int [] numbers) {
    if(numbers == null || numbers.length == 0) return "";
    for(int i = 0;i<numbers.length - 1;++i){
        for(int j = i+1;j<numbers.length;++j){
            int sum1 = Integer.parseInt(numbers[i]+""+numbers[j]);
            int sum2 = Integer.parseInt(numbers[j]+""+numbers[i]);
            if(sum1 > sum2){
                int temp = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = temp;
            }
        }
    }
    StringBuilder sb = new StringBuilder();
    for(int i = 0;i<numbers.length;i++){
        sb.append(numbers[i]);
    }
    return sb.toString();
}

public int InversePairs(int [] array) {
    if(array == null || array.length == 0)    return 0;
    int count = getCount(array,0,array.length-1);
    return count;
}

private int getCount(int[] array,int low,int high){
    if(low>=high)    return 0;
    int mid = low + (high - low)/2;
    int left = getCount(array,low,mid)% 1000000007;
    int right = getCount(array,mid+1,high)% 1000000007;

    int count = 0;
    int i = mid;//前一部分末尾
    int j = high;//后一部分末尾
    int[] temp = new int[high-low+1];
    int k = high - low;

    while(i>=low && j >= mid+1){
        if(array[i] > array[j]){
            count += (j-mid);//后部分当前位置减去后部分的开头，其实是j-(mid+1)+1
            temp[k--] = array[i--];
            if(count >= 1000000007)
                count %= 1000000007;
        }else{
            temp[k--] = array[j--];
        }
    }
    while(i>=low){
        temp[k--] = array[i--];
    }
    while(j>=mid+1){
        temp[k--] = array[j--];
    }
    for(k=0;k<temp.length;k++){//把这段数组排好序后赋值回去，以免重复计算
        array[low+k] = temp[k];
    }

    return (count + left + right)% 1000000007;
}
//https://www.cnblogs.com/yongh/p/9955977.html

public int GetNumberOfK(int [] array , int k) {
    if(array == null || array.length <= 0)    return 0;
    int first = getFirst(array,k);
    int last = getLast(array,k);
    int count = 0;
    if(first > -1 && last > -1)
        count = last - first + 1;
    return count;
}
    
private int getFirst(int[] array,int target){
    int left = 0, right = array.length - 1;
    while (left <= right) {
    int mid = left + (right - left) / 2;
    if (array[mid] < target) {
            left = mid + 1;
        }else if (array[mid] > target) {
            right = mid - 1;
        }else if (array[mid] == target) {
            // 别返回，锁定左侧边界
            right = mid - 1;
        }
    }
    // 最后要检查 left 越界的情况
    if (left >= array.length || array[left] != target)
        return -1;
    return left;
}
    
private int getLast(int[] array,int target){
    int left = 0, right = array.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (array[mid] < target) {
            left = mid + 1;
        } else if (array[mid] > target) {
            right = mid - 1;
        } else if (array[mid] == target) {
            // 别返回，锁定右侧边界
            left = mid + 1;
        }
    }
    // 最后要检查 right 越界的情况
    if (right < 0 || array[right] != target)
        return -1;
    return right;
}
//https://www.cnblogs.com/yongh/p/9957949.html

//https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247485044&idx=1&sn=e6b95782141c17abe206bfe2323a4226&chksm=9bd7f87caca0716aa5add0ddddce0bfe06f1f878aafb35113644ebf0cf0bfe51659da1c1b733&scene=21#wechat_redirect

解法一：HashMap的方法。时间复杂度O(n),空间复杂度O(n)
import java.util.HashMap;

public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
    if(array == null || array.length <= 0)    return ;
    HashMap<Integer,Integer> map = new HashMap<>();
    for(int i = 0;i < array.length;++i){
        if(map.containsKey(array[i]))
            map.put(array[i],2);
        else
            map.put(array[i],1);
    }
    int count = 0;
    for(int i = 0;i < array.length;++i){
        if(map.get(array[i]) == 1){
            if(count == 0){
                num1[0] = array[i];
                count ++;
            }else{
                num2[0] = array[i];
            }
        }
    }
}

解法二：异或。时间复杂度O(n),空间复杂度O(1)
https://www.cnblogs.com/yongh/p/9960018.html

public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
    ArrayList<Integer> result = new ArrayList<>();
    if(array == null || array.length <= 0)    return result;
    int low = 0,high = array.length - 1;
    while(low <= high){
        int temp = array[low] + array[high];
        if(temp == sum){
            result.add(array[low]);
            result.add(array[high]);
            break;
        }else if(temp > sum){
            high --;
        }else if(temp < sum){
            low++;
        }
    }
    return result;
}

public boolean duplicate(int numbers[],int length,int [] duplication) {
    if(numbers == null)    return false;
    int i = 0;
    while(i < length){
        if(numbers[i] == i){
            i++;
            continue;
        }
        if(numbers[numbers[i]] == numbers[i]){
            duplication[0] = numbers[i];
            return true;
        }    
        int temp = numbers[i];
        numbers[i] = numbers[temp];
        numbers[temp] = temp;
    }
    return false;
}

import java.util.*;
public boolean duplicate(int numbers[],int length,int [] duplication) {
    if(numbers == null || length <= 0)    return false;
    Set<Integer> set = new HashSet<>();
    int ith = 0;
    for(int i = 0;i < length;++i){
        if(set.contains(numbers[i])){
            duplication[ith++] = numbers[i];
            if(ith == 1){
                return true;
            }
        }else{
            set.add(numbers[i]);
        }
    }
    return false;
}

public int[] multiply(int[] A) {
    if(A == null || A.length == 0)    return null;
    int[] B = new int[A.length];
    B[0] = 1;
    for(int i= 1;i<A.length;++i){
        B[i] = B[i-1] * A[i-1];
    }
    int temp = 1;
    for(int i = A.length - 2;i>=0;--i){
        temp *= A[i+1];
        B[i] *= temp;
    }
    return B;
}
//https://www.cnblogs.com/yongh/p/9971936.html#_labelTop

public int[] multiply(int[] A) {
    if(A == null || A.length == 0)    return null;
    int[] B = new int[A.length];
    for(int i = 0;i<A.length;++i){
        int temp = A[i];
        int ret = 1;
        A[i] = 1;
    
        for(int j = 0;j<A.length;++j){
            ret *=A[j];
        }
        B[i] = ret;
        A[i] = temp;
        ret = 1;
    }
    return B;
}

法一：
import java.util.*;

public ArrayList<Integer> maxInWindows(int [] num, int size)
{
    ArrayList<Integer> res = new ArrayList<>();
    if(num == null || num.length == 0 || size < 1 || size > num.length)    return res;
    PriorityQueue<Integer> heap = new PriorityQueue<>((o1,o2) -> o2 - o1);
    int left = 0,right = 0;
    while(right < size){
        heap.add(num[right++]);
    }
    res.add(heap.peek());
    while(right < num.length){
        heap.remove(num[left++]);
        heap.add(num[right++]);
        res.add(heap.peek());
    }

    return res;
}

法二：
public ArrayList<Integer> maxInWindows(int [] num, int size)
{
    ArrayList<Integer> res = new ArrayList<>();
    if(num == null || num.length == 0 || size == 0)    return res;

    int left = 0,right = 0,max = num[0];

    while(right < num.length){
        if(right - left < size-1){
            right++;
        }else{
            max = getMax(num,left,right);
            res.add(max);
            left++;
            right++;
        }
    }

    return res;
}

private int getMax(int[] array,int low,int high){
    int max = array[low];
    for(int i = low+1;i<=high;i++){
        max = Math.max(max,array[i]);
    }
    return max;
}

public int movingCount(int threshold, int rows, int cols)
{
    if(rows <= 0 || cols <= 0 || threshold < 0)    return 0;
    boolean[] visited = new boolean[rows*cols];
    return movingCountHelper(threshold,rows,cols,0,0,visited);
}

private int movingCountHelper(int threshold,int rows,int cols,int x,int y,boolean[] visited){
    if(x < 0 || x >=rows || y < 0 || y >= cols 
        || visited[x*cols + y] == true
        || getDigitSum(x) + getDigitSum(y) > threshold)    return 0;
    
    visited[x*cols+y] = true;//访问过
    return 1 + movingCountHelper(threshold,rows,cols,x-1,y,visited)
            + movingCountHelper(threshold,rows,cols,x+1,y,visited)
            + movingCountHelper(threshold,rows,cols,x,y-1,visited)
            + movingCountHelper(threshold,rows,cols,x,y+1,visited);
}

private int getDigitSum(int num){
    int sum = 0;
    while(num>0){
        sum += num%10;
        num /= 10;
    }
    return sum;
}

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    Stack<Integer> stack = new Stack<>();
    ArrayList<Integer> result = new ArrayList<>();
    while(listNode != null){
        stack.push(listNode.val);
        listNode = listNode.next;
    }
    while(!stack.isEmpty()){
        result.add(stack.pop());
    }
    return result;
}

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ArrayList<Integer> result = new ArrayList<>();
    ListNode list = new ListNode(-1);
    while(listNode != null){
        //反转链表，更改原来链表
        ListNode temp = listNode.next;
        listNode.next = list.next;
        list.next = listNode;
        listNode = temp;

        /* 头插法，重新生成一个链表
        ListNode temp = new ListNode(listNode.val);
        temp.next = list.next;
        list.next = temp;
        listNode = listNode.next;
        */
    }

    list = list.next;
    while(list != null){
        result.add(list.val);
        list = list.next;
    }
    return result;
}

public ListNode FindKthToTail(ListNode head,int k) {
    if(head == null || k == 0) return null;
    ListNode fast = head,slow = head;
    while(k-- >0){
        if(fast == null)    return null;//链表长度小于k，返回null,没有所求结点
        fast = fast.next;
    }
    while(fast != null){
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

recursive:
public ListNode ReverseList(ListNode head) {
    if(head == null || head.next == null) return head;
    ListNode newHead = ReverseList(head.next);
    head.next.next = head;
    head.next = null;
         
    return newHead;
}

iterative:
public ListNode ReverseList(ListNode head) {
    if(head == null)    return head;
    ListNode pre = null,cur = head;
    while(cur != null){
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

public ListNode mergeTwoLists(ListNode l1,ListNode l2){
    if(l1 == null)
      return l2;
    else if(l2 == null)
      return l1;
    else{
      ListNode head = new ListNode(0);
      ListNode temp = head;
      while(l1 != null && l2 != null){
        if(l1.val < l2.val){
          temp.next = l1;
          l1 = l1.next;
        }
        else{
          temp.next = l2;
          l2 = l2.next;
        }
        temp = temp.next;
      }
      if(l1 == null)
        temp.next = l2;
      if(l2 == null)
        temp.next = l1;

    return head.next;
    }
}

recursively:
public ListNode mergeTwoLists(ListNode l1,ListNode l2){
    if(l1 == null){
      return l2;
    }else if(l2 == null){
      return l1;
    }
    else{
      if(l1.val < l2.val){
        l1.next = mergeTwoLists(l1.next,l2);
        return l1;
      }else{
        l2.next = mergeTwoLists(l1,l2.next);
        return l2;
      }
    }
}

/*
1.遍历链表，直接在原链表上复制每个节点
2.重新遍历链表，复制老节点的随机指针给新节点，如A1.random = A.random.next
3.拆分链表，将链表拆分为原链表和复制的新链表
*/
public RandomListNode Clone(RandomListNode pHead)
{
    if(pHead == null){
        return null;
    }  
    RandomListNode cur = pHead;
    while(cur != null){//1.
        RandomListNode cloneNode = new RandomListNode(cur.label);
        RandomListNode nextNode = cur.next;
        cur.next = cloneNode;
        cloneNode.next = nextNode;
        cur = nextNode;
    }
         
    cur = pHead;
    while(cur != null){//2.
        cur.next.random = cur.random == null?null:cur.random.next;
        cur = cur.next.next;
    }
         
    cur = pHead;
    RandomListNode pCloneHead = pHead.next;
    while(cur != null){//3.
        RandomListNode cloneNode = cur.next;
        cur.next = cloneNode.next;
        cloneNode.next = cloneNode.next == null?null:cloneNode.next.next;
        cur = cur.next;
    }
         
    return pCloneHead;
}

import java.util.ArrayList;
public TreeNode Convert(TreeNode pRootOfTree) {
    if(pRootOfTree == null)    return null;
    ArrayList<TreeNode> list = new ArrayList<>();
    InOrder(pRootOfTree,list);

    return ConvertHelper(list);
}

private void InOrder(TreeNode pRoot,ArrayList<TreeNode> list){
    if(pRoot.left != null)    InOrder(pRoot.left,list);
    list.add(pRoot);
    if(pRoot.right != null)    InOrder(pRoot.right,list);
}

private TreeNode ConvertHelper(ArrayList<TreeNode> list){
    for(int i = 0;i < list.size() - 1;++i){
        list.get(i).right = list.get(i+1);
        list.get(i+1).left = list.get(i);
    }
    return list.get(0);
}

https://www.cnblogs.com/yongh/p/9860700.html

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    if(pHead1 == null || pHead2 == null)    return null;
    ListNode l1 = pHead1,l2 = pHead2;
    while(l1 != l2){
        l1 = l1 == null ? pHead2 : l1.next;
        l2 = l2 != null ? l2.next : pHead1;
    }
    return l1;
}

public ListNode EntryNodeOfLoop(ListNode pHead) {
    ListNode fast = pHead, slow = pHead;
    while (true) {
        if (fast == null || fast.next == null)  return null;
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) break;
    }
    fast = pHead;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return fast;
}

//0, 1, …, n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字
public int LastRemaining_Solution(int n, int m) {
    if(n < 1 || m < 1)    return -1;
    LinkedList<Integer> list = new LinkedList<>();//LinkedList比ArrayList更适合增删操作
    for(int i = 0;i<n;++i){
        list.add(i);
    }
    int removeIndex = 0;
    while(list.size()>1){
        removeIndex = (removeIndex + m - 1) % list.size();
        list.remove(removeIndex);
    }
    return list.getFirst();
}
https://www.cnblogs.com/yongh/p/9970189.html

public ListNode deleteDuplication(ListNode pHead)
{
    if(pHead == null || pHead.next == null)    return pHead;
    ListNode head = new ListNode(-1);
    head.next = pHead;
    ListNode pre = head,cur = head.next;

    while(cur != null){
        if(cur.next != null && cur.next.val == cur.val){
            while(cur.next != null && cur.next.val == cur.val){
                cur = cur.next;
            }
            cur = cur.next;//重复的结点不保留
            pre.next = cur;
        }else{
            pre = cur;
            cur = cur.next;
        }
    }
    return head.next;
}

public String replaceSpace(StringBuffer str) {
    if(str == null)    return null;
    String string = str.toString();
    int len = string.length();
    StringBuilder sb = new StringBuilder();
    for(int i=0;i<len;++i){
        char c = str.charAt(i);
        if(c == ' ')
            sb.append("%20");
        else{
            sb.append(c);
        }
    }
    return sb.toString();
}

public String replaceSpace(StringBuffer str) {
    String string = str.toString();
    char[] array = string.toCharArray();
    int length = array.length;
    int spaceLength = 0;
    for(int i = 0;i<length;++i){
        if(array[i] == ' ')
            spaceLength ++;
    }
    int newLength = length + 2*spaceLength;
    char[] newArray = new char[newLength];
    for(int i = length - 1,k = newLength - 1;i>=0;--i){
        if(array[i] == ' '){
            newArray[k--] = '0';
            newArray[k--] = '2';
            newArray[k--] = '%';
        }else{
            newArray[k--] = array[i];
        }
    }
    return new String(newArray);
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;

//回溯法思想
public ArrayList<String> Permutation(String str) {
    ArrayList<String> list = new ArrayList<>();
    if(str == null || str.length() <= 0)    return list;
    PermutationHelper(str.toCharArray(),0,list);
    Collections.sort(list);

    return list;
}

private void PermutationHelper(char[] array,int i,ArrayList<String> list){
    if(i == array.length - 1){
    String val = new String(array);
        if(!list.contains(val)) list.add(val);
    }else{
        HashSet<Character> set = new HashSet<>();
        for(int j = i;j<array.length;++j){
            if(!set.contains(array[j])){
                set.add(array[j]);
                swap(array,i,j);
                PermutationHelper(array,i+1,list);
                swap(array,j,i);
            }
        }
    }
}

private void swap(char[] array,int i,int j){
    char temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

public int FirstNotRepeatingChar(String str) {
    int len = str.length();
    if(str == null || len <= 0)    return -1;
    int cnt[] = new int[256];//由于字符（char）是长度为8的数据类型，共有256中可能
    for(int i = 0;i<len;i++){
        cnt[str.charAt(i)]++;
    }
    for(int i = 0;i<len;++i){
        if(cnt[str.charAt(i)] == 1)    return i;
    }
    return 0;
}

import java.util.HashMap;
import java.util.ArrayList;

HashMap<Character,Integer> map = new HashMap<>();
ArrayList<Character> list = new ArrayList<>();

//Insert one char from stringstream
public void Insert(char ch)
{
    if(map.containsKey(ch)){
        map.put(ch,map.get(ch) + 1);
    }else{
        map.put(ch,map.getOrDefault(ch,0)+1);
    }
    list.add(ch);
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
    char ch = '#';
    for(char key : list){
        if(map.get(key) == 1){
            ch = key;
            break;
        }
    }
    return ch;
}

解法一：利用String自带的substring方法
public String LeftRotateString(String str,int n) {
    if(str == null || str.length() <= 0)    return "";
        
    //public String substring(int beginIndex)
    //public String substring(int beginIndex, int endIndex)
    return str.substring(n) + str.substring(0,n);
}

解法二：翻转三次字符串
public String LeftRotateString(String str,int n) {
    if(str == null || str.length() <= 0)    return "";
    char[] strArray = str.toCharArray();
    reverse(strArray,0,n-1);
    reverse(strArray,n,strArray.length - 1);
    reverse(strArray,0,strArray.length - 1);
        
    return new String(strArray);
}
    
private void reverse(char[] strArray,int start,int end){
    while(start < end){
        char temp = strArray[start];
        strArray[start] = strArray[end];
        strArray[end] = temp;
        start++;
        end--;
    }
}

解法一：自带split函数处理
public String ReverseSentence(String str) {
    if(str == null || str.length() == 0)    return str;
    String[] words = str.split(" ");
    int len = words.length;
    if(len == 0)    return str;
    StringBuilder sb = new StringBuilder();

    for(int i = len - 1;i >= 0; --i){
        if(i == 0){
            sb.append(words[i]);
        }else{
            sb.append(words[i]).append(" ");
        }
    }

    return sb.toString();
}

解法二：先翻转整个句子，再依次翻转每个单词
public String ReverseSentence(String str) {
    if(str == null || str.length() == 0)    return str;
    char[] arr = str.toCharArray();
    //先翻转整个句子
    reverse(arr,0,arr.length - 1);
    //再翻转每个单词
    int start = 0,end = 0;
    while(start < arr.length){
        while(end < arr.length && arr[end] != ' ')
            end ++;
        reverse(arr,start,end - 1);//空格前内容
        end ++;//跨过空格
        start = end;

    }
    return new String(arr);
}

private void reverse(char[] arr,int start,int end){
    while(start < end){
        char tmp = arr[start];
        arr[start] = arr[end];
        arr[end] = tmp;
        start ++;
        end --;
    }
}

public boolean isContinuous(int [] numbers) {
    if(numbers == null || numbers.length == 0)    return false;
    Arrays.sort(numbers);
    int numOfZero = 0;
    int numOfInterval = 0;
    for(int i = 0;i<numbers.length - 1;++i){
        if(numbers[i] == 0){
            numOfZero ++;
            continue;
        }
        if(numbers[i] == numbers[i+1])
            return false;
        numOfInterval += numbers[i+1] - numbers[i] - 1;
    }

    return numOfZero >= numOfInterval;
}

public int StrToInt(String str) {
    if(str == null || str.length()<=0)    return 0;
    char[] chars = str.toCharArray();
    long num = 0;//先用long来存数，以防止越界
    boolean minus = false;
    for(int i=0;i<chars.length;i++){
        if(i==0 && chars[0] == '-'){
            minus = true;
        }else if(i == 0 && chars[0] == '+'){
            minus = false;
        }else{
            int a = (int)(chars[i] - '0');//char 转 int
            //int 转 char，大(范围)转小,需强转:(char)int + '0'
            if(a<0 || a>9)    return 0;
            num = (minus == false) ? num*10 + a : num*10 - a;
            if((!minus && num > 0x7FFFFFFF) || (minus && num < 0x80000000))    return 0;
            //记住int类型最大正整数为0x7FFFFFFF，最小负整数为0x80000000
        }
    }
    return (int) num;
}
//https://www.cnblogs.com/yongh/p/9973036.html

public boolean match(char[] str, char[] pattern)
{
    if(str == null || pattern == null)    return false;
    return matchCore(str,0,pattern,0);
}

private boolean matchCore(char[] str,int i,char[] pattern,int j){
    if(i == str.length && j == pattern.length)    return true;
    else if(j == pattern.length)    return false;


    boolean next = (j + 1 < pattern.length && pattern[j + 1] == '*');
    if(next){//模式串下一个字符是*
        if(i< str.length && (pattern[j] == '.' || str[i] == pattern[j])){
            //模式串当前字符是. 或者 模式串当前字符和匹配串当前字符能匹配上
            //继续从模式串的后两个位置开始比较 或者 从匹配串的下一个字符开始比较
            return matchCore(str,i,pattern,j+2) || matchCore(str,i+1,pattern,j);
        }else{
            //否则从模式串的后两个位置继续比较
            return matchCore(str,i,pattern,j+2);
        }
    }else{//模式串下一个字符不是*
        if(i< str.length && (pattern[j] == '.' || str[i] == pattern[j])){
            //模式串当前字符是. 或者 模式串当前字符和匹配串当前字符能匹配上
            //继续从模式串和匹配串的下一个字符开始比较
            return matchCore(str,i+1,pattern,j+1);
        }else{
            //都匹配不上直接返回false结束
            return false;
        }
    }
}

解法一：利用正则表达式匹配
import java.util.regex.Pattern;
public boolean isNumeric(char[] str) {
    String pattern = "^[+-]?\\d*(?:\\.\\d*)?(?:[eE][+-]?\\d+)?$";

/*
^是界定符，表示匹配字符串的开始
$也是界定符，表示匹配字符串的结束
[+-]?\\d*：表示能出现正负号0次或1次，整数0-9中数字0次或无数次。这里是尾数，样例中可以不出现数字。
(?:\\.\\d*)?：(?: …)?表示一个可选的非捕获型分组
          \\.\\d*表示出现小数点后0或无数次0-9的整数。尾数的小数点后数字可有可无。
(?:[eE][+-]?\\d+)?：[eE][+-]?\\d+表示出现指数符号e或者E一次，正负号0次或1次，整数0-9中数字1次或无数次。这里是指数，样例中至少要出现一个数字。
*/

    String s = new String(str);

    return Pattern.matches(pattern,s);
//https://www.nowcoder.com/questionTerminal/6f8c901d091949a5837e24bb82a731f2?answerType=1&f=discussion
}

解法二：自己判断表达式类型
public boolean isNumeric(char[] str) {
    if(str == null || str.length == 0)    return false;
    boolean hasE = false;
    boolean sign = false;
    boolean point = false;

    for(int i = 0;i<str.length;i++){
        char ch = str[i];
        if(ch == 'e' || ch == 'E'){
            if(hasE)    return false;
            if(i == str.length - 1)    return false;
            hasE = true;
        }else if(ch == '+' || ch == '-'){
            if(sign && str[i-1]!='e' && str[i-1]!='E')    return false;
            if(!sign && i>0 && str[i-1]!='e' && str[i-1]!='E')    return false;
            sign = true;
        }else if(ch == '.'){
            if(hasE || point)    return false;
            point = true;
        }else if(ch < '0' || ch > '9'){
            return false;
        }
    }
    return true;
}

public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
    if(pre == null || in == null
        || pre.length <= 0 || in.length <= 0
        || pre.length != in.length)    return null;
    return construct(pre,in,0,pre.length - 1,0,in.length - 1);
}

private TreeNode construct(int prel,int prer,int[] pre,int ml,int mr,int[] mid){
    TreeNode root = new TreeNode(pre[prel]);
    if(prel == prer && ml == mr)    return root;
    int index = ml;//找中序中根结点的位置
    while(root.val != mid[index] && index <= mr){
        index++;
    }
    int leftcount = index - ml;
    if(leftcount >0)//左侧
        root.left = construct(prel+1,prel+leftcount,pre,ml,index-1,mid);
    if(leftcount < mr - ml)//右侧
        root.right = construct(prel+leftcount+1,prer,pre,index+1,mr,mid);

    return root;
}

public boolean HasSubtree(TreeNode root1,TreeNode root2) {
    if(root1 == null || root2 == null)    return false;//这题和leetcode不同在于：约定空树不是任意一个树的子结构
    return isSubTreeWithRoot(root1,root2)
        || HasSubtree(root1.left,root2)
        || HasSubtree(root1.right,root2);
}

private boolean isSubTreeWithRoot(TreeNode s,TreeNode t){
    if(t == null)    return true;
    if(s == null || t == null)    return false;
    if(s.val != t.val)    return false;

    return isSubTreeWithRoot(s.left,t.left) && isSubTreeWithRoot(s.right,t.right);
}

public void Mirror(TreeNode root) {
    invertTree(root);
}

private TreeNode invertTree(TreeNode root){
    if(root == null)    return root;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
    return root;
}

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>();
    if(root == null)    return result;

    Deque<TreeNode> q = new ArrayDeque<>();
        q.offer(root);

    while(!q.isEmpty()){
        int sz = q.size();
        for(int i = 0;i<sz;i++){
            TreeNode node = q.poll();
            result.add(node.val);
            if(node.left != null)
                q.offer(node.left);
            if(node.right != null)
                q.offer(node.right);
        }
    }

    return result;
}

二叉搜索树的后序序列特征：
最后一个结点是根节点，且剩余数字中小于根节点的数排在前面，即左子树；大于根节点的数排在后面，即右子树。这个特性是递归特性。

public boolean VerifySquenceOfBST(int [] sequence) {
    if(sequence == null || sequence.length == 0)    return false;

    return VerifyCore(sequence,0,sequence.length - 1);
}

private boolean VerifyCore(int[] sequence,int start,int end){
    if(start >= end)    return true;//递归出口，判断完毕
    //判断左子树
    int mid = start;
    while(sequence[mid] < sequence[end])
        mid ++;
    //判断右子树
    for(int i = mid;i<end;i++){
        if(sequence[i] < sequence[end])    return false;
    }

    return VerifyCore(sequence,start,mid-1) && VerifyCore(sequence,mid,end - 1);
}

ArrayList<ArrayList<Integer>> res = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
    if(root == null)    return res;
    ArrayList<Integer> list = new ArrayList<>();
    getPath(root,target,list);
    return res;
}

private void getPath(TreeNode root,int target,ArrayList<Integer> list){
    if(root == null)    return;
    list.add(root.val);
    target -= root.val;
    if(target == 0 && root.left == null && root.right == null){
        res.add(new ArrayList<Integer>(list));
        //https://blog.csdn.net/Lyuwalle/article/details/107742558
    }else{
        getPath(root.left,target,list);
        getPath(root.right,target,list);
    }
    list.remove(list.size()-1);
}

public TreeNode Convert(TreeNode pRootOfTree) {
    if(pRootOfTree == null)    return null;
    ArrayList<TreeNode> list = new ArrayList<>();
    InOrder(pRootOfTree,list);

    return ConvertHelper(list);
}

private void InOrder(TreeNode pRoot,ArrayList<TreeNode> list){
    if(pRoot.left != null)    InOrder(pRoot.left,list);
    list.add(pRoot);
    if(pRoot.right != null)    InOrder(pRoot.right,list);
}

private TreeNode ConvertHelper(ArrayList<TreeNode> list){
    for(int i = 0;i < list.size() - 1;i++){
        list.get(i).right = list.get(i+1);
        list.get(i+1).left = list.get(i);
    }
    return list.get(0);
}

public int TreeDepth(TreeNode root) {
    if(root == null)    return 0;

    return Math.max(TreeDepth(root.left),TreeDepth(root.right)) + 1;
}

public boolean IsBalanced_Solution(TreeNode root) {
    if(root == null) return true;
    return Math.abs(getHeight(root.left) - getHeight(root.right)) < 2
    && IsBalanced_Solution(root.left)
    && IsBalanced_Solution(root.right);
}

private int getHeight(TreeNode root){
    if(root == null) return 0;
    return Math.max(getHeight(root.left),getHeight(root.right)) + 1;
}

解法一：先存中序遍历结果，再找到树根结点，再遍历结果数组找结果
ArrayList<TreeLinkNode> list = new ArrayList<>();
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
    TreeLinkNode par = pNode;
    while(par.next != null)
        par = par.next;//往上一直找到树的根节点
    InOrder(par);
    for(int i = 0;i < list.size();i++){
        if(pNode == list.get(i))
            return i == list.size() - 1 ? null : list.get(i+1);
    }
    return null;
}

private void InOrder(TreeLinkNode pRoot){
    if(pRoot != null){
        InOrder(pRoot.left);
        list.add(pRoot);
        InOrder(pRoot.right);
    }
}

解法二：直接找其中序遍历的下个结点
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
    if(pNode == null)    return null;
    if(pNode.right != null){//如果有右子树，则找右子树的最左结点
        pNode = pNode.right;
        while(pNode.left != null)    pNode = pNode.left;
        return pNode;
    }
    while(pNode.next!=null){ //没右子树，则向上找，表明其可能在某一结点的左子树上，接下来要找根结点

        //找第一个 父节点左孩子的节点 等于 当前结点，返回其父节点
        //样例[8,6,10,5,7,9,11],7 结果为8，画图一目了然

        if(pNode.next.left==pNode) return pNode.next;
        pNode = pNode.next;
    }
    return null;//退到了根节点仍没找到，返回null
}

递归：
Java:
public boolean isSymmetric(TreeNode pRoot){
  if(pRoot == null) return true;
  return isSymmetric(pRoot.left,pRoot.right);
}

private boolean isSymmetric(TreeNode t1,TreeNode t2){
  if(t1 == null && t2 == null) return true;
  if(t1 == null || t2 == null) return false;
  if(t1.val != t2.val) return false;

  return isSymmetric(t1.left,t2.right) && isSymmetric(t1.right,t2.left);

}

迭代：
public boolean isSymmetric(TreeNode root){
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    queue.add(root);
    while(!queue.isEmpty()){
        TreeNode t1 = queue.poll();
        TreeNode t2 = queue.poll();
        if(t1 == null && t2 == null)  continue;
        if(t1 == null || t2 == null)  return false;
        if(t1.val != t2.val)  return false;
        queue.add(t1.left);
        queue.add(t2.right);
        queue.add(t1.right);
        queue.add(t2.left);
    }
    return true;
}

import java.util.ArrayList;
import java.util.Stack;

public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    ArrayList<ArrayList<Integer> > res = new ArrayList<>();
    if(pRoot == null)    return res;
    Stack<TreeNode> s1 = new Stack<>();//奇数行内容,栈从右至左进，才能从左至右出
    Stack<TreeNode> s2 = new Stack<>();//偶数行内容,栈从左至右进，才能从右至左出
    int layer = 1;//行数
    s1.push(pRoot);

    ArrayList<Integer> tempOdd;
    ArrayList<Integer> tempEven;

    while(!s1.empty() || !s2.empty()){
        if((layer&1) == 1){//当前奇数行，要进偶数行内容,栈从左至右进，才能从右至左出
            int sz = s1.size();
            tempOdd = new ArrayList<>();
            for(int i = 0;i<sz;i++){
                TreeNode node = s1.pop();
                tempOdd.add(node.val);
                if(node.left!= null)    s2.push(node.left);
                if(node.right != null)    s2.push(node.right);
            }
            res.add(tempOdd);
        }else{//当前偶数行，要进奇数行内容，栈从右至左进，才能从左至右出
            int sz = s2.size();
            tempEven = new ArrayList<>();
            for(int i = 0;i<sz;i++){
                TreeNode node = s2.pop();
                tempEven.add(node.val);
                if(node.right != null)    s1.push(node.right);
                if(node.left != null)    s1.push(node.left);
            }
            res.add(tempEven);
        }
        layer ++;
    }
    return res;
}

ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    ArrayList<ArrayList<Integer> > res = new ArrayList<>();
    if(pRoot == null)    return res;
    Deque<TreeNode> q = new ArrayDeque<>();
    q.offer(pRoot);

    while(!q.isEmpty()){
        ArrayList<Integer> tmp = new ArrayList<>();
        int sz = q.size();
        for(int i = 0;i<sz;++i){
            TreeNode node = q.poll();
            tmp.add(node.val);
            if(node.left != null)    q.offer(node.left);
            if(node.right != null)    q.offer(node.right);
        }
        res.add(tmp);
    }
    return res;
}

int index = -1;
String Serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    if(root == null){
        sb.append("#,");
        return sb.toString();
    }
    sb.append(root.val + ",");
    sb.append(Serialize(root.left));
    sb.append(Serialize(root.right));
    return sb.toString();
}

TreeNode Deserialize(String str) {
    index ++;
    String[] arr = str.split(",");
    TreeNode node = null;
    if(!arr[index].equals("#")){
        node = new TreeNode(Integer.parseInt(arr[index]));
        node.left = Deserialize(str);
        node.right = Deserialize(str);
    }
    return node;
}
//https://www.cnblogs.com/gzshan/p/10898708.html

TreeNode treeNode = null;
int cnt = 0;
TreeNode KthNode(TreeNode pRoot, int k)
{
    if(pRoot == null || k <= 0)    return    null;
    InOrder(pRoot,k);
    return treeNode;
}

void InOrder(TreeNode pNode,int k){
    if(cnt < k && pNode.left != null)
        InOrder(pNode.left,k);
    cnt++;
    if(cnt == k) treeNode = pNode;
    if(cnt < k && pNode.right != null)
        InOrder(pNode.right,k);
}

import java.util.ArrayList;
import java.util.Stack;

public boolean IsPopOrder(int [] pushA,int [] popA) {
    if(pushA.length == 0 || popA.length == 0)    return false;
    Stack<Integer> s = new Stack<>();//辅助栈
    int popIndex = 0;//标识弹出序列的位置
    for(int i = 0;i < pushA.length;i++){
        s.push(pushA[i]);
        //栈不为空，且栈顶元素等于弹出序列
        while(!s.empty() && s.peek() == popA[popIndex]){
            s.pop();//出栈
            popIndex++;//弹出序列后退一位
        }
    }
    return s.empty();
}

private Stack<Integer> dataStack = new Stack<>();
private Stack<Integer> minStack = new Stack<>();
private int min = Integer.MAX_VALUE;

public void push(int node) {
    dataStack.push(node);
    min = Math.min(min,node);
    minStack.push(min);
}

public void pop() {
    dataStack.pop();
    minStack.pop();
    min = minStack.isEmpty() ? Integer.MAX_VALUE : minStack.peek();
}

public int top() {
    return dataStack.peek();
}

public int min() {
    return minStack.peek();
}

Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node) {
    stack1.push(node);
}

public int pop() {
    in2out();
    return stack2.pop();
}

private void in2out(){
    if(stack2.empty()){
        while(!stack1.empty()){
            stack2.push(stack1.pop());
        }
    }
}

public int Fibonacci(int n) {
    if(n == 0)    return 0;
    if(n <= 2)    return 1;
    return Fibonacci(n-2) + Fibonacci(n-1);
}

public int JumpFloor(int target) {
    if(target == 0)    return 0;
    if(target == 1)    return 1;
    if(target == 2)    return 2;
    return JumpFloor(target - 2) + JumpFloor(target - 1);
}

public int RectCover(int target) {
    if(target == 0)    return 0;
    if(target == 1)    return 1;
    if(target == 2)    return 2;
    return RectCover(target - 2) + RectCover(target - 1);
}

public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
    boolean[] flag = new boolean[matrix.length];//矩阵是否访问过
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            if(hasPathHelper(matrix,i,j,rows,cols,flag,str,0))
                return true;
        }
    }
    return false;
}

private boolean hasPathHelper(char[] matrix,int i,int j,int rows,int cols,boolean[] flag,
                                char[] str,int k){
    int index = j + cols * i;//矩阵index
    if(i<0||j<0||i>=rows ||j>=cols||matrix[index] != str[k] || flag[index] == true)
        return false;

    if(k == str.length - 1)
        return true;

    //不用回溯到底，有解就退出，所以这里不用循环遍历到结尾
    flag[index] = true;//确定选择
    if(hasPathHelper(matrix,i-1,j,rows,cols,flag,str,k+1) ||
        hasPathHelper(matrix,i+1,j,rows,cols,flag,str,k+1) ||
        hasPathHelper(matrix,i,j-1,rows,cols,flag,str,k+1) ||
        hasPathHelper(matrix,i,j+1,rows,cols,flag,str,k+1)){
        return true;
    }
    flag[index] = false;//撤销选择

    return false;//当前选择走不通
}

public int minNumberInRotateArray(int [] array) {
    if(array == null || array.length == 0)    return 0;
    int low = 0,high = array.length - 1;
    int mid = 0;
    while(low <= high){//统一这里写成小于等于，之后返回high。
    //如果写成小于，就返回low。总之返回集合缩小后的最后一个数
        if(array[low] < array[high])    return array[low];//正常的顺序，没有旋转，最小值肯定是最低位
        mid = low + (high - low)/2;
        if(array[mid] > array[low])    low = mid + 1;//此时肯定旋转了，中间数还是比最低位大，所以最小值还没旋到中间位置，肯定在中间位置右边，所以缩小左端
        else if(array[mid] < array[high])    high = mid;//此时肯定旋转了，最高位还是比中间值大，所以最小值肯定旋过了中间位置，在中间位置或在中间位置的左边
        else low++;//针对非递减情况，或者左边一样大，但都比右边大，一律缩小左边界，直到变成正常顺序或成上面两种情况
    }
    return array[high];//返回集合中最后一个值
}
//https://blog.nowcoder.net/n/dcb0f2e6ffd44e1895b7a5297e362778?f=comment

暴力：
public int NumberOf1Between1AndN_Solution(int n) {
    int count = 0;
    while(n>0){
        String str = String.valueOf(n);
        char[] chars = str.toCharArray();
        for(int i = 0;i<chars.length;i++){
            if(chars[i] == '1')
                count++;
        }
        n--;
    }
    return count;
}

优化：
public int NumberOf1Between1AndN_Solution(int n) {
    if(n <= 9){
        if(n == 0)return 0;
        else return 1;
    }else{
        int[] dp = new int[n+1];
        // 初始化9个元素
        for(int i=0; i < 10; i++){
            if(i==1)dp[i] = 1;
            else dp[i]=0;
        }

        //初始化9个元素的和为1
        int number = 1;
        //计算后面的数字
        for(int i = 10; i <= n; i++){
            int count = 0;
            int temp = i;
            while(temp/10 > 0){
                count++;
                temp = temp/10;
            }
            dp[i] += temp == 1 ? 1: 0;//如果最高位是1，加上1
            dp[i] += dp[i - ((int)(Math.pow(10, count)) ) * temp];//把后面的数化成0-9的部分，加上去
            number += dp[i];
        }
        return number;
    }
}

import java.util.PriorityQueue;
import java.util.Comparator;

//堆常常被当做优先队列使用，因为可以快速的访问到“最重要”的元素
//实际上是一个堆（不指定Comparator时默认为小根堆），通过传入自定义的Comparator函数可以实现大顶堆
private PriorityQueue<Integer> minHeap = new PriorityQueue<>();//
private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(11,new Comparator<Integer>(){
    public int compare(Integer o1,Integer o2){//默认初始长度11， 升序   大根堆
        return o2 - o1;
    }
});

int cnt = 0;
//每次插入小顶堆的是当前大顶堆中最大的数
//每次插入大顶堆的是当前小顶堆中最小的数
//这样保证小顶堆中的数永远大于等于大顶堆中的数
//中位数就可以方便地从两者的根结点中获取了

public void Insert(Integer num) {
    //个数为偶数的话，则先插入到大顶堆，然后将大顶堆中最大的数插入小顶堆中
    if(cnt % 2 == 0){
        maxHeap.offer(num);
        int max = maxHeap.poll();
        minHeap.offer(max);
    }else{
        //个数为奇数的话，则先插入到小顶堆，然后将小顶堆中最小的数插入大顶堆中
        minHeap.offer(num);
        int min = minHeap.poll();
        maxHeap.offer(min);
    }
    cnt ++;
}

public Double GetMedian() {
    if(cnt % 2 == 0){
        //当前为偶数个，则取小顶堆和大顶堆的堆顶元素求平均
        return new Double(minHeap.peek()+maxHeap.peek())/2;
    }else{
        //当前为奇数个，则直接从小顶堆中取元素即可
        return new Double(minHeap.peek());
    }
}

public int cutRope(int target) {
    int[] dp = new int[target+1];
    for(int i = 0;i<=target;i++)
        dp[i] = i;
    for(int i = 0;i<=target;++i){
        for(int j = 1;j<i;++j){//一刀都不剪 和 剪从1到现有长度依次比较
            dp[i] = Math.max(dp[i],dp[i-j]*dp[j]);
        }
    }
    return dp[target];
}

public int JumpFloorII(int target) {
    if(target == 0 || target == 1)    return 1;
    int[] dp = new int[target+1];
    dp[0] = 1;
        
    for(int i = 1;i<=target;++i){
        for(int j =0;j<i;++j){
            dp[i] += dp[j];
        }
    }
    return dp[target];
}

public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
    ArrayList<ArrayList<Integer> > res = new ArrayList<>();
    if(sum == 0)    return res;
    int low = 1,high = 2;
    while(low < high){
        int temp = (low + high)*(high - low + 1) /2;//等差数列求和
        if(temp == sum){
            ArrayList<Integer> a = new ArrayList<>();
            for(int i = low ;i<=high;i++){
                a.add(i);
            }
            res.add(a);
            low ++;//要找出所有的序列
        }else if(temp < sum){
            high ++;
        }else{
            low ++;
        }
    }
    return res;
}

/*
从丑数的定义我们知道，一个丑数的因子只有2,3,5，那么丑数p = 2 ^ x * 3 ^ y * 5 ^ z，
换句话说一个丑数一定由另一个丑数乘以2或者乘以3或者乘以5得到，
那么我们从1开始乘以2,3,5，就得到2,3,5三个丑数，
在从这三个丑数出发乘以2,3,5就得到4，6,10,6，9,15,10,15,25九个丑数，
我们发现这种方法得到重复的丑数，而且我们题目要求第N个丑数，这样的方法得到的丑数也是无序的。
所以要维护三个因子队列：乘2队列、乘3队列、乘5队列
最小的数进丑数数组
*/
public int GetUglyNumber_Solution(int index) {
    if(index <= 0)    return 0;
    int p2 = 0,p3 = 0,p5 = 0;//3个队列的队首下标
    int[] res = new int[index];//丑数数组
    res[0] = 1;
    for(int i = 1; i < index;++i){
        res[i]= Math.min(res[p2]*2,Math.min(res[p3]*3,res[p5]*5));
        if(res[i] == res[p2]*2) p2++;
        if(res[i] == res[p3]*3) p3++;
        if(res[i] == res[p5]*5) p5++;
    }
    return res[index-1];
}

可以用三步走的方式计算二进制值相加： 5-101，7-111 
第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。
第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，(101&111)<<1。
第三步重复上述两步， 各位相加 010^1010=1000，进位值为100=(010&1010)<<1。
     继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果

public int Add(int num1,int num2) {
    while(num2 != 0){
        int temp = num1 ^ num2;
        num2 = (num1 & num2)<<1;
        num1 = temp;
    }
    return num1;
}

public int Sum_Solution(int n) {
    int sum=n;
    //短路原理,用以替代循环和判断，整体是递归操作
    boolean t = (sum != 0) && ((sum += Sum_Solution(n-1)) != 0);
    return sum;
}

暴力：
public double Power(double base, int exponent) {
    if(exponent == 0)    return 1.0;
    double res = 1;
    int num;
    num = exponent >= 0 ? exponent : -exponent;
    for(int i = 0;i<num;i++){
        res *= base;
    }
    if(exponent < 0)
        res = 1 / res;
    return res;
}

快速幂：O(logn)
x^8 = (x^4)^2;  x^7 = (x^3)^2 * x; ==》n为偶数，x^n = (x^n/2)*(x^n/2);  n为奇数，x^n = (x^n/2)*(x^n/2)*x;

public double Power(double base, int exponent) {
    if(exponent < 0){
        base = 1/ base;
        exponent = -exponent;
    }
    return q_power(base,exponent);
}
private double q_power(double base,int exponent){
    if(exponent == 0)    return 1.0;
    double res = q_power(base,exponent/2);
    if((exponent&1) == 0)//指数是偶数
        return res * res;
    else//指数是奇数，还要多乘一个底数
        return res * res * base;
}

一个二进制数1100，从右边数起第三位是处于最右边的一个1。
减去1后得到的结果是1011，我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.
也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.
那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。

public int NumberOf1(int n) {
    if(n == 0)    return 0;
    int cnt = 0;
    while(n != 0){
        cnt++;
        n = n&(n-1);
    }
    return cnt;
}