【DFS】寻找数字

题目

4726. 寻找数字

---

给定一个正整数 $n$ ，请你找到一个正整数 $x$ ，要求：

1. $x \ge n$
2. $x$ 的各个数位均不包含 $4$ 和 $7$ 以外的数字，且 $x$ 中包含的 $4$ 的数量与 $7$ 的数量恰好相等。
3. 满足前两个条件的前提下， $x$ 应尽可能小。

输入格式

一个正整数 $n$ 。

输出格式

一个正整数，表示 $x$ 。

数据范围

前 $6$ 个测试点满足 $1 \le n \le 5000$ 。
所有测试点满足 $1 \le n \le 10^9$ 。

输入样例1：

4500

输出样例1：

4747

输入样例2：

47

输出样例2：

47

解题

方法一：DFS

思路

输入数字为 n，设它的位数为 d。

• 如果 d 为偶数那么要找的数要么为 d 位要么为 d+2 位。
• 如果 d 为奇数那么要找的数必为 d+1 位。

确定了要找的数的位数(d)就可以用 DFS 很方便地构造了：数中 4 和 7 的数量一定是 d/2 个，那么只需要先把数中所有位先填满 7 然后从高位往低位依次替换为 4 直到其数量达到 d/2 个即为一个符合要求的数，然后把该数与 n 进行比较，输出构造出的第一个满足条件的数。

代码

#include <iostream>
#include <unordered_set>

using namespace std;

typedef long long LL;

string n;
bool flag = false;
unordered_set<string> vis;

void dfs(string s, int x, int d) {
    if (flag) return;
    if (x == 1) {
        if (stol(s) >= stol(n)) {
            cout << s << "\n";
            flag = true;
        }
        return;
    }
    for (int i = 0; i < d; ++i) {
        if (s[i] == '7') {
            s[i] = '4';
            if (vis.find(s) == vis.end()) {
                dfs(s, x - 1, d);
                vis.insert(s);
            }
            s[i] = '7';
        }
    }
}

void build(int d) {
    string s(d, '7');
    int hf = d / 2;
    for (int i = 0; i < d; ++i) {
        if (flag) return;
        s[i] = '4';
        dfs(s, hf, d);
        s[i] = '7';
    }
}

int main() {
    getline(cin, n);
    int d = n.size();
    if (d & 1) ++d;
    build(d);
    if (!flag) build(d += 2);

    return 0;
}