狗家Fall Intern电面

第一题 立扣 糁舅舅

zhangsikai123 发表于 2017-7-13 10:26
第二题个人感觉应该属于人工智能领域的CSP问题，类似八皇后问题，本身是NP-hard，但也有很多优化方法，这里 ...

N 皇后这个思路很赞！  dp解超过我的能力了

zhangsikai123 发表于 2017-7-13 10:26
第二题个人感觉应该属于人工智能领域的CSP问题，类似八皇后问题，本身是NP-hard，但也有很多优化方法，这里 ...

参照大神点拔的八皇后思路。用bit manipulation 存状态 做了backtracking. 如下。大神的dp解更优。我这个可能稍微适合普通玩家理解一点。

1. #include <iostream>
   
2. #include <vector>
   
3. using namespace std;
   
4. 
   
5. #define N 6  // N is the length of target string
   
6. 
   
7. bool helper(vector<string>& strs, string target, int state, int pos){
   
8.    
   
9.     // calculate cross: indices of chars in target that also appear in strs[pos]. Those indices are set at the corresponding bit in "cross".
   
10.     if(state == (1 << N) - 1) return true; // all bits are set
    
11.     if(pos == N) return false; // already tried all strings in strs without success
    
12.    
    
13.     int cross = 0;
    
14.     string& curr = strs[pos];
    
15.     for(int i = 0; i < N; i++) {
    
16.         if(count(curr.begin(), curr.end(), target[i]))
    
17.             cross |= (1 << i);
    
18.     }
    
19.     int cand = cross & (~state);
    
20.     for(; cand != 0; cand -= cand & (-cand)) {
    
21.         if(helper(strs, target, state + (cand&(-cand)), pos+1)) return true;
    
22.     }
    
23.     return false;
    
24. }
    
25. 
    
26. bool makeTarget(vector<string>& strs, string target) {
    
27.     int state = 0;
    
28.     return helper(strs, target, state, 0);
    
29. }
    
30. 
    
31. int main(int argc, const char * argv[]) {
    
32.     // insert code here...
    
33.     vector<string> strs = {
    
34.         "abcdef",
    
35.         "abcdef",
    
36.         "abcdef",
    
37.         "abcdef",
    
38.         "abcdef",
    
39.         "abcdef"
    
40.     };
    
41.     cout << helper(strs, "abcdef", 0, 0) << endl;
    
42.    
    
43.     strs = vector<string> ({
    
44.         "abcdef",
    
45.         "abcdef",
    
46.         "abcdef",
    
47.         "abcdef",
    
48.         "abcdef"
    
49.     });
    
50.     cout << helper(strs, "abcdef", 0, 0) << endl;
    
51.    
    
52.     strs = vector<string> ({
    
53.         "axxxxx",
    
54.         "abyyyy",
    
55.         "abczzz",
    
56.         "abcdqq",
    
57.         "abcdep",
    
58.         "lllllf"
    
59.     });
    
60.     cout << helper(strs, "abcdef", 0, 0) << endl;
    
61.     return 0;
    
62. }

复制代码

codemonk 发表于 2017-8-25 05:09
N 皇后这个思路很赞！  dp解超过我的能力了

正解应该是网络流，Edmonds-Karp算法: https://en.wikipedia.org/wiki/Maximum_flow_problem, CLRS上也有。这俩人靠这个算法拿了图灵奖....如果半小时空想想出来那只可能是神。