基础算法-学习

2021年9月12日 3点热度 0条评论 来源: ML李嘉图

目录

回溯

回溯法解决的问题

回溯法,一般可以解决如下几种问题:

  • 组合问题:N个数里面按一定规则找出k个数的集合
  • 切割问题:一个字符串按一定规则有几种切割方式
  • 子集问题:一个N个数的集合里有多少符合条件的子集
  • 排列问题:N个数按一定规则全排列,有几种排列方式
  • 棋盘问题:N皇后,解数独等等

另外,什么是排列?

组合是不强调元素顺序的,排列是强调元素顺序

解决一个回溯问题,实际上就是一个决策树的遍历过程。你只需要思考 3 个问题:

1、路径:也就是已经做出的选择。

2、选择列表:也就是你当前可以做的选择。

3、结束条件:也就是到达决策树底层,无法再做选择的条件。

模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯,撤销处理结果
    }
}

溯和递归是相辅相成的。

接着提到了回溯法的效率,回溯法其实就是暴力查找,并不是什么高效的算法。

组合

给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。

示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

每次从集合中选取元素,可选择的范围随着选择的进行而收缩,调整可选择的范围

图中可以发现n相当于树的宽度,k相当于树的深度

那么如何在这个树上遍历,然后收集到我们要的结果集呢?

图中每次搜索到了叶子节点,我们就找到了一个结果

相当于只需要把达到叶子节点的结果收集起来,就可以求得 n个数中k个数的组合集合。

lass Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        combineHelper(n, k, 1);
        return result;
    }

    /**
     * 每次从集合中选取元素,可选择的范围随着选择的进行而收缩,调整可选择的范围,就是要靠startIndex
     * @param startIndex 用来记录本层递归的中,集合从哪里开始遍历(集合就是[1,...,n] )。
     */
    private void combineHelper(int n, int k, int startIndex){
        //终止条件
        if (path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){
            path.add(i);
            combineHelper(n, k, i + 1);
            path.removeLast();
        }
    }
}

剪枝优化

我们说过,回溯法虽然是暴力搜索,但也有时候可以有点剪枝优化一下的。

来举一个例子,n = 4,k = 4的话,那么第一层for循环的时候,从元素2开始的遍历都没有意义了。 在第二层for循环,从元素3开始的遍历都没有意义了。

贪心

什么是贪心

贪心的本质是选择每一阶段的局部最优,从而达到全局最优

贪心一般解题步骤

贪心算法一般分为如下四步:

  • 将问题分解为若干个子问题
  • 找出适合的贪心策略
  • 求解每一个子问题的最优解
  • 将局部最优解堆叠成全局最优解

分发饼干

假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。

对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

示例 1: 输入: g = [1,2,3], s = [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。 虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。 所以你应该输出1。

这里的局部最优就是大饼干喂给胃口大的,充分利用饼干尺寸喂饱一个,全局最优就是喂饱尽可能多的小孩

class Solution {
    // 思路1:优先考虑饼干,小饼干先喂饱小胃口
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int start = 0;
        int count = 0;
        for (int i = 0; i < s.length && start < g.length; i++) {
            if (s[i] >= g[start]) {
                start++;
                count++;
            }
        }
        return count;
    }
}

动态规划

什么是动态规划

动态规划,英文:Dynamic Programming,简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的。

动态规划算法就是将待求解问题分解成若干子问题,

先求解子问题并保存子问题的答案避免重复计算,然后从这些子问题的解得到原问题的解。

而如何断定一个问题是否可以用动态规划来解决,就需要掌握动态规划的两个基本要素,「最优子结构性质」「重叠子问题性质」

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

示例 1: 输入: 2 输出: 2 解释: 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶
class Solution {
    public int climbStairs(int n) {
        if(n <= 2) return n;
        int a = 1, b = 2, sum = 0;
        
        for(int i = 3; i <= n; i++){
            sum = a + b;
            a = b;
            b = sum;
        }
        return b;
    }
}
// 常规方式
public int climbStairs(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
// 用变量记录代替数组
public int climbStairs(int n) {
    int a = 0, b = 1, c = 0; // 默认需要1次
    for (int i = 1; i <= n; i++) {
        c = a + b;          // f(i - 1) + f(n - 2)
        a = b;              // 记录上一轮的值
        b = c;              // 向后步进1个数
    }
    return c;
}
    原文作者:ML李嘉图
    原文地址: https://www.cnblogs.com/zwtblog/p/15255500.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。