笔试必会算法
来自董巨佬的推荐
最大公约数
场景：unkown
// 递归
public int gcd(int x, int y) {
return y ? gcd(y, x % y) : x;
}
// 迭代
public int gcd(int x, int y) {
if (x < y) {
int t = y;
y = x;
x = t;
}
while (x % y != 0) {
int t = x % y;
x = y;
y = t;
}
return y;
}
快速幂
场景：出现求幂的时候 x^n
public double pow(double x, int n) {
double res = 1;
boolean flag = n > 0;
while (n != 0) {
if ((n & 1) != 0) res *= x;
x *=x;
n /= 2;
}
return flag ? res : 1 / res;
}
动态规划
01 背包
// N 为可携带物品数， W 为最大承受重量
// weights 为物品的重量，values 为物品的价值
public int zeroOnePackage(int N, int W, int[] weights, int[] values) {
int[] dp = new int[N + 1][W + 1];
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= W; j++) {
if (j >= values[i])
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
else
dp[i][j] = dp[i - 1][j];
}
}
return dp[N][W];
}
完全背包
有N种物品和一个容量为T的背包，每种物品都就可以选择任意多个，第i种物品的价值为P[i]，体积为V[i]，求解：选哪些物品放入背包，使得这些物品的价值最大，并且体积总和不超过背包容量。
public int Knapsack(int[] P, int[] V, int T) {
int[][] dp = new int[P.length + 1][T + 1];
for (int i = 0; i < P.length; i++) {
for (int j = 0; j < T + 1; j++) {
for (int k = 0; k * V[i] <= j; k++) {
dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j - k * V[i]] + k * P[i])
}
}
}
return dp[P.length][T];
}
多重背包
有 N 种物品，第 i 种物体的体积是 P[i]，价值是 V[i]，每种物品的数量是有限的为 M[i]，现有容量 T 的背包，使得总价值尽可能大
int MultiKnapsack(int[] P, int[] V, int[] M, int T) {
int[][] dp = new int[P.length + 1][T + 1];
for (int i = 0; i < P.length; i++) {
for (int j = 0; j < T + 1; j++) {
for (int k = 0; k <= M[i] && k * V[i] <= j; k++) {
dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j - k * V[i]] + k * P[i]);
}
}
}
return dp[P.length][T];
}
二分
一般二分
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 注意
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1; // 注意
else if (nums[mid] > target)
right = mid - 1; // 注意
}
return -1;
}
左侧逼近二分
int left_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length; // 注意
while (left < right) { // 注意
int mid = (left + right) / 2;
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid; // 注意
}
}
return left;
}
右侧逼近二分
int right_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0, right = nums.length;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
left = mid + 1; // 注意
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return left - 1; // 注意
}
并查集
public class UF {
private final int[] uf;
public UF(int n) {
id = new int[n];
for (int i = 0; i < n; i++) id[i] = i;
}
public int find(int p) {
while (p != uf[p]) p = uf[p];
return p;
}
public boolean connected(int x, int y) {
return find(x) == find(y);
}
public void union(int x, int y) {
uf[find(x)] = find(y);
}
}
编辑距离
class Solution {
public int minDistance(String word1, String word2) {
if (word1.length() == 0 || word2.length() == 0) return word1.length() + word2.length();
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
for (int i = 1; i <= word1.length(); i++) dp[i][0] = i;
for (int i = 1; i <= word2.length(); i++) dp[0][i] = i;
for (int i = 1; i <= word1.length(); i++) {
for (int j = 1; j <= word2.length(); j++) {
if (word1.charAt(i) == word2.charAt(j)) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
}
}
return dp[word1.length()][word2.length()];
}
}
快速排序
public void QuickSort(int[] array, int left, int right) {
if (left >= right) return;
int i = partition(array, left, right);
QuickSort(array, left, i - 1);
QuickSort(array, i + 1, right);
}
public void partition(int[] array, int left, int right) {
int k = array[left];
int i = left, j = right;
while (i < j) {
while (i < j && array[j] >= k) j--;
if (i < j) {
array[i] = array[j];
i++;
}
while (i < j && array[i] < k) i++;
if (i < j) {
array[j] = array[i];
j--;
}
}
array[i] = k;
return i;
}