02.8.1.4 数学与模拟技巧
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.8 贪心与技巧题 / 02.8.1 贪心与技巧
02.8.1.4-001 数学类题目的一般解题思路是什么?
一句话结论
先把题意抽象为公式、数列或几何关系,找规律或不变量,再判断能否直接公式求解;无明显规律时用枚举/模拟兜底;数学题优先保证边界与溢出正确。
概念解释
- 公式:直接由关系推导结果。
- 规律:小样本观察周期/递推。
- 不变量:过程中保持不变的量。
原理流程
- 抽象变量与约束。
- 列关系,尝试公式/递推。
- 小规模验证规律,再写实现。
代码 / 图示
抽象 → 公式/规律 → 小样本验证 → 边界与溢出核对
常见误区
- 误区:直接暴力枚举所有情况;正解:先找数学规律降低复杂度。
- 误区:忽略整数溢出;正解:估算结果范围,必要时用 long。
追问
- Q:数学题复杂度怎么报? A:按公式 O(1) 或筛法/枚举口径分别说明。
- Q:规律验证不出来怎么办? A:回到模拟,标注未证明的假设。
02.8.1.4-002 怎么判断一个数是不是质数?
一句话结论
n < 2 非质数;试除 2 到 sqrt(n),存在整除因子则非质数;只需检查到平方根,因为因子成对出现;时间 O(sqrt(n))。
概念解释
- 质数:大于 1 且无 1 和自身外因子。
- 因子成对:d 与 n/d 同时存在。
- 平方根:成对因子的分界。
原理流程
- 处理 n <= 1、n == 2、偶数。
- 从 3 试除到 sqrt(n),步长 2。
- 有因子返回 false,否则 true。
代码 / 示例
boolean isPrime(int n) {
if (n < 2) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (int i = 3; (long) i * i <= n; i += 2)
if (n % i == 0) return false;
return true;
}
常见误区
- 误区:试除到 n;正解:到 sqrt(n) 即可。
- 误区:
i*i溢出;正解:用(long)i*i <= n或i <= n/i。
追问
- Q:批量判质数用什么? A:埃氏筛预处理,见下题。
- Q:1 是质数吗? A:不是。
02.8.1.4-003 埃氏筛怎么求区间质数?
一句话结论
布尔表初始全真,0/1 置假;从 2 开始,若当前为质数则把其倍数标记为合数;筛到 sqrt(n) 即可;时间 O(n log log n)。
概念解释
- 合数标记:质数的倍数必为合数。
- 起点:从 p² 开始标记更小倍数已被筛过。
- 复杂度:调和级数对数级。
原理流程
- 建表 isPrime[0..n]。
- i 从 2 到 sqrt(n)。
- 质数则标记倍数为假。
代码 / 示例
boolean[] sieve(int n) {
boolean[] p = new boolean[n + 1];
Arrays.fill(p, true);
p[0] = p[1] = false;
for (int i = 2; (long) i * i <= n; i++)
if (p[i])
for (int j = i * i; j <= n; j += i) p[j] = false;
return p;
}
常见误区
- 误区:从 2 开始标所有倍数;正解:从 i*i 开始,前面倍数已被小质数筛过。
- 误区:筛到 n 才停;正解:到 sqrt(n),剩余未标记即质数。
追问
- Q:空间复杂度? A:O(n)。
- Q:线性筛了解吗? A:欧拉筛 O(n),每个合数只被最小质因子标记。
02.8.1.4-004 最大公约数与最小公倍数怎么求?
一句话结论
gcd 用欧几里得辗转相除:gcd(a,b) = gcd(b, a%b),b=0 时返回 a;lcm = a / gcd(a,b) * b,先除后乘防溢出。
概念解释
- gcd:公共最大因子。
- lcm:公共最小倍数。
- 关系:gcd(a,b) * lcm(a,b) = a*b。
原理流程
- 辗转相除到余数 0。
- lcm 由 gcd 换算。
- 顺序防溢出。
代码 / 示例
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
常见误区
- 误区:lcm 直接
a*b/gcd;正解:先除后乘避免乘积溢出。 - 误区:负数未取绝对值;正解:gcd 结果取非负。
追问
- Q:gcd 递归深度? A:O(log min(a,b))。
- Q:多个数 gcd? A:两两结合
gcd(gcd(a,b),c)。
02.8.1.4-005 进制转换怎么实现?
一句话结论
十进制转其他进制:除基取余倒序排列;其他进制转十进制:按位乘权累加;注意字符映射、前导零与负数符号。
概念解释
- 除基取余:低位先得,结果倒序。
- 按权展开:每一位 × 基数^位权。
- 字符表:0-9、A-Z 映射。
原理流程
- 确定目标进制与字符表。
- 除基取余或按权累加。
- 处理符号与零。
代码 / 示例
// 十进制转二进制:反复 n % 2 记录余数,n /= 2,余数倒序
常见误区
- 误区:余数顺序正着输出;正解:低位先出,需反转。
- 误区:十六进制字母映射漏;正解:余数 >= 10 映射 A 起。
追问
- Q:负数怎么转? A:先处理符号,按绝对值转换后加负号。
- Q:小数进制转换? A:整数除基取余,小数乘基取整,本题一般只考整数。
02.8.1.4-006 阶乘末尾有多少个零?
一句话结论
末尾零由因子 10 = 2×5 产生,阶乘中 2 多于 5,零的个数等于 n! 中因子 5 的个数:n/5 + n/25 + n/125 + ...。
概念解释
- 10 的因子:2 和 5。
- 5 稀缺:计数由 5 决定。
- 多倍数:25 贡献两个 5,125 贡献三个。
原理流程
- 累加 n/5。
- n 除以 5 继续累加。
- 到商为 0 停止。
代码 / 示例
int trailingZeroes(int n) {
int c = 0;
while (n > 0) { n /= 5; c += n; }
return c;
}
常见误区
- 误区:数末尾 5 的数字个数;正解:要计 25、125 的多因子贡献。
- 误区:先算阶乘再数零;正解:阶乘极大,直接公式计数。
追问
- Q:复杂度? A:O(log_5 n)。
- Q:因子 2 为什么不统计? A:偶数足够多,不构成瓶颈。
02.8.1.4-007 回文数怎么判断?
一句话结论
负数不是回文;反转后半段数字与前半段比较:逐次取末位构造反转数,原数小于反转数时停止;避免整数反转带来的溢出问题。
概念解释
- 回文:正反读相同。
- 半段反转:只翻后半部分。
- 溢出规避:不构造完整反转。
原理流程
- 负数与末位为 0 且非 0 直接排除。
- 循环取末位构造 reverted。
- 原数 <= 反转数时停止,比较相等(偶数位)或去掉中位(奇数位)。
代码 / 示例
boolean isPalindrome(int x) {
if (x < 0 || (x % 10 == 0 && x != 0)) return false;
int rev = 0;
while (x > rev) { rev = rev * 10 + x % 10; x /= 10; }
return x == rev || x == rev / 10;
}
常见误区
- 误区:转字符串判断;正解:面试常要求纯数值做法,字符串法可作为对照。
- 误区:整数反转溢出;正解:半段反转不会超过原数量级。
追问
- Q:字符串法复杂度? A:O(n) 时间 O(n) 空间。
- Q:奇数长度中位怎么处理? A:
rev/10去掉中间位再比。
02.8.1.4-008 罗马数字与整数怎么互转?
一句话结论
罗马转整数:对照字符值,当前值小于后一值则减,否则加;整数转罗马:按贪心从大到小面值表依次取倍数;面值表包含 4、9 等减法组合。
概念解释
- 减法规则:小在前减(IV、IX)。
- 面值表:M、CM、D、CD、C...
- 贪心:大额优先匹配。
原理流程
- 转整数:遍历比较相邻值。
- 转罗马:面值降序,能取几组写几组符号。
代码 / 示例
// 罗马→整数:if (value[i] < value[i+1]) sum -= v; else sum += v
常见误区
- 误区:只按单字符加总;正解:减法组合要判断相邻大小。
- 误区:转罗马漏掉 4/9 组合;正解:面值表内置 CM/CD/IX/IV 等。
追问
- Q:复杂度? A:O(1),面值种类有限。
- Q:合法罗马数前提? A:输入保证规范序列。
02.8.1.4-009 快乐数怎么判断?
一句话结论
反复把各位数字平方求和;陷入 1 是快乐数,进入循环(重复出现非 1 的数)则不是;用哈希集记录出现过的数,或快慢指针判环。
概念解释
- 平方和变换:f(n)。
- 循环检测:重复即有环。
- 终止:到达 1 或重复。
原理流程
- 集合记录已出现数。
- 计算下一个平方和。
- 为 1 返回 true,重复返回 false。
代码 / 示例
boolean isHappy(int n) {
Set<Integer> seen = new HashSet<>();
while (n != 1 && !seen.contains(n)) {
seen.add(n);
n = squareSum(n);
}
return n == 1;
}
常见误区
- 误区:平方和一直增大;正解:位数有限时会收敛进循环。
- 误区:用数组记录;正解:数值范围不定,用哈希集。
追问
- Q:快慢指针怎么做? A:同链表环检测,快两步慢一步,相遇即环。
- Q:复杂度? A:环长度有限,O(log n) 量级变换次数。
02.8.1.4-010 多数元素(出现次数超一半)怎么找?
一句话结论
摩尔投票法:候选与计数,遇到相同计数加一,不同减一,计数归零换候选;出现超半数的候选不会被抵消完;最后需复核候选是否真超半数。
概念解释
- 抵消:不同元素两两抵消。
- 多数派:剩余候选必为多数元素(题设保证)。
- 复核:无保证时需统计确认。
原理流程
- candidate 任意,count = 0。
- 相同 +1,不同 -1,归零换候选。
- (可选)复核计数。
代码 / 示例
int majorityElement(int[] nums) {
int cand = 0, count = 0;
for (int x : nums) {
if (count == 0) cand = x;
count += (x == cand) ? 1 : -1;
}
return cand;
}
常见误区
- 误区:未复核就断定候选多数;正解:题设无超半数保证时必须再统计。
- 误区:计数减到负才换;正解:归零即换候选。
追问
- Q:复杂度? A:O(n) 时间,O(1) 空间。
- Q:出现次数为 n/3 的元素? A:摩尔投票可扩展到至多 k-1 个候选。
02.8.1.4-011 杨辉三角怎么生成?
一句话结论
每行首尾为 1,中间元素等于上一行左上与右上之和;按行迭代生成;第 i 行长度 i+1,递推基于上一行。
概念解释
- 边界:行首行尾 1。
- 递推:c[i][j] = c[i-1][j-1] + c[i-1][j]。
- 逐层生成。
原理流程
- 首行 [1]。
- 逐行构造,首尾补 1。
- 中间按上一行求和。
代码 / 示例
List<List<Integer>> generate(int n) {
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
List<Integer> row = new ArrayList<>();
for (int j = 0; j <= i; j++)
row.add(j == 0 || j == i ? 1 : res.get(i-1).get(j-1) + res.get(i-1).get(j));
res.add(row);
}
return res;
}
常见误区
- 误区:中间元素越界;正解:首尾位置单独赋值,只在内部求上一行和。
- 误区:行号从 1 还是 0 混淆;正解:按 0 起索引写递推。
追问
- Q:取某行怎么做? A:滚动两行或组合数 C(n,k)。
- Q:复杂度? A:O(n²),空间 O(n²)(结果)。
02.8.1.4-012 螺旋矩阵遍历怎么模拟?
一句话结论
维护上下左右四条边界,按右、下、左、上顺序遍历,每走完一边收缩对应边界并判断是否越界;方向固定循环,避免反复转向漏格。
概念解释
- 边界:top、bottom、left、right。
- 转向:一行/一列走完换方向。
- 收缩:已遍历的边移出边界。
原理流程
- 初始化四边。
- 右行 → 上边界收缩;下行 → 右边界收缩;左行 → 下边界收缩;上行 → 左边界收缩。
- 每步判断边界合法性。
代码 / 示例
while (top <= bottom && left <= right) {
右遍历 top 行;top++;
下遍历 right 列;right--;
左遍历 bottom 行;bottom--;
上遍历 left 列;left++;
}
常见误区
- 误区:收缩边界后不复查越界;正解:横向/纵向遍历前判断边界仍合法。
- 误区:方向顺序乱跳;正解:固定顺时针四方向循环。
追问
- Q:复杂度? A:O(mn),每格一次。
- Q:矩阵非方阵注意什么? A:中间剩单行/单列时方向判断易重复,需边界检查。
02.8.1.4-013 矩阵顺时针旋转 90 度怎么做?
一句话结论
原地旋转:先上下翻转(行逆序),再沿主对角线转置;或先转置再左右翻转;两步均为 O(n²),原地交换元素。
概念解释
- 翻转:行序颠倒。
- 转置:matrix[i][j] 与 matrix[j][i] 交换。
- 组合:等价于 90 度旋转。
原理流程
- 上下交换行。
- 主对角线转置。
- 核对角落位置映射。
代码 / 示例
// 先 reverse 各行顺序,再双层循环 swap(i,j) 与 (j,i)
常见误区
- 误区:直接按公式写新矩阵却声称原地;正解:原地需翻转组合,新建矩阵另算空间。
- 误区:转置遍历全表重复交换;正解:只遍历上三角交换。
追问
- Q:旋转后坐标映射? A:(i,j) → (j, n-1-i)。
- Q:非方阵能原地转吗? A:维度改变,需新建矩阵。
02.8.1.4-014 生命游戏原地更新怎么处理状态?
一句话结论
细胞下一代状态依赖邻居当前状态;原地更新需用中间编码:2 表示活→死,-1 表示死→活;先按旧状态统计邻居数并编码,第二轮解码为新状态。
概念解释
- 两代分离:计算时不能被新值干扰。
- 中间态:保留旧值信息同时标记新值。
- 两轮扫描:一轮编码,一轮解码。
原理流程
- 遍历统计八邻居旧活细胞数。
- 按规则写入中间编码。
- 第二轮把编码转成 0/1。
代码 / 示例
活细胞邻居 2/3 存活,否则死;死细胞邻居 3 复活;
中间态:1→0 记 2,0→1 记 -1
常见误区
- 误区:边遍历边写新状态;正解:邻居统计被新值污染,结果错误。
- 误区:邻居越界未处理;正解:八个方向先判断坐标合法。
追问
- Q:空间复杂度? A:原地 O(1) 额外,O(mn) 结果本身。
- Q:八邻居怎么数? A:方向数组两层循环。
02.8.1.4-015 模拟题的通用框架是什么?
一句话结论
模拟框架:明确状态与输入 → 定义方向/规则/边界 → 按时间或位置顺序推进 → 每步更新状态并记录 → 收尾校验;核心是边界条件与状态一致性,不靠花哨算法。
概念解释
- 状态:当前已知量。
- 规则:每步如何变化。
- 边界:越界、空输入、终止条件。
原理流程
- 列状态变量。
- 写推进规则。
- 循环到终止,核对输出。
代码 / 图示
状态初始化 → 规则推进 → 边界检查 → 结果记录
常见误区
- 误区:模拟题简单不写边界;正解:边界与越界是主要失分点。
- 误区:状态更新顺序错;正解:先算所有新状态再统一提交,避免互相污染。
追问
- Q:模拟题复杂度怎么估? A:按推进步数 × 每步操作。
- Q:常见模拟类型? A:矩阵方向、排队调度、字符串解析、时钟日期。
02.8.1.4-016 数值范围与溢出怎么预判?
一句话结论
先估结果量级(位数/乘积/累加),超过 int 范围用 long;累加与乘积先判溢出;比较时统一类型;不确定范围标注待确认并说明验证点。
概念解释
- int 上限:约 21 亿。
- long 上限:约 9.2×10¹⁸。
- 溢出表现:符号反转、数值截断。
原理流程
- 估算最大结果位数。
- 选数据类型。
- 运算前后核对边界。
代码 / 示例
long sum = 0; // 累加先按 long
// 乘积:先除后乘或检查范围
常见误区
- 误区:int 中间结果溢出后再转 long;正解:变量类型一开始就选 long。
- 误区:比较 int 与 long 自动转换遗漏;正解:统一类型后比较。
追问
- Q:阶乘结果用什么存? A:n 稍大即超 long,需大数类或只统计特征(如末尾零)。
- Q:溢出怎么发现? A:边界用例看结果是否符号反转。
02.8.1.4-017 组合数与取模在面试中掌握到什么程度?
一句话结论
理解组合数含义 C(n,k) 与递推 C(n,k)=C(n-1,k-1)+C(n-1,k);超大组合数通常取模,了解杨辉三角打表与阶乘逆元概念即可,不必深钻数论细节。
概念解释
- 组合:不计顺序选取。
- 递推:选/不选当前元素。
- 取模:结果过大时按模数计算。
原理流程
- 识别计数问题是否为组合。
- 小规模用递推表。
- 取模场景了解逆元存在。
代码 / 示例
C(n,k) = C(n-1,k-1) + C(n-1,k);边界 C(n,0)=C(n,n)=1
常见误区
- 误区:排列组合公式套错顺序;正解:先判是否有序。
- 误区:取模除法直接除;正解:模意义下需逆元。
追问
- Q:与 DP 什么关系? A:子集计数、背包计数都是组合思想的 DP 化。
- Q:面试会要求实现 Lucas 吗? A:一般不深挖,了解概念即可。
02.8.1.4-018 随机数取模要注意均匀性吗?
一句话结论
由区间随机映射到 [0,m) 时,直接 rand() % m 在 m 不整除随机范围时有轻微偏差;均匀要求高时用拒绝采样丢弃边界超出部分;面试题通常假设给定随机源均匀。
概念解释
- 取模偏差:余数分布不均。
- 拒绝采样:丢弃映射不均的尾段。
- 均匀性:每个目标值等概率。
原理流程
- 判断随机源范围与目标区间。
- 整除映射直接取模。
- 不整除则拒绝采样。
代码 / 示例
若范围 R 不被 m 整除,丢弃 >= floor(R/m)*m 的样本后再取模
常见误区
- 误区:取模一定均匀;正解:边界长度不齐时有偏差。
- 误区:随机算法结果不可复现;正解:固定种子可复现调试。
追问
- Q:蓄水池采样解决什么? A:未知长度数据流等概率抽样,见 02.8.1.5。
- Q:洗牌算法均匀性? A:Fisher-Yates 每排列等概率。
02.8.1.4-019 坐标与几何模拟要注意什么?
一句话结论
网格题用行列坐标与方向数组;距离按题目口径(曼哈顿/欧氏/切比雪夫);坐标越界先判断;旋转、反射等变换先写坐标映射公式再落代码。
概念解释
- 方向数组:dr、dc 四/八方向。
- 距离口径:曼哈顿 |dx|+|dy| 等。
- 变换:坐标公式先推导。
原理流程
- 定义坐标与方向。
- 越界检查。
- 按距离/变换规则计算。
代码 / 示例
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
常见误区
- 误区:距离口径混用;正解:按题目选曼哈顿或欧氏。
- 误区:行列坐标与 xy 坐标写反;正解:先约定 row、col 含义。
追问
- Q:网格 BFS 用什么距离? A:无权网格按步数(曼哈顿可达性)。
- Q:几何题精度问题? A:浮点比较用容差,避免直接判等。
02.8.1.4-020 怎么识别一道题是数学规律题还是模拟题?
一句话结论
存在闭式公式、递推规律或不变量 → 数学题,按规律求解;规则明确但过程需逐步推演、无简洁公式 → 模拟题,按状态推进;先试小样本找规律,找不到再模拟。
概念解释
- 闭式:O(1) 或低次幂公式。
- 模拟:按规则逐步走。
- 小样本:3~5 个用例观察规律。
原理流程
- 列小规模用例。
- 观察是否有周期/公式/不变量。
- 有规律走数学,否则模拟。
代码 / 图示
小样本 → 规律/不变量 → 公式;否则 → 状态模拟
常见误区
- 误区:模拟题硬找公式;正解:规则分支多时模拟更稳。
- 误区:数学规律未验证就套;正解:多个小样本核对。
追问
- Q:数学题面试讲什么? A:规律推导 + 公式 + 边界与溢出。
- Q:模拟题讲什么? A:状态变量 + 推进规则 + 边界处理。