基础算法学习

作者: ML李嘉图
算法 Java JShell


目录

  • [回溯]
  • [回溯法解决的问题]
  • [模板]
  • [组合]
  • [剪枝优化]
  • [贪心]
  • [什么是贪心]
  • [贪心一般解题步骤]
  • [分发饼干]
  • [动态规划]
  • [什么是动态规划]
  • [爬楼梯]


回溯

回溯法解决的问题

回溯法，一般可以解决如下几种问题：

  • 组合问题：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

文章列表

更多推荐

更多
  • AWS自动化机器学习-十一、MLSDLC 的持续集成、部署和训练 技术要求，编纂持续集成阶段，管理持续部署阶段，管理持续训练，延伸，构建集成工件，构建测试工件，构建生产工件，自动化持续集成流程，回顾构建阶段，回顾测试阶段，审查部署和维护阶段，回顾应用用户体验，创建新的鲍鱼调查数据，回顾持续训练流程，清
    Apache CN

    机器学习

  • AWS自动化机器学习-六、使用 AWS 步骤函数自动化机器学习过程 技术要求，介绍 AWS 步骤功能，使用 Step 函数 Data Science SDK for CI/CD，建立 CI/CD 渠道资源，创建状态机，解决状态机的复杂性，更新开发环境，创建管道工件库，构建管道应用构件，部署 CI/CD
    Apache CN

    机器学习

  • AWS自动化机器学习-第三部分：优化以源代码为中心的自动化机器学习方法 本节将向您介绍整体 CI/CD 流程的局限性，以及如何将 ML 从业者的角色进一步整合到管道构建流程中。本节还将介绍这种角色集成如何简化自动化过程，并通过向您介绍 AWS Step 函数向您展示一种优化的方法。本节包括以下章节:
    Apache CN

    机器学习

  • AWS自动化机器学习-一、AWS 上的自动化机器学习入门 技术要求，洗钱流程概述，洗钱过程的复杂性，端到端 ML 流程示例，AWS 如何使 ML 开发和部署过程更容易自动化，介绍 ACME 渔业物流，ML 的情况，从数据中获得洞察力，建立正确的模型，训练模型，评估训练好的模型，探索可能的后续步
    Apache CN

    机器学习

  • AWS自动化机器学习-二、使用 SageMaker 自动驾驶器自动化机器学习模型开发 技术要求，介绍 AWS AI 和 ML 前景，SageMaker 自动驾驶器概述，利用 SageMaker 自动驾驶器克服自动化挑战，使用 SageMaker SDK 自动化 ML 实验，SageMaker Studio 入门，准备实验
    Apache CN

    机器学习

  • AWS自动化机器学习-四、机器学习的持续集成和持续交（CI/CD） 四、机器学习的持续集成和持续交CI/CD技术要求，介绍 CI/CD 方法，通过 CI/CD 实现 ML 自动化，在 AWS 上创建 CI/CD 管道，介绍 CI/CD 的 CI 部分，介绍 CI/CD 的 CD 部分，结束循环，采取以部
    Apache CN

    机器学习

  • AWS自动化机器学习-九、使用 Amazon Managed Workflows 为 Apache AirFlow 构建 ML 工作流 技术要求，开发以数据为中心的工作流程，创建合成鲍鱼调查数据，执行以数据为中心的工作流程，构建和单元测试数据 ETL 工件，构建气流 DAG，清理， 在前面的年龄计算器示例中，我们了解了如何通过 ML 从业者和开发人员团队之间的跨职能
    Apache CN

    机器学习

  • AWS自动化机器学习-七、使用 AWS 步骤函数构建 ML 工作流 技术要求，构建状态机工作流，执行集成测试，监控管道进度，设置服务权限，创建 ML 工作流程， 在本章中，我们将从第六章中的 [处继续，使用 AWS 步骤函数自动化机器学习过程。您将从那一章中回忆起，我们正在努力实现的主要目标是简化
    Apache CN

    机器学习

  • AWS自动化机器学习-八、使用 Apache Airflow 实现机器学习过程的自动化 技术要求，介绍阿帕奇气流，介绍亚马逊 MWAA，利用气流处理鲍鱼数据集，配置 MWAA 系统的先决条件，配置 MWAA 环境， 当建立一个 ML 模型时，有一个所有 ML 从业者都知道的基本原则；也就是说，最大似然模型只有在数据被训练时
    Apache CN

    机器学习

  • AWS自动化机器学习-五、自动化 ML 模型的持续部署 技术要求，部署 CI/CD 管道，构建 ML 模型工件，执行自动化 ML 模型部署，整理管道结构，创建 CDK 应用，部署管道应用，查看建模文件，审查申请文件，查看模型服务文件，查看容器构建文件，提交 ML 工件，清理， 在 [第 4
    Apache CN

    机器学习

    • ML李嘉图

    69
    文章数
    1066
    获赞数
    1024
    粉丝数
    算法 Java JShell

    近期文章

    更多
    文章目录

      热门标签

      更多

      推荐作者

      更多