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

Commit9148989

Browse files
committed
add more solutions
1 parentdf69de6 commit9148989

File tree

53 files changed

+1891
-225
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

53 files changed

+1891
-225
lines changed
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
// Say you have an array for which the ith element is the price of a given stock on day i.
2+
3+
// Design an algorithm to find the maximum profit. You may complete at most two transactions.
4+
5+
// Note:
6+
// You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
7+
8+
// http://www.cnblogs.com/springfor/p/3877068.html
9+
10+
/**
11+
*@param {number[]} prices
12+
*@return {number}
13+
*/
14+
varmaxProfit=function(prices){
15+
// Calculate MaxProfit from 0 to x and MaxProfit from x + 1 to len - 1;
16+
varprofitFromZeroToX=[];
17+
varprofitFromXToEnd=[];
18+
varmin=prices[0];
19+
20+
// get max profit from 0 to x
21+
for(varx=1;x<prices.length;x++){
22+
varprice=prices[x];
23+
min=Math.min(price,min);
24+
profitFromZeroToX[x]=Math.max(profitFromZeroToX[x-1]||0,price-min);
25+
}
26+
// get max profit from i + 1 to end
27+
varmax=prices[prices.length-1];
28+
for(x=prices.length-2;x>=0;x--){
29+
price=prices[x];
30+
max=Math.max(price,max);
31+
profitFromXToEnd[x]=Math.max(profitFromXToEnd[x+1]||0,max-price);
32+
}
33+
34+
varmaxProfit=0;
35+
for(x=0;x<prices.length;x++){
36+
varmaxProfitSeperateAtX=(profitFromZeroToX[x]||0)+(profitFromXToEnd[x]||0);
37+
maxProfit=Math.max(maxProfitSeperateAtX,maxProfit);
38+
}
39+
40+
returnmaxProfit;
41+
};

‎126 Word Ladder II.js

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
// Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
2+
3+
// Only one letter can be changed at a time
4+
// Each intermediate word must exist in the word list
5+
// For example,
6+
7+
// Given:
8+
// beginWord = "hit"
9+
// endWord = "cog"
10+
// wordList = ["hot","dot","dog","lot","log"]
11+
// Return
12+
// [
13+
// ["hit","hot","dot","dog","cog"],
14+
// ["hit","hot","lot","log","cog"]
15+
// ]
16+
// Note:
17+
// All words have the same length.
18+
// All words contain only lowercase alphabetic characters.
19+
20+
/**
21+
*@param {string} beginWord
22+
*@param {string} endWord
23+
*@param {Set} wordList
24+
* Note: wordList is a Set object, see:
25+
* https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set
26+
*@return {string[][]}
27+
*/
28+
varfindLadders=function(beginWord,endWord,wordList){
29+
30+
};

‎127 Word Ladder.js

Lines changed: 50 additions & 39 deletions
Original file line numberDiff line numberDiff line change
@@ -1,57 +1,68 @@
1+
// Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
2+
3+
// Only one letter can be changed at a time
4+
// Each intermediate word must exist in the word list
5+
// For example,
6+
7+
// Given:
8+
// beginWord = "hit"
9+
// endWord = "cog"
10+
// wordList = ["hot","dot","dog","lot","log"]
11+
// As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
12+
// return its length 5.
13+
14+
// Note:
15+
// Return 0 if there is no such transformation sequence.
16+
// All words have the same length.
17+
// All words contain only lowercase alphabetic characters.
18+
// Amazon LinkedIn Snapchat Facebook Yelp
19+
20+
121
// Leetcode 127
222
// Language: Javascript
323
// Problem: https://leetcode.com/problems/word-ladder/
424
// Author: Chihung Yu
25+
526
/**
627
*@param {string} beginWord
728
*@param {string} endWord
8-
*@param {set<string>} wordDict
29+
*@param {Set} wordList
30+
* Note: wordList is a Set object, see:
31+
* https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set
932
*@return {number}
1033
*/
11-
12-
String.prototype.replaceAt=function(i,c){
13-
returnthis.substring(0,i)+c+this.substring(i+1);
14-
};
15-
16-
varladderLength=function(beginWord,endWord,wordDict){
17-
if(beginWord===null||endWord===null||beginWord.length!==endWord.length||beginWord.length===0||endWord.length===0){
18-
return0;
19-
}
20-
21-
varqueue=[];
22-
queue.push(beginWord);
34+
varladderLength=function(beginWord,endWord,wordList){
2335
varvisited=newSet();
24-
visited.add(beginWord);
25-
36+
varqueue=[];
2637
varlevel=1;
27-
varcurLvlCnt=1;
28-
varnextLvlCnt=0;
38+
varletters='abcdefghijklmnopqrstuvwxyz';
39+
queue.push(beginWord);
40+
visited.add(beginWord);
2941

30-
while(queue.length!==0){
31-
varcur=queue.shift();
32-
curLvlCnt--;
42+
while(queue.length>0){
3343

34-
for(vari=0;i<cur.length;i++){
35-
for(varj=0;j<26;j++){
36-
varchar=String.fromCharCode('a'.charCodeAt(0)+j);
37-
varword=cur.replaceAt(i,char);
38-
39-
if(word===endWord){
40-
returnlevel+1;
41-
}
42-
if(wordDict.has(word)&&!visited.has(word)){
43-
nextLvlCnt++;
44-
queue.push(word);
45-
visited.add(word);
44+
varlen=queue.length;
45+
46+
for(vari=0;i<len;i++){
47+
varword=queue.shift();
48+
49+
for(varj=0;j<word.length;j++){
50+
for(vark=0;k<letters.length;k++){
51+
varnewWord=word.substring(0,j)+letters[k]+word.substring(j+1);
52+
53+
if(newWord===endWord){
54+
returnlevel+1;
55+
}
56+
if(wordList.has(newWord)&&!visited.has(newWord)){
57+
queue.push(newWord);
58+
visited.add(newWord);
59+
}
4660
}
4761
}
4862
}
49-
if(curLvlCnt===0){
50-
curLvlCnt=nextLvlCnt;
51-
nextLvlCnt=0;
52-
level++;
53-
}
63+
64+
level++;
5465
}
66+
5567
return0;
56-
};
57-
68+
};

‎133 Clone Graph.js

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,26 @@
1+
// Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
2+
3+
4+
// OJ's undirected graph serialization:
5+
// Nodes are labeled uniquely.
6+
7+
// We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
8+
// As an example, consider the serialized graph {0,1,2#1,2#2,2}.
9+
10+
// The graph has a total of three nodes, and therefore contains three parts as separated by #.
11+
12+
// First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
13+
// Second node is labeled as 1. Connect node 1 to node 2.
14+
// Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
15+
// Visually, the graph looks like the following:
16+
17+
// 1
18+
// / \
19+
// / \
20+
// 0 --- 2
21+
// / \
22+
// \_/
23+
124
/**
225
* Definition for undirected graph.
326
* function UndirectedGraphNode(label) {

‎138 Copy List With Random Pointer.js

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
// A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
2+
3+
// Return a deep copy of the list.
4+
5+
// Hide Company Tags Amazon Microsoft Bloomberg Uber
6+
// Show Tags
7+
// Show Similar Problems
8+
9+
10+
/**
11+
* Definition for singly-linked list with a random pointer.
12+
* function RandomListNode(label) {
13+
* this.label = label;
14+
* this.next = this.random = null;
15+
* }
16+
*/
17+
18+
/**
19+
*@param {RandomListNode} head
20+
*@return {RandomListNode}
21+
*/
22+
varcopyRandomList=function(head){
23+
varhashMap={};
24+
varnewHead=newRandomListNode(0);
25+
newHead.next=copyList(head);
26+
27+
functioncopyList(node){
28+
if(node===null){
29+
returnnode;
30+
}
31+
32+
if(hashMap[node.label]){
33+
returnhashMap[node.label];
34+
}
35+
36+
varnewNode=newRandomListNode(node.label);
37+
hashMap[node.label]=newNode;
38+
39+
newNode.next=copyList(node.next);
40+
newNode.random=copyList(node.random);
41+
42+
returnnewNode;
43+
}
44+
45+
returnnewHead.next;
46+
};

‎146 LRU Cache.js

Lines changed: 6 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,3 @@
1-
// Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
2-
3-
// get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
4-
// set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
51
classNode{
62
constructor(key,val){
73
this.key=key;
@@ -18,7 +14,7 @@ var LRUCache = function(capacity) {
1814
this.map=newMap();
1915
this.head=null;
2016
this.tail=null;
21-
this.size=capacity;
17+
this.capacity=capacity;
2218
this.curSize=0;
2319
};
2420

@@ -27,12 +23,11 @@ var LRUCache = function(capacity) {
2723
*@returns {number}
2824
*/
2925
LRUCache.prototype.get=function(key){
30-
if(!this.map.get(key)){
26+
letnode=this.map.get(key);
27+
if(!node){
3128
return-1;
3229
}
3330

34-
letnode=this.map.get(key);
35-
3631
if(node===this.head){
3732
returnnode.val;
3833
}
@@ -70,7 +65,7 @@ LRUCache.prototype.set = function(key, value) {
7065
}
7166

7267
this.head=newNode;
73-
this.curSize++;
68+
//this.curSize++;
7469

7570
// update
7671
if(this.map.get(key)){
@@ -84,11 +79,9 @@ LRUCache.prototype.set = function(key, value) {
8479
oldNode.prev.next=oldNode.next;
8580
oldNode.next.prev=oldNode.prev;
8681
}
87-
88-
this.curSize--;
89-
9082
}else{
91-
if(this.curSize>this.size){
83+
this.curSize++
84+
if(this.curSize>this.capacity){
9285
//delete tail
9386
this.map.delete(this.tail.key);
9487
this.tail=this.tail.prev;

‎148 Sort List.js

Lines changed: 9 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,5 @@
1+
// Sort a linked list in O(n log n) time using constant space complexity.
2+
13
/**
24
* Definition for singly-linked list.
35
* function ListNode(val) {
@@ -28,13 +30,18 @@ var sortList = function(head) {
2830
returnnewHead;
2931

3032
functionsort(len){
33+
// there will be no case of len = 0 which is caused by 1/2
3134
if(len===1){
3235
vartemp=head;
33-
head=head.next;
36+
// !!! important: moving pointer to the next
37+
// e.g. 1->2->3->4
38+
// head-> 1
39+
// now head will be point to 2
40+
head=head.next;
3441
temp.next=null;
3542
returntemp;
3643
}
37-
44+
// there will be no case of len = 0 which is caused by 1/2
3845
varleftHead=sort(parseInt(len/2));
3946
varrightHead=sort(len-parseInt(len/2));
4047
varnewHead=merge(leftHead,rightHead);

‎186 Reverse Words in a String II.js

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
// Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.
2+
3+
// The input string does not contain leading or trailing spaces and the words are always separated by a single space.
4+
5+
// For example,
6+
// Given s = "the sky is blue",
7+
// return "blue is sky the".
8+
9+
// Could you do it in-place without allocating extra space?
10+
11+
/**
12+
*@param {character[]} str
13+
*@return {void} Do not return anything, modify the string in-place instead.
14+
*/
15+
varreverseWords=function(str){
16+
vararr=str;
17+
18+
reverse(arr,0,arr.length-1);
19+
varlast=0;
20+
21+
for(vari=0;i<=arr.length;i++){
22+
if(arr[i]===' '||i===arr.length){
23+
reverse(arr,last,i-1);
24+
last=i+1;
25+
}
26+
}
27+
28+
functionreverse(arr,beg,end){
29+
while(beg<end){
30+
vartmp=str[beg];
31+
str[beg]=str[end];
32+
str[end]=tmp;
33+
beg++;
34+
end--;
35+
}
36+
}
37+
};

0 commit comments

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