算法笔记 - Java
根据数据范围估算时间复杂度
算法的时间复杂度是大致确定的，但是数据范围却千变万化。所以根据数据范围选择最优算法是一种简单而准确的方法。
以下介绍几种根据数据范围大致对应的时间复杂度。
- $N\leq 20$ $O(2^n)$
- $20<N\leq 100$ $O(n^3)$
- $100<N\leq 1000$ $O(n^2)$
- $10000<N\leq 10^5$ $O(nlogn)$
- $10^5<N\leq 10^8$ $O(n)$
- $N>10^8$ $O(logn)$
十大经典排序算法
常用算法复杂度
| 排序方法 | 时间（平均） | 时间（最坏） | 时间（最好） | 空间 | 稳定性 | 备注 |
|---|---|---|---|---|---|---|
| 插入排序 | $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | 稳定 | 最坏比较次数 $\frac{n(n-1)}{2}$ |
| 希尔排序 | $O(n^{1.3-2})$ | $O(n^2)$ | $O(n)$ | $O(1)$ | 不稳定 | |
| 选择排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 不稳定 | 数组不稳定，链表稳定 |
| 堆排序 | $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ | $O(1)$ | 不稳定 | |
| 冒泡排序 | $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | 稳定 | 最坏比较次数 $\frac{n(n-1)}{2}$ |
| 快速排序 | $O(nlogn)$ | $O(n^2)$ | $O(nlogn)$ | $O(logn)$ | 不稳定 | 最坏比较次数 $\frac{n(n-1)}{2}$ 最坏情况：已排序 or 数值全部相等 |
| 归并排序 | $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ | $O(n)$ | 稳定 |
稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同
// 插入排序
public void insertSort(int[] nums) {
// [0, i]是有序的
for (int i = 0; i < nums.length - 1; ++i) {
int j = i + 1;
int tmp = nums[i + 1];
// 帮i+1找到一个合适的位置，并插入
for (; j - 1 >= 0 && tmp < nums[j - 1]; --j) {
nums[j] = nums[j - 1];
}
nums[j] = tmp;
}
}
// 选择排序
public void selectSort(int[] nums) {
for (int i = 0; i < nums.length; ++i) {
int min = nums[i];
int minIdx = i;
// 在[i+1, nums.length-1]中找到小于nums[i]且最小的元素进行交换
for (int j = i + 1; j < nums.length; ++j) {
if (nums[j] < min) {
min = nums[j];
minIdx = j;
}
}
nums[minIdx] = nums[i];
nums[i] = min;
}
}
// 冒泡排序
public void bubbleSort(int[] nums) {
for (int i = 0; i < nums.length; ++i) {
// 不停地暴力交换
for (int j = 0; j < nums.length - 1; ++j) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
}
}
}
}
// 希尔排序
public void shellSort(int[] nums) {
for (int gap = nums.length / 2; gap > 0; gap /= 2) {
// 同插入排序，但是每次处理的数据间隙是逐步减小的
for (int i = 0; i + gap < nums.length; i += gap) {
int tmp = nums[i + gap];
int j = i + gap;
for (; j - gap >= 0 && tmp < nums[j - gap]; j -= gap) {
nums[j] = nums[j - gap];
}
nums[j] = tmp;
}
}
}
// 归并排序 merge(nums, 0, nums.length - 1)
public void mergeSort(int[] nums, int left, int right) {
int mid = left + (right - left) / 2;
if (left < right) {
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
merge(nums, left, mid, right);
}
}
private void merge(int[] nums, int left, int center, int right) {
int[] tmpArr = new int[nums.length];
// 右数组第一个元素索引
int mid = center + 1;
// third 记录临时数组的索引
int idx = left;
// 缓存左数组第一个元素的索引
int tmp = left;
while (left <= center && mid <= right) {
// 从两个数组中取出最小的放入临时数组
if (nums[left] <= nums[mid]) {
tmpArr[idx++] = nums[left++];
} else {
tmpArr[idx++] = nums[mid++];
}
}
// 剩余部分依次放入临时数组（实际上两个 while 只会执行其中一个）
while (mid <= right) {
tmpArr[idx++] = nums[mid++];
}
while (left <= center) {
tmpArr[idx++] = nums[left++];
}
// 将临时数组中的内容拷贝回原数组中
// 原 left-right 范围的内容被复制回原数组
while (tmp <= right) {
nums[tmp] = tmpArr[tmp++];
}
}
// 快速排序
public void quickSort(int[] nums) {
quickSort0(nums, 0, nums.length-1);
}
// [from, to]
private void quickSort0(int[] nums, int from, int to) {
if (from >= to) {
return ;
}
int cmp = nums[from];
int l = from, r = to;
while (l < r) {
while (l <= r && nums[l] <= cmp) {
++l;
}
while (l <= r && nums[r] > cmp) {
--r;
}
if (l < r) {
swap(nums, l, r);
}
}
swap(nums, from, r);
quickSort0(nums, from, r-1);
quickSort0(nums, r+1, to);
}
private void swap(int[] nums, int idxA, int idxB) {
int tmp = nums[idxA];
nums[idxA] = nums[idxB];
nums[idxB] = tmp;
}
// 堆排序
public void heapSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
heapify(arr, 0, i);
}
}
private void heapInsert(int[] arr, int i) {
int parent = 0;
while (i != 0) {
parent = (i - 1) / 2;
if (arr[parent] < arr[i]) {
swap(arr, parent, i);
i = parent;
} else {
break;
}
}
}
private void heapify(int[] arr, int i, int size) {
int left = i * 2 + 1;
int right = i * 2 + 2;
int largest = i;
while (left < size) {
if (arr[left] > arr[i]) {
largest = left;
}
if (right < size && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, largest, i);
} else {
break;
}
i = largest;
left = i * 2 + 1;
right = i * 2 + 2;
}
}
private void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}递归和动态规划 DP
斐波那契数列
1, 1, 2, 3, 5, 8, …
求第n项；
1）暴力递归 – $O(2^N)$
public int f1(int n) {
if (n < 1) return 0;
if (n == 1 || n == 2) return 1;
return f1(n - 1) + f1(n - 2);
}2）顺序计算 – $O(N)$
public int f2(int n) {
if (n < 1) return 0;
if (n == 1 || n == 2) return 1;
int res = 1, pre = 1, tmp = 0;
for (int i = 3; i <= n; i++) {
tmp = res;
res += pre;
pre = tmp;
}
return res;
}3）加速矩阵乘法的动态规划 – $O(logN)$
$(F(n),F(n-1))=(F(n-1),F(n-2))\times \begin{vmatrix}
1 & 1 \
1 & 0 \
\end{vmatrix}=(1,1)\times {\begin{vmatrix}
1 & 1 \
1 & 0 \
\end{vmatrix}}^{n-2} $
// 求矩阵m的p次方
public int[][] matrixPower(int[][] m, int p) {
int[][] res = new int[m.length][m[0].length];
// 先设res为单位矩阵
for (int i = 0; i < res.length; i++) res[i][i] = 1;
int [][] tmp = m;
// 根据p的二进制数形式进行累乘
for (; p != 0; p >>= 1) {
if ((p & 1) != 0) {
res = multiMatrix(res, tmp);
}
tmp = multiMatrix(tmp, tmp);
}
return res;
}
// 两矩阵相乘
public int[][] multiMatrix(int[][] m1, int[][] m2) {
int[][] res = new int[m1.length][m2[0].length];
for (int i = 0; i < m1.length; i++) {
for (int j = 0; j < m2[0].length; j++) {
for (int k = 0; k < m2.length; k++) {
res[i][j] += m1[i][k] * m2[k][j];
}
}
}
return res;
}
public int f3(int n) {
if (n < 1) return 0;
if (n == 1 || n == 2) return 1;
int [][] base = {{1, 1}, {1, 0}};
int [][] res = matrixPower(base, n - 2);
return res[0][0] + res[1][0];
}矩阵的最小路径和
给定一个矩阵m，从左上角开始只能向右或者向下走，最后达到右下角，返回路径上所有数字加起来的最小和；
输入：
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
输出：12
解释：1-3-1-0-6-1-0
1）dp 矩阵 – 时间 $O(M\times N)$ - 空间 $O(M\times N)$
首先确定第一行和第一列的路径和，其次根据上边和左边的较小值得到整个路径和的矩阵；
public int minPathSum1(int[][] m) {
if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
return 0;
}
int row = m.length, col = m[0].length;
// 初始化dp矩阵
int[][] dp = new int[row][col];
dp[0][0] = m[0][0];
for (int i = 1; i < row; i++) {
dp[i][0] = dp[i - 1][0] + m[i][0];
}
for (int j = 1; j < col; j++) {
dp[0][j] = dp[0][j - 1] + m[0][j];
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
}
}
// 返回结果
return dp[row - 1][col - 1];
}2）空间压缩法（仅适于求最优解，不可回溯） – 时间 $O(M\times N)$ - 空间 $O(min{M,N})$
public int minPathSum2(int[][] m) {
if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
return 0;
}
// 定义行数与列数中的较大和较小的身份
int more = Math.max(m.length, m[0].length);
int less = Math.min(m.length, m[0].length);
// 行数是否大于列数
boolean rowMore = more == m.length;
int[] arr = new int[less]; // 辅助数组的长度仅为较小值
arr[0] = m[0][0];
for (int i = 1; i < less; i++) {
arr[i] = arr[i - 1] + (rowMore ? m[0][i] : m[i][0]);
}
for (int i = 1; i < more; i++) {
arr[0] += rowMore ? m[i][0] : m[0][i];
for (int j = 1; j < less; j++) {
arr[j] = Math.min(arr[j - 1], arr[j]) + (rowMore ? m[i][j] : m[j][i]);
}
}
return arr[less - 1];
}换钱的最少货币数
arr中所有值都是正数且不重复，每个值代表一种面值的货币（可以使用任意张），求组成aim（要找的钱数）的最少货币数；
eg.
arr=[5,2,3], aim=20
4张5元，return 4
arr=[5,2,3], aim=0
不使用任何货币，return 0
arr=[3,5], aim=2
不能找开，return -1
空间压缩法 – 时间 $O(N\times aim)$ - 空间 $O(aim)$
public int minCoins2(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) return -1;
int max = Integer.MAX_VALUE;
int[] dp = new int[aim + 1];
for (int j = 1; j <= aim; j++) {
dp[j] = max;
if (j - arr[0] >= 0 && dp[j - arr[0]] != max) {
dp[j] = dp[j - arr[0]] + 1;
}
}
int tmp;
for (int i = 1; i < arr.length; i++) {
for (int j = 1; j <= aim; j++) {
tmp = max;
if (j - arr[i] >= 0 && dp[j - arr[i]] != max) {
tmp = dp[j - arr[i]] + 1;
}
dp[j] = Math.min(tmp, dp[j]);
}
}
return dp[aim] == max ? -1 : dp[aim];
}换钱的方法数
arr中所有值都是正数且不重复，每个值代表一种面值的货币（可以使用任意张），求组成aim（要找的钱数）的方法数；
eg.
arr=[5,10,25,1], aim=0
return 1
arr=[5,10,25,1], aim=15
return 6
arr=[3,5], aim=2
return 0
1）暴力递归 – 时间 $O(aim^N)$
public int coins1(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) return 0;
return process1(arr, 0, aim);
}
// 如果用arr[index..N-1]面值的钱组成aim，返回总的方法数
public int process1(int[] arr, int index, int aim) {
int res = 0;
if (index == arr.length) {
res = aim == 0 ? 1 : 0; // 递归出口
} else {
for (int i = 0; arr[index] * i <= aim; i++) {
res += process1(arr, index + 1, aim - arr[index] * i);
}
}
return res;
}2）记忆化搜索方法（n维map存储已经计算出的值，n为递归影响因素的个数） – 时间 $O(N\times aim^2)$
记忆化搜索是对必须要计算的递归过程才去计算并记录的。
3）动态规划的优化 – 时间 $O(N\times aim)$
public int coins4(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) return 0;
int[][] dp = new int[arr.length][aim + 1];
for (int i = 0; i < arr.length; i++) {
dp[i][0] = 1;
}
for (int j = 1; arr[0] * j <= aim; j++) {
dp[0][arr[0] * j] = 1;
}
for (int i = 1; i < arr.length; i++) {
for (int j = 1; j <= aim; j++) {
dp[i][j] = dp[i - 1][j]; // 0张此面值的钱的情况
dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0; // 判断是不是越界了
}
}
return dp[arr.length - 1][aim];
}4）动态规划的优化 + 空间压缩 – 时间 $O(N\times aim)$ - 空间 $O(aim)$
public int coins5(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) return 0;
int[] dp = new int[aim + 1];
for (int j = 0; arr[0] * j <= aim; j++) {
dp[arr[0] * j] = 1;
}
for (int i = 1; i < arr.length; i++) {
for (int j = 1; j <= aim; j++) {
dp[j] += j - arr[i] >= 0 ? dp[j - arr[i]] : 0;
}
}
return dp[aim];
}正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*‘ 的正则表达式匹配。
‘.’ 匹配任意单个字符
‘*‘ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。示例 1：
输入：s = “aa”, p = “a”
输出：false
解释：”a” 无法匹配 “aa” 整个字符串。示例 2：
输入：s = “aa”, p = “a*“
输出：true
解释：因为 ‘*‘ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。示例 3：
输入：s = “ab”, p = “.*“
输出：true
解释：”.*“ 表示可匹配零个或多个（’*‘）任意字符（’.’）。
public boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 0; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) != '*') {
if (i >= 1 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')) {
dp[i][j] = dp[i - 1][j - 1];
}
} else {
if (j >= 2 && i >= 1 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')) {
dp[i][j] = dp[i - 1][j];
}
if (j >= 2) {
dp[i][j] |= dp[i][j - 2];
}
}
}
}
return dp[m][n];
}经典题目
背包问题
public class BackPack {
/**
* 0-1 背包
* 有 N 件物品和一个容量为 capacity 的背包。放入第 i 件物品耗费的空间是 cost，得到的价值是 value。
* 求解将哪些物品装入背包可使价值总和最大。
*
* @param N 物品数量
* @param capacity 背包容量
* @param cost 消耗空间
* @param value 价值
* @return 最大价值
*/
public int zeroOnePack(int N, int capacity, int[] cost, int[] value) {
int[][] dp = new int[N + 1][capacity + 1];
boolean[] isAdd = new boolean[N + 1];
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= capacity; j++) {
if (j >= cost[i]) {
dp[i][j] = Math.max(dp[i - 1][j - cost[i]] + value[i], dp[i - 1][j]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
int C = capacity;
for (int i = N; i >= 1; i--) {
if (dp[i][C] == dp[i - 1][C])
isAdd[i] = false;
else {
isAdd[i] = true;
C -= cost[i];
}
}
System.out.println(Arrays.toString(isAdd));
return dp[N][capacity];
}
/**
* 完全背包
* 有 N 种物品和一个容量为 capacity 的背包，每种物品都有无限件可用。放入第i种物品的耗费的空间是 cost，得到的价值是 value。
* 求解：将哪些物品装入背包，可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。
*
* @param N 物品数量
* @param capacity 背包容量
* @param cost 消耗空间
* @param value 价值
* @return 最大价值
*/
public int completePack(int N, int capacity, int[] cost, int[] value) {
int[] dp = new int[capacity + 1];
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= capacity; j++) {
if (j >= cost[i]) {
dp[j] = Math.max(dp[j - cost[i]] + value[i], dp[j]);
}
}
}
return dp[capacity];
}
/**
* 多重背包
* 有 N 种物品和一个容量为 capacity 的背包。第 i 种物品最多有 many 件可用，每件耗费的空间是 cost，价值是 value。
* 求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。
*
* @param N 物品数量
* @param capacity 背包容量
* @param many 物品数量
* @param cost 消耗空间
* @param value 价值
* @return 最大价值
*/
public int multiPack(int N, int capacity, int[] many, int[] cost, int[] value) {
int[][] dp = new int[N + 1][capacity + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= capacity; j++) {
for (int k = 0; k <= many[i]; k++) {
if (j < k * cost[i]) {
continue;
}
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * cost[i]] + k * value[i]);
}
}
}
return dp[N][capacity];
}
}接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
输出：6
解释：上面是由数组 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
public int trap(int[] height) {
int n = height.length;
if (n == 0) {
return 0;
}
// 统计左投影下的雨水量
int[] leftMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; ++i) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
// 统计右投影下的雨水量
int[] rightMax = new int[n];
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; --i) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
// 取较小值，再减去原高度
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
}计算右侧小于当前元素的个数
给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例 1：
输入：nums = [5,2,6,1]
输出：[2,1,1,0]
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素示例 2：
输入：nums = [-1]
输出：[0]示例 3：
输入：nums = [-1,-1]
输出：[0,0]
class Solution {
static int[] ansNum;
static int[] indexes;
public List<Integer> countSmaller(int[] nums) {
indexes = new int[nums.length];
ansNum = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
indexes[i] = i;
}
merge(nums, 0, nums.length - 1);
List<Integer> ans = new ArrayList<>();
for (int num : ansNum) {
ans.add(num);
}
return ans;
}
void merge(int[] nums, int left, int right) {
int mid = left + (right - left) / 2;
if (left < right) {
merge(nums, left, mid);
merge(nums, mid + 1, right);
mergeSort(nums, left, mid, right);
}
}
void mergeSort(int[] nums, int left, int mid, int right) {
int[] tmp = new int[right - left + 1];
int[] tmp_indexes = new int[right - left + 1];
int index = 0;
int indexA = left, indexB = mid + 1;
while (indexA <= mid && indexB <= right) {
if (nums[indexA] <= nums[indexB]) {
tmp_indexes[index] = indexes[indexA];
// 增加符合条件的个数
ansNum[indexes[indexA]] += indexB - mid - 1;
tmp[index++] = nums[indexA++];
} else {
tmp_indexes[index] = indexes[indexB];
tmp[index++] = nums[indexB++];
}
}
while (indexA <= mid) {
tmp_indexes[index] = indexes[indexA];
// 增加符合条件的个数
ansNum[indexes[indexA]] += indexB - mid - 1;
tmp[index++] = nums[indexA++];
}
while (indexB <= right) {
tmp_indexes[index] = indexes[indexB];
tmp[index++] = nums[indexB++];
}
System.arraycopy(tmp, 0, nums, left, tmp.length);
System.arraycopy(tmp_indexes, 0, indexes, left, tmp_indexes.length);
}
}数组题目
和为K的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2示例 2：
输入：nums = [1,2,3], k = 3
输出：2
// 构建前缀和数组，空间换时间
public int subarraySum(int[] nums, int k) {
int n = nums.length;
int[] preSum = new int[n + 1];
preSum[0] = 0;
for (int i = 0; i < n; i++) {
preSum[i + 1] = nums[i] + preSum[i];
}
int ans = 0;
for (int left = 0; left < n; left++) {
for (int right = left; right < n; right++) {
if (preSum[right + 1] - preSum[left] == k) {
ans++;
}
}
}
return ans;
}:star: 未排序数组中累加和为给定值的最长子数组
给定一个无序数组 arr，其中元素可正、可负、可 0。给定一个整数 k，求 arr 所有的子数组中累加和为 k 的最长子数组长度。
int maxLength(int[] arr, int k) {
if (arr == null || arr.length == 0) {
return 0;
}
// map 的 key 值代表某个累加和，value 值代表这个累加和在路径中最早出现的位置
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1); // 关键点：从 -1 位置开始累加
int len = 0, sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
if (map.containsKey(sum - k)) {
len = Math.max(i - map.get(sum - k), len);
}
if (!map.containsKey(sum)) {
map.put(sum, i);
}
}
return len;
}二叉树题目
字符串构造树
/**
* 将字符串转化为整型数组
*
* @param str "[3,9,20,null,null,15,7]"
* @return {3, 9, 20, Integer.MAX_VALUE, Integer.MAX_VALUE, 15, 7}
*/
private static int[] strToIntArray(String str) {
// 起点为1，终点为length-1，去除前后中括号
str = str.substring(1, str.length() - 1);
String[] strs = str.split(",");
int[] arr = new int[strs.length];
for (int i = 0; i < arr.length; i++) {
if ("null".equals(strs[i])) {
// 遇到null转化为整型最大值
arr[i] = Integer.MAX_VALUE;
} else {
arr[i] = Integer.parseInt(strs[i]);
}
}
return arr;
}
/**
* 根据字符串生成树的结构
*
* @param str "[3,9,20,null,null,15,7]"
* @return TreeNode
*/
public static TreeNode mkTree(String str) {
int[] arr = strToIntArray(str);
// 创建节点数组，并以arr内的值创建节点
TreeNode[] nodes = new TreeNode[arr.length + 1];
for (int i = 1; i < nodes.length; i++) {
if (arr[i - 1] != Integer.MAX_VALUE) {
nodes[i] = new TreeNode(arr[i - 1]);
} else {
nodes[i] = null;
}
}
// 根据字符串排序规则，建立节点之间的联系
TreeNode node = null;
for (int i = 1; i < nodes.length / 2; i++) {
node = nodes[i];
if (node == null) {
continue;
}
node.left = nodes[2 * i];
node.right = nodes[2 * i + 1];
}
return nodes[1];
}根据先序和中序数组生成后序数组
一棵二叉树所有的节点值都不同，给定这棵树正确的先序和中序数组，不要重建整棵树，而是通过这两个数组直接生成正确的后序数组
public int[] getPosArray(int[] pre, int[] in) {
if (pre == null || in == null) {
return null;
}
int len = pre.length;
int[] pos = new int[len];
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < len; i++) {
map.put(in[i], i);
}
setPos(pre, 0, len - 1, in, 0, len - 1, pos, len - 1, map);
return pos;
}
// 从右往左依次填好后序数组 s
// si 为后序数组 s 该填的位置
// 返回值为 s 该填的下一个位置
public int setPos(int[] p, int pi, int pj, int[] n, int ni, int nj,
int[] s, int si, HashMap<Integer, Integer> map) {
if (pi > pj) {
return si;
}
s[si--] = p[pi];
int i = map.get(p[pi]);
si = setPos(p, pj - nj + i + 1, pj, n, i + 1, nj, s, si, map);
return setPos(p, pi + 1, pi + i - ni, n, ni, i - 1, s, si, map);
}树形动态规划
第一步：以某个节点 X 为头节点的子树中，分析答案来自哪些可能性，并且这种分析是以 X 的左子树、X 的右子树和 X 整棵树的角度来考虑可能性的。
第二步：根据第一步的可能性分析，列出所有需要的信息。
第三步：根据第二步信息汇总。定义信息 ReturnType 类。
第四步：设计递归函数。递归函数是处理以 X 为头节点的情况下的答案，包括设计递归的 base case、默认直接得到左树和右树的所有信息、把可能性做整合、返回第三步的信息结构这四个小步骤。
/* 以“二叉树节点间的最大距离问题”为例 */
public class ReturnType {
// 左子树和右子树都需要知道自己这棵子树上的最大距离、高度这两个信息
public int maxDistance;
public int height;
public ReturnType(int maxDistance, int height) {
this.maxDistance = maxDistance;
this.height = height;
}
}
public ReturnType process(Node head) {
// 设计递归的 base case
if (head == null) {
return new ReturnType(0, 0);
}
// 默认直接得到左树和右树的所有信息
ReturnType leftData = process(head.left);
ReturnType rightData = process(head.right);
// 把可能性做整合
int height = Math.max(leftData.height, rightData.height) + 1;
int maxDistance = Math.max(leftData.height + rightData.height + 1,
Math.max(leftData.maxDistance, rightData.maxDistance));
// 返回第三步的信息结构
return new ReturnType(maxDistance, height);
}
public int getMaxDistance(Node head) {
return process(head).maxDistance;
}寻找公共祖先
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
}
return left != null ? left : right;
}字符串题目
:star: KMP 算法
给定两个字符串 str 和 match，长度分别为 N 和 M。实现一个算法，如果字符串 str 中含有子串 match，则返回 match 在 str 中的开始位置，不含有则返回-1。
str=”acbc”，match=”bc”，返回 2。
str=”acbc”，match=”bcc”，返回-1。
int strStr(String haystack, String needle) {
int M = needle.length();
int N = haystack.length();
int[][] dp = new int[M][256];
// base case
dp[0][needle.charAt(0)] = 1;
// 影子状态 X 初始为 0
int X = 0;
// 构建状态转移图（稍改的更紧凑了）
for (int j = 1; j < M; j++) {
System.arraycopy(dp[X], 0, dp[j], 0, 256);
dp[j][needle.charAt(j)] = j + 1;
// 更新影子状态
X = dp[X][needle.charAt(j)];
}
int j = 0;
for (int i = 0; i < N; i++) {
j = dp[j][haystack.charAt(i)];
if (j == M) return i - M + 1;
}
return -1;
}正则表达式匹配问题
给定字符串 str，其中绝对不含有字符’.’和’*‘。再给定字符串 exp，其中可以含有’.’或’*‘，’*‘字符不能是 exp 的首字符，并且任意两个’*‘字符不相邻。exp 中的’.’代表任何一个字符，exp 中的’*‘表示’*‘的前一个字符可以有 0 个或者多个。请写一个函数，判断 str 是否能被 exp 匹配。
// 检查字符串的有效性
boolean isValid(char[] s, char[] e) {
for (int i = 0; i < s.length; i++) {
if (s[i] == '*' || s[i] == '.') {
return false;
}
}
for (int i = 0; i < e.length; i++) {
if (e[i] == '*' && (i == 0 || e[i - 1] == '*')) {
return false;
}
}
return true;
}
/* 方法一：递归函数 */
boolean isMatch(String str, String exp) {
if (str == null || exp == null) {
return false;
}
char[] s = str.toCharArray();
char[] e = exp.toCharArray();
return isValid(s, e) ? process(s, e, 0, 0) : false;
}
boolean process(char[] s, char[] e, int si, int ei) {
if (ei == e.length) {
return si == s.length;
}
if (ei + 1 == e.length || e[ei + 1] != '*') {
return si != s.length && (e[ei] == s[si] || e[ei] == '.')
&& process(s, e, si + 1, ei + 1);
}
while (si != s.length && (e[ei] == s[si] || e[ei] == '.')) {
if (process(s, e, si, ei + 2)) {
return true;
}
si++;
}
return process(s, e, si, ei + 2);
}
/* 方法二：动态规划 */
boolean isMatchDP(String str, String exp) {
if (str == null || exp == null) {
return false;
}
char[] s = str.toCharArray();
char[] e = exp.toCharArray();
if (!isValid(s, e)) {
return false;
}
boolean[][] dp = initDPMap(s, e);
for (int i = s.length - 1; i > -1; i--) {
for (int j = e.length - 2; j > -1; j--) {
// 字符相等或 '.'
if (e[j + 1] != '*') {
dp[i][j] = (s[i] == e[j] || e[j] == '.')
&& dp[i + 1][j + 1];
} else {
// 考虑 '*' 的情况
int si = i;
while (si != s.length && (s[si] == e[j] || e[j] == '.')) {
if (dp[si][j + 2]) {
dp[i][j] = true;
break;
}
si++;
}
if (dp[i][j] != true) {
dp[i][j] = dp[si][j + 2];
}
}
}
}
return dp[0][0];
}
boolean[][] initDPMap(char[] s, char[] e) {
int slen = s.length;
int elen = e.length;
boolean[][] dp = new boolean[slen + 1][elen + 1];
dp[slen][elen] = true; // 含义是 str 已经结束
// 考虑 '*' 的情况
for (int j = elen - 2; j > -1; j = j - 2) {
if (e[j] != '*' && e[j + 1] == '*') {
dp[slen][j] = true;
} else {
break;
}
}
// 字符相等或 '.'
if (slen > 0 && elen > 0) {
if ((e[elen - 1] == '.' || s[slen - 1] == e[elen - 1])) {
dp[slen - 1][elen - 1] = true;
}
}
return dp;
}位运算
交换两个整数的值
void swap(int a, int b) {
a = a ^ b;
b = a ^ b;
a = a ^ b;
}实现整数的加减乘除运算
/* 加法 */
int add(int a, int b) {
int sum = a;
while (b != 0) {
sum = a ^ b;
b = (a & b) << 1;
a = sum;
}
return sum;
}
/* 减法 */
// 取反加 1，求相反数
int negNum(int n) {
return add(~n, 1);
}
int minus(int a, int b) {
return add(a, negNum(b));
}
/* 乘法 */
// a×b 的结果可以写成 a×2^0×b0+a×2^1×b1+…+a×2^i×bi+…+ a×2^31×b31
int multi(int a, int b) {
int res = 0;
while (b != 0) {
if ((b & 1) != 0) {
res = add(res, a);
}
// >>表示右移，如果该数为正，则高位补0，若为负数，则高位补1
// >>>表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0
// 左移没有<<<运算符
a <<= 1;
b >>>= 1;
}
return res;
}
/* 除法 */
boolean isNeg(int n) {
return (1 ^ ((n >> 31) & 1)) == 1;
}
// 适用于大多数情况
int div(int a, int b) {
int x = isNeg(a) ? negNum(a) : a;
int y = isNeg(b) ? negNum(b) : b;
int res = 0;
for (int i = 31; i > -1; i = minus(i, 1)) {
if ((x >> i) >= y) {
res |= (1 << i);
x = minus(x, y << i);
}
}
return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
}
// 考虑到 int 的最小值
int divide(int a, int b) {
if (b == 0) {
throw new RuntimeException("divisor is 0");
}
if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
return 1;
} else if (b == Integer.MIN_VALUE) {
return 0;
} else if (a == Integer.MIN_VALUE) {
int res = div(add(a, 1), b);
return add(res, div(minus(a, multi(res, b)), b));
} else {
return div(a, b);
}
}整数的二进制数表达中有多少个 1
int count(int n) {
int res = 0;
while (n != 0) {
n &= (n - 1);
res++;
}
return res;
}数位 DP
特征：[l, r] 区间中，满足某条件的数或者数字的数量
求给定区间 $[X,Y]$ 中满足下列条件的整数个数：这个数恰好等于 $K$ 个互不相等的 $B$ 的整数次幂之和。例如，设 X=15, Y=20, K=2, B=2，则有且仅有下列三个数满足题意：17 = 2^4 + 2^0 & 18 = 2^4 + 2^1 & 20 = 2^4 + 2^2
题目解析参考：数位DP：我的理解与模板【java实现】_java 数位dp
/**
* 求[x, y]区间中，表示为b进制时，所含有的幂次的系数全部为1或者0的数的个数。
* 如，1011（十进制）= 1 * 10^3 + 0 * 10^2 + 1 * 10^1 + 1 * 10^0
* 实际上，求得是一类x，当将x表示为b进制时，和为x的所有b幂次的系数`全为1`
*/
public int solve(int x, int y, int k, int b) {
return dp(y, b, k) - dp(x - 1, b, k);
}
// f[i][j]:求i位b进制数中，数字只有0和1的情况下，1的个数为j的数的个数。
static final int N = 32;
static int[][] dp = new int[N + 1][N + 1]; // 从数位最多为二进制考虑，即最大为32位，也就最多有32个1
static {
// 习惯性的不考虑任何i=0的情况
for (int i = 1; i <= N; i++) {
// 从i位数中选取0个1，当前只有全为为0这种解了。
dp[i][0] = 1;
}
dp[1][1] = 1; //f[1][i] = 0, (i > 1)
for (int i = 2; i <= N; i++) {
for (int j = 1; j <= N; j++) {
// 求i位中1的个数位j的情况，就是求1的排列数
// 从动态规划角度考虑：i位数j个1，对于任何一个数位，只有两种情况:
// 1)为0，则就需要在剩下的i-1个数中得到j个1；
// 2)为1，就需要在剩下i-1个数中得到j-1个1.
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}
}
}
// 将区间问题，统一转化为[0, n]的问题，这样区间问题就变成了dp(y) - dp(x - 1)问题。
public int dp(int n, int b, int k) {
// 看题意，必须处理0防止bits为空。
if (n == 0) return 1;
// 1. 获取数位
// 1) 预估数位个数：32位整数位数最多的进制为2进制，即32位，剩下所有进制都没有32个，故开辟32位作为数位数组是足够的
int[] bits = new int[32];
// 2) 得到每个数位，高位在最后一位
int len = 0;
while (n != 0) {
bits[len++] = n % b;
n /= b;
}
// 2. 模板部分
int res = 0; // 结果变量，根据实际情况可能是一个数组
int last = 0; // 保存dp树右边界的上一个状态，这里记录有边界上已经取得的1的数量【这个设置初始值比较有讲究，需要满足不能干扰第一次遍历的特点，本题中，我们想要的是n表示为b进制时，1的数量，所以0不会干扰求解】。
for (int i = len - 1; i >= 0; i--) { // 习惯上都是从高位向着低位探索
int x = bits[i];
if (x >= 1) { // 若当前位为0，那么为了保证右边界的数能够小于等于原数【之前每一位全部都相等】，只能填0，因此这一位可以直接跳过，被固定死了
// 只要当前位大于0，那么结果集里面，当前位为0的全部答案都能被覆盖，这就让这个穷举的问题变成了一个可以直接求解的问题
// (PS:这个`通过结果集覆盖某个分支而直接求解这个分支`的思想是数位DP的核心，而`直接求解`这件事本身是数位DP另一个要点，就是上面的预处理数组f)
res += dp[i + 1][k - last]; // 将当前位置固定为0后，后面无论怎么取都能满足`? < n`, 所以可以通过预处理直接求解[?指通过排列0，1得到的目标数]
if (x > 1) {
// 同理，若当前位置大于1，则可以取得当前数位为1的全部解【无论后面怎么排列，都必定满足? < n】，故可以直接求解
if (k - last - 1 >= 0) {
res += dp[i + 1][k - last - 1]; // 可以取1的另一个条件是，右边界上全部的1的数量last仍然小于k
}
// 因为右子树的含义是：`？的第i位取当前数位值x的情况下`，接下来的情况数; 而这题要求的是只能取1或者0，而此时的x>1，不符合条件，右子树被直接剪枝
break;
} else {
// 由于当前位置刚好为1，解集合没能完全覆盖这个分支，所以只能继续`递归`求解
last++;
if (last > k) {
// 但是，若是右子树取了这个1以后，导致右边界1的数量已经超过了k，那么右子树下的任何解都必定不满足要求，直接剪枝
break;
}
}
}
if (i == 0 && last == k) {
// 右边界本身【即n本身】就是一个可行解，而我们即将退出循环，导致这个可行解没有考虑到，在这里补上
res++;
}
}
return res;
}其他
回溯法：全排列
给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]示例 3：
输入：nums = [1]
输出：[[1]]
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> output = new ArrayList<Integer>();
for (int num : nums) {
output.add(num);
}
backtrack(nums.length, output, res, 0);
return res;
}
public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
// 所有数都填完了
if (first == n) {
res.add(new ArrayList<Integer>(output));
}
for (int i = first; i < n; i++) {
// 动态维护数组
Collections.swap(output, first, i);
// 继续递归填下一个数
backtrack(n, output, res, first + 1);
// 撤销操作
Collections.swap(output, first, i);
}
}:star: 并查集
给定一个没有重复值的整型数组 arr，初始时认为 arr 中每一个数各自都是一个单独的集合。设计一种叫 UnionFind 的结构，并提供以下两个操作。
1）boolean isSameSet(int a, int b)：查询 a 和 b 这两个数是否属于一个集合。
2）void union(int a, int b)：把 a 所在的集合与 b 所在的集合合并在一起，原本两个集合各自的元素以后都算作同一个集合。如果调用 isSameSet 和 union 的总次数逼近或超过 O(N)，请做到单次调用 isSameSet 或 union 方法的平均时间复杂度为 O(1)。
public class Element<V> {
public V value;
public Element(V value) {
this.value = value;
}
}
public class UnionFindSet<V> {
public HashMap<V, Element<V>> elementMap;
public HashMap<Element<V>, Element<V>> fatherMap;
public HashMap<Element<V>, Integer> rankMap;
public UnionFindSet(List<V> list) {
elementMap = new HashMap<>();
fatherMap = new HashMap<>();
rankMap = new HashMap<>();
for (V value : list) {
Element<V> element = new Element<V>(value);
elementMap.put(value, element);
fatherMap.put(element, element);
rankMap.put(element, 1);
}
}
private Element<V> findHead(Element<V> element) {
Stack<Element<V>> path = new Stack<>();
while (element != fatherMap.get(element)) {
path.push(element);
element = fatherMap.get(element);
}
while (!path.isEmpty()) {
fatherMap.put(path.pop(), element);
}
return element;
}
public boolean isSameSet(V a, V b) {
if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
}
return false;
}
public void union(V a, V b) {
if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
Element<V> aF = findHead(elementMap.get(a));
Element<V> bF = findHead(elementMap.get(b));
if (aF != bF) {
Element<V> big = rankMap.get(aF) >= rankMap.get(bF) ? aF : bF;
Element<V> small = big == aF ? bF : aF;
fatherMap.put(small, big);
rankMap.put(big, rankMap.get(aF) + rankMap.get(bF));
rankMap.remove(small);
}
}
}
}求两个数的最大公约数
// 辗转消除法
int gcd(int m, int n) {
return n == 0 ? m : gcd(n, m % n);
}选择区间覆盖最大次数（差分数组）
给出 n 颗流星的出现时刻，找到最多流星的时刻，输出相应的流星数量和时刻数量。
/*
3
2 1 5
6 3 7
2 4（时刻 2、3、6、7）
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] arr = new int[2][n];
for (int i = 0; i < n; i++) {
arr[0][i] = sc.nextInt();
}
for (int i = 0; i < n; i++) {
arr[1][i] = sc.nextInt();
}
// finish input
// 使用 map 存储差分数组的端点
Map<Integer, Integer> diff = new HashMap<>();
for (int i = 0; i < n; i++) {
int start = arr[0][i] - 1, end = arr[1][i] - 1;
diff.put(start, (diff.getOrDefault(start, 0)) + 1);
if (end + 1 < Math.pow(10, 9)) {
diff.put(end + 1, (diff.getOrDefault(end, 0)) - 1);
}
}
int max_count = 0;
int count = 0;
ArrayList<int[]> list = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : diff.entrySet()) {
count += entry.getValue();
max_count = Math.max(count, max_count);
list.add(new int[]{entry.getKey(), count});
}
int ans = 0;
for (int i = 0; i < list.size(); ++i) {
if (list.get(i)[1] == max_count) {
ans += list.get(i + 1)[0] - list.get(i)[0];
}
}
System.out.println(max_count + " " + ans);
}布隆过滤器
一个布隆过滤器精确地代表一个集合，并可以精确判断一个元素是否在集合中。布隆过滤器的优势在于使用很少的空间就可以将准确率做到很高的程度。
$n$ 为样本个数，$p$ 为失误率，布隆过滤器的大小 $m$ 的公式为：$m=-\frac{n\times \ln{p}}
算法笔记 - Java
http://lpxz.work/posts/90a93b4b/