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

Commite88994f

Browse files
authored
Merge branch 'TheAlgorithms:master' into master
2 parentsaa5f9db +8c27d86 commite88994f

31 files changed

+764
-21
lines changed

‎.github/workflows/Ci.yml

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,7 @@ jobs:
1212
runs-on:ubuntu-latest
1313
steps:
1414
-uses:actions/checkout@v3
15+
1516
-uses:actions/setup-node@v3
1617
with:
1718
node-version:16
@@ -20,8 +21,13 @@ jobs:
2021
-name:📦 Install dependencies
2122
run:npm ci
2223

23-
-name:🧪 Run tests
24-
run:npm test
24+
-name:🧪 Run all tests
25+
if:${{ github.event_name == 'push' }}
26+
run:npm run test
27+
28+
-name:🧪 Run tests for changed files only
29+
if:${{ github.event_name == 'pull_request' }}
30+
run:npm run test-changed
2531

2632
-name:💄 Code style
2733
run:npm run style

‎.gitpod.yml

Lines changed: 9 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,11 @@
1+
github:
2+
prebuilds:
3+
addBadge:true
4+
addComment:false
5+
addCheck:false
6+
master:true
7+
branches:true
8+
pullRequestsFromForks:true
9+
110
tasks:
211
-init:npm install
3-

‎.husky/pre-commit

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,4 +2,4 @@
22
."$(dirname"$0")/_/husky.sh"
33

44
npm run style
5-
npm runtest
5+
npm run test-changed

‎CONTRIBUTING.md

Lines changed: 9 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -63,15 +63,16 @@ should add unique value.
6363

6464
####Module System
6565

66-
We use the[ES Module](https://hacks.mozilla.org/2018/03/es-modules-a-cartoon-deep-dive/) system, which bring an official, standardized module system to JavaScript.
66+
We use the[ES Module](https://hacks.mozilla.org/2018/03/es-modules-a-cartoon-deep-dive/) system, which bring an
67+
official, standardized module system to JavaScript.
6768

6869
It roughly means you will need to use`export` and`import` statements instead of`module.exports` and`require()`.
6970

7071
####Testing
7172

7273
Be confident that your code works. When was the last time you committed a code change, your build failed, and half of
7374
your app stopped working? Mine was last week. Writing tests for our Algorithms will help us ensure the implementations
74-
areair tight even after multiple fixes and code changes.
75+
areairtight even after multiple fixes and code changes.
7576

7677
We use[Jest](https://jestjs.io/) to run unit tests on our algorithms. It provides a very readable and expressive way to
7778
structure your test code.
@@ -107,6 +108,12 @@ You can also start Jest in "watch" mode:
107108
npmtest -- --watchAll
108109
```
109110

111+
We also prepared a helper script that runs tests only for changed files:
112+
113+
```shell
114+
npm run test-changed
115+
```
116+
110117
This will run all tests and watch source and test files for changes. When a change is made, the tests will run again.
111118

112119
####Coding Style

‎DIRECTORY.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -89,6 +89,7 @@
8989
*[ClimbingStairs](Dynamic-Programming/ClimbingStairs.js)
9090
*[CoinChange](Dynamic-Programming/CoinChange.js)
9191
*[EditDistance](Dynamic-Programming/EditDistance.js)
92+
*[FastFibonacciNumber](Dynamic-Programming/FastFibonacciNumber.js)
9293
*[FibonacciNumber](Dynamic-Programming/FibonacciNumber.js)
9394
*[FindMonthCalendar](Dynamic-Programming/FindMonthCalendar.js)
9495
*[KadaneAlgo](Dynamic-Programming/KadaneAlgo.js)
@@ -104,6 +105,7 @@
104105
*[RodCutting](Dynamic-Programming/RodCutting.js)
105106
*[Shuf](Dynamic-Programming/Shuf.js)
106107
*[SieveOfEratosthenes](Dynamic-Programming/SieveOfEratosthenes.js)
108+
*[UniquePaths](Dynamic-Programming/UniquePaths.js)
107109
***Sliding-Window**
108110
*[LongestSubstringWithoutRepeatingCharacters](Dynamic-Programming/Sliding-Window/LongestSubstringWithoutRepeatingCharacters.js)
109111
*[PermutationinString](Dynamic-Programming/Sliding-Window/PermutationinString.js)
@@ -240,6 +242,7 @@
240242
*[Problem020](Project-Euler/Problem020.js)
241243
*[Problem023](Project-Euler/Problem023.js)
242244
*[Problem025](Project-Euler/Problem025.js)
245+
*[Problem028](Project-Euler/Problem028.js)
243246
*[Problem044](Project-Euler/Problem044.js)
244247
***Recursive**
245248
*[BinaryEquivalent](Recursive/BinaryEquivalent.js)
@@ -249,6 +252,7 @@
249252
*[FibonacciNumberRecursive](Recursive/FibonacciNumberRecursive.js)
250253
*[FloodFill](Recursive/FloodFill.js)
251254
*[KochSnowflake](Recursive/KochSnowflake.js)
255+
*[LetterCombination](Recursive/LetterCombination.js)
252256
*[Palindrome](Recursive/Palindrome.js)
253257
*[SubsequenceRecursive](Recursive/SubsequenceRecursive.js)
254258
*[TowerOfHanoi](Recursive/TowerOfHanoi.js)

‎Data-Structures/Array/Reverse.js

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
/** https://www.geeksforgeeks.org/write-a-program-to-Reverse-an-array-or-string/
2+
* This function will accept an array and
3+
* Reverse its elements and returns the inverted array
4+
*@param {Array} arr array with elements of any data type
5+
*@returns {Array} array with inverted elements
6+
*/
7+
8+
constReverse=(arr)=>{
9+
// limit specifies the amount of Reverse actions
10+
for(leti=0,j=arr.length-1;i<arr.length/2;i++,j--){
11+
consttemp=arr[i]
12+
arr[i]=arr[j]
13+
arr[j]=temp
14+
}
15+
returnarr
16+
}
17+
export{Reverse}
Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
import{Reverse}from'../Reverse.js'
2+
importeachfrom'jest-each'
3+
4+
describe('reverse elements in an array',()=>{
5+
each`
6+
array | expected
7+
${[]} |${[]}
8+
${[1]} |${[1]}
9+
${[1,2,3,4]} |${[4,3,2,1]}
10+
`.test('returns $expected when given $array',({ array, expected})=>{
11+
expect(Reverse(array)).toEqual(expected)
12+
})
13+
})

‎Data-Structures/Tree/SegmentTree.js

Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
/**
2+
* Segment Tree
3+
* concept : [Wikipedia](https://en.wikipedia.org/wiki/Segment_tree)
4+
* inspired by : https://www.geeksforgeeks.org/segment-tree-efficient-implementation/
5+
*
6+
* time complexity
7+
* - init : O(N)
8+
* - update : O(log(N))
9+
* - query : O(log(N))
10+
*
11+
* space complexity : O(N)
12+
*/
13+
classSegmentTree{
14+
size
15+
tree
16+
constructor(arr){
17+
// we define tree like this
18+
// tree[1] : root node of tree
19+
// tree[i] : i'th node
20+
// tree[i * 2] : i'th left child
21+
// tree[i * 2 + 1] : i'th right child
22+
// and we use bit, shift operation for index
23+
this.size=arr.length
24+
this.tree=newArray(2*arr.length)
25+
this.tree.fill(0)
26+
27+
this.build(arr)
28+
}
29+
30+
// function to build the tree
31+
build(arr){
32+
const{ size, tree}=this
33+
// insert leaf nodes in tree
34+
// leaf nodes will start from index N
35+
// in this array and will go up to index (2 * N – 1)
36+
for(leti=0;i<size;i++){
37+
tree[size+i]=arr[i]
38+
}
39+
40+
// build the tree by calculating parents
41+
// tree's root node will contain all leaf node's sum
42+
for(leti=size-1;i>0;--i){
43+
// current node's value is the sum of left child, right child
44+
tree[i]=tree[i*2]+tree[i*2+1]
45+
}
46+
}
47+
48+
update(index,value){
49+
const{ size, tree}=this
50+
51+
// only update values in the parents of the given node being changed.
52+
// to get the parent move to parent node (index / 2)
53+
54+
// set value at position index
55+
index+=size
56+
// tree[index] is leaf node and index's value of array
57+
tree[index]=value
58+
59+
// move upward and update parents
60+
for(leti=index;i>1;i>>=1){
61+
// i ^ 1 turns (2 * i) to (2 * i + 1)
62+
// i ^ 1 is second child
63+
tree[i>>1]=tree[i]+tree[i^1]
64+
}
65+
}
66+
67+
// interval [L,R) with left index(L) included and right (R) excluded.
68+
query(left,right){
69+
const{ size, tree}=this
70+
// cause R is excluded, increase right for convenient
71+
right++
72+
letres=0
73+
74+
// loop to find the sum in the range
75+
for(left+=size,right+=size;left<right;left>>=1,right>>=1){
76+
// L is the left border of an query interval
77+
78+
// if L is odd it means that it is the right child of its parent and our interval includes only L and not the parent.
79+
// So we will simply include this node to sum and move to the parent of its next node by doing L = (L + 1) / 2.
80+
81+
// if L is even it is the left child of its parent
82+
// and the interval includes its parent also unless the right borders interfere.
83+
if((left&1)>0){
84+
res+=tree[left++]
85+
}
86+
87+
// same in R (the right border of an query interval)
88+
if((right&1)>0){
89+
res+=tree[--right]
90+
}
91+
}
92+
93+
returnres
94+
}
95+
}
96+
97+
export{SegmentTree}
Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
import{SegmentTree}from'../SegmentTree'
2+
3+
describe('SegmentTree sum test',()=>{
4+
consta=[1,2,3,4,5,6,7,8,9,10,11,12]
5+
6+
constsegment=newSegmentTree(a)
7+
8+
it('init sum check',()=>{
9+
expect(segment.query(0,2)).toBe(6)
10+
})
11+
12+
it('init sum check',()=>{
13+
segment.update(2,1)
14+
expect(segment.query(0,2)).toBe(4)
15+
})
16+
})

‎Dynamic-Programming/UniquePaths.js

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
2+
/*
3+
*
4+
* Unique Paths
5+
*
6+
* There is a robot on an `m x n` grid.
7+
* The robot is initially located at the top-left corner.
8+
* The robot tries to move to the bottom-right corner.
9+
* The robot can only move either down or right at any point in time.
10+
*
11+
* Given the two integers `m` and `n`,
12+
* return the number of possible unique paths that the robot can take to reach the bottom-right corner.
13+
* More info: https://leetcode.com/problems/unique-paths/
14+
*/
15+
16+
/*
17+
*@param {number} m
18+
*@param {number} n
19+
*@return {number}
20+
*/
21+
22+
constuniquePaths=(m,n)=>{
23+
// only one way to reach end
24+
if(m===1||n===1)return1
25+
26+
// build a linear grid of size m
27+
// base case, position 1 has only 1 move
28+
constpaths=newArray(m).fill(1)
29+
30+
for(leti=1;i<n;i++){
31+
for(letj=1;j<m;j++){
32+
// paths[j] in RHS represents the cell value stored above the current cell
33+
// paths[j-1] in RHS represents the cell value stored to the left of the current cell
34+
// paths [j] on the LHS represents the number of distinct pathways to the cell (i,j)
35+
paths[j]=paths[j-1]+paths[j]
36+
}
37+
}
38+
returnpaths[m-1]
39+
}
40+
41+
export{uniquePaths}
Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
import{uniquePaths}from'../UniquePaths'
2+
3+
describe('Unique Paths',()=>{
4+
it('should return 28 when m is 3 and n is 7',()=>{
5+
expect(uniquePaths(3,7)).toBe(28)
6+
})
7+
8+
it('should return 48620 when m is 10 and n is 10',()=>{
9+
expect(uniquePaths(10,10)).toBe(48620)
10+
})
11+
})

0 commit comments

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