public static int binarySearch(int[] arr, int key) {
    int low = 0;
    int high = arr.length - 1;
    //当要查询的数小于最小值或大于最大值时，直接返回，不需要进入while循环内部
    if (key < arr[low] || key > arr[high]) {
        return -1;
    }
    while (low <= high) {
        int middle = (low + high) / 2;
        if (key == arr[middle]) {
            return middle;
        } else if (key < arr[middle]) {
            high = middle - 1;
        } else {
            low = middle + 1;
        }
    }
    return -1;
}

（2）递归实现

public static int recursionBinarySearch(int[] arr, int key, int low, int high) {
    int middle = (low + high) / 2;
    if (key < arr[low] || key > arr[high]) {
        return -1;
    }
    if (key == arr[middle]) {
        return middle;
    } else if (key < arr[middle]) {
        return recursionBinarySearch(arr, key, low, middle - 1);
    } else {
        return recursionBinarySearch(arr, key, middle + 1, high);
    }
}

2、冒泡排序

比较两个相邻的元素，若第二个元素比第一个元素小，则交换两者的位置，第一轮比较完成后，最大的数会浮到最顶端。排除此最大数，继续下一轮的比较。

时间复杂度：O(N^2)

空间复杂度：O(1)

为稳定排序

可以为冒泡排序进行优化，当某一趟未发生交换时，则说明数组已经有序了，无需再进行排序。

public static void bubbleSort(int[] arr) {
    //一共需要进行n-1趟循环
    for (int i = 0; i < arr.length - 1; i++) {
        //假设本次循环中，没有发生交换
        boolean flag = false;
        //本次循环一共需要比较n-i-1次
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j + 1] < arr[j]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                //本次循环发生交换了
                flag = true;
            }
        }
        //如果本次循环后，未发生交换，则表明数组有序，退出排序
        if (!flag) {
            break;
        }
    }
}

3、层序遍历二叉树

结点类

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

层序遍历（非递归）

public void layerOrder(TreeNode root) {
    LinkedList<TreeNode> list = new LinkedList<>();
    TreeNode t;
    if (root != null) {
        list.push(root);
    }
    while (!list.isEmpty()) {
        t = list.removeFirst();
        System.out.print(t.getValue());
        if (t.getLeft() != null) {
            list.addLast(t.getLeft());
        }
        if (t.getRight() != null) {
            list.addLast(t.getRight());
        }
    }
}

4、选择排序

第一轮从整个数组中选择最小的数，与第一个数交换。

第二轮排除第一个数，从剩下来的数中选择最小的数，与第二个数交换。

以此类推。

时间复杂度：O(N^2)

空间复杂度：O(1)

为稳定排序

public static void selectSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        //假设当前下标代表最小的数
        int min = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[min]) {
                min = j;
            }
        }
        if (min != i) {
            int temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }
}

5、反转单链表

结点类

public static class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

这里我们采用两种方法，分别是迭代与递归。

（1）迭代

从链表头部开始处理，我们需要定义三个连续的结点pPre，当前需要反转的结点pCur，下一个需要反转的结点pFuture和一个永远指向头结点的pFirst。每次我们只需要将pPre指向pFuture，pCur指向pFirst，调整头结点pFirst，调整当前需要反转的结点为下一个结点即pFuture，最后调整pFuture为pCur的next结点。

/**
* 迭代方式
*
* @param head 翻转前链表的头结点
* @return 翻转后链表的头结点
*/
public ListNode reverseList(ListNode head) {
    if (head == null) {
        return null;
    }
    //始终指向链表的头结点
    ListNode pFirst = head;
    //三个结点中的第一个结点
    ListNode pPre = pFirst;
    //当前需要反转的结点
    ListNode pCur = head.next;
    //下一次即将需要反转的结点
    ListNode pFuture = null;
    while (pCur != null) {
        pFuture = pCur.next;
        pPre.next = pFuture;
        pCur.next = pFirst;
        pFirst = pCur;
        pCur = pFuture;
    }
    return pFirst;
}

（2）递归

递归与迭代不同，递归是从链表的尾结点开始，反转尾结点与前一个结点的指向。

/**
* 递归方式
*
* @param head 翻转前链表的头结点
* @return 翻转后链表的头结点
*/
public ListNode reverseList2(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode pNext = head.next;
    head.next = null;
    ListNode reverseListNode = reverseList2(pNext);
    pNext.next = head;
    return reverseListNode;
}

6、插入排序

（1）两层for循环

public static void insertSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int cur = i;
        int t = a[i];
        for (int j = i - 1; j >= 0; j--) {
            if (t < a[j]) {
                a[j + 1] = a[j];
                cur = j;
            }
        }
        //cur位置是最后空出来的，将本次待插入的数t放进去即可
        a[cur] = t;
    }
}

（2）内层使用while循环（不太好理解）

public static void insertSort2(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int temp = a[i];
        int j = i - 1;
        while (j >= 0 && temp < a[j]) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = temp;
    }
}

7、判断链表是否有环

节点类：

static class ListNode {
    public int val;
    public ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

（1）使用额外空间来判断链表中是否有环

思路：遍历整个链表，将每一次遍历的节点存入Set中，利用Set存入相同元素返回false的特性，判断链表中是否有环。

public boolean hasCycle(ListNode head) {
    Set<ListNode> set = new HashSet<>();
    while (head != null) {
        boolean result = set.add(head);
        if (!result) {
            return true;
        }
        head = head.next;
    }
    return false;
}

由于遍历，导致时间复杂度为O(n)，由于使用了Set集合，空间复杂度为O(n)。

（2）使用快慢指针。

思路：快慢指针都从头节点开始，快指针一次走两步，慢指针一次，如果慢指针能够追赶上快指针，则证明链表中有环。

public boolean hasCylce2(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        //如果慢指针追赶上快指针的话，则说明有环
        if (fast == slow) {
            return true;
        }
    }
    return false;
}

拓展问题1：

如果链表有环，找出环的入口节点。

思路：快慢指针的相遇点到环入口的距离等于头节点到环入口的距离，那么在头节点和相遇点各设一个相同步伐的指针，他们相遇的那个节点就是环入口。

public ListNode getEntrance(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    boolean isCycle = false;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        //如果慢指针追赶上快指针的话，则说明有环
        if (fast == slow) {
            isCycle = true;
            break;
        }
    }

    if (isCycle) {
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
    return null;
}

拓展问题2：

若链表有环，求出环的长度。

思路：若链表有环，得到环入口，然后让指针指向环入口，指针遍历完重新回到环入口的路程即环的长度。

public int getCylceLength(ListNode head) {
    int length = 0;
    ListNode cycleNode = getEntrance(head);
    if (cycleNode != null) {
        ListNode temp = cycleNode;
        while (true) {
            temp = temp.next;
            length++;
            if (temp == cycleNode) {
                break;
            }
        }
    }
    return length;
}

8、快速排序

在数组中选定一个基准数，通过一次排序后，基准数左边的元素都比基准数小，基准数右边的元素都比基准数大。

最差时间复杂度O(N^2)

平均时间复杂度O(N*log2N)

为不稳定排序

public static void quickSort(int[] a, int left, int right) {
    if (left > right) {
        return;
    }
    //以数组第一个元素为基准点
    int key = a[left];
    int i = left;
    int j = right;

    while (i < j) {
        //j位于最右边，向左边进行遍历，直到找到一个小于基准数的元素，取其下标
        while (i < j && a[j] >= key) {
            j--;
        }
        //i位于最左边，向右边进行遍历，直到找到一个大于基准数的元素，取其下标
        while (i < j && a[i] <= key) {
            i++;
        }
        //若找到以上两个数，则交换他们
        if (i < j) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    //此时离开while循环，说明i==j，将a[i]与基准数进行交换
    a[left] = a[i];
    a[i] = key;
    //对左边进行递归排序
    quickSort(a, left, i - 1);
    //对右边进行递归排序
    quickSort(a, i + 1, right);
}

9、求二叉树最大的深度（宽度）

（1）递归实现

/**
* 求二叉树的深度（使用递归）
*
* @param root
* @return
*/
public int getHeight(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftHeight = getHeight(root.getLeft());
    int rightHeight = getHeight(root.getRight());
    return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

（2）非递归实现

按照层序遍历的思想，记录某一层的元素总数与本层中已经遍历过的元素个数，当两者相等时，深度自增。

也可用于求二叉树的最大宽度，遍历的同时取每层元素总数的最大值即可。

/**
* 求二叉树的深度（不使用递归）
*
* @param root
* @return
*/
public int getHeight2(TreeNode root) {
    if (root == null) {
        return 0;
    }
    LinkedList<TreeNode> list = new LinkedList<>();
    list.offer(root);
    //最大宽度留备用
    int max=0;
    //二叉树的深度
    int level = 0;
    //本层中元素总数
    int size = 0;
    //本层已经访问过的元素个数
    int cur = 0;
    while (!list.isEmpty()) {
        size = list.size();
        max=Math.max(max,size);
        cur = 0;
        while (cur < size) {
            TreeNode node = list.poll();
            cur++;
            if (node.getLeft() != null) {
                list.offer(node.getLeft());
            }
            if (node.getRight() != null) {
                list.offer(node.getRight());
            }
        }
        level++;
    }
    System.out.println("二叉树最大宽度为:"+max);
    return level;
}

10、爬楼梯

题目描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例：输入3，输出3

走法：

（1）1，1，1

（2）1，2

（3）2，1

思考：

第n阶楼梯的爬法 =（第n-1阶楼梯的爬法+第n-2阶楼梯的爬法）

（1）递归（可能会出现超时情况）

public int climbStairs(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    if (n == 2) {
        return 2;
    }
    return climbStairs(n - 1) + climbStairs(n - 2);
}

（2）动态规划

public int climbStairs2(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    int[] a = new int[n + 1];
    a[0] = 1;
    a[1] = 1;
    for (int i = 2; i <= n; i++) {
        a[i] = a[i - 1] + a[i - 2];
    }
    return a[n];
}

11、合并两个有序链表

结点类

static class ListNode {
    int val;
    ListNode next;

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

（1）非递归解法

public static ListNode mergeList2(ListNode l1, ListNode l2) {

    ListNode head = new ListNode(-1, null);
    ListNode temp = head;

    //第一个while,只要l1和l2都还有元素时，依据大小进行合并
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            head.next = l1;
            l1 = l1.next;
        } else {
            head.next = l2;
            l2 = l2.next;
        }
        head = head.next;
    }
    //第二个while,此时l1已经为空，则将l2剩余的结点合并到新链表中
    while (l2 != null) {
        head.next = l2;
        head = head.next;
        l2 = l2.next;
    }
    //第三个while,此时l2已经为空，则将l1剩余的结点合并到新链表中
    while (l1 != null) {
        head.next = l1;
        head = head.next;
        l1 = l1.next;
    }
    return temp.next;
}

（2）递归解法

public static ListNode mergeList(ListNode l1, ListNode l2) {
    //递归的最小规模解
    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }
    //递归的规模分解
    if (l1.val <= l2.val) {
        l1.next = mergeList(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeList(l1, l2.next);
        return l2;
    }
}

12、数组的最大子序和

题目描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

使用动态规划法：

假设sum（i，j）表示nums数组中从i到j的元素之和，那么我们必须遵循的条件是sum（i，j-1）>0，我们可以认为sum（i，j）有可能是最大子序和，需要和其满足这个条件的情况进行比较。如果sum（i，j-1）<0，我们就抛弃nums[i]到nums[j-1]之间的元素（两端也抛弃，抛弃之前，先与最大值进行比较，防止出现数组全负数的情况）。再从nums[j]开始，即求sum（j，k）的最大值，如果sum（i，k-1）<0，我们就再从nums[k]开始，以此类推。

public static int getMaxSum(int[] a) {
    int max = a[0];
    int cur = a[0];
    for (int i = 1; i < a.length; i++) {
        if (cur > 0) {
            cur += a[i];
        } else {
            cur = a[i];
        }
        if (cur > max) {
            max = cur;
        }
    }
    return max;
}

13、求两个数的最大公约数与最小公倍数

（1）最大公约数

使用相减法

/**
* 相减法
*/
public static int getMaxCommonDivisor(int x, int y) {
    while (x != y) {
        if (x > y) {
            x = x - y;
        } else {
            y = y - x;
        }
    }
    return x;
}

（2）最小公倍数

基于定理两数乘积=最大公约数*最小公倍数

public static int getMinCommonMultiple(int x, int y) {
return x * y / getMaxCommonDivisor(x, y);
}

14、堆排序

时间复杂度：O( N*logN )

空间复杂度：O(1)

为不稳定排序

注意点：

（1）初始化大顶堆时是从最后一个有子节点开始往上调整最大堆。

（2）而堆顶元素(最大数)与堆最后一个数交换后，需再次调整成大顶堆，此时是从上往下调整的。

（3）不管是初始大顶堆的从下往上调整，还是堆顶堆尾元素交换，每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换，交换之后都可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整。

package day1024;

/**
* 堆排序
*/
public class Solution {
    public static void heapSort(int[] a) {
        //从第一个非叶子节点开始，从下往上，从右向左调整堆
        for (int i = a.length / 2 - 1; i >= 0; i--) {
            adjust(a, i, a.length);
        }

        //构建完堆后，需要首先交换堆顶元素与尾元素，然后除堆尾元素，再次进行堆的调整
        for (int j = a.length - 1; j > 0; j--) {
            //交换堆顶元素与尾元素
            swap(a, 0, j);
            //再次对堆进行排序，每次都需要排除有序的元素
            adjust(a, 0, j);

        }
    }

    /**
     * 调整节点a[i]，其左节点a[2i+1]，右节点a[2i+2],且左右子节点均在length范围内
     */
    public static void adjust(int[] a, int i, int length) {
        //先是该节点的左节点b，然后是b的左节点，
        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
            //如果该节点有右节点的话，并且右节点最大时，将k指向右节点
            if (k + 1 < length && a[k] < a[k + 1]) {
                k++;
            }
            //此时a[k]已经是左右两节点最大的节点
            if (a[k] > a[i]) {
                //交换两元素
                swap(a, i, k);
                //由于交换节点与子节点，导致子节点构成的堆乱序，因此将元素下标改为其子节点下标
                i = k;
            } else {
                break;
            }
        }

    }

    /**
     * 交换数组中的两个元素
     */
    public static void swap(int[] a, int m, int n) {
        int temp = a[m];
        a[m] = a[n];
        a[n] = temp;
    }

    public static void main(String[] args) {
        int[] a = {-7, 11, 44, 7, -89, 34, 12, 67, 90, 34, 67, -89, 3, 1, 9, 0, 4, 2, -7, 95, 700, 21, 65, -900};
        heapSort(a);
        for (int temp : a) {
            System.out.print(temp + " ");
        }
    }

}

15、最长回文子串

要求：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1：

输入: "babad"

输出: "bab"

这里我们采用动态规划。

主要思路：

（1）声明一个布尔类型的二维数组dp，boolean[][] dp = new boolean[len][len]，len为字符串s的长度，那么如果dp[i][j]为true时，则表示字符串s从第i个位置开始到第j个位置结束之间的子字符串为回文子串。

如：s="abac"，那么此时dp声明为dp[4][4]，那么dp[0][0],dp[1][1],dp[2][2],dp[3][3],dp[0][2]都为true,表示对应位置的字母都是回文子串，那么这里最大长度的回文子串为aba。

（2）如果dp[i][j]为true，那么dp[i+1][j-1]也必定为true，即“abba”为回文子串，那么“bb”也为回文子串。因此我们的状态转移方程为dp[i+1][j-1]=true&&s.charAt(i)==s.charAt(j) => dp[i][j]为true。

（3）如果j-i<=2时，即可能为回文的字符串最大长度为3时，如果有s.charAt(i)==s.charAt(j)，就直接断定dp[i][j]=true，并不需要dp[i+1][j-1]=true。即当s="abad",i=0;j=2,s.charAt(0)==s.charAt(2)，则直接判定aba为回文字符串，即dp[0][2]=true。

（4）使用两层for循环，外层循环指示器i控制所求字符串的开始位置，内层循环指示器j控制所求字符串的结束位置。但不是简单的使得i从0开始，i++，j=i，j++，而是需要i从最大值开始，即字符串的长度-1开始，i--，j=i，j++，先求出小范围内下标大的dp情况，再求出大范围内下标小的情况，因为后者依赖前者。例如dp[0][3]依赖dp[1][2]的值。

public static String longestPalindrome(String str) {
    int len = str.length();
    boolean[][] dp = new boolean[len][len];
    //回文串最大长度，开始下标，结束下标
    int max = 0;
    int start = 0;
    int stop = 0;

    //先从下标大的元素开始，因为dp[0][8]依赖dp[2][6]
    for (int i = len - 1; i >= 0; i--) {
        for (int j = i; j < len; j++) {
            if (str.charAt(i) == str.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                if (max < j - i + 1) {
                    max = j - i + 1;
                    start = i;
                    stop = j;
                }
            }
        }
    }
    return str.substring(start, stop + 1);
}