笔试必会算法

Scroll Down

笔试必会算法

来自董巨佬的推荐

最大公约数

场景: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;
}

待续