public int findRepeatNumber(int[] nums) {
  int i = 0;
  while(i < nums.length) {
    if(nums[i] == i) {
      i++;
      continue;
    }
    if(nums[nums[i]] == nums[i]) return nums[i];
    int tmp = nums[i];
    nums[i] = nums[tmp];
    nums[tmp] = tmp;
  }
  return -1;
}

public String replaceSpace(String s) {
  StringBuilder res = new StringBuilder();
  for(Character c : s.toCharArray())
  {
    if(c == ' ') res.append("%20");
    else res.append(c);
  }
  return res.toString();
}

//先序遍历A(recur就是对根节点的操作,相当于打印,然后依次操作左右子节点)
public boolean isSubStructure(TreeNode A, TreeNode B) {
  if(A==null || B==null) return false;// 当树A为空或树B为空时，直接返回 false;
  //若树 B 是树 A 的子结构，则必满足以下三种情况之一:
  //节点A为根节点的子树包含树B;树B是树A的子结构;树B是树A的子结构
  return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}

//判断A中以n_a为根节点的子树是否包含树B
boolean recur(TreeNode A, TreeNode B) {
  if(B == null) return true; //当节点 B 为空：说明树 B 已匹配完成（越过叶子节点）
  //当节点 A 为空：说明已经越过树 A 叶子节点，即匹配失败;当节点 A 和 B 的值不同：说明匹配失败
  if(A == null || A.val != B.val) return false; 
  //判断 A 和 B 的左子节点是否相等 && 判断 A 和 B 的右子节点是否相等
  return recur(A.left, B.left) && recur(A.right, B.right);
}

public boolean isSymmetric(TreeNode root) {
  return root == null ? true : recur(root.left, root.right);
}
boolean recur(TreeNode L, TreeNode R) {
  if(L == null && R == null) return true;
  if(L == null || R == null || L.val != R.val) return false;
  return recur(L.left, R.right) && recur(L.right, R.left);
}

// 方法一
private ArrayList<String> res = new ArrayList<>(); // 结果集
private Set<String> set = new HashSet<>(); // 保存已遍历过的前缀，用于剪枝

private List<String> permutation(String s) {
  backtrack(s.toCharArray(), new LinkedList<Integer>());
  String[] ans = new String[res.size()];
  for(int i=0;i<res.size();i++){
    ans[i] = res.get(i);
  }
  return ans;
}

// list : 当前路径,已遍历过的字符下标
private void backtrack(char[] arr, LinkedList<Integer> list) {
  // 回溯终止条件
  if (list.size() == arr.length) {
    res.add(getString(arr,list));
    return;
  }

  // 遍历可选列表
  for (int i = 0; i < arr.length; i++) {
    if (!list.contains(i)) {
      // 做选择
      list.add(i);
      // 判断是否要开启后续递归(当前串是否为遍历过的前缀)
      String temp = getString(arr, list);
      if (set.contains(temp)){
        list.removeLast();
        continue;
      }
      set.add(temp);
      
      backtrack(arr, list);
      
      // 撤回选择
      list.removeLast();
    }
  }
}

// 将已遍历过的字符转换为字符串
private String getString(char[] arr, LinkedList<Integer> list){
  StringBuilder builder = new StringBuilder();
  for (int i : list) {
    builder.append(arr[i]);
  }
  return builder.toString();
}

// 方法二 两两交换
private ArrayList<String> res = new ArrayList<>(); // 结果集

private List<String> permutation(String s) {
  backtrack(s.toCharArray(),  0);
  return res;
}

// index: 当前交换字符的下标
private void backtrack(char[] arr, int index){
  if (index == arr.length-1) {
    res.add(new String(arr));
    return;
  }

  // 为排除重复方案，需在固定某位字符时，保证 “每种字符只在此位固定一次” ，即遇到重复字符时不交换，直接跳过。
  HashSet<Character> set = new HashSet<>();
  // 选择列表：当前字符可与 自己和之后的字符进行交换
  for (int i = index; i < arr.length; i++) {
    if (set.contains(arr[i])) continue;
    set.add(arr[i]);

    swap(arr,index,i);
    backtrack(arr,index+1);
    swap(arr,index,i);
  }

}

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

public int maxSubArray(int[] nums) {
  int[] dp = new int[2];
  int res = Integer.MIN_VALUE;
  for(int i = 0;i<nums.length;i++){
    dp[0] = dp[1];
    dp[1] = Math.max(dp[0]+nums[i],nums[i]);
    res = dp[1]>res?dp[1]:res;
  }
  return res;
}

// 快排
Random random = new Random();
public String minNumber(int[] nums) {
  String[] strArr = new String[nums.length];
  for(int i=0;i<nums.length;i++){
    strArr[i] = String.valueOf(nums[i]);
  }
  // 自定义快速排序
  quickSort(strArr,0,nums.length-1);
  StringBuilder builder = new StringBuilder();
  for(String s:strArr){
    builder.append(s);
  }
  return builder.toString();

}

public void quickSort(String[] arr, int start, int end) {
  if (start >= end) return;

  int left = start;
  int right = end;
  // TODO 随机枢纽
  int i =random.nextInt(end - start + 1)+start;
  String temp = arr[left];
  arr[left]=arr[i];
  arr[i]=temp;

  String pivot = arr[left];

  while (left < right) { // 3, 30, 34, 5, 9
    while ((pivot + arr[right]).compareTo(arr[right] + pivot) <= 0 && left < right) {
      right--;
    }
    arr[left] = arr[right];

    while ((pivot+arr[left]).compareTo( arr[left]+pivot) >= 0 && left < right) {
      left++;
    }
    arr[right] = arr[left];
  }
  // 复原中枢点
  arr[left] = pivot;
  quickSort(arr, start, left - 1);
  quickSort(arr, left + 1, end);
}

// JDK 比较器
public String minNumber(int[] nums) {
  String[] strArr = new String[nums.length];
  for(int i=0;i<nums.length;i++){
    strArr[i] = String.valueOf(nums[i]);
  }

  Arrays.sort(strArr,(x,y)->(x+y).compareTo(y+x));
  StringBuilder builder = new StringBuilder();
  for(String s:strArr){
    builder.append(s);
  }
  return builder.toString();
}

public int add(int a, int b) { // a无进位和 b进位
  if (b == 0) { // 没有进位后退出递归
    return a;
  }

  // 转换成非进位和 + 进位
  return add(a ^ b, (a & b) << 1);
}