Skip to content

Commit ab7c381

Browse files
jianminchenjianminchen
committed
check in source code
1 parent ccbd9b6 commit ab7c381

9 files changed

+795
-0
lines changed

‎2017 May - 2018 May 42 Algorithms Submission/Leetcode 277 Celebrity Two Loops - Linear algorithm Practice II.cs

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Linq;
4+
using System.Text;
5+
using System.Threading.Tasks;
6+
7+
namespace Leetcode277_FindCelebrity
8+
{
9+
/* Leetcode 277: find celebrity
10+
*
11+
* Suppose you are at a party with n people (labeled from 0 to n - 1) and among them,
12+
* there may exist one celebrity. The definition of a celebrity is that all the other
13+
* n - 1 people know him/her but he/she does not know any of them.
14+
15+
Now you want to find out who the celebrity is or verify that there is not one. The
16+
* only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?"
17+
* to get information of whether A knows B. You need to find out the celebrity (or
18+
* verify there is not one) by asking as few questions as possible (in the asymptotic
19+
* sense).
20+
21+
You are given a helper function bool knows(a, b) which tells you whether A knows B.
22+
* Implement a function int findCelebrity(n), your function should minimize the number
23+
* of calls to knows.
24+
25+
Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity's
26+
* label if there is a celebrity in the party. If there is no celebrity, return -1.
27+
*
28+
* source code is based on
29+
* http://www.cnblogs.com/grandyang/p/5310649.html
30+
*/
31+
class Program
32+
{
33+
static void Main(string[] args)
34+
{
35+
var celebrity = FindCelebrity(100);
36+
}
37+
38+
/// <summary>
39+
/// my job is to find O(N) solution, N is number of candidates
40+
/// </summary>
41+
/// <param name="n"></param>
42+
/// <returns></returns>
43+
public static int FindCelebrity(int n)
44+
{
45+
if (n <= 0)
46+
{
47+
return -1;
48+
}
49+
50+
for (int i = 0, j = 0; i < n; ++i)
51+
{
52+
for (j = 0; j < n; ++j)
53+
{
54+
if (i != j && (knows(i, j) || !knows(j, i))) break;
55+
}
56+
57+
if (j == n) return i;
58+
}
59+
60+
return -1;
61+
}
62+
63+
/// <summary>
64+
/// assume that there are more than 10 people, and make 10th people as a celebrity.
65+
/// </summary>
66+
/// <param name="a"></param>
67+
/// <param name="b"></param>
68+
/// <returns></returns>
69+
private static bool knows(int a, int b)
70+
{
71+
if (a == b)
72+
return true;
73+
74+
if (a == 10)
75+
return false;
76+
77+
return true; // false
78+
}
79+
}
80+
}

‎2017 May - 2018 May 42 Algorithms Submission/Leetcode 277 Celebrity Two Loops - Linear algorithm Practice III.cs

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Linq;
4+
using System.Text;
5+
using System.Threading.Tasks;
6+
7+
namespace Leetcode277_FindCelebrity
8+
{
9+
/* Leetcode 277: find celebrity
10+
*
11+
* Suppose you are at a party with n people (labeled from 0 to n - 1) and among them,
12+
* there may exist one celebrity. The definition of a celebrity is that all the other
13+
* n - 1 people know him/her but he/she does not know any of them.
14+
15+
Now you want to find out who the celebrity is or verify that there is not one. The
16+
* only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?"
17+
* to get information of whether A knows B. You need to find out the celebrity (or
18+
* verify there is not one) by asking as few questions as possible (in the asymptotic
19+
* sense).
20+
21+
You are given a helper function bool knows(a, b) which tells you whether A knows B.
22+
* Implement a function int findCelebrity(n), your function should minimize the number
23+
* of calls to knows.
24+
25+
Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity's
26+
* label if there is a celebrity in the party. If there is no celebrity, return -1.
27+
*
28+
* source code is based on
29+
* http://www.cnblogs.com/grandyang/p/5310649.html
30+
*/
31+
class Program
32+
{
33+
static void Main(string[] args)
34+
{
35+
var celebrity = FindCelebrity(100);
36+
}
37+
38+
/// <summary>
39+
/// my job is to find O(N) solution, N is number of candidates
40+
/// </summary>
41+
/// <param name="n"></param>
42+
/// <returns></returns>
43+
public static int FindCelebrity(int n)
44+
{
45+
if (n <= 0)
46+
{
47+
return -1;
48+
}
49+
50+
// find the candidate first
51+
int candidate = 0;
52+
for (int i = 0; i < n; ++i)
53+
{
54+
if (candidate != i && knows(candidate, i))
55+
{
56+
candidate = i;
57+
}
58+
}
59+
60+
// verify candidate is the celebrity
61+
for (int i = 0; i < n; ++i)
62+
{
63+
if (candidate != i && (knows(candidate, i) || !knows(i, candidate)))
64+
{
65+
return -1;
66+
}
67+
}
68+
69+
return candidate;
70+
}
71+
72+
/// <summary>
73+
/// assume that there are more than 10 people, and make 10th people as a celebrity.
74+
/// </summary>
75+
/// <param name="a"></param>
76+
/// <param name="b"></param>
77+
/// <returns></returns>
78+
private static bool knows(int a, int b)
79+
{
80+
if (a == b)
81+
return true;
82+
83+
if (a == 10)
84+
return false;
85+
86+
return true; // false
87+
}
88+
}
89+
}

‎2017 May - 2018 May 42 Algorithms Submission/Leetcode 277 Celebrity Two Loops - Linear algorithm.cs

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Linq;
4+
using System.Text;
5+
using System.Threading.Tasks;
6+
7+
namespace Leetcode277_FindCelebrity
8+
{
9+
/* Leetcode 277: find celebrity
10+
*
11+
* Suppose you are at a party with n people (labeled from 0 to n - 1) and among them,
12+
* there may exist one celebrity. The definition of a celebrity is that all the other
13+
* n - 1 people know him/her but he/she does not know any of them.
14+
15+
Now you want to find out who the celebrity is or verify that there is not one. The
16+
* only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?"
17+
* to get information of whether A knows B. You need to find out the celebrity (or
18+
* verify there is not one) by asking as few questions as possible (in the asymptotic
19+
* sense).
20+
21+
You are given a helper function bool knows(a, b) which tells you whether A knows B.
22+
* Implement a function int findCelebrity(n), your function should minimize the number
23+
* of calls to knows.
24+
25+
Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity's
26+
* label if there is a celebrity in the party. If there is no celebrity, return -1.
27+
*
28+
* source code is based on
29+
* http://www.cnblogs.com/grandyang/p/5310649.html
30+
*/
31+
class Program
32+
{
33+
static void Main(string[] args)
34+
{
35+
var celebrity = FindCelebrity(100);
36+
}
37+
38+
/// <summary>
39+
/// my job is to find O(N) solution, N is number of candidates
40+
/// </summary>
41+
/// <param name="n"></param>
42+
/// <returns></returns>
43+
public static int FindCelebrity(int n)
44+
{
45+
if (n <= 0)
46+
return -1;
47+
48+
var candidates = new bool[n];
49+
for (int i = 0; i < n; i++)
50+
candidates[i] = true;
51+
52+
for (int i = 0; i < n; ++i)
53+
{
54+
for (int j = 0; j < n; ++j)
55+
{
56+
if (candidates[i] && i != j)
57+
{
58+
if (knows(i, j) || !knows(j, i)) // i knows j, or j does not know i
59+
{
60+
candidates[i] = false;
61+
break;
62+
}
63+
else
64+
{
65+
candidates[j] = false;
66+
}
67+
}
68+
}
69+
70+
if (candidates[i])
71+
{
72+
return i;
73+
}
74+
}
75+
76+
return -1;
77+
}
78+
79+
/// <summary>
80+
/// assume that there are more than 10 people, and make 10th people as a celebrity.
81+
/// </summary>
82+
/// <param name="a"></param>
83+
/// <param name="b"></param>
84+
/// <returns></returns>
85+
private static bool knows(int a, int b)
86+
{
87+
if (a == b)
88+
return true;
89+
90+
if (a == 10)
91+
return false;
92+
93+
return true; // false
94+
}
95+
}
96+
}

‎By Algorithms/Leetcode 277 Find celebrity/Leetcode 277 Celebrity Two Loops - Linear algorithm Practice II.cs

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Linq;
4+
using System.Text;
5+
using System.Threading.Tasks;
6+
7+
namespace Leetcode277_FindCelebrity
8+
{
9+
/* Leetcode 277: find celebrity
10+
*
11+
* Suppose you are at a party with n people (labeled from 0 to n - 1) and among them,
12+
* there may exist one celebrity. The definition of a celebrity is that all the other
13+
* n - 1 people know him/her but he/she does not know any of them.
14+
15+
Now you want to find out who the celebrity is or verify that there is not one. The
16+
* only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?"
17+
* to get information of whether A knows B. You need to find out the celebrity (or
18+
* verify there is not one) by asking as few questions as possible (in the asymptotic
19+
* sense).
20+
21+
You are given a helper function bool knows(a, b) which tells you whether A knows B.
22+
* Implement a function int findCelebrity(n), your function should minimize the number
23+
* of calls to knows.
24+
25+
Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity's
26+
* label if there is a celebrity in the party. If there is no celebrity, return -1.
27+
*
28+
* source code is based on
29+
* http://www.cnblogs.com/grandyang/p/5310649.html
30+
*/
31+
class Program
32+
{
33+
static void Main(string[] args)
34+
{
35+
var celebrity = FindCelebrity(100);
36+
}
37+
38+
/// <summary>
39+
/// my job is to find O(N) solution, N is number of candidates
40+
/// </summary>
41+
/// <param name="n"></param>
42+
/// <returns></returns>
43+
public static int FindCelebrity(int n)
44+
{
45+
if (n <= 0)
46+
{
47+
return -1;
48+
}
49+
50+
for (int i = 0, j = 0; i < n; ++i)
51+
{
52+
for (j = 0; j < n; ++j)
53+
{
54+
if (i != j && (knows(i, j) || !knows(j, i))) break;
55+
}
56+
57+
if (j == n) return i;
58+
}
59+
60+
return -1;
61+
}
62+
63+
/// <summary>
64+
/// assume that there are more than 10 people, and make 10th people as a celebrity.
65+
/// </summary>
66+
/// <param name="a"></param>
67+
/// <param name="b"></param>
68+
/// <returns></returns>
69+
private static bool knows(int a, int b)
70+
{
71+
if (a == b)
72+
return true;
73+
74+
if (a == 10)
75+
return false;
76+
77+
return true; // false
78+
}
79+
}
80+
}

0 commit comments

Comments
 (0)