Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitbbf5af3

Browse files
committed
add more solutions
1 parent6a85535 commitbbf5af3

9 files changed

+486
-0
lines changed

‎243 Shortest Word Distance.js

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
// Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
2+
3+
// For example,
4+
// Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
5+
6+
// Given word1 = “coding”, word2 = “practice”, return 3.
7+
// Given word1 = "makes", word2 = "coding", return 1.
8+
9+
// Note:
10+
// You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
11+
12+
// Hide Company Tags LinkedIn
13+
// Hide Tags
14+
15+
16+
varshortestDistance=function(words,word1,word2){
17+
varidx1=-1;
18+
varidx2=-1;
19+
vardist=words.length-1;
20+
21+
for(vari=0;i<words.length;i++){
22+
if(words[i]===word1){
23+
idx1=i;
24+
}elseif(words[i]===word2){
25+
idx2=i;
26+
}
27+
28+
if(idx1!==-1&&idx2!==-1){
29+
dist=Math.min(dist,Math.abs(idx1-idx2))
30+
}
31+
}
32+
33+
returndist;
34+
};

‎244 Shortest Word Distance II.js

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
// This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?
2+
3+
// Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.
4+
5+
// For example,
6+
// Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
7+
8+
// Given word1 = “coding”, word2 = “practice”, return 3.
9+
// Given word1 = "makes", word2 = "coding", return 1.
10+
11+
// Note:
12+
// You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
13+
14+
// Hide Company Tags LinkedIn
15+
// Hide Tags Hash Table Design
16+
// Show Similar Problems
17+
18+
19+
/**
20+
*@constructor
21+
*@param {string[]} words
22+
*/
23+
varWordDistance=function(words){
24+
this.positions={};
25+
26+
for(vari=0;i<words.length;i++){
27+
varword=words[i];
28+
29+
this.positions[word]=this.positions[word]||[];
30+
this.positions[word].push(i);
31+
}
32+
};
33+
34+
/**
35+
*@param {string} word1
36+
*@param {string} word2
37+
*@return {integer}
38+
*/
39+
WordDistance.prototype.shortest=function(word1,word2){
40+
vari=0;
41+
varj=0;
42+
vardist=Infinity;
43+
varpos1=this.positions[word1];
44+
varpos2=this.positions[word2];
45+
46+
while(i<pos1.length&&j<pos2.length){
47+
vari1=pos1[i];
48+
vari2=pos2[j];
49+
50+
dist=Math.min(dist,Math.abs(i1-i2));
51+
52+
if(i1<i2){
53+
i++;
54+
}else{
55+
j++;
56+
}
57+
}
58+
59+
returndist;
60+
};
61+
62+
/**
63+
* Your WordDistance object will be instantiated and called as such:
64+
* var wordDistance = new WordDistance(words);
65+
* wordDistance.shortest("word1", "word2");
66+
* wordDistance.shortest("anotherWord1", "anotherWord2");
67+
*/

‎245 Shortest Word Distance III.js

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
// This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.
2+
3+
// Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
4+
5+
// word1 and word2 may be the same and they represent two individual words in the list.
6+
7+
// For example,
8+
// Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
9+
10+
// Given word1 = “makes”, word2 = “coding”, return 1.
11+
// Given word1 = "makes", word2 = "makes", return 3.
12+
13+
// Note:
14+
// You may assume word1 and word2 are both in the list.
15+
16+
// Hide Company Tags LinkedIn
17+
// Hide Tags Array
18+
// Hide Similar Problems
19+
20+
21+
/**
22+
*@param {string[]} words
23+
*@param {string} word1
24+
*@param {string} word2
25+
*@return {number}
26+
*/
27+
varshortestWordDistance=function(words,word1,word2){
28+
varidx1=-1;
29+
varidx2=-1;
30+
vardist=words.length-1;
31+
32+
for(vari=0;i<words.length;i++){
33+
if(words[i]===word1){
34+
if(words[idx1]===word1&&word1===word2){
35+
idx2=idx1;
36+
}
37+
38+
idx1=i;
39+
}elseif(words[i]===word2){
40+
idx2=i;
41+
}
42+
43+
if(idx1!==-1&&idx2!==-1){
44+
dist=Math.min(dist,Math.abs(idx1-idx2))
45+
}
46+
}
47+
48+
returndist;
49+
};

‎277 Find the Celebrity.js

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
// Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them.
2+
3+
// Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?" to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).
4+
5+
// You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.
6+
7+
// Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity's label if there is a celebrity in the party. If there is no celebrity, return -1.
8+
9+
// Hide Company Tags LinkedIn Facebook
10+
// Show Tags
11+
12+
13+
14+
/**
15+
* Definition for knows()
16+
*
17+
*@param {integer} person a
18+
*@param {integer} person b
19+
*@return {boolean} whether a knows b
20+
* knows = function(a, b) {
21+
* ...
22+
* };
23+
*/
24+
25+
/**
26+
*@param {function} knows()
27+
*@return {function}
28+
*/
29+
varsolution=function(knows){
30+
/**
31+
*@param {integer} n Total people
32+
*@return {integer} The celebrity
33+
*/
34+
returnfunction(n){
35+
varcandidate=0;
36+
37+
// iterate through the list,
38+
// if candidate is known by i -> continue
39+
// if i doesnt know candidate, i becomes the candidate
40+
for(vari=1;i<n;i++){
41+
if(!knows(i,candidate)){
42+
candidate=i;
43+
}
44+
}
45+
46+
for(i=0;i<n;i++){
47+
if(i===candidate){
48+
continue;
49+
}
50+
51+
// if candidate is not known by i or candidate know i
52+
if(!knows(i,candidate)||knows(candidate,i)){
53+
return-1;
54+
}
55+
}
56+
57+
returncandidate;
58+
};
59+
};

‎339 Nested List Weight Sum.js

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
// Given a nested list of integers, return the sum of all integers in the list weighted by their depth.
2+
3+
// Each element is either an integer, or a list -- whose elements may also be integers or other lists.
4+
5+
// Example 1:
6+
// Given the list [[1,1],2,[1,1]], return 10. (four 1's at depth 2, one 2 at depth 1)
7+
8+
// Example 2:
9+
// Given the list [1,[4,[6]]], return 27. (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 4*2 + 6*3 = 27)
10+
11+
// Hide Company Tags LinkedIn
12+
// Show Tags
13+
// Show Similar Problems
14+
15+
16+
/**
17+
* // This is the interface that allows for creating nested lists.
18+
* // You should not implement it, or speculate about its implementation
19+
* function NestedInteger() {
20+
*
21+
* Return true if this NestedInteger holds a single integer, rather than a nested list.
22+
*@return {boolean}
23+
* this.isInteger = function() {
24+
* ...
25+
* };
26+
*
27+
* Return the single integer that this NestedInteger holds, if it holds a single integer
28+
* Return null if this NestedInteger holds a nested list
29+
*@return {integer}
30+
* this.getInteger = function() {
31+
* ...
32+
* };
33+
*
34+
* Return the nested list that this NestedInteger holds, if it holds a nested list
35+
* Return null if this NestedInteger holds a single integer
36+
*@return {NestedInteger[]}
37+
* this.getList = function() {
38+
* ...
39+
* };
40+
* };
41+
*/
42+
/**
43+
*@param {NestedInteger[]} nestedList
44+
*@return {number}
45+
*/
46+
47+
vardepthSum=function(nestedList){
48+
49+
functiontraverse(arr,lvl){
50+
varsum=0;
51+
52+
for(vari=0;i<arr.length;i++){
53+
if(arr[i].isInteger()){
54+
sum+=arr[i].getInteger()*lvl;
55+
}else{
56+
sum+=traverse(arr[i].getList(),lvl+1);
57+
}
58+
}
59+
60+
returnsum;
61+
}
62+
63+
returntraverse(nestedList,1);
64+
};

‎364 Nested List Weight Sum II.js

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
// Given a nested list of integers, return the sum of all integers in the list weighted by their depth.
2+
3+
// Each element is either an integer, or a list -- whose elements may also be integers or other lists.
4+
5+
// Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.
6+
7+
// Example 1:
8+
// Given the list [[1,1],2,[1,1]], return 8. (four 1's at depth 1, one 2 at depth 2)
9+
10+
// Example 2:
11+
// Given the list [1,[4,[6]]], return 17. (one 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 1*3 + 4*2 + 6*1 = 17)
12+
13+
// Hide Company Tags LinkedIn
14+
// Show Tags
15+
// Show Similar Problems
16+
17+
/**
18+
* // This is the interface that allows for creating nested lists.
19+
* // You should not implement it, or speculate about its implementation
20+
* function NestedInteger() {
21+
*
22+
* Return true if this NestedInteger holds a single integer, rather than a nested list.
23+
*@return {boolean}
24+
* this.isInteger = function() {
25+
* ...
26+
* };
27+
*
28+
* Return the single integer that this NestedInteger holds, if it holds a single integer
29+
* Return null if this NestedInteger holds a nested list
30+
*@return {integer}
31+
* this.getInteger = function() {
32+
* ...
33+
* };
34+
*
35+
* Return the nested list that this NestedInteger holds, if it holds a nested list
36+
* Return null if this NestedInteger holds a single integer
37+
*@return {NestedInteger[]}
38+
* this.getList = function() {
39+
* ...
40+
* };
41+
* };
42+
*/
43+
/**
44+
*@param {NestedInteger[]} nestedList
45+
*@return {number}
46+
*/
47+
vardepthSumInverse=function(nestedList){
48+
49+
functiongetDepth(arr,lvl){
50+
varmaxDepth=lvl;
51+
52+
for(vari=0;i<arr.length;i++){
53+
if(!arr[i].isInteger()){
54+
// maxDepth represents the max depth at that level,
55+
// e.g. [[[[55]]],[[31]],[99],[],75]
56+
// at lvl 1, we want to know which [[[55]]], [[31]], [99], [], 75
57+
// has the maxDepth
58+
maxDepth=Math.max(maxDepth,getDepth(arr[i].getList(),lvl+1));
59+
}
60+
}
61+
62+
returnmaxDepth;
63+
}
64+
65+
vardepth=getDepth(nestedList,1);
66+
67+
functiontraverse(arr,lvl){
68+
varsum=0;
69+
70+
for(vari=0;i<arr.length;i++){
71+
if(arr[i].isInteger()){
72+
sum+=arr[i].getInteger()*lvl;
73+
}else{
74+
sum+=traverse(arr[i].getList(),lvl-1);
75+
}
76+
}
77+
78+
returnsum;
79+
}
80+
81+
returntraverse(nestedList,depth);
82+
};

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp