lintcode 570. 寻找丢失的数 II

喜欢ヅ旅行 2023-05-22 08:44 13阅读 0赞

给一个由 1 - n 的整数随机组成的一个字符串序列，其中丢失了一个整数，请找到它。

样例
    样例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
    注意事项
    n <= 30
    数据保证有且仅有唯一解

递归寻找所有可能的搭配情况，直到找出所丢失的数

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 findMissing2(int n, string &str) {
        
            // write your code here
            vector<bool>visit(n+1,false);
            return dfs(str,n,visit,0);
        }
        int dfs(string &str,int n,vector<bool> &visit,int index)
        {
        
            if(index==str.size())
            {
        
                vector<int>res;
                for (int i = 1; i <= n; i++) {
        
                    if(!visit[i]) res.push_back(i);
                }
                if(res.size()==1) return res[0];
                else return -1;
            }
            else if(str[index]=='0') return -1;
            else
            {
        
                for(int i = 1; i < 3;i++)
                {
        
                    if(index+i-1<str.size())
                    {
        
                        int num=stoi(str.substr(index,i));
                        if(num>=1&&!visit[num]&&num<=n)
                        {
        
                            visit[num]=true;
                            int ret=dfs(str,n,visit,index+i);
                            if(ret!=-1) return ret;
                            visit[num]=false;
                        }
                    }
                }
                return -1;
            }
        }
    };