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

Example

Given n = 20, str = 19201234567891011121314151618

return 17

这题是网上借鉴别人的代码一开始没有想到要用DFS 利用这道题顺便复习了下DFS的schema 注意flag 是用来剪枝避免重复计算的

 1 public class Solution {
 2     /**
 3      * @param n an integer
 4      * @param str a string with number from 1-n
 5      *            in random order and miss one number
 6      * @return an integer
 7      */
 8     int ans=0;
 9     boolean flag =false;
10     public int findMissing2(int n, String str) {
11         // Write your code here
12         boolean[] appear = new boolean[n+1];
13         dfs(0, n, str, appear);
14         return ans;
15     }
16     
17     private void dfs(int i, int n, String s, boolean[] appear){
18         if(i>=s.length()||flag){
19             if(!flag){
20                 for(int k=1; k<=n;k++){
21                     if(!appear[k]){
22                         ans = k;
23                     }
24                 }
25             }
26             flag = true;
27             return;
28         }
29         int sum = s.charAt(i)-'0';
30         if(sum ==0){
31             return;
32         }
33         int j = i+1;
34         while(sum<=n){
35             if(!appear[sum]){
36                 appear[sum] = true;
37                 dfs(j, n, s, appear);
38                 appear[sum] = false;
39             }
40             if(j>=s.length()) return;
41             sum = 10*sum + (s.charAt(j++)-'0');
42         }
43     }
44 }