给定一个正整数 n, 不带前导零（例如，数字 04 不正确）。 在一个操作中，你可以删除给定整数的任何数字，使结果保持为不带前导零的正整数。 确定最少操作数，使最终的正整数成为完全平方数。如果不可能输出-1。c++代码

### 回答1：
以下是 C++ 的代码实现：

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;

int n, ans = INF;
bool used[10];

void dfs(int cur, int cnt) {
    if (cur == 0) {
        return;
    }
    int root = sqrt(cur);
    if (root * root == cur) {
        ans = min(ans, cnt);
        return;
    }
    for (int i = 0; i <= 9; ++i) {
        if (used[i] || (cur < 10 && i == 0)) {
            continue;
        }
        used[i] = true;
        dfs(cur / 10 * 10 + i, cnt + 1);
        used[i] = false;
    }
}

int main() {
    cin >> n;
    dfs(n, 0);
    cout << (ans == INF ? -1 : ans) << endl;
    return 0;
}

首先，我们定义一个全局变量 `ans` 表示最小操作数，将其初始化为正无穷。

然后我们使用深度优先搜索（DFS）来枚举所有可能的操作序列，找到最少操作数的完全平方数。

对于每个操作序列，我们首先判断当前数字是否为完全平方数，如果是，则更新最小操作数，并返回。

如果不是，则枚举删除每个数字的所有可能，并继续进行搜索。

需要注意的是，如果当前数字以 0 开头，那么删除任何数字都会导致前导 0，因此需要特判。

最后输出答案即可，如果不存在完全平方数，则输出 -1。

### 回答2：
首先，我们可以将整数 n 转化为字符串，并检查是否存在前导零。如果存在，则直接输出 -1。

接下来，我们需要确定一个最小操作数，使得最终的整数成为完全平方数。我们可以使用动态规划来解决这个问题，其中 dp[i] 表示对前 i 个数字进行操作所需的最小次数。

考虑最后一个数字的平方，可以推出一个状态转移方程：dp[i] = min(dp[i-j*j]+1)，其中 j*j <= i，并且 i - j*j 可以通过删除数字得到。由于我们要求最小次数，所以我们需要遍历所有的 j*j 并选择最小的 dp[i-j*j]+1。

最后，我们返回 dp[n] 的值作为结果。

代码如下所示：

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
using namespace std;

int minOperations(int n) {
    string num = to_string(n);
    if (num[0] == '0') {
        return -1;
    }
    int size = num.size();
    vector<int> dp(size + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= size; i++) {
        for (int j = 1; j * j <= i; j++) {
            dp[i] = min(dp[i], dp[i - j * j] + 1);
        }
    }
    return dp[size] == INT_MAX ? -1 : dp[size];
}

int main() {
    int n;
    cin >> n;
    cout << minOperations(n) << endl;
    return 0;
}

这段代码的时间复杂度为 O(n * sqrt(n))，其中 n 是给定的正整数。

### 回答3：
首先，我们可以考虑暴力解法。枚举所有数字 i，从 1 到 n，删除其中的一位或多位数字，然后判断剩下的数字是否为完全平方数。最后统计删除的操作数，找出最小的操作数即可。

但是这种暴力解法的时间复杂度为 O(n * log(n) ^ 2)，当 n 的范围较大时，不适用。

我们可以通过动态规划来解决这个问题。
设状态 dp[i] 表示前 i 位数字的最小操作数。我们从最高位开始计算，假设第 i 位数字为 d。

对于第 i 位数字，我们可以选择删除它或者保留它。如果删除第 i 位数字，则最终的数字是由前 i-1 位组成。
否则，最终的数字是由前 i-1 位与第 i 位组成，即将第 i 位数字作为最低位。

如果我们删除了第 i 位数字，并且前 i-1 位数字的最小操作数为 dp[i-1]，则需要进行 dp[i-1] + 1 次操作。
如果我们保留了第 i 位数字，并将第 i 位数字作为最低位，则需要判断前 i 位数字与第 i 位数字组成的数是否为完全平方数。
如果是，则不需要进行额外操作；如果不是，则需要进行 1 次操作。

因此，我们可以得到状态转移方程为：
dp[i] = min(dp[i-1]+1, dp[i]), i-1>=0
其中，dp[i-1]+1 表示删除第 i 位数字的操作数，dp[i] 表示保留第 i 位数字后的操作数。

最终的答案为 dp[n]。

下面是实现该算法的 C 代码：

#include <stdio.h>
#include <math.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int getMinOperations(int n) {
    int dp[n+1];
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = i; // 初始化为 i，表示最坏情况下每一位数字都需要删除
        int num = i;
        for (int j = 0; j < 9; j++) {
            dp[i] = min(dp[i], dp[i / 10] + 1); // 删除第 i 位数字
            if (num % 10 != 0 && (int)sqrt(num + (int)pow(10, j)) == (int)sqrt(num + (int)pow(10, j)))
                dp[i] = min(dp[i], dp[i / 10]); // 保留第 i 位数字
            num /= 10;
        }
    }
    return dp[n];
}

int main() {
    int n;
    printf("请输入一个正整数: ");
    scanf("%d", &n);
    int result = getMinOperations(n);
    if (result == n)
        printf("不可能\n");
    else
        printf("最少操作数为: %d\n", result);
    return 0;
}

这样就可以通过动态规划得到最小操作数，使最终的正整数成为完全平方数。如果不可能，输出 -1。