排序&查找
二分查找
题目：在有序数组中查找一个值，返回该值的索引。（非递归方式&递归方式）
//非递归方式
public static int binaryFind(int[] list, int value) {
int left = 0;
int right = list.length - 1;
int mid;
while (left <= right) {// 当最小索引大于最大索引时，那么一定没有这个数了
// mid = (left + right) / 2;//（不建议这样取中，因为可能数太大超出范围）
// mid = left + ((right - left) >> 1);
mid = left + (right - left) / 2;// 中间索引
if (value == list[mid]) {//找到之后返回索引
return mid;
} else if (value > list[mid]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;// 没有找到，返回-1
}
//递归方式
public static int binaryFind2(int[] list, int value, int left, int right) {
if (left <= right) {
int mid = left + (right - left) / 2;
if (list[mid] == value) {
return mid;
} else if (list[mid] > value) {
return binaryFind2(list, value, left, mid - 1);
} else {
return binaryFind2(list, value, mid + 1, right);
}
} else
return -1;
}
冒泡排序（优化后）
O(N^2) 时间
public static int[] bubbleSort(int[] a) {
int leng = a.length;
for (int i = 0; i < leng; i++) {
boolean flag = true;
for (int j = 0; j < leng - i - 1; j++) {
if (a[j] > a[j + 1]) {
int tem = a[j];
a[j] = a[j + 1];
a[j + 1] = tem;
flag = false;
}
}
if (flag) {
break;
}
System.out.println("排序次数：" + i);
}
return a;
}
选择排序
O(N^2) 时间（每次选择最小的或最大的来生成一个数组）
public static int[] ChoiceSort(int[] a) {
for (int i = 0; i < a.length; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[min] > a[j]) {
min = j;
}
}
int tem = a[i];
a[i] = a[min];
a[min] = tem;
//display(a);
}
return a;
}
快速排序
平均O(NLogN) 时间（）
public static void sort(int[] list, int left, int right) {
int division = division(list, left, right);
if (left < right) {
sort(list, left, division - 1);
sort(list, division + 1, right);
}
}
public static int division(int[] list, int left, int right) {
int base = list[left];
while (left < right) {
while (left < right && list[right] >= base) {
right--;
}
list[left] = list[right];
while (left < right && list[left] <= base) {
left++;
}
list[right] = list[left];
}
list[left] = base;
return left;
}
反转字符串（多种方法）
方法1：利用栈实现
String str = "how are you";
Stack stack = new Stack();
char[] ch = str.toCharArray();
for (char c : ch) {
stack.push(c);
}
while (!stack.isEmpty()) {
System.out.print(stack.pop());
}
方法2.1：通过数组
public static String fanzhuan(String str) {
if ("".equals(str)) {
return "";
}
int len = str.length();
char[] s = str.toCharArray();
for (int i = 0; i < len ; i++) {
s[i] = str.charAt(len - i - 1);
}
return new String(s);
}
//方法2.2：通过数组（减少一半）
public static String fanzhuan(String str) {
if ("".equals(str)) {
return "";
}
int len = str.length();
char[] s = str.toCharArray();
for (int i = 0; i < len / 2; i++) {
s[i] = str.charAt(len - i - 1);
s[len - 1 - i] = str.charAt(i);
}
return new String(s);
}
//方法3：使用StringBuilder逆序遍历
//方法4：使用递归
public static String reverse(String str) {
if ("".equals(str))
return "";
int len = str.length();
if (len == 1) {
return str;
}
return reverse(str.substring(1)) + str.charAt(0);
}
Top k问题（多种方法）
堆排序之后取前k个：O（NlogN）
代码直接看堆排序即可
利用堆排序：O（NlogK）
伪代码：
heap[k] = make_heap(arr[1, k]);
for(i=k+1 to n){
adjust_heap(heep[k],arr[i]);
}
return heap[k];
public static int[] top(int[] list, int k) {
if (list.length <= k) {
return list;
}
int[] array = new int[k];
for (int i = 0; i < k; i++) {
array[i] = list[i];
}
headSort(array);
for (int i = k; i < list.length; i++) {
if (array[0] < list[i]) {
array[0] = list[i];
headSort(array);
}
}
return array;
}
public static int[] headSort(int[] inputList) {// 堆排序
int length = inputList.length;
for (int i = length / 2; i >= 0; i--) {// 建立初始堆
heap(inputList, i, length);
}
for (int i = length - 1; i >= 0; i--) {// n-1次循环完成排列
// 将最后一个元素和第一个元素进行交换（第一个元素是最大的，交换位置后，最大的就在排最后了）
int tem = inputList[i];
inputList[i] = inputList[0];
inputList[0] = tem;
heap(inputList, 0, i);// 将inputList中前i个记录重新调整为大顶堆
}
return inputList;
}
public static void heap(int[] list, int parent, int len) {// 构建堆
int tem = list[parent];
int child = 2 * parent + 1;
while (child < len) {
if (child + 1 < len && list[child + 1] > list[child]) {
child++;
}
if (list[child] <= tem) {
break;
}
list[parent] = list[child];
parent = child;
child = 2 * parent + 1;
}
list[parent] = tem;
}
使用优先队列PriorityQueue
(PriorityQueue就是通过堆实现的)
public static int[] topk(int[] list, int k) {
if (list.length <= k) {
return list;
}
PriorityQueue<Integer> pq = new PriorityQueue<>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;//最大堆
//return o2 - o1;//最小堆
}
});
for (int num : list) {
if (pq.size() < k) {
pq.offer(num);
} else if (pq.peek() < num) {
pq.poll();
pq.offer(num);
}
}
int[] array = new int[k];
for (int i = 0; i < k; i++) {
array[i] = pq.poll();
}
return array;
}
动态规划
最长公共子串与最长公共子序列
连续子数组的最大和
该算法在每次元素累加和小于0时，从下一个元素重新开始累加。实现代码如下：
public static int sum(int[] list) {
int maxSum = 0;//记录最大的值
int cursum = 0;//记录 暂时累加和
for (int i = 0; i < list.length; i++) {
cursum += list[i];
if (cursum > maxSum) {//如果 暂时累加 大于历史最大值，则保存
maxSum = cursum;
}
if (cursum < 0) {//如果 暂时累加和 小于0，则将暂时累加和更新为0
cursum = 0;
}
}
return maxSum;
}
链表
反转链表
public static Node reverseListNode(Node head) {
if (head == null || head.next == null) {// 单链表为空或只有一个节点，直接返回原单链表
return head;
}
Node preNode = null;// 前一个节点指针
Node curNode = head;// 当前节点指针
Node nextNode = null;// 下一个节点指针
while (curNode != null) {
nextNode = curNode.next;// nextNode 指向下一个节点
curNode.next = preNode;// 将当前节点next域指向前一个节点
preNode = curNode;// preNode 指针向后移动
curNode = nextNode;// curNode指针向后移动
}
return preNode;
}
链表中倒数第k个结点
public static Node findKthToTail(Node node, int k) {
if (node == null || k == 0) {
return null;
}
Node head = node;
Node behind = node;
for (int i = 0; i < k-1; i++) {
if(head.next==null){
return null;
}
head=head.next;
}
while(head.next!=null){
head=head.next;
behind=behind.next;
}
return behind;
}
链表中环的入口结点
public static Node entryNodeOfLoop(Node node) {
if (node == null || node.next == null) {
return null;
}
Node fast = node;
Node slow = node;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
fast = node;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
if(fast==slow){
return slow;
}
}
}
return null;
}
二叉树
判断二叉树是否平衡
//class Tree {
// int value;
// Tree left;
// Tree right;
//
// public Tree(int value) {
// this.value = value;
// left = null;
// right = null;
// }
//}
public static boolean isBalance(Tree tree) {
if (tree == null) {
return true;
}
int left = treeDepth(tree.left);
int right = treeDepth(tree.right);
int diff = right - left;
if (diff > 1 || diff < -1) {
return false;
}
return isBalance(tree.left) && isBalance(tree.right);
}
public static int treeDepth(Tree tree) {//二叉树的深度
if (tree == null) {
return 0;
}
int left = treeDepth(tree.left);
int right = treeDepth(tree.right);
return left > right ? left + 1 : right + 1;
}
寻找二叉搜索树第k个结点
public static TreeNode findKthNode(TreeNode root, int k) {
TreeNode target=null;
if(root.left!=null){
target=findKthNode(root.left,k)
}
if(）{
}
if(root.right!=null){
target=findKthNode(root.right,k)
}
}
贪心
买卖股票的最佳时机
找到局部最优解，然后再得到整体的最优解。我们可以从第一天的股票价钱出发，和第二天的对比，如果第二天比第一天价格更高了(稳赚)，就赶紧买进第1天的，然后第二天卖出。同理，到了第二天，我就和第三天的价格做对比，只要后一天的价格高于今天的，我就买进今天的股票，到后一天再卖出。赚到的钱依次相加，得到最大的利润。当然如果后一天的价格比今天的低，我们就不买。
public static int price(int[] list) {
int result = 0;
for (int i = 1; i < list.length; i++) {
result = Math.max(result + list[i] - list[i - 1], result);
}
return result;
}
网友评论