算法

堆排序
java

public static void heapSort(int[] arr) {
        int len = arr.length;
        // 1. 构建大顶堆
        for (int i = len / 2 - 1; i >= 0; i --) {
            // 从倒数第一个非叶子结点从下至上，从右至左调整结构
            heapAdjust(arr, i, len);
        }
        // 2. 每一趟排序，都将大顶堆的堆顶与数组的索引j处的值交换
        // 索引j最开始指向数组尾部，随着每一趟排序的结束自减，直到指向数组头部
        for (int j = len - 1; j > 0; j--) {
            int tmp = arr[0];
            arr[0] = arr[j];
            arr[j] = tmp;
            heapAdjust(arr, 0, j);
        }
    }
    public static void heapAdjust(int[] arr, int i, int len) {
        // 记录传入节点值
        int tmp = arr[i];
        // 从i节点的左子节点开始，即i*2+1
        for (int k = 2 * i + 1; k < len; k = 2 * k + 1) {
            // 当左子节点小于右子节点，则让父节点与右子节点相比
            if (k + 1 < len && arr[k] < arr[k+1]) {
                k++;
            }
            // 若最大的子节点比传入节点大，则将最大的子节点的位置移到传入节点上
            if (arr[k] > tmp) {
                arr[i] = arr[k];
                i = k;
            } else {
                break;
            }
        }
        // 传入节点值放在最终的位置
        arr[i] = tmp;
    }

go

func heapSort(arr []int) {
    l := len(arr)
    // 1. 构建大顶堆
    for i := l / 2 - 1; i >= 0; i-- {
        // 从最后一个非叶子节点，从下至上，从右至左调整结构
        heapAdjust(arr, i, l)
    }
    // 2. 每一趟排序，都将大顶堆堆顶与数组的索引j处的值交换
    for j := l - 1; j > 0; j-- {
        arr[0], arr[j] = arr[j], arr[0]
        heapAdjust(arr, 0, j)
    }
}
func heapAdjust(heap []int, i int, l int) {
    // 记录传入的节点值
    tmp := heap[i]
    // 从i的左子节点开始
    for k := 2 * i + 1; k < l; k = k * 2 + 1 {
        // 当左子节点小于右子节点，则让父亲节点与右子节点相比较
        if k + 1 < l && heap[k] < heap[k + 1] {
            k++
        }
        if heap[k] > tmp {
            heap[i] = heap[k]
            i = k
        } else {
            break
        }
    }
    // 传入节点值最终放在的位置
    heap[i] = tmp
}

归并排序
java

public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
    }
}
public static void merge(int[] arr, int left, int mid, int right) {
    int[] tmpArr = new int[right - left + 1];
    int index = 0;
    int i = left, j = mid + 1;
    while (i <= mid && j < right) {
        tmpArr[index++] = (arr[i] <= arr[j] ? arr[i++] : arr[j++]);
    }
    while (i <= mid) tmpArr[index++] = arr[i++];
    while (j <= right) tmpArr[index++] = arr[j++];
    for (int val : tmpArr) {
        arr[left++] = val  
    }
}

go

func mergeSort(arr []int, left, right int) {
    if left < right {
        mid := left + (right - left) / 2
        mergeSort(arr, left, mid)
        mergeSort(arr, mid + 1, right)
        merge(arr, left, mid, right)
    }
}
func merge(arr []int, left, mid, right int) {
    tmpArr := make([]int, right - left + 1)
    index := 0
    i := left
    j := mid + 1
    for i <= mid && j <= right {
        if arr[i] < arr[j] {
            tmpArr[index] = arr[i]
            i++
        } else {
            tmpArr[index] = arr[j]
            j++
        }
        index++
    }
    for i <= mid {
        tmpArr[index] = arr[i]
        i++
        index++
    }
    for j <= right {
        tmpArr[index] = arr[j]
        j++
        index++
    }
    for idx, val := range tmpArr {
        arr[left + idx] = val
    }
}

补充题4.
手撕快速排序
java

public static void quickSort(int[] arr, int low, int high) {
    int p, i, j, temp;
    if (low >= high) {
        return;
    }
    p = arr[low];
    i = low;
    j = high;
    while (i < j) {
        while (i < j && arr[j] >= p) {
            j--;
        }
        while (i < j && arr[i] <= p) {
            i++;
        }
        temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    arr[low] = arr[i];
    arr[i] = p;
    quickSort(arr, low, i - 1);
    quickSort(arr, i + 1, high);
}

go

func quickSort(arr []int, left, right int) {
    if left >= right {
        return
    }
    i := left
    j := right
    p := arr[left]
    for i < j {
        for i < j &&  arr[j] >= p {
            j--
        }
        for i < j && arr[i] <= p {
            i++
        }
        arr[i], arr[j] = arr[j], arr[i]
    }
    arr[left], arr[i] = arr[i], arr[left]
    quickSort(arr, left, i - 1)
    quickSort(arr, i + 1, right)
}

1. 反转链表 7
   java

   /**
   * Definition for singly-linked list.
   * public class ListNode {
   *     int val;
   *     ListNode next;
   *     ListNode() {}
   *     ListNode(int val) { this.val = val; }
   *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   * }
   */
   class Solution {
   public ListNode reverseList(ListNode head) {
    ListNode pre = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
   }
   }

   go

   /**
   * Definition for singly-linked list.
   * type ListNode struct {
   *     Val int
   *     Next *ListNode
   * }
   */
   func reverseList(head *ListNode) *ListNode {
   var pre *ListNode
   cur := head
   for cur != nil {
    next := cur.Next
    cur.Next = pre
    pre = cur
    cur = next
   }
   return pre
   }

2. 二分查找 6

class Solution {
    public int search(int[] nums, int target) {
        int pivot, left = 0, right = nums.length - 1;
        while (left <= right) {
            pivot = left + (right - left) / 2;
            if (target == nums[pivot]) return pivot;
            else if (target < nums[pivot]) right = pivot - 1;
            else left = pivot + 1;
        }
        return -1;
    }
}

go

func search(nums []int, target int) int {
    left := 0
    right := len(nums) - 1
    for left <= right {
        pivot := left + (right - left) / 2
        if target == nums[pivot] {
            return pivot
        } else if target < nums[pivot] {
            right = pivot - 1
        } else {
            left = pivot + 1
        }
    }
    return -1
}

1. 字符串相加 6

1. 二叉树的层序遍历 5

2. 用 Rand7() 实现 Rand10() 5

3. 最大子序和 4

4. 寻找两个正序数组的中位数 4

5. 环形链表