《剑指 Offer》专项突破版 - 面试题 98、99 和 100 : 和动态规划相关的矩阵路径问题(C++ 实现)

目录

前言

面试题 98 : 路径的数目

面试题 99 : 最小路径之和

面试题 100 : 三角形中最小路径之和


 


前言

矩阵路径是一类常见的可以用动态规划来解决的问题。这类问题通常输入的是一个二维的格子,一个机器人按照一定的规则从格子的某个位置走到另一个位置,要求计算路径的条数或找出最优路径

矩阵路径相关问题的状态转移方程通常有两个参数,即 f(i, j) 的两个参数 i、j 通常是机器人当前到达的坐标。需要根据路径的特点找出到达坐标 (i, j) 之前的位置,通常是坐标 (i - 1, j - 1)、(i - 1, j)、(i, j - 1) 中的一个或多个。相应地,状态转移方程就是找出 f(i, j) 与 f(i - 1, j - 1)、f(i - 1, j) 或 f(i, j - 1) 的关系

可以根据状态转移方程写出递归代码,但值得注意的是一定要将 f(i, j) 的结果用一个二维数组缓存,以避免不必要的重复计算。也可以将计算所有 f(i, j) 看成填充二维表格的过程,相应地,可以创建一个二维数组并逐一计算每个元素的值。通常,矩阵路径相关的问题的代码都可以优化空间效率,用一个一维数组就能保存所有必需的数据

接下来列举几个高频的矩阵类型的问题。


面试题 98 : 路径的数目

题目

一个机器人从 m x n 的格子的左上角出发,它每步要么向下要么向右,直到抵达格子的右下角。请计算机器人从左上角到达右下角的路径的数目。例如,如果格子的大小是 3 x 3,那么机器人从左上角到达右下角有 6 条符合条件的不同路径,如下图所示。

分析

机器人每次只能走一步,它从格子的左上角到达右下角需要走多步。机器人每走一步都有两个选择,要么向下走要么向右走。一个任务需要多个步骤才能完成,每步面临若干选择,这类问题看起来可以用回溯法解决,但由于这个题目只要求计算从左上角到达右下角的路径的数目,并没有要求列出所有的路径,因此这个问题更适合用动态规划解决。

分析确定状态转移方程

应用动态规划解决问题的关键在于找出状态转移方程。可以用函数 f(i, j) 表示从格子的左上角坐标为 (0, 0) 的位置出发到达坐标为 (i, j) 的位置的路径的数目。如果格子的大小为 m x n,那么 f(m - 1, n - 1) 就是问题的解

  1. 当 i 等于 0 时,机器人位于格子最上面一行,机器人不可能从某个位置向下走一步到达一个行号 i 等于 0 的位置。因此,f(0, j) 等于 1,即机器人只有一种方法可以到达坐标为 (0, j) 的位置,即从 (0, j - 1) 的位置向右走一步

  2. 当 j 等于 0 时,机器人位于格子最左边的一列,机器人不可能从某个位置向右走一步到达一个行号 j 为 0 的位置,因此,f(i, 0) 等于 1,即机器人只有一种方法可以到达坐标为 (i, 0) 的位置,即从 (i - 1, 0) 的位置向下走一步

  3. 当行号 i、列号 j 都大于 0 时,机器人有两种方法可以到达坐标为 (i, j) 的位置。它既可以从坐标 (i - 1, j) 的位置向下走一步,也可以从坐标 (i, j - 1) 的位置向右走一步,因此,f(i, j) 等于 f(i - 1, j) 与 f(i, j - 1) 之和

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 1));
        for (int i = 1; i < m; ++i)
        {
            for (int j = 1; j < n; ++j)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

上述代码用一个二维数组 dp 保存 f(i, j) 的计算结果,f(i, j) 保存在 dp[i][j] 中。

上述代码的时间复杂度和空间复杂度都是 O(mn)。

优化空间效率

接下来尝试优化代码的空间效率。在计算 f(i, j) 时只需要用到 f(i - 1, j) 和 f(i, j - 1) 的值,因此只需要保存标号分别为 i - 1 和 i 的两行就可以。如果创建一个只有两行的二维数组 dp,将 f(i, j) 保存在 dp[i % 2][j] 中,那么就将空间复杂度优化到 O(n)。

还可以进一步优化空间效率,只需要创建一个一维数组 dp 就可以。在计算 f(i, j) 时需要用到 f(i - 1, j) 和 f(i, j - 1) 的值。接下来在计算 f(i, j + 1) 时需要用到 f(i - 1, j + 1) 和 f(i, j) 的值。在计算完 f(i, j) 之后就不再需要 f(i - 1, j) 的值。在二维表格中,f(i, j) 和 f(i - 1, j) 是上下相邻的两个位置。由于在用 f(i - 1, j) 计算出 f(i, j) 之后就不再需要 f(i - 1, j),因此可以只用一个位置来保存 f(i - 1, j) 和 f(i, j) 的值。这个位置在计算 f(i, j) 之前保存的是 f(i - 1, j) 的值,计算 f(i, j) 之后保存的是 f(i, j) 的值。由于每个位置能够用来保存两个值,因此只需要一个一维数组就能保存表格中的两行

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n, 1);
        for (int i = 1; i < m; ++i)
        {
            for (int j = 1; j < n; ++j)
            {
                dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }
};

上述代码的时间复杂度仍然是 O(mn),但空间复杂度被优化到 O(n)


面试题 99 : 最小路径之和

题目

在一个 m x n(m、n 均大于 0)的格子中,每个位置都有一个数字。一个机器人每步只能向下或向右,请计算它从格子的左上角到达右下角的路径的数字之和的最小值。例如,从下图中 3 x 3 的格子的左上角到达右下角的路径的数字之和的最小值是 8,图中数字之和最小的路径用灰色背景表示。

分析

和面试题 98 类似,机器人从格子的左上角到达右下角需要多步,每步都可能有向下或向右两个选择。由于这个题目并没有要求列出所有的路径,而是求出路径的数字之和的最小值,也就是求最优解,因此这个问题适合应用动态规划求解。

分析确定状态转移方程

应用动态规划解决问题的关键在于找出状态转移方程。用函数 f(i, j) 表示从格子的左上角坐标为 (0, 0) 的位置(用 grid[0][0] 表示)出发到达坐标为 (i, j) 的位置(用 grid[i][j] 表示)的路径的数字之和的最小值。如果格子的大小为 m x n,那么 f(m - 1, n - 1) 就是问题的解

\begin{cases} f(0, 0) = grid[0][0] \\ f(0, j) = f(0, j - 1) + grid[0][j], j > 0 \\ f(i, 0) = f(i - 1, 0) + grid[i][0], i > 0 \\ f(i, j) = min(f(i - 1, j), f(i, j - 1)) + grid[i][j], i, j > 0 \end{cases}

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n));
        dp[0][0] = grid[0][0];
        for (int j = 1; j < n; ++j)
        {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
​
        for (int i = 1; i < m; ++i)
        {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
            for (int j = 1; j < n; ++j)
            {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
};

上述代码用二维数组 dp 保存状态转移方程的计算结果,f(i, j) 保存在 dp[i][j] 中。

上述代码的时间复杂度和空间复杂度都是 O(mn)。

优化空间效率

由于计算 f(i, j) 时只需要用到它上面一行的 f(i - 1, j),因此实际上只需要保存两行就可以。也就是说,创建一个只有两行的数组 dp,将 f(i, j) 保存到 dp[i % 2][j] 中即可。

还可以进一步优化空间效率,即只需要一个一维数组 dp。在计算 f(i, j) 时需要 f(i - 1, j) 的值。值得注意的是,f(i - 1, j) 在完成 f(i, j) 的计算之后再也用不到了,因此将 f(i - 1, j) 和 f(i, j) 保存到同一个数组 dp 的同一个位置 dp[j] 中。在计算 f(i, j) 之前,dp[j] 保存的是 f(i - 1, j) 的值,用 f(i - 1, j) 的值计算出 f(i, j) 的值之后,将 f(i, j) 的值保存到 dp[j] 中。虽然之前保存在 dp[j] 中的 f(i - 1, j) 的值被覆盖了,但这个值也不再需要,它被覆盖不会带来任何问题

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> dp(n);
        dp[0] = grid[0][0];
        for (int j = 1; j < n; ++j)
        {
            dp[j] = dp[j - 1] + grid[0][j];
        }
​
        for (int i = 1; i < m; ++i)
        {
            dp[0] += grid[i][0];
            for (int j = 1; j < n; ++j)
            {
                dp[j] = min(dp[j], dp[j - 1]) + grid[i][j];
            }
        }
        return dp[n - 1];
    }
};

优化之后的代码的时间复杂度仍然是 O(mn),但空间复杂度变成了 O(n)


面试题 100 : 三角形中最小路径之和

题目

在一个由数字组成的三角形中,第 1 行有 1 个数字,第 2 行有 2 个数字,以此类推,第 n 行有 n 个数字。例如,下图是一个包含 4 行数字的三角形。如果每步只能前往下一行中相邻的数字,请计算从三角形顶部到底部的路径经过的数字之和的最小值。如下图所示,从三角形顶部到底部的路径数字之和的最小值为 11,对应的路径经过的数字用阴影表示。

分析

可能需要用矩阵坐标来定位三角形中的数字。上图中的相邻两行数字的位置相互交错,这样很难用矩阵坐标来表示数字的位置。可以移动三角形每行的位置使它们左端对齐,如下图所示。对齐之后就能很方便地用矩阵的行坐标和列坐标来定位每个数字。如果三角形有 n 行数字,将这些行左端对齐之后就成了一个 n x n 的矩阵和左下半部分。如果三角形中某个数字在矩阵中的行号和列号分别是 i 和 j,那么 i >= j

在左端对齐的三角形中,从一个数字出发,下一步要么前往下一行正下方的数字,要么前往右下方的数字。例如,在上图的三角形中从顶部的数字 2 出发,可以前往第 2 行位于它正下方的数字 3,也可以前往右下方的数字 4。

如果一个三角形有多行,那么从它的顶部到底部需要多步,而且每步都面临两个选择。例如,在上图的三角形中,从顶部数字 2 出发,下一步既可能前往第 2 行的第 1 个数字 3,也可能前往第 2 行的第 2 个数字 4。解决一个问题需要多个步骤,而且每个步骤都面临多个选择,这看起来可以用回溯法解决。但这个题目并没有要求列出从顶部到底部的所有路径,而是要求计算路径之和的最小值,也就是求最优解。因此,动态规划更适合解决这个问题。

分析确定状态转移方程

应用动态规划解决问题的关键在于确定状态转移方程。可以用 f(i, j) 表示从三角形的顶部出发到达行号和列号分别为 i 和 j(i >= j)的位置时路径数字之和的最小值,同时用 T[i][j] 表示三角形行号和列号分别为 i 和 j 的数字。如果三角形中包含 n 行数字,那么 f(n - 1, j) 的最小值就是整个问题的最优解

  1. f(0, 0) 等于 T[0][0]

  2. 如果 j 等于 0,也就是当前到达某行的第 1 个数字。由于路径的每步都是前往正下方或右下方的数字,而此时当前位置的左上方没有数字,那么前一步一定是来自它的正上方的数字,因此 f(i, 0) 等于 f(i - 1, 0) 与 T[i][0] 之和(i > 0)

  3. 如果 i 等于 j,也就是当前到达某行的最后一个数字,此时它的正上方没有数字,前一步只能是来自它左上方的数字,因此 f(i, j) 等于 f(i - 1, j - 1) 与 T[i][j] 之和(i > 0)

  4. 如果当前行号和列号分别为 i 和 j 的位置位于某行的中间,那么前一步既可能是来自它正上方的数字(行号和列号分别为 i - 1 和 j),也可能是来自它左上方的数字(行号和列号分别为 i - 1 和 j - 1),所以 f(i, j) 等于 f(i - 1, j) 与 f(i - 1, j - 1) 的最小值再加上 T[i][j]

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>> dp(n, vector<int>(n));
        dp[0][0] = triangle[0][0];
        
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j <= i; ++j)
            {
                dp[i][j] += triangle[i][j];
                if (j == 0)
                    dp[i][j] += dp[i - 1][j];
                else if (j == i)
                    dp[i][j] += dp[i - 1][j - 1];
                else
                    dp[i][j] += min(dp[i - 1][j], dp[i - 1][j - 1]);
            }
        }
​
        int result = INT_MAX;
        for (int num : dp[n - 1])
        {
            result = min(result, num);
        }
        return result;
    }
};

上述代码创建了一个 n x n(n 为三角形的行数)的二维数组 dp,但实际上只用到了数组的左下半部分。先用一个二重循环按照状态转移方程逐一计算 f(i, j) 的值并保存到 dp[i][j] 中,然后用一个 for 循环找出二维数组 dp 最后一行的最小值作为整个问题的最优解

上述代码的时间复杂度和空间复杂度都是 O(n^2)。

优化空间效率

由于计算 f(i, j) 时只需要用到它上面一行的 f(i - 1, j) 和 f(i - 1, j - 1),因此实际上只需要保留两行就可以。也就是说,创建一个只有两行的数组 dp,将 f(i, j) 保存到 dp[i % 2][j] 中即可。

还可以考虑进一步优化空间效率,即能否只需要一个一维数组 dp。如果能够将 f(i, j) 和 f(i - 1, j) 都保存到 dp[j] 中,那么一个一维数组就可以保存所需的数据

假设在计算 f(i, j) 之前 dp[j] 中保存的是 f(i - 1, j) 的值。在计算 f(i, j) 时需要 f(i - 1, j - 1) 和 f(i - 1, j)。在计算完 f(i, j) 之后能否用 f(i, j) 的值覆盖保存在 dp[j] 中的 f(i - 1, j) 取决于是否还需要 f(i - 1, j) 的值

  1. 如果每行按照从左到右的顺序,那么在计算完 f(i, j) 之后将计算 f(i, j + 1),而计算 f(i, j + 1) 可能需要 f(i - 1, j) 和 f(i - 1, j + 1) 的值,也就是 f(i - 1, j) 的值在计算 f(i, j + 1) 时可能会被用到,因此在计算完 f(i, j) 之后不能将 f(i - 1, j) 的值丢掉

  2. 但计算 f(i, j) 时并不依赖同一行左侧的 f(i, j - 1),因此并不一定要按照从左到右的顺序计算每行,按照从右到左的顺序计算也可以。如果按照从右到左的顺序,则先计算 f(i, j),需要用到 f(i - 1, j - 1) 和 f(i - 1, j)。接下来计算 f(i, j - 1),需要用到 f(i - 1, j - 2) 和 f(i - 1, j - 1)。计算 f(i - 1, j - 1) 并不需要用到 f(i - 1, j)。因此,按照从右到左的顺序在计算完 f(i, j) 之后,将 f(i, j) 的值保存到 dp[j] 中并替换 f(i - 1, j) 的值,并且不会带来任何问题,因此 f(i - 1, j) 的值以后就不再需要

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<int> dp(n);
        dp[0] = triangle[0][0];
​
        for (int i = 1; i < n; ++i)
        {
            for (int j = i; j >= 0; --j)
            {
                if (j == i)
                    dp[j] = dp[j - 1] + triangle[i][j];
                else if (j == 0)
                    dp[j] += triangle[i][j];
                else
                    dp[j] = min(dp[j - 1], dp[j]) + triangle[i][j];
            }
        }
​
        int result = INT_MAX;
        for (int num : dp)
        {
            result = min(result, num);
        }
        return result;
    }
};

上述代码的时间复杂度仍然是 O(n^2),但空间复杂度变成了 O(n)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/506039.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

软件杯 深度学习YOLOv5车辆颜色识别检测 - python opencv

文章目录 1 前言2 实现效果3 CNN卷积神经网络4 Yolov56 数据集处理及模型训练5 最后 1 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; **基于深度学习YOLOv5车辆颜色识别检测 ** 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0…

Java 面试宝典:请说下你对 Netty 中Reactor 模式的理解

大家好&#xff0c;我是大明哥&#xff0c;一个专注「死磕 Java」系列创作的硬核程序员。 本文已收录到我的技术网站&#xff1a;https://skjava.com。有全网最优质的系列文章、Java 全栈技术文档以及大厂完整面经 回答 Reactor 模式是一种高效处理并发网络事件的设计模式&…

SQLite3进行数据库各项常用操作

目录 前言1、SQLite介绍2、通过SQLite创建一个数据库文件3、往数据库文件中插入数据4、数据库文件信息查询5、修改数据库中的内容6、删除数据库中的内容 前言 本文是通过轻量化数据库管理工具SQLite进行的基础操作和一些功能实现。 1、SQLite介绍 SQLite是一个广泛使用的嵌入…

GEE土地分类——基于遥感影像数据的不同作物的分类

简介 这里我们首先要更改原始代码的中的影像和研究区矢量的问题,这个为了防止我们计算的过程超限,建议先将我们的研究区影像和样本点先存在自己的assets中,然后导入到新的脚本中。然周本文就是对其进行影像进行归一化处理,然后进行样本点值提取至点,然后训练样本点,进行…

系统架构体系

一、单体架构 1.浏览器&#xff0c;DNS服务器&#xff08;解析域名&#xff0c;转换为IP地址&#xff09;&#xff0c;一台计算机就相当于一个服务器&#xff08;用端口号进行区分Tomcat&#xff08;web服务&#xff09;&#xff0c;数据库服务&#xff09; 2.本次架构解决…

3D转换1111

1.三维坐标系 1.3D位移: translate3d(x,y,z)  translform:translateX(100px)&#xff1a;仅仅是在x轴上移动  translform:translateY(100px)&#xff1a;仅仅是在Y轴上移动  translform:translateZ(100px)&#xff1a;仅仅是在Z轴上移动&#xff08;注意&#xff1…

HTTP/1.1 如何优化?(计算机网络)

有三种方法&#xff1a; 第一个思路是&#xff0c;通过缓存技术来避免发送 HTTP 请求。客户端收到第一个请求的响应后&#xff0c;可以将其缓存在本地磁盘&#xff0c;下次请求的时候&#xff0c;如果缓存没过期&#xff0c;就直接读取本地缓存的响应数据。如果缓存过期&#…

Uibot6.0 (RPA财务机器人师资培训第6天 )发票验真机器人案例实战

类似于小北的这篇博客&#xff1a;Uibot (RPA设计软件&#xff09;Mage AI智能识别&#xff08;发票识别&#xff09;———课前材料五_uibot 添加mageai-CSDN博客https://blog.csdn.net/Zhiyilang/article/details/135591297?spm1001.2014.3001.5501训练网站&#xff1a;泓江…

122、内网安全——域信息收集应用网络凭据CS插件AdfindBloodHound

文章目录 理解域域信息搜集 理解域 假设有1000台计算机&#xff0c;运维人员需要为每一台计算机进行软件的安装、环境部署&#xff0c;实际上运维人员不可能亲自对每一台计算机进行软件的安装和环境部署。实际&#xff0c;将所有1000台计算机放入一个域中&#xff0c;域内有一…

简单爬虫,爬取某东某商品评论前十页

商品链接地址&#xff1a;【博世四坑5系 6x100x160】博世&#xff08;BOSCH&#xff09;四坑5系&#xff08;1支装&#xff09;圆柄两坑两槽混凝土钻头 6x100x160mm【行情 报价 价格 评测】-京东 首先抓包&#xff0c;用搜索框搜索评论&#xff0c;看评论在哪个包中 为了好看筛…

Python - 深度学习系列31 - ollama的搭建与使用

说明 做这个的主要目的是为了搭建Langchain的本地环境&#xff0c;使用LangChain让LLM具备调用自定义函数的功能。 内容 1 安装server 以下将ollama的安装方式&#xff0c;以及使用做一个简单的说明(记录&#xff09;。之前对这个工具没有了解&#xff0c;只是从快速实践的…

【python】pip清华大学镜像

1、修改pip源为清华源&#xff1a; pip config set global.index-url https://pypi.tuna.tsinghua.edu.cn/simple2、结果是自动给我创建了一个文件&#xff1a; 3、打开这个文件所在的文件夹&#xff1a; 4、打开文件&#xff1a; 5、如果不想指定清华的&#xff0c;就删掉…

微信小程序引导组件【添加到我的小程序】

微信小程序引导组件&#xff0c;点击按钮&#xff0c;弹窗引导用户【添加到我的小程序】 源代码 https://ext.dcloud.net.cn/plugin?id17303

算法学习——LeetCode力扣图论篇3(127. 单词接龙、463. 岛屿的周长、684. 冗余连接、685. 冗余连接 II)

算法学习——LeetCode力扣图论篇3 127. 单词接龙 127. 单词接龙 - 力扣&#xff08;LeetCode&#xff09; 描述 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> … -> sk&#xff1a; 每一对相…

动态内存管理-错题合集讲解

空指针的解应用操作&#xff08;错误信息合集&#xff09; 越界访问 首先我们上一个代码&#xff0c;看看这个的代码的问题 这个代码的问题显而易见 &#xff0c;就是在循环里面&#xff0c;产生了越界访问的问题&#xff0c;这里你开辟了10个整形空间&#xff0c;但是从0-1…

爬虫的验证码处理

1.我们先进入chrome浏览器的审查页面找到input方法&#xff1a; 为了不少找到一个input&#xff0c;我们ctrlf的方法输入input来查找 看见我们有6个需要输入的参数。 除了上面几个的input参数&#xff0c;我们还需要获取验证码的图片&#xff0c;后续要将字母填入进去。 二.安…

XDMA windos 编译

1、先安装 Visual Studio 2019 2、Download the Windows Driver Kit (WDK) - Windows drivers | Microsoft Learn 以前的 WDK 版本和其他下载 - Windows 驱动程序 |Microsoft学习 注意版本&#xff1a;下载2004的版本 3、 选择使用10.0.19041.0 安装这个sdk. 先按vs2019 然后…

后端SpringBoot+Mybatis 查询订单数据库奇怪报错加一

排错过程&#xff1a; 看报错意思是SQL语句存在错误&#xff0c;然后使用图形化工具运行这个SQL语句 其实这里稍微细心想一下就能发现问题&#xff0c;但是当时没深入想&#xff0c;就觉得order表前加了数据库名字影响不大&#xff0c;所以感觉SQL语句是没问题的&#xff0c;然…

HarmonyOS实战开发-一次开发,多端部署-视频应用

介绍 随着智能设备类型的不断丰富&#xff0c;用户可以在不同的设备上享受同样的服务&#xff0c;但由于设备形态不尽相同&#xff0c;开发者往往需要针对具体设备修改或重构代码&#xff0c;以实现功能完整性和界面美观性的统一。OpenHarmony为开发者提供了“一次开发&#x…

【Java与数学】若不等式x^2-a*x+a<0的解集中恰有3个整数,求a的范围?

【分析】 既然不等式存在解集&#xff0c;说明一元二次方程x^2-a*xa0有解&#xff1b; 解之间横跨三个整数&#xff0c;说明Δ大于0&#xff1b; 三个整数必然是连续的&#xff0c;因为f(x)x^2-a*xa最多只与x存在两个交点&#xff0c;这是题设里的隐含条件。 【传统解法】 …