前置知识：时间复杂度、全排列递归代码的执行细节

一个基本事实

C/C++ 运行时间 1s，Java/Python/Go 等其他语言运行时间 1s~2s，对应的常数指令操作量（常数操作）是 $1 0^{7} ∽ 1 0^{8}$ ，不管什么测试平台，不管什么 cpu，都是这个数量级

一般来说，算法的常数操作量大于 $1 0^{8}$ ，即 C/C++ 运行时间超过 1s，测试平台会报“时间超出限制”而不通过

所以可以根据这个基本事实，来猜测自己设计的算法最终有没有可能在规定时间内通过

运用根据数据量猜解法技巧的必要条件：

题目要给定各个入参的范围最大值，正式笔试、比赛的题目一定都会给，面试中要和面试官确认
对于自己设计的算法，时间复杂度要有准确的估计

运用根据数据量猜解法技巧的说明：

该技巧只保证能够通过题目，不一定是最优解，常用于答题时间紧张的笔试、比赛中
该技巧既可以提前获知自己的方法能不能通过，也可以对题目的分析有引导作用

问题规模和可用算法

	$l o g n$	$n$	$n * l o g n$	$n * n$	$n^{2}$	$2^{n}$	$n!$
$n \leq 11$	Yes	Yes	Yes	Yes	Yes	Yes	Yes
$n \leq 25$	Yes	Yes	Yes	Yes	Yes	Yes	No
$n \leq 5000$	Yes	Yes	Yes	Yes	Yes	No	No
$n \leq 1 0^{5}$	Yes	Yes	Yes	Yes	No	No	No
$n \leq 1 0^{6}$	Yes	Yes	Yes	No	No	No	No
$n \leq 1 0^{7}$	Yes	Yes	No	No	No	No	No
$n \leq 1 0^{8}$	Yes	No	No	No	No	No	No

上面每个复杂度，课上都讲过类似的过程了

除了 $n * n$ ，这个复杂度常出现在“莫队算法”能解决的相关题目里，后续的【挺难】课程会有系统讲述

质数筛选问题也是 $n * n$

这张表其实作用有限，因为时间复杂度的估计很多时候并不是一个入参决定，可能是多个入参共同决定。比如 $O (n * m)$ 、 $O (n + m)$ 等

所以最关键的就是记住常数指令操作量是 $1 0^{7} ∽ 1 0^{8}$ ，然后方法是什么复杂度就可以估计能否通过了

题目1.最优的技能释放顺序

题目描述

现在有一个打怪类型的游戏，这个游戏是这样的，你有 n 个技能，每一个技能会有一个伤害，同时若怪物低于一定的血量，则该技能可能造成双倍伤害，每一个技能最多只能释放一次，已知怪物有 m 点血量，现在想问你最少用几个技能能消灭掉他（血量小于等于 0）

数据量： $1 \leq n \leq 10$ ， $0 \leq m \leq 1 0^{6}$ ， $1 \leq A (技能伤害), x (双倍伤害血量阈值) \leq m$

测试链接

消灭怪物

思路

$1 \leq n \leq 10$ ，所以将技能全排列（ $O (n!)$ ）也能通过时间限制

答案

牛客这道题没有 Go 环境，用 Java 吧

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
 
public class Main {
    public static int MAXN = 11;
    // 技能可以打多少血
    public static int[] kill = new int[MAXN];
    // 双倍伤害血量阈值
    public static int[] blood = new int[MAXN];
    // 一共有几个技能
    public static int n = 0;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int t = (int)in.nval;
            for (int i = 0; i < t; i++) {
                in.nextToken();
                n = (int)in.nval;
                in.nextToken();
                int m = (int)in.nval;
                for (int j = 0; j < n; j++) {
                    in.nextToken();
                    kill[j] = (int)in.nval;
                    in.nextToken();
                    blood[j] = (int)in.nval;
                }
                int ans = f(0, m);
                out.println(ans == Integer.MAX_VALUE ? -1 : ans);
            }
        }
        out.flush();
        br.close();
        out.close();
    }
 
    // idx: 当前来到了第几号技能
    // rest: 怪兽目前的剩余血量
    public static int f(int idx, int rest) {
        if (rest <= 0) {
            // 之前的决策已经让怪兽挂了！返回使用了多少个技能
            return idx;
        }
        if (idx == n) {
            // 没打死，之前的决策无效
            return Integer.MAX_VALUE;
        }
 
        // 返回至少需要几个技能可以将怪兽杀死
        int ans = Integer.MAX_VALUE;
        for (int i = idx; i < n; i++) {
            swap(i, idx);
            ans = Math.min(ans, f(idx + 1,
                                  rest - (rest > blood[idx] ? kill[idx] : 2 * kill[idx])));
            swap(i, idx);
        }
        return ans;
    }
 
    public static void swap(int i, int j) {
        int tmp = kill[i];
        kill[i] = kill[j];
        kill[j] = tmp;
        tmp = blood[i];
        blood[i] = blood[j];
        blood[j] = tmp;
    }
}

题目2.超级回文数的数目

题目描述

如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。

现在，给定两个正整数 L 和 R （以字符串形式表示），返回包含在范围 [L, R] 中的超级回文数的数目。

示例：

输入：L = "4", R = "1000"

输出：4

解释：4，9，121，以及 484 是超级回文数。注意 676 不是一个超级回文数： 26 * 26 = 676，但是 26 不是回文数

提示：

1 <= len(L) <= 18
1 <= len(R) <= 18
L 和 R 是表示 [1, 10^18) 范围的整数的字符串。
int(L) <= int(R)

测试链接

906.超级回文数

思路

由题目数据量可以看到，一个一个遍历的话，常数操作是 $1 0^{18}$ 规模的，这必然超时

一个数 $x$ 是超级回文数的话， $x$ 也必须是回文数，所以可以遍历 $1 ∽ x$ 的回文数看它的平方在不在 [L, R] 范围内，这样就降到了 $1 0^{9}$ 规模，还是超时

其实只需要看 $x$ 的前一半字符即可获得 $x$ ，如：前一半字符是 123，则 $x$ 可以是 12321 和 123321，这样就降到了 $1 0^{5}$ 规模

答案

func superpalindromesInRange(left string, right string) int {
	ans := 0
	l, _ := strconv.Atoi(left)
	r, _ := strconv.Atoi(right)
	// 最大根号 x，数据规模 10^9
	limit := int(math.Sqrt(float64(r)))
	// 根号 x 的前一半字符，数据规模 10^5
	seed := 1
	// 根号 x
	num := 0
	for num < limit {
		num = evenEnlarge(seed)
		if check(num*num, l, r) {
			ans++
		}
		num = oddEnlarge(seed)
		if check(num*num, l, r) {
			ans++
		}
		seed++
	}
	return ans
}
 
// 放大到偶数回文串
// 123 -> 123321
func evenEnlarge(seed int) int {
	ans := seed
	for seed != 0 {
		ans = ans*10 + seed%10
		seed /= 10
	}
	return ans
}
 
// 放大到奇数回文串
// 123 -> 12321
func oddEnlarge(seed int) int {
	ans := seed
	seed /= 10
	for seed != 0 {
		ans = ans*10 + seed%10
		seed /= 10
	}
	return ans
}
 
func check(x, l, r int) bool {
	return x >= l && x <= r && isPalindrome(x)
}
 
// 验证 x 是不是回文数字
func isPalindrome(x int) bool {
	offset := 1
	// 注意这么写是为了防止溢出
	for x/offset >= 10 {
		offset *= 10
	}
 
	for x != 0 {
		if x/offset != x%10 {
			return false
		}
		x = (x % offset) / 10
		offset /= 100
	}
	return true
}

解释

`evenEnlarge`

// 放大到偶数回文串
// 123 -> 123321
func evenEnlarge(seed int) int {
	ans := seed
	for seed != 0 {
		ans = ans*10 + seed%10
		seed /= 10
	}
	return ans
}

seed = 123

ans = 123 * 10 + 123 % 10 = 1233, seed = 12
ans = 1233 * 10 + 12 % 10 = 12332, seed = 1
ans = 12332 * 10 + 1 % 10 = 123321, seed = 0

oddEnlarge 同理

`isPalindrome`

是单独的一道题：回文数

打表的方法

用上面的方法看下整个 int64 范围内所有的超级回文数

package main
 
import (
	"fmt"
	"math"
	"sort"
)
 
func main() {
	superpalindromes := collectSuperpalindromes()
	sort.Slice(superpalindromes, func(i, j int) bool {
		return superpalindromes[i] < superpalindromes[j]
	})
	fmt.Println(len(superpalindromes)) // 86
	// fmt.Println(superpalindromes)
}
 
// 收集超级回文数
func collectSuperpalindromes() []int64 {
	var (
		l    int64 = 1
		r    int64 = math.MaxInt64
		seed int64 = 1
		num  int64 = 0
	)
	superpalindromes := []int64{}
	limit := int64(math.Sqrt(float64(r)))
	for num < limit {
		num = evenEnlarge(seed)
		if check(num*num, l, r) {
			superpalindromes = append(superpalindromes, num*num)
		}
		num = oddEnlarge(seed)
		if check(num*num, l, r) {
			superpalindromes = append(superpalindromes, num*num)
		}
		seed++
	}
	return superpalindromes
}
 
// 放大到偶数回文串
// 123 -> 123321
func evenEnlarge(seed int64) int64 {
	ans := seed
	for seed != 0 {
		ans = ans*10 + seed%10
		seed /= 10
	}
	return ans
}
 
// 放大到奇数回文串
// 123 -> 12321
func oddEnlarge(seed int64) int64 {
	ans := seed
	seed /= 10
	for seed != 0 {
		ans = ans*10 + seed%10
		seed /= 10
	}
	return ans
}
 
func check(x, l, r int64) bool {
	return x >= l && x <= r && isPalindrome(x)
}
 
// 验证 x 是不是回文数字
func isPalindrome(x int64) bool {
	var offset int64 = 1
	// 注意这么写是为了防止溢出
	for x/offset >= 10 {
		offset *= 10
	}
 
	for x != 0 {
		if x/offset != x%10 {
			return false
		}
		x = (x % offset) / 10
		offset /= 100
	}
	return true
}

发现 int64 范围内只有 86 个超级回文数，直接打表求解，时间复杂度 $O (1)$ ，无敌快！

var (
	record = [...]int{1, 4, 9, 121, 484, 10201, 12321, 14641, 40804, 44944, 1002001, 1234321, 4008004, 100020001, 102030201, 104060401, 121242121, 123454321, 125686521, 400080004, 404090404, 10000200001, 10221412201, 12102420121, 12345654321, 40000800004, 1000002000001, 1002003002001, 1004006004001, 1020304030201, 1022325232201, 1024348434201, 1210024200121, 1212225222121, 1214428244121, 1232346432321, 1234567654321, 4000008000004, 4004009004004, 100000020000001, 100220141022001, 102012040210201, 102234363432201, 121000242000121, 121242363242121, 123212464212321, 123456787654321, 400000080000004, 10000000200000001, 10002000300020001, 10004000600040001, 10020210401202001, 10022212521222001, 10024214841242001, 10201020402010201, 10203040504030201, 10205060806050201, 10221432623412201, 10223454745432201, 12100002420000121, 12102202520220121, 12104402820440121, 12122232623222121, 12124434743442121, 12321024642012321, 12323244744232321, 12343456865434321, 12345678987654321, 40000000800000004, 40004000900040004, 1000000002000000001, 1000220014100220001, 1002003004003002001, 1002223236323222001, 1020100204020010201, 1020322416142230201, 1022123226223212201, 1022345658565432201, 1210000024200000121, 1210242036302420121, 1212203226223022121, 1212445458545442121, 1232100246420012321, 1232344458544432321, 1234323468643234321, 4000000008000000004}
)
 
func superpalindromesInRange(left string, right string) int {
	l, _ := strconv.Atoi(left)
	r, _ := strconv.Atoi(right)
	n := len(record)
 
	// 二分都懒得用
	i := 0
	for ; i < n; i++ {
		if record[i] >= l {
			break
		}
	}
	j := n - 1
	for ; j >= 0; j-- {
		if record[j] <= r {
			break
		}
	}
	return j - i + 1
}

题目3.回文数

题目描述

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是

测试链接

9.回文数

思路一

// 验证 x 是不是回文数字
func isPalindrome(x int) bool {
	if x < 0 {
		return false
	}
	offset := 1
	// 注意这么写是为了防止溢出
	for x/offset >= 10 {
		offset *= 10
	}
 
	for x != 0 {
		if x/offset != x%10 {
			return false
		}
		x = (x % offset) / 10
		offset /= 100
	}
	return true
}

x = 123321

offset = 100000

x/offset = 123321/100000 = 1 // 提取最左侧数字（最高位）
x/10 = 123321/10 = 1         // 提取最右侧数字（最低位）

x = (x % offset) / 10
  = 23321 / 10
  = 2332                     // 去除最高位和最低位


offset /= 100 
  = 100000/100
  = 1000                     // 去除两位，保持和 x 位数一样

思路二

把数字逆序，然后和原数比较

func isPalindrome(x int) bool {
	if x < 0 {
		return false
	}
	reversed := 0
	for i := x; i != 0; i /= 10 {
		reversed = reversed*10 + i%10
	}
	return reversed == x
}

该方法能通过测试，但是有个问题：如果 x 已经确定不是回文数，而且它逆序的结果会溢出。有没有可能存在某个 x，逆序溢出之后得到的结果还是 x，导致判断错误？如果没有这种可能，需要证明；而思路一一定不溢出，一定是正确的。

思路三

int 转 string 后左右双指针

My-Notes

Explorer

025.根据数据量猜解法的技巧-天字第一号重要技巧

一个基本事实

问题规模和可用算法

题目1.最优的技能释放顺序

题目描述

测试链接

思路

答案

题目2.超级回文数的数目

题目描述

测试链接

思路

答案

解释

`evenEnlarge`

`isPalindrome`

打表的方法

题目3.回文数

题目描述

测试链接

思路一

思路二

思路三

Graph View

Table of Contents

Backlinks

My-Notes

Explorer

025.根据数据量猜解法的技巧-天字第一号重要技巧

一个基本事实 §

问题规模和可用算法 §

题目1.最优的技能释放顺序 §

题目描述 §

测试链接 §

思路 §

答案 §

题目2.超级回文数的数目 §

题目描述 §

测试链接 §

思路 §

答案 §

解释 §

evenEnlarge §

isPalindrome §

打表的方法 §

题目3.回文数 §

题目描述 §

测试链接 §

思路一 §

思路二 §

思路三 §

Graph View

Table of Contents

Backlinks

一个基本事实

问题规模和可用算法

题目1.最优的技能释放顺序

题目描述

测试链接

思路

答案

题目2.超级回文数的数目

题目描述

测试链接

思路

答案

解释

`evenEnlarge`

`isPalindrome`

打表的方法

题目3.回文数

题目描述

测试链接

思路一

思路二

思路三