微软SWE暑期实习一面
题目
7个晶体管上的灯的亮暗可以组成0-9的任意一个数字。假设有n组晶体管，每组晶体管中至少有一个亮，可能存在坏了的晶体管。
假设有2组晶体管，第一组是数字2，因为有坏了的可能， 2->2,2->8;其可能为2/8；第2组是数字3，其可能为3/8/9
由此可以组成{23,28,29,83,88,89}
input:n个7位数，即有n组晶体管
output:组成的数字，例如本题的{23,28,29,83,88,89}
面试思路
- 得到残缺的数字中的暗的晶体管，若包含正常数字的所有暗的晶体管，则可以变成这个数字。用set
- 得到数字之后全排列就可以得到答案
- 但是没有写出来
提示
- 数字位运算（&）就可以得到是否包含
例如:2 (1011011) 只有2和5为暗，其他为亮
8 (1111111) 全亮
2 & 8 （每一位按位与）= 2 （则可以由2拓展到8）
- 每一组晶体管都有一系列可以拓展的值（dfs,回溯）
代码
//tag: dfs,回溯,位运算
#include<bits/stdc++.h>
using namespace std;
vector<int> v(10) ;
void init() {
v[0] = 0b0111111; // 可以用二进制表示0b101100等等
v[1] = 0b0000110;
v[2] = 0b1011011;
v[3] = 0b1001111;
v[4] = 0b1100110;
v[5] = 0b1101101;
v[6] = 0b1111101;
v[7] = 0b0000111;
v[8] = 0b1111111;
v[9] = 0b1101111;
}
vector<vector<int>> ha;
string ans;
vector<string> res;
void dfs(int n) {
if (n == ha.size()) { //终止条件
res.push_back(ans);
return;
}
for (int i = 0; i < ha[n].size(); i++) { //扩展新结点
ans.push_back(char(ha[n][i] + '0'));
dfs(n + 1);
ans.pop_back(); // 回溯
}
}
void d(vector<int> in) {
ha.resize(in.size());
for (int i = 0; i < in.size(); i++) {
for (int j = 0; j < 10; j++) {
if ((in[i] & v[j])== in[i]) {
ha[i].push_back(j);
}
}
}
dfs(0);
}
int main() {
init();
vector<int> in ({0b1011011, 0b1001111});
d(in);
for (int i = 0; i < res.size(); i++) {
cout << res[i] << endl;
}
return 0;
} 
