题目描述

难度分:$1400$

输入$n(1 \leq n \leq 10^9)$。每次操作，你可以删除$n$的一个数字。需要保证删除后$n$仍然是一个没有前导零的正整数。你可以操作任意次。

问：把$n$变成一个完全平方数，至少需要操作几次？

输出操作次数。如果无法做到，输出$-1$。

输入样例$1$

8314

输出样例$1$

2

输入样例$2$

625

输出样例$2$

0

输入样例$3$

333

输出样例$3$

-1

算法

递归

先做一个预处理，将$[1,n]$中所有的完全平方数存入到一个哈希集合中。然后对$n$进行递归处理，对于每次递归，只要发现$n$在集合中就返回$0$。否则需要删除一位，枚举删除的数位，继续递归剩下的部分。

递归边界是$n$是一个个位数时可以直接检查它是否在完全平方数的集合中，对于一般情况，可以写成一个状态转移方程式$dp[cur]=1+min_{nxt}dp[nxt]$，其中$nxt$是去除掉$cur$的一个数位所表示的无前导零整数。最终答案就是$dp[n]$，不过本题的数据量下没有必要做记忆化。

复杂度分析

时间复杂度

预处理的时间复杂度为$O(\sqrt{n})$；递归的第一层$n$有$x$位（$x$最大为$10$），第二层还剩$x-1$位，直到最后一层剩下$1$位，时间复杂度应该为$O(x!)$。因此，算法总体的时间复杂度为$O(\sqrt{n}+x!)$。

空间复杂度

递归层数的消耗只和$n$的位数有关，相比$n$的话很小，因此空间瓶颈是集合的消耗，额外空间复杂度为$O(\sqrt{n})$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
unordered_set<int> us;

int dfs(int n) {
    if(n < 10) return us.count(n)? 0: INF;
    if(us.count(n)) return 0;
    int res = INF;
    string str = to_string(n);
    int sz = str.size();
    for(int i = 0; i < sz; i++) {
        string substr = str.substr(0, i) + str.substr(i + 1);
        if(substr[0] != '0') {
            int x = stoi(substr);
            int nxt = dfs(x);
            if(nxt != INF) res = min(res, 1 + nxt);
        }
    }
    return res;
}

int main() {
    int n;
    scanf("%d", &n);
    if(us.empty()) {
        // 预处理
        for(int i = 1; (LL)i*i <= n; i++) {
            us.insert(i*i);
        }
    }
    int res = dfs(n);
    if(res == INF) res = -1;
    printf("%d\n", res);
    return 0;
}