数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中寻找名人
假设我们有 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()，它将接收 a、b，
当 graph[a, b] 为真时返回真
从主方法执行以下操作：
定义一个栈 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) 为假，则：
返回 -1
返回 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
更新于: 2020-11-18
122 次浏览
广告