基礎算法
背模板加刷題
排序
快排
主要思想：分治
- 第一步：確認一個分界點，比如起點，中間點（分界點），末點
- 第二步：調整區間，使得第一個區間的數都小于等于分界點，第二個區間都大于分界點
- 遞歸處理左右兩端
private static int[] quickSort(int[] arr, int left, int right) {// 遞歸終止條件，如果左邊界大于等于右邊界則認為遞歸結束if (left >= right) {return arr;}// 設定一個分界值，這里是（left + right）/ 2int p = arr[left + right >> 1];// 左右提前預留一個位置int i = left - 1;int j = right + 1;while (i < j) {// 等效于do while// 當數值小于分界值時持續遍歷，直到找到第一個大于等于分界值的索引// 如果是逆序則調整兩個while循環while (arr[++i] < p);while (arr[--j] > p);// 交換左右兩側不符合預期的數值if (i < j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 由于分界值取的是left + right >> 1，因此遞歸取的是left，j j + 1，rightquickSort(arr, left, j);quickSort(arr, j + 1, right);return arr;
}
歸并排序
歸并排序本質上就是分治！
但是跟快排的分治方法不一樣
- 以整個數組的中間點劃分
- 遞歸排序兩邊
- 將兩個有序的數組合并
private static int[] mergeSort(int[] arr, int left, int right) {// 遞歸終止條件，如果左邊界大于等于右邊界則認為遞歸結束if (left >= right) {return arr;}// 設定一個分界值，這里是（left + right）/ 2int mid = left + right >> 1; // 位運算// 切割arr = mergeSort(arr, left, mid);arr = mergeSort(arr, mid + 1, right);// 歸并，長度剛好是 left 到 rightint[] temp = new int[right - left + 1];int i = left;int j = mid + 1;// 用來歸并的索引int k = 0;while (i <= mid && j <= right) {// 如果是逆序則調整if條件if (arr[i] <= arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}// 如果其中一半已經遍歷完，另一半可能還有剩余元素，直接全部拷貝過來。一般二者肯定會剩下一個出來while (i <= mid) {temp[k++] = arr[i++];}while (j <= right) {temp[k++] = arr[j++];}// 根據歸并后的數組重新賦值排序后的數組for (i = left, j = 0; i <= right; i++, j++) {arr[i] = temp[j];}return arr;
}
二分
有單調性一定可以二分，但是二分不一定有單調性
整數二分
// 檢查x是否滿足某種性質
private static boolean check(int x) { /* ... */
} // 區間[left, right]被劃分成[left, mid]和[mid + 1, right]時使用：
// 或者稱之為左二分查詢，查找左側第一個滿足條件的數
private static int leftBinarySearch(int[] arr, int left, int right) { while (left < right) { int mid = arr[left + right >> 1]; if (check(mid)) { right = mid; // check()判斷mid是否滿足性質 } else { left = mid + 1; } } return left;
} // 區間[left, right]被劃分成[left, mid - 1]和[mid, right]時使用：
// 或者稱之為右二分查詢，查找右側最后一個滿足條件的數
private static int rightBinarySearch(int[] arr, int left, int right) { while (left < right) { int mid = arr[left + right + 1 >> 1]; if (check(mid)) { left = mid; // check()判斷mid是否滿足性質 } else { right = mid - 1; // 有加必有減} } return left;
}
浮點二分
// 檢查x是否滿足某種性質
private static boolean check(double x) { /* ... */
} // eps 表示精度，取決于題目對精度的要求，默認負六次方
private static double EPS = 1e-6;private static double floatBinarySearch(double left, double right) { while (right - left > EPS) { double mid = (left + right) / 2; if (check(mid)) { right = mid; } else { left = mid; } } return left;
}
一維前綴和
S[i] = a[1] + a[2] + … a[i]
a[l] + … + a[r] = S[r] - S[l - 1]
private static final int N = 100010;
private static final int[] a = new int[N + 5];
private static final int[] s = new int[N + 5];private static void init(int n) { for (int i = 1; i <= n; i++) { s[i] = s[i - 1] + a[i]; }
} private static int sumPrefix(int left, int right) { return s[right] - s[left - 1];
}
二維前綴和
S[i, j] = 第 i 行 j 列格子左上部分所有元素的和
以(x1, y1)為左上角，(x2, y2)為右下角的子矩陣的和為：
S[x2, y2] - S[x1-1, y2] - S[x2, y1-1] + S[x1-1, y1-1]
private static final int N = 1010;
private static final int[][] a = new int[N + 5][N + 5];
private static final int[][] s = new int[N + 5][N + 5];private static void init(int n, int m) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]; } }
} private static int sumPrefix(int x1, int y1, int x2, int y2) { return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
}
一維差分
給區間[l, r]中的每個數加上 c：B[l] += c, B[r + 1] -= c
private static final int N = 100010;
private static final int[] a = new int[N + 5];
private static final int[] b = new int[N + 5];private static void init(int n) { for (int i = 1; i <= n; i++) { b[i] = a[i] - a[i - 1]; }
} private static void difference(int left, int right, int c) { b[left] += c; b[right + 1] -= c;
}
