用 C++ 查找名人
c++server side programmingprogramming更新于 2025/4/10 1:52:17
假设我们有 n 个人(从 0 到 n - 1 标记)，其中可能存在一位名人。当其他 n - 1 个人都认识 x，但 x 不认识其中任何人时，我们可以说 x 是名人。在这里，我们必须找出名人是谁，或者验证没有名人。
我们只能向"A"问一个问题，即"嗨，A。你认识 B 吗?"，以获取 A 是否认识 B 的信息。我们必须问最少的问题才能找出名人。有一个列表列表作为输入，称为图，当第 i 个人认识第 j 个人时，graph[i,j] = 1，否则为 0。
因此，如果输入类似 graph = [[1,1,0],[0,1,0],[1,1,1]],
然后输出将为 1，因为名人是标记为 1 的人，因为 0 和 2 都认识他，但 1 不认识任何人。
为了解决这个问题，我们将遵循以下步骤 −
定义一个函数 knows()，这将需要一个， b,
当 graph[a, b] 为真时返回 true
从主方法执行以下操作 −
定义一个堆栈 st
初始化 i := 0，当 i < n 时，更新(将 i 增加 1)，执行 −
将 i 插入 st
当 st 的大小 > 1，执行 −
x := st 的顶部元素
从 st 中删除元素
y := st 的顶部元素
从 st 中删除元素
如果 knows(x, y) 为真，则执行 −
将 y 插入 st
否则
将 x 插入 st
x := st 的顶部元素
初始化 i := 0，当 i < n 时，更新(将 i 增加 1)，执行 −
如果 i 与 x 相同，则 −
忽略以下部分，跳至下一次迭代
如果 knows(x, i) 为真或 knows(i, x) 为假，则 −
return -1
return x
示例
让我们看下面的实现，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
vector<vector<int<> graph;
public:
Solution(vector<vector<int<> &graph){
this->graph = graph;
}
bool knows(int a, int b){
return graph[a][b];
}
int findCelebrity(int n) {
stack<int< st;
for (int i = 0; i < n; i++) {
st.push(i);
}
while (st.size() > 1) {
int x = st.top();
st.pop();
int y = st.top();
st.pop();
if (knows(x, y)) {
st.push(y);
}
else {
st.push(x);
}
}
int x = st.top();
for (int i = 0; i < n; i++) {
if (i == x)
continue;
if (knows(x, i) || !knows(i, x)) {
return -1;
}
}
return x;
}
};
main(){
vector<vector<int<> v = {{1,1,0},{0,1,0},{1,1,1}};
Solution ob(v);
cout << (ob.findCelebrity(3));
}
输入
{{1,1,0},{0,1,0},{1,1,1}}
3
输出
1
