接触 Android 开发也有一段时间了，前段时间便开始想抽空整理一些知识点，通过笔记整理的方式减少自己重复学习的时间成本和提高自身的效率。

本文总结的部分是常见面试算法题，算法题解均有 java 实现。目录可以在右边侧边栏查看跳转。

之后会整理的知识点还会有 java、Android SDK、Android 源码、其他的一些计算机基础以及常见的面试题等几个部分，往后的一个月时间里会陆续补充更新，在 Github 上创建了项目，想关注的欢迎 star 。

• Android复习资料

另外，可查看下一篇：：

• Android复习资料——常见面试算法题汇总（二）

排序

比较排序

冒泡排序

重复地走访过要排序的数列，每次比较相邻两个元素，如果它们的顺序错误就把它们交换过来，越大的元素会经由交换慢慢“浮”到数列的尾端。

public void bubbleSort(int[] arr) {
    int temp = 0;
    boolean swap;
    for (int i = arr.length - 1; i > 0; i--) { // 每次需要排序的长度
        // 增加一个swap的标志，当前一轮没有进行交换时，说明数组已经有序
        swap = false;
        for (int j = 0; j < i; j++) { // 从第一个元素到第i个元素
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swap = true;
            }
        }
        if (!swap){
            break;
        }
    }
}

归并排序

分解待排序的数组成两个各具 n/2 个元素的子数组，递归调用归并排序两个子数组，合并两个已排序的子数组成一个已排序的数组。

public void mergeSort(int[] arr) {
    int[] temp = new int[arr.length];
    mergeSort(arr, temp, 0, arr.length - 1);
}

private void mergeSort(int[] arr, int[] temp, int left, int right) {
    // 当left == right时，不需要再划分
    if (left < right) {
        int mid = (left + right) / 2;
        internalMergeSort(arr, temp, left, mid);
        internalMergeSort(arr, temp, mid + 1, right);
        mergeSortedArray(arr, temp, left, mid, right);
    }
}

// 合并两个有序子序列
public void mergeSortedArray(int[] arr, int[] temp, int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= right) {
        temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    // 把temp数据复制回原数组
    for (i = 0; i < k; i++) {
        arr[left + i] = temp[i];
    }
}

快速排序

在待排序的数组选取一个元素作为基准，将待排序的元素进行分区，比基准元素大的元素放在一边，比其小的放另一边，递归调用快速排序对两边的元素排序。选取基准元素并分区的过程采用双指针左右交换。

public void quickSort(int[] arr){
    quickSort(arr, 0, arr.length-1);
}

private void quickSort(int[] arr, int low, int high){
    if (low >= high)
        return;
    int pivot = partition(arr, low, high);        //将数组分为两部分
    quickSort(arr, low, pivot - 1);                   //递归排序左子数组
    quickSort(arr, pivot + 1, high);                  //递归排序右子数组
}

private int partition(int[] arr, int low, int high){
    int pivot = arr[low];     //基准
    while (low < high){
        while (low < high && arr[high] >= pivot) {
            high--;
        }
        arr[low] = arr[high];             //交换比基准大的记录到左端
        while (low < high && arr[low] <= pivot) {
            low++;
        }
        arr[high] = arr[low];           //交换比基准小的记录到右端
    }
    //扫描完成，基准到位
    arr[low] = pivot;
    //返回的是基准的位置
    return low;
}

线性排序

计数排序

根据待排序的数组中最大和最小的元素，统计数组中每个值为i的元素出现的次数，存入数组C的第i项，对所有的计数累加，然后反向填充目标数组。

public void countSort(int[] arr) {
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < arr.length; i++){
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }

    int[] b = new int[arr.length]; // 存储数组
    int[] count = new int[max - min + 1]; // 计数数组

    for (int num = min; num <= max; num++) {
        // 初始化各元素值为0，数组下标从0开始因此减min
        count[num - min] = 0;
    }

    for (int i = 0; i < arr.length; i++) {
        int num = arr[i];
        count[num - min]++; // 每出现一个值，计数数组对应元素的值+1
        // 此时count[i]表示数值等于i的元素的个数
    }

    for (int i = min + 1; i <= max; i++) {
        count[i - min] += count[i - min - 1];
        // 此时count[i]表示数值<=i的元素的个数
    }

    for (int i = 0; i < arr.length; i++) {
            int num = arr[i]; // 原数组第i位的值
            int index = count[num - min] - 1; //加总数组中对应元素的下标
            b[index] = num; // 将该值存入存储数组对应下标中
            count[num - min]--; // 加总数组中，该值的总和减少1。
    }

    // 将存储数组的值替换给原数组
    for(int i=0; i < arr.length;i++){
        arr[i] = b[i];
    }
}

桶排序

找出待排序数组中的最大值max、最小值min，数组ArrayList作为桶，桶里放的元素用ArrayList存储。计算每个元素 arr[i] 放的桶，每个桶各自排序，遍历桶数组，把排序好的元素放进输出数组。

public static void bucketSort(int[] arr){
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < arr.length; i++){
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }
    // 桶数
    int bucketNum = (max - min) / arr.length + 1;
    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
    for(int i = 0; i < bucketNum; i++){
        bucketArr.add(new ArrayList<Integer>());
    }
    // 将每个元素放入桶
    for(int i = 0; i < arr.length; i++){
        int num = (arr[i] - min) / (arr.length);
        bucketArr.get(num).add(arr[i]);
    }
    // 对每个桶进行排序
    for(int i = 0; i < bucketArr.size(); i++){
        Collections.sort(bucketArr.get(i));
        for (int j = 0; j < bucketArr.get(i).size(); j++) {
            arr[j] = bucketArr.get(i).get(j);
        }
    }
}

二叉树

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

    public TreeNode(int val) {
        this.val = val;
    }
}

顺序遍历

先序遍历: 根->左->右
中序遍历: 左->根->右
后序遍历: 左->右->根

// 先序遍历
public void preTraverse(TreeNode root) {
    if (root != null) {
        System.out.println(root.val);
        preTraverse(root.left);
        preTraverse(root.right);
    }
}

// 中序遍历
public void inTraverse(TreeNode root) {
    if (root != null) {
        inTraverse(root.left);
        System.out.println(root.val);
        inTraverse(root.right);
    }
}

// 后序遍历
public void postTraverse(TreeNode root) {
    if (root != null) {
        postTraverse(root.left);
        postTraverse(root.right);
        System.out.println(root.val);
    }
}

层次遍历

// 层次遍历(DFS)
public static List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    
    dfs(root, res, 0);
    return res;
}

private void dfs(TreeNode root, List<List<Integer>> res, int level) {
    if (root == null) {
        return;
    }
    if (level == res.size()) {
        res.add(new ArrayList<>());
    }
    res.get(level).add(root.val);
    
    dfs(root.left, res, level + 1);
    dfs(root.right, res, level + 1);
}

// 层次遍历(BFS)
public List<List<Integer>> levelOrder(TreeNode root) {
    List result = new ArrayList();

    if (root == null) {
        return result;
    }

    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        ArrayList<Integer> level = new ArrayList<Integer>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode head = queue.poll();
            level.add(head.val);
            if (head.left != null) {
                queue.offer(head.left);
            }
            if (head.right != null) {
                queue.offer(head.right);
            }
        }
        result.add(level);
    }

    return result;
}

// "Z"字遍历
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    
    if (root == null){
        return result;
    }
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    boolean isFromLeft = false;
    while(!queue.isEmpty()){
        int size = queue.size();
        isFromLeft = !isFromLeft;
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < size; i++){
            TreeNode node;
            if (isFromLeft){
                node = queue.pollFirst();
            }else{
                node = queue.pollLast();
            }
            list.add(node.val);
            
            if (isFromLeft){
                if (node.left != null){
                    queue.offerLast(node.left);
                }
                if (node.right != null){
                    queue.offerLast(node.right);
                }
            }else{
                if (node.right != null){
                    queue.offerFirst(node.right);
                }
                if (node.left != null){
                    queue.offerFirst(node.left);
                }
            }
        }
        result.add(list);
    }
    
    return result;
}

左右翻转

public void invert(TreeNode root) {
    if (root == null) {
        return;
    }
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    
    invert(root.left);
    invert(root.right);
}

最大值

public int getMax(TreeNode root) {
    if (root == null) {
        return Integer.MIN_VALUE;
    } else {
        int left = getMax(root.left);
        int right = getMax(root.right);
        return Math.max(Math.max(left, rigth), root.val);
    }
}

最大深度

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    return Math.max(left, right) + 1;
}

最小深度

public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    
    int left = minDepth(root.left);
    int right = minDepth(root.right);
    
    if (left == 0) {
        return right + 1;
    } else if (right == 0) {
        return left + 1;
    } else {
        return Math.min(left, right) + 1;
    }
}

平衡二叉树

平衡二叉树每一个节点的左右两个子树的高度差不超过1

public boolean isBalanced(TreeNode root) {
    return maxDepth(root) != -1;
}

private int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
        return -1;
    }
    return Math.max(left, right) + 1;
}

链表

public class ListNode {
     int val;
     ListNode next;
     ListNode(int x) {
         val = x;
         next = null;
    }
}

删除节点

public void deleteNode(ListNode node) {
    if (node.next == null){
        node = null;
        return;
    }
    // 取缔下一节点
    node.val = node.next.val
    node.next = node.next.next
}

翻转链表

public ListNode reverse(ListNode head) {
    //prev表示前继节点
    ListNode prev = null;
    while (head != null) {
        //temp记录下一个节点，head是当前节点
        ListNode temp = head.next;
        head.next = prev;
        prev = head;
        head = temp;
    }
    return prev;
}

中间元素

public ListNode findMiddle(ListNode head){
    if(head == null){
        return null;
    }
    
    ListNode slow = head;
    ListNode fast = head;
    
    // fast.next = null 表示 fast 是链表的尾节点
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

判断是否为循环链表

public Boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }

    ListNode slow = head;
    ListNode fast = head.next;
    
    while (fast != slow) {
        if(fast == null || fast.next == null) {
            return false;
        }
        fast = fast.next.next;
        slow = slow.next;
    } 
    return true;
}

合并两个已排序链表

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode lastNode = dummy;
    
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            lastNode.next = l1;
            l1 = l1.next;
        } else {
            lastNode.next = l2;
            l2 = l2.next;
        }
        lastNode = lastNode.next;
    }
    
    if (l1 != null) {
        lastNode.next = l1;
    } else {
        lastNode.next = l2;
    }
    
    return dummy.next;
}

链表排序

可利用归并、快排等算法实现

// 归并排序
public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode mid = findMiddle(head);

    ListNode right = sortList(mid.next);
    mid.next = null;
    ListNode left = sortList(head);

    return mergeTwoLists(left, right);
}

// 快速排序
public ListNode sortList(ListNode head) {
    quickSort(head, null);
    return head;
}

private void quickSort(ListNode start, ListNode end) {
    if (start == end) {
        return;
    }
    
    ListNode pt = partition(start, end);
    quickSort(start, pt);
    quickSort(pt.next, end);
}

private ListNode partition(ListNode start, ListNode end) {
    int pivotKey = start.val;
    ListNode p1 = start, p2 = start.next;
    while (p2 != end) {
        if (p2.val < pivotKey) {
            p1 = p1.next;
            swapValue(p1, p2);
        }
        p2 = p2.next;
    }
    
    swapValue(start, p1);
    return p1;
}

private void swapValue(ListNode node1, ListNode node2) {
    int tmp = node1.val;
    node1.val = node2.val;
    node2.val = tmp;
}

删除倒数第N个节点

public ListNode removeNthFromEnd(ListNode head, int n) {
    if (n <= 0) {
        return null;
    }
    
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    ListNode preDelete = dummy;
    for (int i = 0; i < n; i++) {
        if (head == null) {
            return null;
        }
        head = head.next;
    }
    // 此时head为正数第N个节点
    while (head != null) {
        head = head.next;
        preDelete = preDelete.next;
    }
    preDelete.next = preDelete.next.next;
    return dummy.next;
}

两个链表是否相交

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }

    ListNode currA = headA;
    ListNode currB = headB;
    int lengthA = 0;
    int lengthB = 0;

    // 让长的先走到剩余长度和短的一样
    while (currA != null) {
        currA = currA.next;
        lengthA++;
    }
    while (currB != null) {
        currB = currB.next;
        lengthB++;
    }

    currA = headA;
    currB = headB;
    while (lengthA > lengthB) {
        currA = currA.next;
        lengthA--;
    }
    while (lengthB > lengthA) {
        currB = currB.next;
        lengthB--;
    }
    
    // 然后同时走到第一个相同的地方
    while (currA != currB) {
        currA = currA.next;
        currB = currB.next;
    }
    // 返回交叉开始的节点
    return currA;
}

栈 / 队列

带最小值操作的栈

实现一个栈, 额外支持一个操作：min() 返回栈中元素的最小值

public class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack; // 维护一个辅助栈，传入当前栈的最小值
    
    public MinStack() {
        stack = new Stack<Integer>();
        minStack = new Stack<Integer>();
    }

    public void push(int number) {
        stack.push(number);
        if (minStack.isEmpty()) {
            minStack.push(number);
        } else {
            minStack.push(Math.min(number, minStack.peek()));
        }
    }

    public int pop() {
        minStack.pop();
        return stack.pop();
    }

    public int min() {
        return minStack.peek();
    }
}

有效括号

给定一个字符串所表示的括号序列，包含以下字符： ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’， 判定是否是有效的括号序列。括号必须依照 “()” 顺序表示， “()[]{}” 是有效的括号，但 “([)]” 则是无效的括号。

public boolean isValidParentheses(String s) {
    Stack<Character> stack = new Stack<Character>();
    for (Character c : s.toCharArray()) {
        if ("({[".contains(String.valueOf(c))) {
            stack.push(c);
        } else {
            if (!stack.isEmpty() && isValid(stack.peek(), c)) {
                stack.pop();
            } else {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

private boolean isValid(char c1, char c2) {
    return (c1 == '(' && c2 == ')') || (c1 == '{' && c2 == '}')
        || (c1 == '[' && c2 == ']');
}

用栈实现队列

public class MyQueue {
    private Stack<Integer> outStack;
    private Stack<Integer> inStack;

    public MyQueue() {
       outStack = new Stack<Integer>();
       inStack = new Stack<Integer>();
    }
    
    private void in2OutStack(){
        while(!inStack.isEmpty()){
            outStack.push(inStack.pop());
        }
    }
    
    public void push(int element) {
        inStack.push(element);
    }

    public int pop() {
        if(outStack.isEmpty()){
            this.in2OutStack();
        }
        return outStack.pop();
    }

    public int top() {
        if(outStack.isEmpty()){
            this.in2OutStack();
        }
        return outStack.peek();
    }
}

逆波兰表达式求值

在反向波兰表示法中计算算术表达式的值, [“2”, “1”, “+”, “3”, “*”] -> (2 + 1) * 3 -> 9

public int evalRPN(String[] tokens) {
    Stack<Integer> s = new Stack<Integer>();
    String operators = "+-*/";
    for (String token : tokens) {
        if (!operators.contains(token)) {
            s.push(Integer.valueOf(token));
            continue;
        }

        int a = s.pop();
        int b = s.pop();
        if (token.equals("+")) {
            s.push(b + a);
        } else if(token.equals("-")) {
            s.push(b - a);
        } else if(token.equals("*")) {
            s.push(b * a);
        } else {
            s.push(b / a);
        }
    }
    return s.pop();
}

二分

二分搜索

public int binarySearch(int[] arr, int start, int end, int hkey){
    if (start > end) {
        return -1;
    }

    int mid = start + (end - start) / 2;    //防止溢位
    if (arr[mid] > hkey) {
        return binarySearch(arr, start, mid - 1, hkey);
    }
    if (arr[mid] < hkey) {
        return binarySearch(arr, mid + 1, end, hkey);
    } 
    return mid;  
}

X的平方根

public int sqrt(int x) {
    if (x < 0)  {
        throw new IllegalArgumentException();
    } else if (x <= 1) {
        return x;
    }

    int start = 1, end = x;
    // 直接对答案可能存在的区间进行二分 => 二分答案
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (mid == x / mid) {
            return mid;
        }  else if (mid < x / mid) {
            start = mid;
        } else {
            end = mid;
        }  
    }
    if (end > x / end) {
        return start;
    }
    return end;
}

哈希表

两数之和

给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。需要实现的函数twoSum需要返回这两个数的下标。

用一个hashmap来记录，key记录target-numbers[i]的值，value记录numbers[i]的i的值，如果碰到一个 numbers[j]在hashmap中存在，那么说明前面的某个numbers[i]和numbers[j]的和为target，i和j即为答案

public int[] twoSum(int[] numbers, int target) {

    HashMap<Integer,Integer> map = new HashMap<>();

    for (int i = 0; i < numbers.length; i++) {
        if (map.containsKey(numbers[i])) {
            return new int[]{map.get(numbers[i]), i};
        }
        map.put(target - numbers[i], i);
    }

    return new int[]{};
}

连续数组

给一个二进制数组，找到 0 和 1 数量相等的子数组的最大长度

使用一个数字sum维护到i为止1的数量与0的数量的差值。在loop i的同时维护sum并将其插入hashmap中。对于某一个sum值，若hashmap中已有这个值，则当前的i与sum上一次出现的位置之间的序列0的数量与1的数量相同。

public int findMaxLength(int[] nums) {
    Map<Integer, Integer> prefix = new HashMap<>();
    int sum = 0;
    int max = 0;
    prefix.put(0, -1); // 当第一个0 1数量相等的情况出现时，数组下标减去-1得到正确的长度
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        if (num == 0) {
            sum--;
        } else {
            sum++;
        }
        
        if (prefix.containsKey(sum)) {
            max = Math.max(max, i - prefix.get(sum));
        } else {
            prefix.put(sum, i);
        }
    }
    
    return max;
}

最长无重复字符的子串

用HashMap记录每一个字母出现的位置。设定一个左边界, 到当前枚举到的位置之间的字符串为不含重复字符的子串。若新碰到的字符的上一次的位置在左边界右边, 则需要向右移动左边界

public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    HashMap<Character, Integer> map = new HashMap<>();
    int max = Integer.MIN_VALUE;
    int start = -1; // 计算无重复字符子串开始的位置
    int current = 0;
    for (int i = 0; i < s.length(); i++) {
        if (map.containsKey(s.charAt(i))) {
            int tmp = map.get(s.charAt(i));
            if (tmp >= start) { // 上一次的位置在左边界右边, 则需要向右移动左边界
                start = tmp;
            }
        } 
        
        map.put(s.charAt(i), i);
        max = Math.max(max, i - start);
    }
    return max;
}

最多点在一条直线上

给出二维平面上的n个点，求最多有多少点在同一条直线上

class Point {
    int x;
    int y;
    Point() { 
        x = 0; y = 0; 
    }
    Point(int a, int b) { 
        x = a; y = b; 
    }
}

通过HashMap记录下两个点之间的斜率相同出现的次数，注意考虑点重合的情况

public int maxPoints(Point[] points) {
    if (points == null) {
        return 0;
    }
    
    int max = 0;
    for (int i = 0; i < points.length; i++) {
        Map<Double, Integer> map = new HashMap<>();
        int maxPoints = 0;
        int overlap = 0;
        for (int j = i + 1; j < points.length; j++) {
            if (points[i].x == points[j].x && points[i].y == points[j].y) {
                overlap++; // 两个点重合的情况记录下来
                continue;
            }
            double rate = (double)(points[i].y - points[j].y) / (points[i].x - points[j].x);
            if (map.containsKey(rate)) {
                map.put(rate, map.get(rate) + 1);
            } else {
                map.put(rate, 2);
            }
            maxPoints = Math.max(maxPoints, map.get(rate));
        }
        if (maxPoints == 0) maxPoints = 1;
        max = Math.max(max, maxPoints + overlap);
    }
    return max;
}

堆 / 优先队列

前K大的数

// 维护一个 PriorityQueue，以返回前K的数
public int[] topk(int[] nums, int k) {
    int[] result = new int[k];
    if (nums == null || nums.length < k) {
        return result;
    }
    
    Queue<Integer> pq = new PriorityQueue<>();
    for (int num : nums) {
        pq.add(num);
        if (pq.size() > k) {
            pq.poll();
        }
    }
    
    for (int i = k - 1; i >= 0; i--) {
        result[i] = pq.poll(); 
    }
    
    return result;
}

前K大的数II

实现一个数据结构，提供下面两个接口：1.add(number) 添加一个元素 2.topk() 返回前K大的数

public class Solution {
    private int maxSize;
    private Queue<Integer> minheap;
    public Solution(int k) {
        minheap = new PriorityQueue<>();
        maxSize = k;
    }

    public void add(int num) {
        if (minheap.size() < maxSize) {
            minheap.offer(num);
            return;
        }
        
        if (num > minheap.peek()) {
            minheap.poll();
            minheap.offer(num);
        }
    }

    public List<Integer> topk() {
        Iterator it = minheap.iterator();
        List<Integer> result = new ArrayList<Integer>();
        while (it.hasNext()) {
            result.add((Integer) it.next());
        }
        Collections.sort(result, Collections.reverseOrder());
        return result;
    }
}

第K大的数

public int kthLargestElement(int k, int[] nums) {
    if (nums == null || nums.length == 0 || k < 1 || k > nums.length){
        return -1;
    }
    return partition(nums, 0, nums.length - 1, nums.length - k);
}

private int partition(int[] nums, int start, int end, int k) {
    if (start >= end) {
        return nums[k];
    }
    
    int left = start, right = end;
    int pivot = nums[(start + end) / 2];
    
    while (left <= right) {
        while (left <= right && nums[left] < pivot) {
            left++;
        }
        while (left <= right && nums[right] > pivot) {
            right--;
        }
        if (left <= right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
    
    if (k <= right) {
        return partition(nums, start, right, k);
    }
    if (k >= left) {
        return partition(nums, left, end, k);
    }
    return nums[k];
}    

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

二叉搜索树

验证二叉搜索树

public boolean isValidBST(TreeNode root) {
    return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean isValidBST(TreeNode root, long min, long max){
    if (root == null) {
        return true;
    }
    
    if (root.val <= min || root.val >= max){
        return false;
    }
    
    return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
}

第K小的元素

增加getCount方法来获取传入节点的子节点数（包括自己），从root节点开始判断k值和子节点数的大小决定递归路径是往左还是往右。

public int kthSmallest(TreeNode root, int k) {
    if (root == null) {
        return 0;
    }
    
    int leftCount = getCount(root.left);
    if (leftCount >= k) {
        return kthSmallest(root.left, k);
    } else if (leftCount + 1 == k) {
        return root.val;
    } else {
        return kthSmallest(root.right, k - leftCount - 1);
    }
}

private int getCount(TreeNode root) {
    if (root == null) {
        return 0;
    }
    
    return getCount(root.left) + getCount(root.right) + 1;
}

数组 / 双指针

加一

给定一个非负数，表示一个数字数组，在该数的基础上+1，返回一个新的数组。该数字按照数位高低进行排列，最高位的数在列表的最前面。

public int[] plusOne(int[] digits) {
    int carries = 1;
    for(int i = digits.length - 1; i >= 0 && carries > 0; i--){ 
        int sum = digits[i] + carries;
        digits[i] = sum % 10;
        carries = sum / 10;
    }
    if(carries == 0) {
        return digits;
    }
        
    int[] rst = new int[digits.length + 1];
    rst[0] = 1;
    for(int i = 1; i < rst.length; i++){
        rst[i] = digits[i - 1];
    }
    return rst;
}

删除元素

给定一个数组和一个值，在原地删除与值相同的数字，返回新数组的长度。

public int removeElement(int[] A, int elem) {
    if (A == null || A.length == 0) {
        return 0;
    }
    
    int index = 0;
    for (int i = 0; i < A.length; i++) {
        if (A[i] != elem) {
            A[index++] = A[i];
        } 
    }
    
    return index;
}

删除排序数组中的重复数字

在原数组中“删除”重复出现的数字，使得每个元素只出现一次，并且返回“新”数组的长度。

public int removeDuplicates(int[] A) {
    if (A == null || A.length == 0) {
        return 0;
    }
    
    int size = 0;
    for (int i = 0; i < A.length; i++) {
        if (A[i] != A[size]) {
            A[++size] = A[i];
        }
    }
    return size + 1;
}

我的日程安排表 I

实现MyCalendar类来存储活动。如果新添加的活动没有重复，则可以添加。类将有方法book(int start，int end)。这代表左闭右开的间隔[start，end)有了预定，范围内的实数x，都满足start <= x < end，返回true。 否则，返回false，并且事件不会添加到日历中。

TreeMap 是一个有序的key-value集合，它通过 红黑树 实现，继承于AbstractMap，所以它是一个Map，即一个key-value集合。TreeMap可以查询小于等于某个值的最大的key，也可查询大于等于某个值的最小的key。 元素的顺序可以改变，并且对新的数组不会有影响。

class MyCalendar {
    TreeMap<Integer, Integer> calendar;

    MyCalendar() {
        calendar = new TreeMap();
    }

    public boolean book(int start, int end) {
        Integer previous = calendar.floorKey(start), next = calendar.ceilingKey(start);
        if ((previous == null || calendar.get(previous) <= start) && (next == null || end <= next)) {
            calendar.put(start, end);
            return true;
        }
        return false;
    }
}

合并排序数组

合并两个排序的整数数组A和B变成一个新的数组。可以假设A具有足够的空间去添加B中的元素。

public void mergeSortedArray(int[] A, int m, int[] B, int n) {
    int i = m - 1, j = n - 1, index = m + n - 1;
    while (i >= 0 && j >= 0) {
        if (A[i] > B[j]) {
            A[index--] = A[i--];
        } else {
            A[index--] = B[j--];
        }
    }
    while (i >= 0) {
        A[index--] = A[i--];
    }
    while (j >= 0) {
        A[index--] = B[j--];
    }
}

贪心

买卖股票的最佳时机

假设有一个数组，它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如，一次买卖股票)，设计一个算法来找出最大利润。

public int maxProfit(int[] prices) {
    if (prices == null || prices.length == 0) {
        return 0;
    }

    int min = Integer.MAX_VALUE; //记录最低的价格
    int profit = 0;
    for (int price : prices) {
        min = Math.min(price, min);
        profit = Math.max(price - min, profit);
    }

    return profit;
}

买卖股票的最佳时机 II

给定一个数组 prices 表示一支股票每天的价格。可以完成任意次数的交易, 不过不能同时参与多个交易，设计一个算法求出最大的利润。

贪心：只要相邻的两天股票的价格是上升的, 我们就进行一次交易, 获得一定利润。

public int maxProfit(int[] prices) {
    int profit = 0;
    for (int i = 0; i < prices.length - 1; i++) {
        int diff = prices[i + 1] - prices[i];
        if (diff > 0) {
            profit += diff;
        }
    }
    return profit;
}

最大子数组

给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。

public int maxSubArray(int[] A) {
    if (A == null || A.length == 0){
        return 0;
    }
    //max记录全局最大值，sum记录区间和，如果当前sum>0，那么可以继续和后面的数求和，否则就从0开始
    int max = Integer.MIN_VALUE, sum = 0;
    for (int i = 0; i < A.length; i++) {
        sum += A[i];
        max = Math.max(max, sum);
        sum = Math.max(sum, 0);
    }

    return max;
}

主元素

给定一个整型数组，找出主元素，它在数组中的出现次数严格大于数组元素个数的二分之一(可以假设数组非空，且数组中总是存在主元素)。

public int majorityNumber(List<Integer> nums) {
    int currentMajor = 0;
    int count = 0;

    for(Integer num : nums) {
        if(count == 0) {
            currentMajor = num;
        }
        
        if(num == currentMajor) {
            count++;
        } else {
            count--;
        }
    }
    return currentMajor;
}

本次的分享就到这啦，喜欢的话可以点个赞👍或关注。如有错误的地方欢迎大家在评论里指出。

本文为个人原创，转载请注明出处。