新鲜G家电面， 顺便求加米

一个国人小哥，45分钟只做出了这一道题，连follow up都没时间问了

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

发现自己大米好少，面试前大部分面经都没权限看，也不知道这道题之前有没有人发过。求加点大米啊。

已加米，楼主能简单说下思路吗

空心蔡 发表于 2019-5-2 04:03
已加米，楼主能简单说下思路吗

我其实没有想到什么特别好的办法，最后的解法接近暴力的DFS，就是从一个颜色开始，先固定这个颜色的一个path，然后dfs下一个颜色，以此类推。找到的话就直接返回，否则就递归继续找下去。

follow up有可能是填满所有格子呢？   楼主最后这问做出来了么

大头菜 发表于 2019-5-6 04:36
follow up有可能是填满所有格子呢？   楼主最后这问做出来了么

做完之后没时间follow up了，recuriter又给补了一个电面，感觉面的一般吧

先用dfs找第一条路径，找到后，当场就找第二条路径。只有在当前路径找到，而且在下一条路径也找到的时候，才返回true.

1. #include <iostream>
   
2. #include <vector>
   
3. #include <unordered_set>
   
4. 
   
5. using namespace std;
   
6. 
   
7. class Solution_flow_free {
   
8.     vector<vector<int>> directions{
   
9.             {0, 1},
   
10.             {0, -1},
    
11.             {1, 0},
    
12.             {-1, 0}
    
13.     };
    
14. 
    
15. public:
    
16.     bool isValid(vector<vector<int>>& nums) {
    
17.         unordered_set<int> nodes;
    
18.         vector<vector<int>> start_nodes;
    
19.         int i = 0, j = 0;
    
20.         for (i = 0; i < nums.size(); i++)
    
21.             for (j = 0; j < nums[0].size(); j++)
    
22.                 if (nums[i][j] != 0 && nodes.find(nums[i][j]) == nodes.end()) {
    
23.                     start_nodes.push_back({i, j, nums[i][j]});
    
24.                     nodes.insert(nums[i][j]);
    
25.                 }
    
26.         if (start_nodes.empty()) return true;
    
27.         i = start_nodes[0][0], j = start_nodes[0][1];
    
28.         return dfs(nums, start_nodes, 0, true, i, j);
    
29.     }
    
30. 
    
31.     bool dfs(vector<vector<int>>& nums, vector<vector<int>>& start_nodes, int n, bool start, int i , int j) {
    
32.         int start_i = start_nodes[n][0], start_j = start_nodes[n][1], target = start_nodes[n][2];
    
33.         if (i < 0 || i == nums.size() || j < 0 || j == nums[0].size())
    
34.             return false;
    
35.         if (nums[i][j] != 0 && nums[i][j] != target) return false;
    
36. 
    
37.         if (!start && nums[i][j] == target) {   // 找到终点，或者回到起点
    
38.             if (i == start_i && j == start_j) return false; // 回到起点
    
39.             // 找到终点了
    
40.             if (n == start_nodes.size() - 1) return true;   // 现在已经是最后一条连线了
    
41.             int next_i = start_nodes[n+1][0];
    
42.             int next_j = start_nodes[n+1][1];
    
43.             return dfs(nums, start_nodes, n+1, true, next_i, next_j);
    
44.         } else {    // 要么是刚刚出发，要么是正在路上
    
45.             if (nums[i][j] == 0) nums[i][j] = -1;   // 正在路上，标记此点已经访问
    
46.             for (const vector<int>& dir: directions) {
    
47.                 int next_i = i + dir[0];
    
48.                 int next_j = j + dir[1];
    
49.                 if (dfs(nums, start_nodes, n, false, next_i, next_j)) return true;
    
50.             }
    
51.             if (!start) nums[i][j] = 0;
    
52.             return false;
    
53.         }
    
54.     }
    
55. };
    
56. 
    
57. 
    
58. 
    
59. int main() {
    
60.     Solution_flow_free sol;
    
61.     vector<vector<int>> nums{
    
62.             {1, 0, 0, 2, 0},
    
63.             {0, 0, 3, 0, 0},
    
64.             {0, 0, 0, 1, 0},
    
65.             {0, 2, 0, 0, 0},
    
66.             {0, 0, 0, 3, 0}
    
67.     };
    
68.     cout << sol.isValid(nums) << endl;
    
69. }

复制代码

大家看看我这个解法行不行