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

### 回答1：
以下是使用BFS（广度优先搜索）求解的C++代码：

#include <iostream>
#include <queue>
#include <unordered_set>
#include <cmath>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    // 计算n的位数
    int len = 0;
    int tmp = n;
    while(tmp) {
        len++;
        tmp /= 10;
    }
    
    // BFS
    queue<pair<int, int>> q; // 第一个元素表示当前数字，第二个元素表示已经删除的数字的个数
    unordered_set<int> visited; // 已经访问过的数字
    q.push({n, 0});
    visited.insert(n);
    while(!q.empty()) {
        int num = q.front().first;
        int cnt = q.front().second;
        q.pop();
        
        // 判断是否为完全平方数
        int sqr = sqrt(num);
        if(sqr * sqr == num) {
            cout << cnt << endl;
            return 0;
        }
        
        // 删除任意一个数字
        for(int i = 0; i < len; i++) {
            int tmp = num;
            int pow10 = pow(10, i);
            int digit = (num / pow10) % 10;
            tmp -= digit * pow10;
            if(tmp > 0 && visited.find(tmp) == visited.end()) {
                q.push({tmp, cnt + 1});
                visited.insert(tmp);
            }
        }
    }
    
    // 无法得到完全平方数
    cout << -1 << endl;
    
    return 0;
}

该代码中使用了队列和哈希表，队列用于BFS，哈希表用于记录已经访问过的数字，避免重复访问。在每一次BFS操作中，我们取出队列中的一个数字，判断它是否为完全平方数，如果是，则输出当前已经删除数字的个数，如果不是，则尝试删除任意一个数字，将得到的新数字加入队列中，继续进行BFS。如果队列为空仍未找到完全平方数，则输出-1。

### 回答2：
题目要求给定一个正整数n，通过删除数字使得结果成为一个完全平方数。我们需要确定最少的操作次数，并输出结果。

我们可以使用动态规划来解决这个问题。首先，我们定义一个数组dp，其中dp[i]表示从1到i能够构成的最少操作次数。接下来，我们可以通过迭代的方式来计算dp数组的值。对于每个dp[i]，我们可以考虑将i拆分成两个数字j和k，然后用dp[j]+dp[k]的值来更新dp[i]，表示通过删除数字j和k来实现最少操作次数。

在计算dp[i]之前，我们需要枚举i能够拆分成的两个数字。我们可以从1开始遍历到i的平方根，这样我们可以保证j和k都是小于i的正整数。对于每个拆分的情况，我们计算dp[j]+dp[k]的值，并取最小值作为dp[i]的值。

最后，我们只需要判断dp[n]是否为正无穷大。如果是，说明无法通过删除数字使得n成为一个完全平方数，输出-1；否则，输出dp[n]的值。

以下是伪代码的实现：

1. 将dp数组初始化为无穷大。
2. dp[0] = 0。
3. for i=1 to n，执行以下步骤：
- for j=1 to sqrt(i)，执行以下步骤：
- k = i - j * j。
- dp[i] = min(dp[i], dp[j] + dp[k])。
4. 如果dp[n]为无穷大，则输出-1；否则，输出dp[n]的值。

参考代码如下：

#include <iostream>
#include <cmath>
#include <algorithm>
#include <limits.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    int dp[n+1];
    fill(dp, dp + n + 1, INT_MAX);
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= sqrt(i); j++) {
            int k = i - j * j;
            dp[i] = min(dp[i], dp[j] + dp[k]);
        }
    }

    if (dp[n] == INT_MAX) {
        cout << -1 << endl;
    } else {
        cout << dp[n] << endl;
    }

    return 0;
}

以上代码使用动态规划和枚举的方法解决了这个问题，并输出了最少操作次数。代码时间复杂度为O(nsqrt(n))，空间复杂度为O(n)。

### 回答3：
题目要求我们给定一个正整数 n，通过删除其中的数字，使得剩下的数字组成的正整数是一个完全平方数，最终要求是求出最少的删除操作数。

我们可以首先判断给定的正整数 n 是否本身就是一个完全平方数，如果是，则最少的删除操作数为 0。否则，我们需要从给定的正整数 n 中删除一些数字，使得剩下的数字组成的正整数最终是一个完全平方数。

我们可以从 n 的十进制表示的最高位开始，依次尝试删除该位的数字并构造剩下的数字，然后判断剩下的数字是否是一个完全平方数，如果是，则最少的删除操作数即为已删除的数字的个数。

具体实现时，我们可以使用一个递归函数来进行尝试删除数字和判断是否是完全平方数的操作。递归函数的参数包括当前已经删除的数字的个数、当前构造的剩下的数字和最终要求的完全平方数。

递归的终止条件是当前构造的剩下的数字是一个完全平方数，此时返回已删除的数字的个数。否则，我们尝试删除当前剩下数字的最高位，并依次将剩下的数字的位数减一进行递归调用。

具体代码实现如下：

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

bool isPerfectSquare(int num) {
    int sqr = sqrt(num);
    return sqr * sqr == num;
}

int minDeleteNum(int n, int deletedNum, int targetNum) {
    // 当前构造的剩下的数字是一个完全平方数
    if (isPerfectSquare(n)) {
        return deletedNum;
    }
    // 当前构造的剩下的数字不是一个完全平方数
    if (n == 0) {
        return -1;
    }
    // 尝试删除当前剩下数字的最高位
    int digitNum = 0, temp = n;
    while (temp > 0) {
        temp /= 10;
        digitNum++;
    }
    int base = pow(10, digitNum - 1);
    int highestDigit = n / base;
    int restNum = n - highestDigit * base;
    return min(minDeleteNum(restNum, deletedNum + 1, targetNum),
               minDeleteNum(n - highestDigit * base * 10, deletedNum + 1, targetNum));
}

int main() {
    int n;
    cin >> n;
    int minDeletedNum = minDeleteNum(n, 0, n);
    cout << minDeletedNum << endl;
    return 0;
}

该算法的时间复杂度为 O(logN)，其中 N 是给定的正整数 n 的大小。