Commit365ec1c

committed

add a solution for 277

1 parentc87ddd7 commit365ec1cCopy full SHA for 365ec1c

File tree

+11

-0

lines changed

+11

-0

lines changed

Lines changed: 11 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -3,10 +3,21 @@`
`3`	`3`	`publicclass_277 {`
`4`	`4`
`5`	`5`	`publicstaticclassSolution1 {`
	`6`	`+/**`
	`7`	`+ * Credit: https://leetcode.com/problems/find-the-celebrity/solution/ approach 2`
	`8`	`+ * 1. we narrow down the possible celebrity candidate to only one person`
	`9`	`+ * 2. we check to make sure that every other person knows`
	`10`	`+ * this candidate and this candidate doesn't know any one of them, otherwise return -1`
	`11`	`+ *`
	`12`	`+ * We can think of this is a directed graph problem, a total of n vertices, the one vertex that has zero outgoing edges`
	`13`	`+ * and n - 1 incoming edges is the celebrity.`
	`14`	`+ */`
`6`	`15`	`publicintfindCelebrity(intn) {`
`7`	`16`	`intcandidate =0;`
`8`	`17`	`for (inti =1;i <n;i++) {`
`9`	`18`	`if (knows(candidate,i)) {`
	`19`	`+//this rules out the possibility that candidiate is a celebrity since he/she knows i`
	`20`	`+//so we update candidate to be i, because at least i doesn't know anybody yet.`
`10`	`21`	`candidate =i;`
`11`	`22`	`}`
`12`	`23`	`}`

Comments

(0)