Lintcode 570 - Find the Missing Number II

Related:
Lintcode 570 - Find the Missing Number II
LeetCode 41 - First Missing Positive
LintCode 196 - Find the Missing Number I
LeetCode 287 - Find the Duplicate Number - Google Interview

https://www.lintcode.com/en/problem/find-the-missing-number-ii/

Giving a string with number from 1-n in random order, but miss 1 number.Find that number.

 Notice

n <= 30

Have you met this question in a real interview?

Yes

Example

Given n = 20, str = 19201234567891011121314151618

return 17

http://blog.csdn.net/gqk289/article/details/66968192

1.     int res = 0;  
2.     boolean found = false;  
3.     public int findMissing2(int n, String str) {  
4.         // Write your code here  
5.         boolean[] cache = new boolean[n + 1];  
6.         dfs(n, str, 0, cache);  
7.         return res;  
8.     }  
9.     private void dfs(int n, String str, int i, boolean[] cache) {  
10.         if (i >= str.length() || found) {  
11.             if (!found) {  
12.                 for (int j = 0; j <= n; j++) {  
13.                     if (!cache[j]) {  
14.                         res = j;  
15.                     }  
16.                 }  
17.                 found = true;  
18.             }  
19.             return;  
20.         }  
21.         int j = i;  
22.         int sum = str.charAt(j) - '0';  
23.         if (sum == 0) {  
24.             return;  
25.         }  
26.         while (sum <= n) {  
27.             if (!cache[sum]) {  
28.                 cache[sum] = true;  
29.                 dfs(n, str, j + 1, cache);  
30.                 cache[sum] = false;  
31.             }  
32.             j++;  
33.             if (j >= str.length()) {  
34.                 break;  
35.             }  
36.             sum = sum * 10 + (str.charAt(j) - '0');  
37.         }  
38.     }  

https://xizha677.gitbooks.io/codenotes/content/find-the-missing-number-ii.html

initialize a foundNums boolean array with false value for number from 1 to n.

If the first digit is less than n, set it as found in foundNums and check the remaining part.

If the first two digits are less than n, set this number as found in foundNums and check the remaining part.

Stop when no more digit left, and return the only missing number in foundNums.

    private int result = 0;

    public int findMissing2(int n, String str) {
        dfs(0, n, str, new boolean[n + 1]);
        return result;
    }

    private void dfs(int idx, int n, String str, boolean[] foundNums) {
        if (idx >= str.length()) {
            int count = 0;
            int firstI = 0;
            for (int i = 1; i <= n; i++) {
                if (!foundNums[i]) {
                    count++;
                    firstI = i;
                }

            }
            if (count == 1) {
                result = firstI;
            }
            return;
        }
        //one digits
        int num = (int)(str.charAt(idx) - '0');
        if (num <= n && !foundNums[num]) {
            foundNums[num] = true;
            dfs(idx + 1, n, str, foundNums);
            foundNums[num] = false;
        }

        //two digits
        if (idx + 1 >= str.length()) {
            return;
        }
        num = num * 10 + (int)(str.charAt(idx + 1) - '0');
        if (num <= n && !foundNums[num]) {
            foundNums[num] = true;
            dfs(idx + 2, n, str, foundNums);
            foundNums[num] = false;
        }
    }

http://blog.hyoung.me/cn/2017/02/find-the-missing-number/

严格来说，这个变形题其实已经跟上面的那一道题关系不是很大了，也无法利用到桶排序的方法，具体原因在下面分析。这本质就是一道搜索类的题目，而且需要穷举才能解决，那么就是用 DFS 了。

具体来说，就是每次从字符串头部选取一个数，如果这个数没有出现过的话，把这个数记录下来，然后继续把剩余的字符串作为子问题继续搜索，直到找到一个可行的组合。最后再去这个组合里面找缺失的数。

因为有了 $n\le 30$ 这个输入的限制条件，我们其实每次只需考察字符串头部前一位和前两位就可以了。此外，若字符串是以0开头，那么直接返回false就好了。

http://www.jiuzhang.com/solutions/find-the-missing-number-ii/

    public boolean flag = false;
    public int ans = 0;
    public int findMissing2(int n, String str) {
        boolean[] happen = new boolean[n + 1];
        dfs(0, n, str, happen);
        return ans;
    }
    
    public void dfs(int i, int n, String s, boolean[] happen) {
        if (i >= s.length() || flag) {
         if (!flag)
            for (int k = 1; k <= n; k++) {
                if (!happen[k]) {
                    ans = k;
                }
            }
         flag = true;
            return;
        }
        int sum = s.charAt(i) - '0';
        int j = i;
        if (sum == 0) {
            return;
        }
        while (sum <= n) {
            if (!happen[sum]) {
                happen[sum] = true;
                dfs(j+1, n, s, happen);
                happen[sum] = false;
            }
            j++;
            if (j >= s.length()) {
                break;
            }
            sum = sum * 10 + (s.charAt(j) - '0');
        }
    }