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

Commitf08fa91

Browse files
committed
add more solutions
1 parent893650b commitf08fa91

6 files changed

+281
-37
lines changed

‎173 Binary Search Tree Iterator.js

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,18 @@
1+
// Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
2+
3+
// Calling next() will return the next smallest number in the BST.
4+
5+
// Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
6+
7+
// Credits:
8+
// Special thanks to@ts for adding this problem and creating all test cases.
9+
10+
// Hide Company Tags LinkedIn Google Facebook Microsoft
11+
// Hide Tags Tree Stack Design
12+
// Hide Similar Problems (M) Binary Tree Inorder Traversal (M) Flatten 2D Vector (M) Zigzag Iterator (M) Peeking Iterator (M) Inorder Successor in BST
13+
14+
15+
116
/**
217
* Definition for binary tree
318
* function TreeNode(val) {

‎209 Minimum Size Subarray Sum.js

Lines changed: 42 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,30 +1,58 @@
11
// http://blog.csdn.net/lisonglisonglisong/article/details/45666975
2+
// http://www.cnblogs.com/grandyang/p/4501934.html
3+
4+
// Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.
5+
6+
// For example, given the array [2,3,1,2,4,3] and s = 7,
7+
// the subarray [4,3] has the minimal length under the problem constraint.
8+
9+
// click to show more practice.
10+
11+
// Credits:
12+
// Special thanks to@Freezen for adding this problem and creating all test cases.
13+
14+
// Hide Company Tags Facebook
15+
// Hide Tags Array Two Pointers Binary Search
16+
// Hide Similar Problems (H) Minimum Window Substring (M) Maximum Size Subarray Sum Equals k
17+
218

319
/**
420
*@param {number} s
521
*@param {number[]} nums
622
*@return {number}
723
*/
24+
25+
// O(n) solution
826
varminSubArrayLen=function(s,nums){
927
varsum=0;
1028
varleft=0;
11-
varright=-1;
12-
varlen=nums.length;
29+
varright=0;
1330
varminLen=Infinity;
1431

15-
while(right<len){
16-
while(right<len&&sum<s){
17-
sum+=nums[++right];
18-
}
19-
if(sum>=s){
20-
minLen=Math.min(right-left+1,minLen);
21-
sum-=nums[left];
22-
left++;
32+
while(right<nums.length){
33+
while(right<nums.length&&sum<s){
34+
sum+=nums[right++];
2335
}
2436

37+
while(sum>=s){
38+
minLen=Math.min(minLen,right-left);
39+
sum-=nums[left++];
40+
}
2541
}
2642

27-
28-
29-
returnminLen>len ?0 :minLen;
30-
};
43+
returnminLen>nums.length ?0 :minLen;
44+
};
45+
46+
// The O(NlogN) solution is to sum up the array
47+
// [1,2,3,4,5] becomes [1,3,6,10,15]
48+
// then iterate through array from index 0 to nums.length - 1
49+
// for each value in the summed array
50+
// binary search values after that index so the difference becomes greater than s
51+
// example
52+
// s = 8
53+
// at index 0 with value 1 look between [3,6,10,15] using binary search.
54+
// we can find that at value 10 the difference is 10 - 1 = 9 the minLen is index 3 - 1 + 1 = 3
55+
// then we check index 1 with value 3 and binary search [6,10,15] we can find that at value 15 we have difference 15 - 3 = 12
56+
// the distance is index 4 - 1 + 1 = 4
57+
58+
// console.log(minSubArrayLen(11, [1,2,3,4,5]));

‎282 Expression Add Operators.js

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
// Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.
2+
3+
// Examples:
4+
// "123", 6 -> ["1+2+3", "1*2*3"]
5+
// "232", 8 -> ["2*3+2", "2+3*2"]
6+
// "105", 5 -> ["1*0+5","10-5"]
7+
// "00", 0 -> ["0+0", "0-0", "0*0"]
8+
// "3456237490", 9191 -> []
9+
// Credits:
10+
// Special thanks to@davidtan1890 for adding this problem and creating all test cases.
11+
12+
// Hide Company Tags Google Facebook
13+
// Hide Tags Divide and Conquer
14+
// Hide Similar Problems (M) Evaluate Reverse Polish Notation (H) Basic Calculator (M) Basic Calculator II (M) Different Ways to Add Parentheses
15+
16+
17+
// reference: http://blog.csdn.net/pointbreak1/article/details/48596115
18+
19+
varaddOperators=function(num,target){
20+
functionopRecur(num,target,lastOp,result,expression,results){
21+
if(num.length===0){
22+
if(target===result){
23+
results.push(expression);
24+
}
25+
return;
26+
}
27+
28+
for(vari=1;i<=num.length;i++){
29+
varcurr=num.substring(0,i);
30+
if(curr.length>1&&curr[0]==='0'){
31+
continue;
32+
}
33+
34+
varrest=num.substring(i);
35+
varcurrVal=parseInt(curr);
36+
37+
if(expression.length===0){
38+
opRecur(rest,target,currVal,currVal,expression+curr,results);
39+
}else{
40+
opRecur(rest,target,currVal,result+currVal,expression+"+"+curr,results);
41+
opRecur(rest,target,-currVal,result-currVal,expression+"-"+curr,results);
42+
opRecur(rest,target,currVal*lastOp,result-lastOp+lastOp*currVal,expression+"*"+curr,results);
43+
}
44+
}
45+
}
46+
47+
varresults=[];
48+
opRecur(num,target,0,0,'',results);
49+
returnresults;
50+
};
51+
52+
console.log(addOperators('01023',3));

‎311 Sparse Matrix Multiplication.js

Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
// Given two sparse matrices A and B, return the result of AB.
2+
3+
// You may assume that A's column number is equal to B's row number.
4+
5+
// Example:
6+
7+
// A = [
8+
// [ 1, 0, 0],
9+
// [-1, 0, 3]
10+
// ]
11+
12+
// B = [
13+
// [ 7, 0, 0 ],
14+
// [ 0, 0, 0 ],
15+
// [ 0, 0, 1 ]
16+
// ]
17+
18+
19+
// | 1 0 0 | | 7 0 0 | | 7 0 0 |
20+
// AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
21+
// | 0 0 1 |
22+
// Hide Company Tags LinkedIn Facebook
23+
// Hide Tags Hash Table
24+
25+
26+
/**
27+
*@param {number[][]} A
28+
*@param {number[][]} B
29+
*@return {number[][]}
30+
*/
31+
32+
// normal matrix mulitplication
33+
// slower version
34+
varmultiply=function(A,B){
35+
varresult=[];
36+
37+
varrowA=A.length;
38+
varcolA=A[0].length;
39+
varrowB=B.length;
40+
varcolB=B[0].length
41+
42+
for(vari=0;i<rowA;i++){
43+
result.push(Array(colB).fill(0));
44+
45+
for(varj=0;j<colB;j++){
46+
47+
for(vark=0;k<colA;k++){
48+
result[i][j]+=A[i][k]*B[k][j]
49+
}
50+
51+
}
52+
}
53+
54+
returnresult;
55+
};
56+
57+
// faster
58+
// skip
59+
multiply=function(A,B){
60+
varresult=[];
61+
vari,j,k;
62+
63+
varrowA=A.length;
64+
varcolA=A[0].length;
65+
varcolB=B[0].length
66+
67+
for(vari=0;i<rowA;i++){
68+
result.push(Array(colB).fill(0));
69+
}
70+
71+
for(i=0;i<rowA;i++){
72+
for(k=0;k<colA;k++){
73+
if(A[i][k]!==0){
74+
for(j=0;j<colB;j++){
75+
if(B[k][j]!==0){
76+
result[i][j]+=A[i][k]*B[k][j];
77+
}
78+
}
79+
}
80+
}
81+
}
82+
83+
returnresult;
84+
};
85+
86+
87+
88+
// var data1 = [[0,1],[0,0],[0,1]];
89+
// var data2 = [[1,0],[1,0]];
90+
91+
// var data1 = [[1,0,0],[-1,0,3]];
92+
// var data2 = [[7,0,0],[0,0,0],[0,0,1]];
93+
94+
vardata1=[[1,-5]];
95+
vardata2=[[12],[-1]];
96+
97+
console.log(multiply(data1,data2));
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
// Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.
2+
3+
// Example 1:
4+
// Given nums = [1, -1, 5, -2, 3], k = 3,
5+
// return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)
6+
7+
// Example 2:
8+
// Given nums = [-2, -1, 2, 1], k = 1,
9+
// return 2. (because the subarray [-1, 2] sums to 1 and is the longest)
10+
11+
// Follow Up:
12+
// Can you do it in O(n) time?
13+
14+
// Hide Company Tags Palantir Facebook
15+
// Hide Tags Hash Table
16+
// Hide Similar Problems (M) Minimum Size Subarray Sum (E) Range Sum Query - Immutable
17+
18+
19+
/**
20+
*@param {number[]} nums
21+
*@param {number} k
22+
*@return {number}
23+
*/
24+
varmaxSubArrayLen=function(nums,k){
25+
varmaxLen=0;
26+
varcurrSum=0;
27+
vardict={0:-1};
28+
29+
for(vari=0;i<nums.length;i++){
30+
currSum+=nums[i];
31+
32+
// since we are looking for the maxlen, dict is used to store the very first
33+
// location where currSum occurred
34+
if(dict[currSum]===undefined){
35+
dict[currSum]=i;
36+
}
37+
38+
if(dict[currSum-k]!==undefined){
39+
maxLen=Math.max(maxLen,i-dict[currSum-k]);
40+
}
41+
}
42+
43+
returnmaxLen;
44+
};

‎43 Multiply Strings.js

Lines changed: 31 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -1,44 +1,52 @@
1+
// Given two numbers represented as strings, return multiplication of the numbers as a string.
2+
3+
// Note:
4+
// The numbers can be arbitrarily large and are non-negative.
5+
// Converting the input string to integer is NOT allowed.
6+
// You should NOT use internal library such as BigInteger.
7+
// Hide Company Tags Facebook Twitter
8+
// Hide Tags Math String
9+
// Hide Similar Problems (M) Add Two Numbers (E) Plus One (E) Add Binary
10+
111
/**
212
*@param {string} num1
313
*@param {string} num2
414
*@return {string}
515
*/
616
varmultiply=function(num1,num2){
7-
if(num1===null||num2===null||num1.length===0||num2.length===0){
8-
return0;
17+
if(num1===null||num2===null||num1.length===0||num2.length===0||num1==='0'||num2==='0'){
18+
return'0';
919
}
1020

1121
vararr1=num1.split('').reverse();
1222
vararr2=num2.split('').reverse();
13-
1423
varresult=[];
1524

16-
for(vari=0;i<arr1.length;i++){
25+
for(vari=0;i<arr1.length;i++){
1726
varcarry=0;
27+
varval1=parseInt(arr1[i]);
1828

19-
for(varj=0;j<arr2.length;j++){
20-
varn1=parseInt(arr1[i]);
21-
varn2=parseInt(arr2[j]);
22-
varexist=parseInt(result[i+j]||0);
23-
vartotal=n1*n2+carry+exist;
24-
25-
varremain=total%10+'';
26-
carry=parseInt(total/10);
27-
result[i+j]=remain;
29+
for(varj=0;j<arr2.length;j++){
30+
varval2=parseInt(arr2[j]);
31+
varproduct=val1*val2+carry;
32+
varexist=result[i+j]||0;
33+
varsum=product+exist;
34+
vardigit=sum%10;
35+
carry=Math.floor(sum/10);
36+
result[i+j]=digit;
2837
}
2938

30-
if(carry>0){
31-
result[i+j]=carry+'';
39+
if(carry>0){
40+
result[i+j]=carry;
3241
}
3342
}
3443

35-
result=result.reverse();
44+
result.reverse();
3645
result=result.join('');
37-
result=result.replace(/^0+/g,'');
46+
result=result.replace(/^0+/,'');
3847

39-
if(result.length===0){
40-
return"0";
41-
}else{
42-
returnresult;
43-
}
44-
};
48+
49+
returnresult;
50+
};
51+
52+
multiply('123','456')

0 commit comments

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