排序&查找

二分查找

题目：在有序数组中查找一个值，返回该值的索引。（非递归方式&递归方式）

//非递归方式
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;
    }

常见算法

常见算法

排序&查找

二分查找

冒泡排序（优化后）

选择排序

快速排序

反转字符串（多种方法）

方法1：利用栈实现

方法2.1：通过数组

Top k问题（多种方法）

堆排序之后取前k个：O（NlogN）

利用堆排序：O（NlogK）

使用优先队列PriorityQueue

动态规划

最长公共子串与最长公共子序列

连续子数组的最大和

链表

反转链表

链表中倒数第k个结点

链表中环的入口结点

二叉树

判断二叉树是否平衡

寻找二叉搜索树第k个结点

贪心

买卖股票的最佳时机