描述
给一个由 1 -n的整数随机组成的一个字符串序列，其中丢失了一个整数，请找到它。
n < 100
数据保证有且仅有唯一解
在线评测地址：领扣题库官网
样例1
输入: n = 20 和 str = 19201234567891011121314151618
输出: 17
解释:
19'20'1'2'3'4'5'6'7'8'9'10'11'12'13'14'15'16'18样例2
输入: n = 6 和 str = 56412
输出: 3
解释:
5'6'4'1'2题解
算法：深度优先搜索
- dfs(now,step,n,len)表示当前的状态为考虑到了第now个字符（第now个字符还没使用），拼凑出来了step个数 一共需要拼出n-1个数，len是整个字符串的长度
- 枚举下次用一个字母还是两个字母来组成新的一个数字，判断组成的数字是不是在1到n之间，判断组成的数字有没有用过，判断组成的数字有没有前导0
- 判断结束后，递归搜索下一层
- 当now==len 并且 step==n-1时看看哪个数字没有用过就找到了最终答案
- 剪枝
剩下的字符每个字符都是一个数字 也凑不到n-1个数字
if(step+len-now<n-1) {
return 0;}
剩下的字符每两个字符构成一个数字，构成的数字也比n-1个要多
if(step+(len-now)/2>n-1){
return 0;}
复杂度
- 时间复杂度
O(C(n,len))O(C(n,len))
C表示组合数，n是多少个数字，len是字符串长度，但因为有很多剪枝，状态量要远远低于这个C(n,len)
- 空间复杂度
多开辟了标记数字有没有用过的数组visO(N)O(N)N是给定的n
代码
class Solution {
public:
/**
* @param n: An integer
* @param str: a string with number from 1-n in random order and miss one number
* @return: An integer
*/
int vis[50];
char s[100];
int dfs(int now, int step, int n, int len) {
//找到解了
//用了len个字符，拼出来n-1个数字
if(step == n - 1 && now == len) {
for(int i = 1; i <= n; i++) {
if(vis[i] == 0) {
return i;
}
}
return 0;
}
//剩下的字符每个字符都是一个数字 也凑不到n-1个数字
if(step + len - now < n - 1) {
return 0;
}
//剩下的字符每两个字符构成一个数字，构成的数字也比n-1个要多
if(step + (len - now) / 2 > n - 1) {
return 0;
}
//下个数字是多少
int tmp = 0;
for(int i = 0; i <= 1; i++) {
tmp = tmp * 10 + s[now + i] - '0';
//不能有前导0
if(tmp == 0)break;
// 判断tmp在不在1到n范围内，判断有没有使用超过len个字符 判断tmp之前有没有用过
if(vis[tmp] == 0 && tmp <= n && tmp >= 1 && now + i < len) {
vis[tmp] = 1;
int ans = dfs(now + 1 + i, step + 1, n, len);
vis[tmp] = 0;
//ans非0 表示找到了解
if(ans) {
return ans;
}
}
}
return 0;
}
int findMissing2(int n, string &str) {
//转成char数组
strcpy(s, str.c_str());
//初始化
for(int i = 1; i <= n; i++) {
vis[i] = 0;
}
int len = str.size();
int ans = dfs(0, 0, n, len);
return ans;
}
};更多题解参考：https://www.jiuzhang.com/solution/find-the-missing-number-ii/?utm_source=sc-zhihuzl-sy
