public static void main(String[] args) {

//1，二维数组中的查找

//2,旋转数组的最小数字

//3，调整数组，使奇数位于偶数前

//4,顺时针打印矩阵

//5,数组中出现次数超过一半的数字

//6，取最小的K个数

//7, 连续子数组的最大和

//8，把数组排成最小的数

//11,数组中只出现一次的数字

//12,扑克牌顺子

//13,孩子们的游戏(圆圈中最后剩下的数)

//14,数组中重复的数字

//15，构建乘积数组

//16，滑动窗口的最大值

int[] arr = {2, 3, 4, 2, 6, 2, 5, 1};

MaxInWindows maxInWindows = new MaxInWindows();

System.out.println(maxInWindows.maxInWindowsByForce(arr, 3));

System.out.println(maxInWindows.maxInWindowsByQueue(arr, 3));

//17，找最大最小值

//18，找到第二大数

//19，两两相加等于sum

//20，把数组右移k位

//21，找第k小的数

//22,找出数组中只出现一次的数字

//23,找出数组中唯一重复1次的数字

//24，用递归求最大值

//25，求数对的最大差值

//26，求给定两个数的最小距离

//28，求指定数字第一次出现的位置，数组中的相邻元素之差为1

//29,对数组的有序子序列进行合并排序

//30，

//31,

}

public boolean findMatrixNum(int[][] matrix, int num) {

int rows = matrix.length;

int cols = matrix[0].length;

if (matrix != null && (rows > 0) && cols > 0) {

int row = 0;

int col = cols - 1;

while (row < rows && col >= 0) {

if (matrix[row][col] == num) {

return true;

} else if (matrix[row][col] > num) {

col--;

} else {

row++;

}

}

}

return false;

}

public boolean findByBinarySearch(int[] arr, int left, int right, int num) {

if (left > right) {

return false;

}

int mid = (left + right) >> 1;

int midVal = arr[mid];

if (num == midVal) {

return true;

} else if (num < midVal) {

return findByBinarySearch(arr, left, mid - 1, num);

} else {

return findByBinarySearch(arr, mid + 1, right, num);

}

}

public int minNumberInRotateArray(int[] arr) {

int low = 0;

int high = arr.length - 1;

while (low < high) {

int mid = (low + high) >> 1;

//一定在右边

if (arr[mid] > arr[high]) {

low = mid + 1;

//一个一个试，使mid和right一步步后退

} else if (arr[mid] == arr[high]) {

low--;

high--;

//一定在左边

} else {

high = mid;

}

}

return arr[low];

}

public void reOrderArray(int[] arr) {

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

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

for (int i = 0; i < arr.length; i++) {

if (arr[i] % 2 == 0) {

evenList.add(arr[i]);

} else {

oddList.add(arr[i]);

}

}

oddList.addAll(evenList);

for (int i = 0; i < arr.length; i++) {

arr[i] = oddList.get(i);

}

}

//问题，那种排序方法是稳定的？

public void reOrderArrayByExchang(int[] arr) {

for (int i = 0; i < arr.length; i++) {

for (int j = 0; j < arr.length - 1; j++) {

if (arr[j] % 2 == 0 && arr[j + 1] % 2 != 0) {

int temp = arr[j + 1];

arr[j + 1] = arr[j];

arr[j] = temp;

}

}

}

}

public ArrayList<Integer> printMatrix(int[][] matrix) {

int row = matrix.length;

int col = matrix[0].length;

ArrayList<Integer> res = new ArrayList<>();

if (row == 0 && col == 0) {

return res;

}

int left = 0, right = col - 1, top = 0, bottom = row - 1;

while (left <= right && top <= bottom) {

//上：从左到右

for (int i = left; i <= right; i++) {

res.add(matrix[top][i]);

System.out.println(matrix[top][i]);

}

//右：从上到下

for (int i = top + 1; i <= bottom; i++) {

res.add(matrix[i][right]);

System.out.println(matrix[i][right]);

}

//下：从右到左

if (top != bottom) {

//防止单行情况

for (int i = right - 1; i >= left; i--) {

res.add(matrix[bottom][i]);

System.out.println(matrix[bottom][i]);

}

}

//左：从下到上

if (left != right) {

//防止单列情况

for (int i = bottom - 1; i > top; i--) {

res.add(matrix[i][left]);

System.out.println(matrix[i][left]);

}

}

left++;

right--;

top++;

bottom--;

}

return res;

}

public int moreThanHalfNumSolutionByHashMap(int[] array) {

HashMap<Integer, Integer> map = new HashMap<>();

int length = array.length;

for (int i = 0; i < length; i++) {

if (!map.containsKey(array[i]))

map.put(array[i], 1);

else

map.put(array[i], map.get(array[i]) + 1);

}

for (Map.Entry<Integer, Integer> entry : map.entrySet()) {

if (entry.getValue() * 2 > length)

return entry.getKey();

}

return 0;

}

public int moreThanHalfNumSolutionBySort(int[] array) {

Arrays.sort(array);

int half = array.length / 2;

int count = 0;

for (int i = 0; i < array.length; i++) {

if (array[i] == array[half])

count++;

}

if (count > half) {

return array[half];

} else {

return 0;

}

}

public int moreThanHalfNumSolution(int[] array) {

//返回出现次数最多的字数

int res = array[0], count = 1;

for (int i = 1; i < array.length; i++) {

if (array[i] == res)

count++;

else {

count--;

}

if (count == 0) {

res = array[i];

count = 1;

}

}

//判断最多字数是否满足个数大于数组长度一半

count = 0;

for (int i = 0; i < array.length; i++) {

if (array[i] == res)

count++;

}

return count > array.length / 2 ? res : 0;

}

public ArrayList<Integer> getLeastNumbersSolutionBySort(int[] arr, int k) {

ArrayList<Integer> res = new ArrayList<>();

if (arr == null || k == 0 || k > arr.length) {

return res;

}

Arrays.sort(arr);

for (int i = 0; i < k; i++) {

res.add(arr[i]);

}

return res;

}

/**

public ArrayList<Integer> getLeastNumbersSolutionByHeap(int[] arr, int k) {

ArrayList<Integer> res = new ArrayList<>();

if (arr == null || k == 0 || k > arr.length) {

return res;

}

//使用PriorityQueue实现大顶堆.PriorityQueue的逻辑结构是一棵完全二叉树，存储结构其实是一个数组。逻辑结构层次遍历的结果刚好是一个数组

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {

public int compare(Integer e1, Integer e2) {

return e2 - e1;

}

});

for (int i = 0; i < arr.length; i++) {

if (maxHeap.size() != k)

maxHeap.offer(arr[i]);

else {

if (maxHeap.peek() > arr[i]) {

maxHeap.poll();

maxHeap.offer(arr[i]);

}

}

}

for (Integer i : maxHeap) {

res.add(i);

}

return res;

}

/**

public int findGreatestSumOfSubArray(int[] array) {

if (array.length == 0) {

return 0;

}

int curSum = array[0];

int max = array[0];

for (int i = 1; i < array.length; i++) {

curSum = curSum > 0 ? curSum + array[i] : array[i]; //当出现连续和为负数时，那么将当前连续和值cur移到下一位

if (max < curSum) {

max = curSum;

}

}

return max;

}

public String getMinNum(int[] arr) {

//装箱处理，不然下面的Arrays.sort无法重写

Integer[] nums = new Integer[arr.length];

for (int i = 0; i < arr.length; i++) {

nums[i] = arr[i];

}

if (nums.length == 0 || nums == null) {

return "";

}

//按照规则排序

Arrays.sort(nums, new Comparator<Integer>() {

//对数组nums用自定义方法排序

@Override

public int compare(Integer o1, Integer o2) {

//重写compare方法来比较o1,o2的大小，当o1+""+o2和o2+""+o1

//都是字符串，比较o1,o2的大小其实是比较两个子串的大小

return (o1 + "" + o2).compareTo(o2 + "" + o1);

}

});

String ss = new String();

for (int i = 0; i < nums.length; i++) {

ss += nums[i];

}

return ss;

}

public static int InversePairs(int[] array) {

if (array == null || array.length <= 1)

return 0;

int[] copy = new int[array.length];

for (int i = 0; i < array.length; i++) {

copy[i] = array[i];

}

return mergeCount(array, copy, 0, array.length - 1);

}

public static int mergeCount(int[] array, int[] copy, int start, int end) {

if (start == end) {

copy[start] = array[start];

return 0;

}

int mid = (start + end) >> 1;

int leftCount = mergeCount(copy, array, start, mid);

int rightCount = mergeCount(copy, array, mid + 1, end);

int i = mid;//i初始化为前半段最后一个数字的下标

int j = end;//j初始化为后半段最后一个数字的下标

int index = end;//辅助数组复制的数组的最后一个数字的下标

int count = 0;//计数--逆序对的数目

while (i >= start && j >= mid + 1) {

if (array[i] > array[j]) {

copy[index--] = array[i--];

count += j - mid;

} else {

copy[index--] = array[j--];

}

}

for (; i >= start; i--) {

copy[index--] = array[i];

}

for (; j >= mid + 1; j--) {

copy[index--] = array[j];

}

return leftCount + rightCount + count;

}

public static List<Integer> binaryAllSearch(int[] arr, int left, int right, int findValue) {

//递归结束条件1

if (left > right) {

return new ArrayList<>();

}

int mid = (left + right) >> 1;

int midVal = arr[mid];

if (findValue > midVal) { //正序,向右查询

return binaryAllSearch(arr, mid + 1, right, findValue);

} else if (findValue < midVal) {

return binaryAllSearch(arr, left, mid - 1, findValue);

} else {

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

//向左扫描

int temp = mid - 1;

while (true) {

if (temp < 0 || arr[temp] != findValue) {

break;

}

resIndexList.add(temp);

temp--;

}

//先将自身加入

resIndexList.add(mid);

//向右扫描

temp = mid + 1;

while (true) {

if (temp > arr.length - 1 || arr[temp] != findValue) {

break;

}

resIndexList.add(temp);

temp++;

}

return resIndexList; //递归结束条件1

}

}

public int[] findNumsAppearOnceByMap(int[] array) {

HashMap<Integer, Integer> tempMap = new HashMap<>();

for (int i = 0; i < array.length; i++) {

if (tempMap.containsKey(array[i])) {

tempMap.remove(array[i]);

} else {

tempMap.put(array[i], 1);

}

}

int[] a = new int[tempMap.size()];

int i = 0;

for (Integer k : tempMap.keySet()) {

a[i] = k;

i++;

}

return a;

}

public int[] findNumsAppearOneByYiHuo(int[] nums) {

int len = nums.length;

if (len < 2) {

return null;

}

//利用异或去重，得到两个唯一不同的两个数的异或值

int AllXOR = 0; //0和任何一个数异或等于他本身，任何数字和本身异或等于0

for (int i = 0; i < nums.length; i++) {

AllXOR ^= nums[i];

}

//找到AllXOR中第一位为1的位置

int res = findFirstBit1(AllXOR);

//无需保存两个数组，直接对两个数组在循环中进行异或运算

int num1 = 0, num2 = 0;

for (int i = 0; i < nums.length; i++) {

if (isBit1(nums[i], res)) {//根据一特定位置是否为1，将数组分为两个子数组进行判断，每一个子数组中包含一个只出现一次的数字

num1 ^= nums[i];

} else {

num2 ^= nums[i];

}

}

int[] resArr = new int[2];

resArr[0] = num1;

resArr[1] = num2;

return resArr;

}

//num&(-num)是把最右边的1保留下来

private static int findFirstBit1(int num) {

return num & (-num);

}

//判断某一特定位置是不是1

private boolean isBit1(int data, int res) {

return ((data & res) != 0);

}

public boolean isContinuous(int[] arr) {

int zero = 0, dis = 0;

//如果不等于5，那么就不满足发牌规则

if (arr.length != 5) {

return false;

}

//排序

Arrays.sort(arr);

//找到arr[i] == 0的个数

for (int i = 0; i < 4; i++) {

if (arr[i] == 0) {

zero++;

continue; //不能忽略，找到大小王时，不再做任何处理

}

//如果牌重复了，不可能是顺子

if (arr[i] == arr[i + 1]) {

return false;

}

if (arr[i + 1] - arr[i] > 1) {

dis += arr[i + 1] - arr[i] - 1;

}

}

if (zero >= dis) {

return true;

} else {

return false;

}

}

public int lastRemainingSolution(int n, int m) {

if (n < 1 || m < 1) {

return -1;

}

LinkedList<Integer> link = new LinkedList<>();

for (int i = 0; i < n; i++) {

link.add(i);

}

int index = -1; //起步是 -1 不是 0

while (link.size() > 1) {

index = (index + m) % link.size(); //对 link的长度求余不是对 n

link.remove(index);

index--;

}

return link.get(0);

}

public boolean duplicate(int numbers[], int length, int[] duplication) {

if (length == 0) {

return false;

}

for (int i = 0; i < length; i++) {

while (i != numbers[i]) {

if (numbers[i] == numbers[numbers[i]]) {

duplication[0] = numbers[i];

return true;

} else {

int temp = numbers[numbers[i]];

numbers[numbers[i]] = numbers[i];

numbers[i] = temp;

}

}

}

return false;

}

public int[] multiply(int[] A) {

/*这道题的中心思想是将返回的数据列成一个矩阵，每一个矩阵的行向量都是一个从a(0)到a(n-1)

int length = A.length;

int[] B = new int[length];

B[0] = 1;

for (int i = 1; i < length; i++) {

B[i] = B[i - 1] * A[i - 1];

}

int temp = 1;

for (int j = length - 2; j >= 0; j--) {

temp *= A[j + 1];//temp始终会记录值，每次只需要加上这行上三角没有乘进来的数就可以了。

B[j] *= temp;

}

return B;

}

//暴力法

public int[] multiplyByForce(int[] A) {

int[] B = new int[A.length];

for (int i = 0; i < A.length; i++) {

int mul = 1;

for (int j = 0; j < A.length; j++) {

if (i != j) {

mul = mul * A[j];

}

}

B[i] = mul;

}

return B;

}

//暴力法

public ArrayList<Integer> maxInWindowsByForce(int[] num, int size) {

ArrayList<Integer> res = new ArrayList<>();

if (num.length < size || size == 0) {

return res;

}

for (int i = 0; i < num.length - size + 1; i++) {

res.add(max(num, i, size));

}

return res;

}

public int max(int[] num, int index, int size) {

int res = num[index];

for (int i = index + 1; i < index + size; i++) {

if (num[i] > res) {

res = num[i];

}

}

return res;

}

//双向队列

public ArrayList<Integer> maxInWindowsByQueue(int[] num, int size) {

ArrayList<Integer> res = new ArrayList<>();

LinkedList<Integer> deque = new LinkedList<>();

if (num.length == 0 || size == 0) {

return res;

}

for (int i = 0; i < num.length; i++) {

//当窗口滑过了窗口长度，那么将就窗口中的最大的数的下标取出

if (!deque.isEmpty() && deque.peekFirst() <= i - size) {

deque.poll();

}

//如果队列的最后一个数小于当前循环到的数，那么删除队列的最后一个数

while (!deque.isEmpty() && num[deque.peekLast()] < num[i]) {

deque.removeLast();

}

//此时，已经将队列中的小于当前循环数的数全干调，下一步就是添加当前循环数

deque.offerLast(i);

//当i + 1 >= size，说明窗口已经开始生效

if (i + 1 >= size) {

res.add(num[deque.peekFirst()]); //头部永远是最大

}

}

return res;

}

int max;

int min;

public void getMaxAndMin(int[] arr) {

max = arr[0];

min = arr[0];

int len = arr.length;

for (int i = 1; i < len; i = i + 2) { //注意是到len - 1

//如果i = len时

if (i + 1 == len) {

if (arr[i] > max) {

max = arr[i];