JAVA 2023 年 9 月 28 日

算法

常见的算法归类

算法

动态规划

重叠子问题

斐波那契数列例子

计算斐波那契数列

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

递归树

时间复杂度：O(2^n)

如何优化？带备忘录的递归解法

int fib(int N) {
    // 备忘录全初始化为 0
    int[] memo = new int[N + 1];
    // 进行带备忘录的递归
    return dp(memo, N);
}

// 带着备忘录进行递归
int dp(int[] memo, int n) {
    // base case
    if (n == 0 || n == 1) return n;
    // 已经计算过，不用再计算了
    if (memo[n] != 0) return memo[n];
    memo[n] = dp(memo, n - 1) + dp(memo, n - 2);
    return memo[n];
}

时间复杂度：O(n)

状态转移方程
1. 确定base case，最小的子问题的解
2. 确定状态，分解子问题时变化的变量
3. 确定选择，改变状态的行为
4. 明确dp数组的定义
最优子结构

可以从子问题的最优结果推出更大规模问题的最优结果

完全背包

有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品有无限个，即一个物品可以放入背包多次，求解将哪些物品装入背包里物品价值总和最大。

dp数组：dp[j]数组的表示容量为j的背包中所得到的物品的最大价值。

状态转移方程：dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])。

// m为物品的个数，n为背包的容量
int m = weight.length, n = bagWeight;
int[] dp = new int[n + 1];
for (int i = 1; i <= m; i++) {
    // 注意这里遍历背包顺序又变成了正序，和01背包不同，很重要
    for (int j = weight[i - 1]; j <= n; j++) {
        dp[j] = Math.max(dp[j], dp[j - weight[i - 1]] + value[i - 1]);
    }
}

最长回文串

给定一个字符串s，返回是回文串的最长子串

dp数组：dp[i][j] 记录从i到j的字符是否为回文串

状态转移方程：dp[i][j] = (char[i]==char[j] && dp[j+1][i-1])

我们要判断 dp[i][j] 是否为回文，只需要判断字符串在i和j两个位置是否为相同的字符并且dp[j+1][i-1]为回文串

char[] charArray = s.toCharArray();
int[][] dp = new int[s.length()][s.length()];
dp[0][0] = 1;
int start = 0;
int end = 0;
for (int i = 1; i < charArray.length; i++) {
    for (int j = 0; j < i; j++) {
        if ((j+1 == i -1 || dp[j+1][i-1] == 1) && charArray[j] == charArray[i]) {
            dp[j][i] = 1;
            if (i - j + 1 > end - start + 1) {
                start = j;
                end = i;
            }
        }
    }
}
System.out.println(s.substring(start, end+1));

排序

快速排序

寻找数组中的第k大的元素

解题思路：在快速排序时，判断第k的元素在哪一边，对这边继续快速排序

public static void main(String[] args) {
    int[] nums = new int[]{3, 2, 1, 5, 6, 4};
    int k = 2;
    List<Integer> list = new ArrayList<>();
    for (int num : nums) {
        list.add(num);
    }
    System.out.println(sort(list, k));
}

public static int sort(List<Integer> nums, int k) {
    int base = nums.get(0);
    List<Integer> left = new ArrayList<>();
    List<Integer> right = new ArrayList<>();
    int equalsNum = 0;
    for (int i = 1; i < nums.size(); i++) {
        if (nums.get(i) < base) {
            left.add(nums.get(i));
        } else if (nums.get(i) == base) {
            equalsNum++;
            left.add(nums.get(i));
        } else {
            right.add(nums.get(i));
        }
    }
    if (right.size() == k - 1) {
        return base;
    } else if (right.size() < k - 1) {
        if (right.size() + equalsNum >= k - 1) {
            return base;
        }
        return sort(left, k - right.size() - 1);
    } else {
        return sort(right, k);
    }
}

LRU

解题思路：使用LinkedHashMap作为一个有序的k-v作为数据接口

public class LRUCache {

    public static void main(String[] args) {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(1, 1);
        lRUCache.put(2, 2);
        System.out.println(lRUCache.get(1));
        lRUCache.put(3, 3);
        System.out.println(lRUCache.get(2));
        lRUCache.put(4, 4);
        System.out.println(lRUCache.get(1));
        System.out.println(lRUCache.get(3));
        System.out.println(lRUCache.get(4));
    }

    private final int capacity;

    private final LinkedHashMap<Integer, Integer> data;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.data = new LinkedHashMap<>(capacity);
    }

    public int get(int key) {
        Integer i = data.get(key);
        if (i == null) {
            return -1;
        }
        data.remove(key);
        data.put(key, i);
        return i;
    }

    public void put(int key, int value) {
        // 是否存在，存在直接覆盖
        Integer i = data.get(key);
        if (i != null) {
            data.remove(key);
            data.put(key, value);
            return;
        }
        if (data.size() == capacity) {
            // 覆盖最近最少使用
            Integer next = data.keySet().iterator().next();
            data.remove(next);
        }
        // 插入
        data.put(key, value);
    }
}

作者： OnlyWaitY 发表日期：2023 年 9 月 28 日