Blkcor Dev

hello algo note

回溯

「回溯算法 backtracking algorithm」是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止。

回溯算法的解题步骤归纳如下几个步骤：

  1. 剪枝
  2. 作出选择
  3. 递归进行下一轮选择
  4. 回退，撤销上一轮选择

回溯算法的框架代码如下：

/* 回溯算法框架 */
void backtrack(State state, List<Choice> choices, List<State> res) {
    // 判断是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
        // 不再继续搜索
        return;
    }
    // 遍历所有选择
    for (Choice choice : choices) {
        // 剪枝：判断选择是否合法
        if (isValid(state, choice)) {
            // 尝试：做出选择，更新状态
            makeChoice(state, choice);
            backtrack(state, choices, res);
            // 回退：撤销选择，恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}

当然，这个框架代码只是提供了最基础的解题思路，有时候我们需要其他的数据结构来辅助我们实现剪枝等等其他的优化策略。

全排列问题

什么是全排列问题？

全排列是指给出一个集合中全部元素的排列情况。

全排列问题的回溯算法解题思路如下：

  • 无相同元素的情况
static void backtrack(List<Integer> state, int[] choices, boolean[] selected, List<List<Integer>> res) {
    // 当state长度等于choices长度时，说明已经找到了一个可行解，记录下来
    if (state.size() == choices.length) {
        res.add(new ArrayList<>(state));
        return;
    }
    // 遍历所有选择
    for (int i = 0; i < choices.length; i++) {
        int choice = choices[i];
        //剪枝：不允许选择重复的元素
        if (!selected[i]) {
            //尝试：做出选择
            selected[i] = true;
            state.add(choice);
            //进行下一轮选择
            backtrack(state, choices, selected, res);
            //回退：撤销选择，恢复到之前的状态
            selected[i] = false;
            state.remove(state.size() - 1);
        }
    }
}
 
/* 全排列 I */
static List<List<Integer>> permutationsI(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(new ArrayList<>(), nums, new boolean[nums.length], res);
    return res;
}
  • 考虑有相同元素的情况下

我们在「每一轮」选择中，开启一个哈希表duplicated，用来记录在「该轮选择」中已经被选中的重复元素。

static void backtrack(List<Integer> state, int[] choices, boolean[] selected, List<List<Integer>> res) {
        // 当state长度等于choices长度时，说明已经找到了一个可行解，记录下来
        if (state.size() == choices.length) {
            res.add(new ArrayList<>(state));
            return;
        }
        HashSet<Integer> duplicated = new HashSet<>();
        // 遍历所有选择
        for (int i = 0; i < choices.length; i++) {
            int choice = choices[i];
            //剪枝：不允许选择重复的元素
            if (!selected[i] && !duplicated.contains(choice)) {
                //尝试：做出选择
                duplicated.add(choice);
                selected[i] = true;
                state.add(choice);
                //进行下一轮选择
                backtrack(state, choices, selected, res);
                //回退：撤销选择，恢复到之前的状态
                selected[i] = false;
                state.remove(state.size() - 1);
            }
        }
    }
 
    /* 全排列 I */
    static List<List<Integer>> permutationsII(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(new ArrayList<>(), nums, new boolean[nums.length], res);
        return res;
    }

子集和问题

给定一个正整数数组 nums 和一个目标正整数 target ，请找出所有可能的组合，使得组合中的元素和等于 target 。给定数组无重复元素，每个元素可以被选取多次。请以列表形式返回这些组合，列表中不应包含重复组合。

  • 无相同元素的情况下：
import java.util.ArrayList;
import java.util.List;
 
public class SubsetSumINaive {
    public static void main(String[] args) {
        System.out.println(subsetSumINaive(9, new int[]{3, 4, 5}));
    }
 
    static void backtrack(List<Integer> state, int target, int total, int[] choices, List<List<Integer>> res) {
        //total等于目标target的时候，记录解
        if (target == total) {
            res.add(new ArrayList<>(state));
            return;
        }
 
        //遍历所有的选择
        for (int i = 0; i < choices.length; i++) {
            int choice = choices[i];
            //剪枝：如果当前选择+total 大于target，跳过当前选择并避免出现相同元素的不同排列：「4，5」和「5，4」
            if (choice + total > target || (i > 0 && !state.isEmpty() && choice < state.get(state.size() - 1)))
                continue;
            //进行选择
            state.add(choice);
            //进行下一轮选择
            backtrack(state, target, total + choice, choices, res);
            //回退：撤销选择
            state.remove(state.size() - 1);
        }
    }
 
    static List<List<Integer>> subsetSumINaive(int target, int[] nums) {
        List<Integer> state = new ArrayList<>(); // 状态（子集）
        int total = 0; // 子集和
        List<List<Integer>> res = new ArrayList<>(); // 结果列表（子集列表）
        backtrack(state, target, total, nums, res);
        return res;
    }
}
  • 考虑有相同元素的情况下

反正元素可以重复选择，不如使用set先对choice进行一次去重，再使用无重复元素的办法进行求解。

N皇后问题

import java.util.ArrayList;
import java.util.List;
 
public class NQueen {
    public static void main(String[] args) {
        nQueen(4).forEach(System.out::println);
    }
    static List<List<List<String>>> nQueen(int n) {
        // 初始化 n*n 大小的棋盘，其中 'Q' 代表皇后，'#' 代表空位
        List<List<String>> state = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List<String> row = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                row.add("#");
            }
            state.add(row);
        }
        boolean[] cols = new boolean[n]; // 记录列是否有皇后
        boolean[] diags1 = new boolean[2 * n - 1]; // 记录主对角线上是否有皇后
        boolean[] diags2 = new boolean[2 * n - 1]; // 记录次对角线上是否有皇后
        List<List<List<String>>> res = new ArrayList<>();
 
        backtrack(0, n, state, res, cols, diags1, diags2);
        return res;
    }
 
 
    private static void backtrack(int row, int n, List<List<String>> state, List<List<List<String>>> res, boolean[] cols, boolean[] diags1, boolean[] diags2) {
        // 当放置完所有行时，记录解
        if (row == n) {
            List<List<String>> copyState = new ArrayList<>();
            for (List<String> sRow : state) {
                copyState.add(new ArrayList<>(sRow));
            }
            res.add(copyState);
            return;
        }
				//遍历所有列
        for (int col = 0; col < n; col++) {
          	//计算主对角线和副对角线的元素index
            int diag1 = row - col + n - 1;
            int diag2 = row + col;
            //剪枝：同行 同列 同对角线上的元素不可选
            if (!cols[col] && !diags1[diag1] && !diags2[diag2]) {
                //进行选择
                state.get(row).set(col, "Q");
                cols[col] = diags1[diag1] = diags2[diag2] = true;
                //进行下一轮选择
                backtrack(row + 1, n, state, res, cols, diags1, diags2);
                //回退：撤销上一轮的选择
                state.get(row).set(col, "#");
                cols[col] = diags1[diag1] = diags2[diag2] = false;
            }
        }
    }
}

动态规划

「动态规划 dynamic programming」是一个重要的算法范式，它将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。

dp问题的特征

1、最优子结构

这便可以引出最优子结构的含义：原问题的最优解是从子问题的最优解构建得来的。

2、无后效性是动态规划能够有效解决问题的重要特性之一，其定义为：给定一个确定的状态，它的未来发展只与当前状态有关，而与过去经历的所有状态无关。

dp问题的解题思路

如何知道一个问题是否适合使用动态规划进行解决

如果问题包含明确的决策概念，并且解是通过一系列决策产生的，那么它就满足决策树模型，通常可以使用回溯来解决。

在此基础上，

  • 问题包含最大，最少，最优等等最优化描述
  • 问题的状态能够使用一个列表，多维矩阵或者树进行描述，并且和之前的状态存在递推关系

以leetcode上一道最短路径的题来解题：

public int minPathSum(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        //初始化dp数组
        int[][] dp = new int[n][m];
        dp[0][0] = grid[0][0];
        //首行dp
        for (int j = 1; j < m; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        //首列dp
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        //其他行其他列dp
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
 
        return dp[n-1][m-1];
    }

由于当前状态只和左边的格子以及上面的格子的状态有关系，因此我们使用一个一维的dp来优化空间大小：

 int n = grid.length;
        int m = grid[0].length;
        //初始化dp数组
        int[] dp = new int[m];
        dp[0] = grid[0][0];
        //首行dp
        for (int j = 1; j < m; j++) {
            dp[j] = dp[j - 1] + grid[0][j];
        }
        for (int i = 1; i < n; i++) {
            //首列dp
            dp[0] = dp[0] + grid[i][0];
            //其他行 其他列dp
            for (int j = 1; j < m; j++) {
                dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
            }
        }
 
        return dp[m - 1];

关键点在于,我们每次只需要记住上一行的 dp 值和当前行的 dp 值,就可以计算出下一行的 dp 值。这样,我们只需要一个一维数组来存储中间结果,从而达到了空间优化的目的。

0-1背包问题

问题描述：

给定 n 个物品，第 i个物品的重量为wei[i−1]、价值为val[i−1] ，和一个容量为caps 的背包。每个物品只能选择一次，问在限定背包容量下能放入物品的最大价值。

private static int knapsackDP(int[] wight, int[] val, int caps) {
        int n = wight.length;
        if (n == 0 || caps == 0) return 0;
        //初始化dp
        int[][] dp = new int[n + 1][caps + 1];
        for (int i = 1; i < n; i++) {
            for (int c = 1; c <= caps; c++) {
                //当前物品重量大于背包容量，选择不放入
                if (c < wight[i]) dp[i][c] = dp[i - 1][c];
                else {
                    dp[i][c] = Math.max(dp[i - 1][c], dp[i - 1][c - wight[i - 1] + val[i - 1]]);
                }
            }
        }
        return dp[n][caps];
    }

空间优化的解法：

每个状态都是取决于正上方或者左上方的格子，假设在遍历第i行时，dp数组中存放的其实是第i-1行的结果。

正是因为如此（只有一个一维数组来保存结果），如果我们正序遍历遍历并且更新dp，那么当我们更新dp[j]的时候，dp[j-weight[i]]的结果会丢失，因此我们需要倒序遍历并且更新。

private static int knapsackDPComp(int[] wight, int[] val, int caps) {
        int n = wight.length;
        int[] dp = new int[caps + 1];
        for (int i = 1; i <= n; i++) {
            for (int cap = caps; cap > 0; cap--) {
                if (cap >= wight[i] - 1) {
                    dp[cap] = Math.max(dp[cap], dp[cap - wight[i - 1]] + val[i - 1]);
                }
            }
        }
        return dp[caps];
    }

完全背包问题

完全背包问题和 0-1 背包问题非常相似，区别仅在于不限制物品的选择次数。

但是需要注意的一点是，完全背包问题进行空间优化的时候，根据状态转移方程可知，dp[i]的状态有一部分是依赖于dp[i]的，因此只能正向更新。

距离编辑问题

问题描述

输入两个字符串 s 和 t ，返回将 s 转换为 t 所需的最少编辑步数。

你可以在一个字符串中进行三种编辑操作：插入一个字符、删除一个字符、将字符替换为任意一个字符。

分析思路参考：https://www.hello-algo.com/chapter_dynamic_programming/edit_distance_problem/#1

题解：

private static int editDistanceDP(String s, String t) {
        int n = s.length(), m = t.length();
        int[][] dp = new int[n + 1][m + 1];
        // 状态转移：首行首列
        for (int i = 1; i <= n; i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= m; j++) {
            dp[0][j] = j;
        }
        //初始化其他行其他列
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[n][m];
    }

空间优化解法：

private static int editDistanceDPComp(String s, String t) {
        int n = s.length(), m = t.length();
        int[] dp = new int[m + 1];
        // 状态转移：首行
        for (int i = 1; i <= m; i++) {
            dp[i] = i;
        }
        //初始化其他行其他列
        for (int i = 1; i <= n; i++) {
            //暂存 dp[i-1][j-1]的值
            int leftup = dp[0];
            dp[0] = i;
            for (int j = 1; j <= m; j++) {
                //暂存遍历同行的时候的下一个leftup
                int temp = dp[j];
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[j] = leftup;
                } else {
                    dp[j] = Math.min(Math.min(dp[j], dp[j - 1]), leftup) + 1;
                }
                leftup = temp;
            }
        }
        return dp[m];
    }

注释：因为我们在遍历第i行是，初始化保存的是i-1行的状态，因此我们dp[0]的位置即当前行更新所依赖的$dp[i-1][j-1]$的值。

同理在更新同行的下一列时，需要使用temp这个变量保存下一列所需要依赖的$dp[i-1][j-1]$的内容，即$dp[j]$。

贪心算法

「贪心算法」用一句话来概述就是期待从局部最优推导出全局的最优解。

分数背包问题

给定 n 个物品，第 i 个物品的重量为 $wgt[i−1]$、价值为 $val[i−1]$ ，和一个容量为 $cap$ 的背包。每个物品只能选择一次，但可以选择物品的一部分，价值根据选择的重量比例计算，问在限定背包容量下背包中物品的最大价值

问题分析：我们可以对物品的单位价值从大到小进行排序，然后根据背包的容量从大到小进行物品的选择，代码实现如下：

import java.util.Arrays;
import java.util.Comparator;
 
class Item {
    //物品的重量
    int w;
    //物品的价值
    int v;
 
    public Item(int w, int v) {
        this.w = w;
        this.v = v;
    }
}
 
public class FractionKnapsack {
    double fractionKnapsack(int[] wgt, int[] val, int cap) {
        //初始化Item列表
        Item[] items = new Item[wgt.length];
        for (int i = 0; i < wgt.length; i++) {
            items[i] = new Item(wgt[i], val[i]);
        }
        //根据物品单价由大到小进行排序
        double res = 0;
        Arrays.sort(items, Comparator.comparingDouble(item -> -((double) item.w / item.v)));
        for (Item item : items) {
            if (item.w <= cap) {
                res += item.v;
                cap -= item.w;
            } else {
                //装不下 对物品进行切割
                res += ((double) cap / item.w) * item.v;
                break;
            }
        }
        return res;
    }
}

最大容量问题

问题描述：

输入一个数组 $ht$ ，其中的每个元素代表一个垂直隔板的高度。数组中的任意两个隔板，以及它们之间的空间可以组成一个容器。

容器的容量等于高度和宽度的乘积（面积），其中高度由较短的隔板决定，宽度是两个隔板的数组索引之差。

请在数组中选择两个隔板，使得组成的容器的容量最大，返回最大容量。

问题分析：

我们假设当前状态为:

左边界对应的索引为$i$，右边界对应的索引为$j$，假设$ht[i] < ht[j]$，如果此时我们移动$j$，这时候可能会存在三种情况：

  • $ht[i] < ht[j-1] < ht[j] $
  • $ht[j-1] < ht[i] < ht[j] $
  • $ht[i] < ht[j] < ht[j-1] $

但是容器的高度是由较小的边界决定的，所以不管是1，2，3中的哪一种情况，容器的大小都会变小。

因此要想让容器的体积变大，我们只能将短的板子向内移动。

代码实现：

private static int maxCapacity(int[] ht) {
        int max = -999;
        int l = 0, r = ht.length - 1;
        while (l < r) {
            int area = Math.min(ht[l], ht[r]) * (r - l);
            max = Math.max(max, area);
            if (ht[l] < ht[r]) {
                //移动较短的板子
                l++;
            } else {
                r--;
            }
        }
        return max;
    }

最大切分乘积问题

问题描述

给定一个正整数 $n$ ，将其切分为至少两个正整数的和，求切分后所有整数的乘积最大是多少。

问题分析

https://www.hello-algo.com/chapter_greedy/max_product_cutting_problem/#1

代码实现

int maxProductCutting(int n) {
        //n不大于3的时候，必须切分出一个1
        if (n <= 3) return (n - 1);
        //a是3的个数，b是余数
        int a = n / 3;
        int b = n % 3;
        //如果余数是1，那么就把一个3和一个1拆成2*2
        if (b == 1) {
            return (int) Math.pow(3, a - 1) * 4;
        }
        //如果余数是2，那么就是3的a次方*2
        if (b == 2) {
            return (int) Math.pow(3, a) * 2;
        }
        //余数是0
        return (int) Math.pow(3, a);
    }