统计给定区间内符合数位交替大小规则的完全平方数及代码问题排查

代码存在的Bug #

1. 数位校验逻辑未处理相等场景 #

原代码的数位判断仅校验了严格大于/小于的非法情况，遗漏了相邻数字相等的非法判断：

• 当isless=true（要求前一位 < 当前位）时，仅当a > b时标记非法，a == b的情况未拦截
• 当isless=false（要求前一位 > 当前位）时，仅当a < b时标记非法，a == b的情况未拦截
  举个反例：完全平方数144（12的平方），数位规则要求1 < 4 > 4，最后两位相等不满足规则，原代码会错误判定为合法，正确结果应为非法。
  修复方案是把判断条件改为包含相等的情况：

if (isless && a >= b) { // 原逻辑仅判断a > b，新增等于的非法场景
    valid = false;
    break;
}
if (!isless && a <= b) { // 原逻辑仅判断a < b，新增等于的非法场景
    valid = false;
    break;
}

2. 大数场景下平方根计算精度风险 #

Math.sqrt返回double类型，double仅能精确表示小于2^53的整数，当后续题目范围扩大到N>1e16时，会出现平方根计算偏差导致枚举范围错误。本题N上限为1e11，平方根仅约3e5，暂时不会触发该问题，如需兼容更大范围可以替换为二分法或牛顿迭代法计算整数平方根。 #

时间复杂度优化思路 #

当前实现的时间复杂度为O(√N * D)，其中D是数位最大长度（本题为11），√1e11 ≈ 3.16 * 10^5，总运算量不到400万，已经完全满足性能要求。如果要进一步优化可以采用以下方案：

• 预计算所有1到√(1e11)范围内符合规则的完全平方数，存入有序列表，后续每次查询直接用二分法统计[M,N]区间内的元素个数，单次查询复杂度可以降到O(log K)，K是符合条件的数的总个数（实际K远小于3e5）
• 对于更大范围的场景（比如N到1e18），可以采用数位DP直接构造满足交替大小规则的数，再判断是否为完全平方数，避免枚举所有平方数。

内容的提问来源于stack exchange，提问作者Learner