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

Commitba6645a

Browse files
committed
refactor(longestSubSeq): add cmp and change name
1 parentb21b5e5 commitba6645a

File tree

2 files changed

+24
-15
lines changed

2 files changed

+24
-15
lines changed

‎src/searching/longest-increasing-subsequence.jsrenamed to‎src/searching/longest-subsequence.js

Lines changed: 12 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -10,19 +10,15 @@
1010
*@private
1111
*@param {Array} array The array in which the largest
1212
* element should be found.
13-
*@param {Function} cmp Function used for comparison.
1413
*@return {Number} index of the first largest element
1514
*/
16-
functionmax(array,cmp){
15+
functionmax(array){
1716
if(!array||!array.length){
1817
return-1;
1918
}
20-
if(!cmp){
21-
cmp=function(a,b){returna-b;};
22-
}
2319
varmaxIdx=0;
2420
for(vari=1;i<array.length;i+=1){
25-
if(cmp(array[maxIdx],array[i])<0){
21+
if(array[maxIdx].distance<array[i].distance){
2622
maxIdx=i;
2723
}
2824
}
@@ -33,8 +29,8 @@
3329
* Default comparison method.
3430
*@private
3531
*/
36-
functioncmp(a,b){
37-
returna.distance-b.distance;
32+
functionasc(a,b){
33+
returna-b;
3834
}
3935

4036
/**
@@ -46,12 +42,12 @@
4642
*@param {Array} array The input array.
4743
*@return {Object} Graph represented with list of neighbours.
4844
*/
49-
functionbuildDag(array){
45+
functionbuildDag(array,cmp){
5046
varresult=[];
5147
for(vari=0;i<array.length;i+=1){
5248
result[i]=[];
5349
for(varj=i+1;j<array.length;j+=1){
54-
if(array[i]<array[j]){
50+
if(cmp(array[i],array[j])<0){
5551
result[i].push(j);
5652
}
5753
}
@@ -87,7 +83,7 @@
8783
neighboursDistance[i]=find(dag,neighbours[i]);
8884
}
8985

90-
maxDist=max(neighboursDistance,cmp);
86+
maxDist=max(neighboursDistance);
9187
maxNode=neighbours[maxDist];
9288
distance=1+neighboursDistance[maxDist].distance;
9389
find.memo[node]=result={
@@ -114,15 +110,16 @@
114110
*@param {Array} array Input sequence.
115111
*@return {Array} Longest increasing subsequence.
116112
*/
117-
returnfunction(array){
113+
returnfunction(array,cmp){
114+
cmp=cmp||asc;
118115
varresults=[];
119-
vardag=buildDag(array);
116+
vardag=buildDag(array,cmp);
120117
varmaxPath;
121118
find.memo=[];
122119
for(vari=0;i<array.length;i+=1){
123120
results.push(find(dag,i));
124121
}
125-
maxPath=results[max(results,cmp)];
122+
maxPath=results[max(results)];
126123
results=[];
127124
while(maxPath){
128125
results.push(array[maxPath.node]);
@@ -133,3 +130,4 @@
133130
})();
134131

135132
})(typeofwindow==='undefined' ?module.exports :window);
133+

‎test/searching/longest-increasing-subsequence.spec.jsrenamed to‎test/searching/longest-subsequence.spec.js

Lines changed: 12 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22

33
varlongestSubsequence=
44
require('../../src/searching/'+
5-
'longest-increasing-subsequence')
5+
'longest-subsequence')
66
.longestSubsequence;
77

88
describe('longest subsequence',function(){
@@ -33,4 +33,15 @@ describe('longest subsequence', function () {
3333
expect(longestSubsequence(sequence).toString())
3434
.toBe([2,3,6,9,11].toString());
3535
});
36+
37+
it('should work with a custom comparator',function(){
38+
varcmp=function(a,b){
39+
returnb-a;
40+
};
41+
varseq=[1,2,-1];
42+
varresult=longestSubsequence(seq,cmp);
43+
expect(result.length).toBe(2);
44+
expect(result).toEqual([1,-1]);
45+
});
3646
});
47+

0 commit comments

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