while ((result = 9 * random9() + random9()) >= 90);
return result % 10 + 1;

public int rand10() {
    int result;
    do {
        result = rand9()+(rand9()-1)*9;
    } while (result > 80);
    return 1 + (result - 1) % 10;
}

public static int random10() {
    int[][] seed = { { 1, 2, 3, 4, 5, 6, 7 }, { 8, 9, 10, 11, 12, 13, 14 },
            { 15, 16, 17, 18, 19, 20, 11 }, { 22, 23, 24, 25, 26, 27, 28 },
            { 29, 30, 31, 32, 33, 34, 35 }, { 36, 37, 38, 39, 40, 41, 42 },
            { 43, 44, 45, 46, 47, 48, 49 } };

    int result;
    do {
        result = seed[random7() - 1][random7() - 1];
    } while (result > 40);
    return result % 10 + 1;
}

import java.util.ArrayList;
import java.util.List;

/*
 * @lc app=leetcode id=51 lang=java
 *
 * [51] N-Queens
 */
public class Solution {

    List<List<String>> result = new ArrayList<>();

    private static int total = 0;

    public List<List<String>> solveNQueens(int n) {
        total = n;
        int[][] board = new int[n][n];
        backtrack(board, 1);
        return result;
    }

    private void backtrack(int[][] board, int idx) {
        if (idx > total) {
            // ok
            result.add(transform(board));
            return;
        }

        for (int i = 0; i < total; i ++) {
            if (isOk(board, idx - 1, i)) {
                //
                board[idx - 1][i] = 1;
                backtrack(board, idx + 1);
                board[idx - 1][i] = 0;
            }
        }
    }

    private boolean isOk(int[][] board, int xx, int yy) {
        for (int i = 0; i < total; i++) {
            if (board[xx][i] == 1) {
                return false;
            }
            if (board[i][yy] == 1) {
                return false;
            }
        }
        int x = xx, y = yy;
        while (x < total && y >= 0)
            if (board[x ++][y --] == 1)
                return false;
        x = xx; y = yy;
        while (x < total && y < total)
            if (board[x ++][y ++] == 1)
                return false;
        x = xx; y = yy;
        while (x >= 0 && y >= 0)
            if (board[x --][y --] == 1)
                return false;
        x = xx; y = yy;
        while (x >=0 && y < total)
            if (board[x --][y ++] == 1)
                return false;
//        System.out.println("OK");
        return true;
    }

    private List<String> transform(int[][] board) {
        List<String> oneAnswer = new ArrayList<>();
        for (int i = 0; i < board.length; i ++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < board[i].length; j ++) {
                sb.append(board[i][j] == 0 ? '.' : 'Q');
            }
            oneAnswer.add(sb.toString());
        }
//        showAnswer(oneAnswer);
        return oneAnswer;
    }

    private void showAnswer(List<String> answer) {
        System.out.println();
        for (String line : answer) {
            System.out.println(line);
        }
    }

    public static void main(String[] args) {
        List<List<String>> result = new Solution().solveNQueens(4);
        System.out.println(result.size());
    }
}

import java.util.ArrayList;
import java.util.List;

/*
 * @lc app=leetcode id=17 lang=java
 *
 * [17] Letter Combinations of a Phone Number
 */
class Solution {
    private int[][] maps = {
        {},
        {},
        {'a', 'b', 'c'},
        {'d', 'e', 'f'},
        {'g', 'h', 'i'},
        {'j', 'k', 'l'},
        {'m', 'n', 'o'},
        {'p', 'q', 'r', 's'},
        {'t', 'u', 'v'},
        {'w', 'x', 'y', 'z'}
    };
    List<String> result = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
         backtrack(digits, "", 0);
         return result;
    }
    private void backtrack(String digits, String sb, int idx) {
        if (idx >= digits.length()) {
            if (sb.length() > 0)
                result.add(sb.toString());
            return;
        }
        int mapsIdx = digits.charAt(idx) - '0';
        for (int i = 0; i < maps[mapsIdx].length; i ++) {
            backtrack(digits, sb + (char) maps[mapsIdx][i], idx + 1);
        }
    }
}

class Solution {
    List<String> sets = new ArrayList<>();

    // 22
    public List<String> generateParenthesis(int n) {
        produce(2 * n, 0, n, n, "");
        return sets;
    }

    private void produce(int blank, int sum, int lcnt, int rcnt, String seq) {
        if (sum < 0)
            return;

        if (blank == 0) {
            sets.add(seq);
            return;
        }

        if (lcnt > 0) {
            produce(blank - 1, sum + 1, lcnt - 1, rcnt, seq + "(");
        }

        if (rcnt > 0) {
            produce(blank - 1, sum - 1, lcnt, rcnt - 1, seq + ")");
        }
    }
}

/*
 * @lc app=leetcode id=37 lang=java
 *
 * [37] Sudoku Solver
 */
public class Solution {
    private static class Point {
        public int x, y;

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

        @Override
        public String toString() {
            return "<" + x + ", " + y + ">";
        }
    }

    static char[][] data = {
            {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
            {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
            {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
            {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
            {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
            {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
            {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
            {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
            {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
    };

    public static void main(String[] args) {
        new Solution().solveSudoku(data);
        printBoard(data, "最终结果");
    }

    private static void printBoard(char[][] data, String msg) {
        System.out.println("\n" + msg + ":");
        for (int i = 0; i < data.length; i ++) {
            for (int j = 0; j < data[i].length; j++) {
                System.out.print(data[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    boolean over = false;

    public void solveSudoku(char[][] board) {
        backtrack(board, nextPoint(board, new Point(0, 0)));
    }

    private void backtrack(char[][] board, Point focus) {
        if (over || isOver(board)) {
            over = true;
            return;
        }

        if (focus == null) {
            over = true;
            return;
        }

        for (int val = 1; val <= 9 && !over; val++) {
            board[focus.x][focus.y] = (char) ('0' + val);
            if (isValid(board, focus, (char) ('0' + val))) {
                backtrack(board, nextPoint(board, focus));
            }
        }
        if (!over)
            board[focus.x][focus.y] = '.';
    }

    private boolean isValid(char[][] board, Point p, char val) {
        // 横向
        for (int i = 0; i <= 8; i++) {
            if (i != p.y && board[p.x][i] == val)
                return false;
        }
        // 纵向
        for (int i = 0; i <= 8; i++) {
            if (i != p.x && board[i][p.y] == val)
                return false;
        }
        // 方形
        for (int i = (p.x / 3 * 3); i <= (p.x / 3 * 3) + 2; i++) {
            for (int j = (p.y / 3 * 3); j <= (p.y / 3 * 3) + 2; j++) {
                if (i != p.x && j != p.y && board[i][j] == val)
                    return false;
            }
        }
//        printBoard(board, "位置" + p + ", 对值<" + (char)val + ">合适");
        return true;
    }

    private boolean isOver(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == '.')
                    return false;
            }
        }
        return true;
    }

    private Point nextPoint(char[][] board, Point p) {
        Point returnPoint = null;
        int x = p.x, y = p.y;
        while (x <= 8 && returnPoint == null) {
            for (int i = y; i <= 8; i++) {
                if (board[x][i] == '.') {
                    returnPoint = new Point(x, i);
                    break;
                }
            }
            y = 0;
            x ++;
        }
//        System.out.println(p + "  ->  " + returnPoint);
        return returnPoint;
    }
}

import java.util.ArrayList;
import java.util.List;

/*
 * @lc app=leetcode id=39 lang=java
 *
 * [39] Combination Sum
 */
class Solution {

    List<List<Integer>> result = new ArrayList();

    private int maxInt = 0;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        sort(candidates);
        maxInt = candidates[candidates.length - 1] + 1;
        backtrack(candidates, target, new ArrayList<>());
        return result;
    }

    private void sort(int[] arr) {
        for (int i = 0; i < arr.length; i ++) {
            for (int j = i; j < arr.length; j ++) {
                if (arr[i] > arr[j]) {
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
    }

    private void backtrack(int[] candidates, int target, List<Integer> answer) {
        if (target == 0) {
            // find the answer
//            showArray(answer);
            if (!isDuplicated(result, answer, candidates))
                result.add(new ArrayList<>(answer));
            else {
//                System.out.println("Duplicated");
            }
        } else if (target < 0) {
            return;
        }

        for (int i = 0; i < candidates.length; i++) {
            answer.add(candidates[i]);
            backtrack(candidates, target - candidates[i] , answer);
            answer.remove(answer.size() - 1);
        }
    }

    private void showArray(List<Integer> arr) {
        System.out.print("[");
        for (int i = 0; i < arr.size(); i ++) {
            System.out.print(String.valueOf(arr.get(i)) + (i == arr.size() - 1 ? "]" : ", "));
        }
        System.out.println();
    }

    private boolean isDuplicated(List<List<Integer>> result, List<Integer> oneAnswer, int[] candidates) {
        for (List<Integer> r : result) {
            if (r.size() == oneAnswer.size()) {
                int[] sr = new int[maxInt];
                int[] si = new int[maxInt];
                for (int i = 0; i < r.size(); i ++) {
//                    System.out.println(r.get(i) + " + 1");
                    sr[r.get(i)] ++;
//                    System.out.println(oneAnswer.get(i) + " + 1");
                    si[oneAnswer.get(i)] ++;
                }
                boolean isDuplicatedWithThisResult = true;
                for (int i = 0; i < candidates.length; i ++) {
                    // System.out.println(candidates[i] + "," + sr[candidates[i]] + "," + si[candidates[i]]);
                    if (sr[candidates[i]] != si[candidates[i]]) {
                        isDuplicatedWithThisResult = false;
                        continue;
                    }
                }
                if (isDuplicatedWithThisResult)
                    return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int [] arr = {8,7,4,3};
        new Solution().combinationSum(arr, 11);
    }
}

class Solution {
    List<List<Integer>> result = new ArrayList();

    private boolean[] USAGE;

    public List<List<Integer>> permute(int[] nums) {
        USAGE = new boolean[nums.length];
        List<Integer> answer = new ArrayList();
        backtrack(nums, 0, answer);
        return result;
    }

    private void backtrack(int[] nums, int idx, List<Integer> answer) {
        if (idx >= nums.length) {
            result.add(new ArrayList(answer));
            return;
        }
        for (int i = 0; i < nums.length; i ++) {
            if (!USAGE[i]) {
                answer.add(nums[i]);USAGE[i] = true;
                backtrack(nums, idx + 1, answer);
                answer.remove(answer.size() - 1);USAGE[i] = false;
            }
        }
    }
}

class Solution {
    private boolean[] usage;
    private String result;
    private int targetIdx, currentIdx;
    private boolean over = false;
    public String getPermutation(int n, int k) {
        targetIdx = k;
        usage = new boolean[n + 1];
        StringBuilder sb = new StringBuilder();
        backtrack(n, 1, sb);
        return result;
    }

    private void backtrack(int n, int idx, StringBuilder sb) {
        if (over)
            return;
        if (idx > n) {
            currentIdx ++;
            if (currentIdx == targetIdx) {
                result = sb.toString();
                over = true;
            }
            return ;
        }
        for (int i = 1; i <= n; i ++) {
            if (over)
                break;
            if (!usage[i]) {
                sb.append(i);usage[i] = true;
                backtrack(n, idx + 1, sb);
                sb.deleteCharAt(sb.length() - 1);usage[i] = false;
            }
        }
    }
}

class Solution {
    private List<List<Integer>> result = new ArrayList();
    private boolean[] USAGE;
    private int depth;

    public List<List<Integer>> combine(int n, int k) {
        depth = k;
        USAGE = new boolean[n + 1];
        backtrack(1, n, 1, new ArrayList<>());
        return result;
    }

    private void backtrack(int startIdx, int n, int idx, List<Integer> answer) {
        if (idx > depth) {
            result.add(new ArrayList(answer));
            return;
        }
        for (int i = startIdx; i <= n; i ++) {
            if (!USAGE[i]) {
                answer.add(i);USAGE[i] = true;
                backtrack(i + 1, n, idx + 1, answer);
                answer.remove(answer.size() - 1);USAGE[i] = false;
            }
        }
    }
}

/**
* @param int[] 未排序数组
* @return int[] 排完序数组
*/
public static int[] InsertSort(int[] array){
    for(int i =1;i<array.length;i++){
        int temp = array[i];
        int j = i-1;
        while(j>=0 && temp < array[j] ){
            array[j+1] = array[j];
            j--;
        }
        array[j+1] = temp;
    }
    return array;
}

/**
* @param int[] 未排序数组
* @return int[] 排完序数组
*/
public int[] sortSelect(int[] arr){
    for (int i = 0; i < arr.length-1; i++) {
        int miniPost = i;
        for (int m = i + 1; m < arr.length; m++) {
            if (arr[m] < arr[miniPost])
         　　miniPost = m;
        }
        if (arr[i] > arr[miniPost]) {
            int temp = arr[i];
            arr[i] = arr[miniPost];
            arr[miniPost] = temp;
        }
    }
    return arr;
}

package sortdemo;

import java.util.Arrays;

/**
 * Created by chengxiao on 2016/12/8.
 */
public class MergeSort {
    public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int []arr){
        int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        sort(arr,0,arr.length-1,temp);
    }
    private static void sort(int[] arr,int left,int right,int []temp){
        if(left<right){
            int mid = (left+right)/2;
            sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
            sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
            merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
        }
    }
    private static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;//左序列指针
        int j = mid+1;//右序列指针
        int t = 0;//临时数组指针
        while (i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while(i<=mid){//将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while(j<=right){//将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right){
            arr[left++] = temp[t++];
        }
    }
}

/**
执行结果
[1, 2, 3, 4, 5, 6, 7, 8, 9]
**/

public static void main(String[] args) {
    int[] arr = new int[]{6,2,4,99,22,56,11,5,7,4,1};
    QuickSort(arr, 0, arr.length - 1);
    printArray(arr);
}

static void QuickSort(int[] arr, int left, int right){
    if (left > right)
        return;
    int pivot_index = partition1(arr, left, right);
    QuickSort(arr, left, pivot_index - 1);
    QuickSort(arr, pivot_index + 1, right);
}

static int partition1(int[] arr, int left, int right){
    int pivot = arr[left];
    while(left < right){
        while(left < right && arr[right] >= pivot){
            right--;
        }
        arr[left] = arr[right];

        while(left < right && arr[left] <= pivot){
            left++;
        }
        arr[right] = arr[left];

    }
    arr[left] = pivot;
    return left;
}