1、快排（NlogN）
public class QuickSort {
public static void quickSort(int[] array, int left, int right) {
int key = array[left];
int start = left;
int end = right;
while (start < end) {
//从后往前
while (array[end] > key && start < end) {
end--;
}
if (array[end] < key) {
int temp = array[end];
array[end] = array[start];
array[start] = temp;
}
//从前往后
while (array[start] < key && start < end) {
start++;
}
if (array[start] > key) {
int temp = array[end];
array[end] = array[start];
array[start] = temp;
}
}
if (start > left) {
quickSort(array, left, start - 1);
}
if (end < right) {
quickSort(array, end + 1, right);
}
}
public static void main(String[] args) {
int[] a = {7,6,5,4,3,2,1};
quickSort(a, 0, a.length - 1);
for (int m = 0; m < a.length; m++) {
System.out.println(a[m]);
}
}
}
2、冒泡（n^2）
public class BubbleSort {
public static void bubbleSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
for(int i = 0; i < arr.length - 1; i ++) {
for(int j = 0; j < arr.length - 1 - i; j ++) {
if(arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] a = {7,6,5,4,3,2,1};
bubbleSort(a);
for (int m = 0; m < a.length; m++) {
System.out.println(a[m]);
}
}
}
3、二分查找（logN）
public class BinarySearch {
public static int binarySearch(int data[], int target) {
if (data == null || data.length == 0) {
return -1;
}
int low = 0;
int high = data.length - 1;
//<=包含等于是可能有这种情况 小标为3和4 mid=3，但是3<key(4),l++=h 这个时候如果不能等于则会丢失可能找不到
while(low <= high) {
int middle = (low + high) / 2;
if (data[middle] == target) {
return middle;
}
if (data[middle] < target) {
high = middle - 1;
}
if (data[middle] > target) {
low = middle + 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] a = {7,6,5,4,3,2,1};
int result = binarySearch(a, 3);
System.out.println(result);
}
}
3.1 旋转有序数组的二分查找
给定一个没有重复元素的旋转数组（它对应的原数组是有序的），求给定元素在旋转数组内的下标（不存在的返回-1）。
例子
有序数组{0，1，2，3，4，5，6，7}对应的旋转数组为{3，4，5，6，7，0，1，2}（左旋、右旋效果相同）。
查找元素5，返回结果2；
查找元素8，返回结果-1。
public class RotateBinarySearch {
public static int rotateBinarySearch(int array[], int target) {
int left = 0;
int right = array.length - 1;
while(right >= left) {
int middle = (left + right) / 2;
if (array[middle] == target) {
return middle;
}
// 说明左半部分有序
if (array[left] < array[middle]) {
// 说明target在有序那部分中
if (array[left] <= target && target < array[middle]) {
right = middle - 1;
} else {
left = middle + 1;
}
}
// 说明右半部分有序
if (array[middle] < array[right]) {
// 说明target在有序那部分中
if (array[middle] < target && target <= array[right]) {
left = middle + 1;
} else {
right = middle - 1;
}
}
}
return -1;
}
public static void main(String[] args) {
int[] array = {3,4,5,6,7,0,1,2};
int result = rotateBinarySearch(array, 1);
System.out.println(result);
}
}
3.2 先升序再降序的数组查找最大值的下标
public class BinarySearchMax {
public static int findMax(int[] array) {
if (array == null && array.length == 0) {
return -1;
}
int left = 0;
int right = array.length;
while (right >= left) {
int middle = (left + right) / 2;
if (array[middle] >= array[middle - 1] && array[middle] >= array[middle + 1]) {
return middle;
} else if (array[middle] > array[middle - 1] && array[middle] < array[middle + 1]) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] array = {1,3,5,7,8,10,6,4,2,0};
System.out.println(findMax(array));
}
}
4、反转二叉树
public class InvertTree {
public static class TreeNode {
int value;
TreeNode left;
TreeNode right;
}
public TreeNode invertTree(TreeNode root) {
//一定要检查指针为空
if (root == null) {
//递归的结束条件
return null;
}
root.left = invertTree(root.left);
root.right = invertTree(root.right);
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
return root;
}
}
5、生产者消费者（wait() notify()）
Producer
public class Producer implements Runnable {
LinkedBlockingQueue<Integer> container;
int maxSize;
public Producer(LinkedBlockingQueue<Integer> container, int maxSize) {
this.container = container;
this.maxSize = maxSize;
}
@Override
public void run() {
while (true) {
synchronized (container) {
if (container.size() >= maxSize) {
System.out.println("producer: 当前容器的大小为: " + container.size());
System.out.println("producer: 容器已满，等待消费......");
try {
container.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
} else {
System.out.println("producer开始生产: 当前容器的大小为: " + container.size());
Random random = new Random();
container.add(random.nextInt());
container.notify();
}
}
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
Consumer
public class Consumer implements Runnable{
LinkedBlockingQueue<Integer> container;
int maxSize;
public Consumer(LinkedBlockingQueue<Integer> container, int maxSize) {
this.container = container;
this.maxSize = maxSize;
}
@Override
public void run() {
while (true) {
synchronized (container) {
if (container.size() <= 0) {
System.out.println("consumer: 当前容器大小为: " + container.size());
System.out.println("consumer: 容器大小为0，等待生产者生产......");
try {
container.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
} else {
System.out.println("consumer开始消费: 当前容器的大小为: " + container.size());
container.remove();
container.notify();
}
}
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
public static void main(String[] args) {
int maxSize = 10;
LinkedBlockingQueue<Integer> container = new LinkedBlockingQueue<>();
Thread producer = new Thread(new Producer(container, maxSize));
Thread consumer = new Thread(new Consumer(container, maxSize));
producer.start();
consumer.start();
}
}
6、回文字符串判断（递归解法）
public class HuiWen {
public static boolean isHuiWei(char[] charArray, int left, int right) {
if (left <= right) {
if (charArray[left] == charArray[right]) {
isHuiWei(charArray, left + 1, right - 1);
//递归结束条件1
return true;
} else {
//递归结束条件2
return false;
}
} else {
//递归结束条件3
return true;
}
}
public static void main(String[] args) {
char[] charArray = {'a','b','c','d','c','b'};
System.out.println(isHuiWei(charArray, 0, charArray.length - 1));
}
}
7、最长回文字符串（动态规划解法）
设状态dp[j][i]表示索引j到索引i的子串是否是回文串。则转移方程为：
image
则dp[j][i]为true时表示索引j到索引i形成的子串为回文子串，且子串起点索引为j,长度为i - j + 1。
算法时间复杂度为O(N ^ 2)。
public class LongestPalindrome {
public static String longestPalindrome(String s) {
int length = s.length();
if (length == 0) {
return "";
}
boolean[][] dp = new boolean[length][length];
int maxLength = 0;
int maxIndex1 = 0;
int maxIndex2 = 0;
for (int i = 0; i < length; i++) {
for (int j = 0; j <= i; j++) {
if (j == i) {
dp[j][i] = true;
}
if (j < i && j >= 0) {
if (s.charAt(i) == s.charAt(j) && (dp[j+1][i-1] == true || (i-1) == j)) {
dp[j][i] = true;
if (maxLength < (i - j + 1)) {
maxLength = i - j + 1;
maxIndex1 = j;
maxIndex2 = i;
}
}
}
}
}
return s.substring(maxIndex1, maxIndex2 + 1);
}
public static void main(String[] args) {
String s = "cbbd";
String longHuiWenString = longestPalindrome(s);
System.out.println(longHuiWenString);
}
}
