package com.xp.java;

import com.xp.java.util.SortTestHelper;

import com.xp.java.util.TestUtil;

import java.util.Arrays;

//一些基础题

public class TextJava {

/*****************位运算*****************/

public static void rightOne2Zero(int x) {

int y = 0;

y = x & (x - 1);

System.out.println(y);

}

//统计1的位数有几个

public static void sumOneCount(int x) {

int count = 0;

while (x > 0) {

x = x & (x - 1);

System.out.println("x = " + x);

count++;

}

System.out.println(count);

}

//反转二进制并且得到反转后的结果，如果是32位反转 补齐位数，从32长度循环

public static void revertBit(int n) {

String binary = Integer.toBinaryString(n);

int result = 0;

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

result = (result << 1) + (n & 1);

n = n >> 1;

}

System.out.println(result);

}

public static void testMaoPao() {

int[] maopao = new int[]{7, 5, 3, 2, 1};

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

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

if (maopao[j + 1] < maopao[j]) {

int temp = maopao[j];

maopao[j] = maopao[j + 1];

maopao[j + 1] = temp;

}

TestUtil.printArray("冒泡排序:", maopao);

}

}

}

public static void selectionSort() {

int[] array = new int[]{7, 5, 3, 2, 1};

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

int min = i;

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

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

min = j;

}

}

if (min != i) {

int temp = array[i];

array[i] = array[min];

array[min] = temp;

}

TestUtil.printArray("选择排序:", array);

}

}

public static void insertSort() {

int[] array = new int[]{7, 5, 3, 2, 1};

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

for (int j = i; j > 0; j--) {

if (array[j] < array[j - 1]) {

int temp = array[j - 1];

array[j - 1] = array[j];

array[j] = temp;

}

}

TestUtil.printArray("插入排序:", array);

}

}

//给定一个长度为n的字符串比如：abcdefgh,空间负责度为O(n)

//置顶索引位置将字符串从索引位置前后置换，比如索引3，变换以后的字符串为defghabc

public static void revertStrings(int start, int end, String[] arrays) {

if (end > arrays.length - 1) {

throw new IllegalStateException("超过最大长度限制");

}

int middle = (start + end) / 2;

while (end > middle) {

String temp = arrays[start];

arrays[start] = arrays[end];

arrays[end] = temp;

start++;

end--;

}

SortTestHelper.printArray(arrays);

}

private static int[] array = new int[]{2, 3, 5, 7, 9, 11, 14, 16, 17};

public static int testSearch(int targetNumber) {

int left = 0;

int right = array.length - 1;

int middle = 0;

if (left > right) return -1;

while (left <= right) {

middle = (left + right) / 2;

if (targetNumber == array[middle]) {

return middle;

} else if (targetNumber > array[middle]) {

left = middle + 1;

} else if (targetNumber < array[middle]) {

right = middle - 1;

}

}

return -1;

}

public static int testSearchCircle(int left, int right, int targetNumber) {

if (left > right) return -1;

int middle = (left + right) / 2;

if (targetNumber == array[middle]) {

return middle;

} else if (targetNumber > array[middle]) {

return testSearchCircle(middle + 1, right, targetNumber);

} else if (targetNumber < array[middle]) {

return testSearchCircle(left, middle - 1, targetNumber);

}

return -1;

}

public static void testQuickSort(int[] array, int start, int end) {

if (start > end) return;

int left = start;

int right = end;

int targetNum = array[start];

while (left < right) {

while (left < right && array[right] > targetNum) {

right--;

}

while (left < right && array[left] <= targetNum) {

left++;

}

int temp = array[left];

array[left] = array[right];

array[right] = temp;

}

int temp = array[start];

array[start] = array[left];

array[left] = temp;

testQuickSort(array, start, left - 1);

testQuickSort(array, left + 1, end);

}

private static void mergeArray() {

int[] arr1 = {1, 4, 5, 9};

int[] arr2 = {2, 6, 7, 8};

int compare = 0;

int[] merge = new int[arr1.length + arr2.length];

int index1 = 0;

int index2 = 0;

int index = 0;

int temp = 0;

while (index1 < arr1.length && index2 < arr2.length) {

if (arr1[index1] > arr2[index2]) {

temp = arr2[index2];

index2++;

System.out.println(++compare);

} else {

temp = arr1[index1];

index1++;

System.out.println(++compare);

}

merge[index] = temp;

index++;

}

while (index1 < arr1.length) {

merge[index] = arr1[index1++];

index++;

}

while (index2 < arr2.length) {

merge[index] = arr2[index2++];

index++;

}

TestUtil.printArray("合并有序数组：", merge);

}

private static void mergeArrayInsert() {

int[] arr1 = {1, 4, 5, 9};

int[] arr2 = {2, 6, 7, 8};

int compare = 0;

int[] merge = new int[arr1.length + arr2.length];

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

merge[i] = arr1[i];

}

for (int j = arr1.length; j < merge.length; j++) {

merge[j] = arr2[j - arr1.length];

for (int k = j; k > 0; k--) {

if (merge[k] < merge[k - 1]) {

int temp = merge[k];

merge[k] = merge[k - 1];

merge[k - 1] = temp;

System.out.println(++compare);

}

}

}

TestUtil.printArray("插入合并有序数组：", merge);

}

private static void testMergeArray() {

// int[] array = {1, 4, 5, 9, 2, 6, 7, 8};

// int r = array.length - 1;

// mergeArray(array, 0, r / 2, r);

int[] array2 = {9, 5, 4, 1, 8, 7, 6, 2};

mergeSort(array2, 0, array2.length - 1);

}

private static void mergeSort(int[] array, int start, int end) {

if (start >= end) return;

int middle = (start + end) / 2;

mergeSort(array, start, middle);

mergeSort(array, middle + 1, end);

mergeArray(array, start, middle, end);

}

//一个数组的前后两部分都是有序的，合并前后两部分之后数组保持有序状态。

//归并排序的核心 合并有序数组

private static void mergeArray(int[] array, int start, int mid, int end) {

//复制 array数组中 从start 到 end 位置的数组。注意这里，不一定是0-length。也有可能是中间段

int[] temp = Arrays.copyOfRange(array, start, end + 1);

int leftStart = start, rightStart = mid + 1;

for (int k = start; k <= end; k++) {

if (leftStart > mid) {

array[k] = temp[rightStart - start];

rightStart++;

} else if (rightStart > end) {

array[k] = temp[leftStart - start];

leftStart++;

} else if (temp[leftStart - start] > temp[rightStart - start]) {

array[k] = temp[rightStart - start];

rightStart++;

} else {

array[k] = temp[leftStart - start];

leftStart++;

}

}

TestUtil.printArray("测试合并：", array);

}

public static void main(String[] args) {

// testConcat();

rightOne2Zero(7);

sumOneCount(7);

// revertBit(10);

// testMaoPao();

// selectionSort();

// insertSort();

// String[] arrays = new String[]{"a","b","c","d","e","f","g","h"};

// revertStrings(0,2,arrays);

// revertStrings(3,arrays.length-1,arrays);

// revertStrings(0,arrays.length-1,arrays);

// System.out.println(testSearch(17));

// System.out.println(testSearchCircle(0,array.length-1,17));

int[] array = new int[]{6, 4, 3, 7, 9, 10, 2, 14, 17};

// testQuickSort(array,0,array.length-1);

TestUtil.printArray("快速排序：", array);

// mergeArray();

// mergeArrayInsert();

// testMergeArray();

// System.out.println(weiSum());

// System.out.println(fun("Smart"));

}

}