8000 added tree , js basics and linked list problems · yashkathe/DSA-with-Javascript@2f5cdd4 · GitHub
[go: up one dir, main page]
Skip to content

Commit 2f5cdd4

Browse files
yashkatheyashkathe
committed
added tree , js basics and linked list problems
1 parent 47cadbb commit 2f5cdd4

File tree

7 files changed

+372
-33
lines changed

7 files changed

+372
-33
lines changed

‎B1 LEETCODE-Easy/Trees/invert-binary-tree.js

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
/*
2+
Given the root of a binary tree, invert the tree, and return its root.
3+
4+
5+
6+
Example 1:
7+
8+
Input: root = [4,2,7,1,3,6,9]
9+
Output: [4,7,2,9,6,3,1]
10+
11+
Example 2:
12+
13+
Input: root = [2,1,3]
14+
Output: [2,3,1]
15+
16+
Example 3:
17+
18+
Input: root = []
19+
Output: []
20+
21+
*/
22+
23+
var invertTree = function (root) {
24+
let dfs = (node) => {
25+
if (!node) return;
26+
27+
dfs(node.left);
28+
dfs(node.right);
29+
30+
let temp = node.left;
31+
node.left = node.right;
32+
node.right = temp;
33+
};
34+
35+
dfs(root);
36+
return root;
37+
};

‎B1 LEETCODE-Easy/Trees/max-depth.js

Lines changed: 31 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -21,15 +21,38 @@ Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,1
2121
Output: 5
2222
*/
2323

24-
var maxDepth = function(root) {
24+
var maxDepth = function (root) {
25+
if (!root) return 0;
26+
maximumDepth = 0;
2527

26-
if(!root) return 0;
27-
maximumDepth = 0;
28+
for (let node of root.children) {
29+
maximumDepth = Math.max(maximumDepth, maxDepth(node));
30+
}
2831

29-
for(let node of root.children) {
30-
maximumDepth = Math.max(maximumDepth, maxDepth(node));
31-
}
32+
return maximumDepth + 1;
33+
};
3234

33-
return maximumDepth + 1;
35+
// BFS
3436

35-
};
37+
var maxDepth = function (root) {
38+
if (!root) return 0;
39+
40+
let level = 0;
41+
let queue = [];
42+
queue.push(root);
43+
44+
while (queue.length) {
45+
let levelSize = queue.length; // snapshot of current queue length
46+
47+
for (let i = 0; i < levelSize; i++) {
48+
let node = queue.shift();
49+
50+
if (node.left) queue.push(node.left);
51+
if (node.right) queue.push(node.right);
52+
}
53+
54+
level += 1;
55+
}
56+
57+
return level;
58+
};

‎B1 LEETCODE-Easy/Trees/merge-two-binary-trees.js

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
/*
2+
You are given two binary trees root1 and root2.
3+
4+
Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.
5+
6+
Return the merged tree.
7+
8+
Note: The merging process must start from the root nodes of both trees.
9+
10+
11+
12+
Example 1:
13+
14+
Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
15+
Output: [3,4,5,5,4,null,7]
16+
17+
Example 2:
18+
19+
Input: root1 = [1], root2 = [1,2]
20+
Output: [2,2]
21+
22+
*/
23+
24+
var mergeTrees = function (root1, root2, self) {
25+
let dfs = (t1, t2) => {
26+
if (!t1 && !t2) return null;
27+
28+
let v1 = t1 ? t1.val : 0;
29+
let v2 = t2 ? t2.val : 0;
30+
31+
let self = new TreeNode(v1 + v2);
32+
33+
self.left = dfs(t1 ? t1.left : null, t2 ? t2.left : null);
34+
self.right = dfs(t1 ? t1.right : null, t2 ? t2.right : null);
35+
36+
return self;
37+
};
38+
39+
return dfs(root1, root2);
40+
};

‎B2 LEETCODE-Medium/Concepts/debouncing.js

Lines changed: 111 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,111 @@
1+
/*
2+
Given a function fn and a time in milliseconds t, return a debounced version of that function.
3+
4+
A debounced function is a function whose execution is delayed by t milliseconds and whose execution is cancelled if it is called again within that window of time. The debounced function should also receive the passed parameters.
5+
6+
For example, let's say t = 50ms, and the function was called at 30ms, 60ms, and 100ms. The first 2 function calls would be cancelled, and the 3rd function call would be executed at 150ms. If instead t = 35ms, The 1st call would be cancelled, the 2nd would be executed at 95ms, and the 3rd would be executed at 135ms.
7+
8+
Debounce Schematic
9+
10+
The above diagram shows how debounce will transform events. Each rectangle represents 100ms and the debounce time is 400ms. Each color represents a different set of inputs.
11+
12+
Please solve it without using lodash's _.debounce() function.
13+
14+
15+
16+
Example 1:
17+
18+
Input:
19+
t = 50
20+
calls = [
21+
{"t": 50, inputs: [1]},
22+
{"t": 75, inputs: [2]}
23+
]
24+
Output: [{"t": 125, inputs: [2]}]
25+
Explanation:
26+
let start = Date.now();
27+
function log(...inputs) {
28+
console.log([Date.now() - start, inputs ])
29+
}
30+
const dlog = debounce(log, 50);
31+
setTimeout(() => dlog(1), 50);
32+
setTimeout(() => dlog(2), 75);
33+
34+
The 1st call is cancelled by the 2nd call because the 2nd call occurred before 100ms
35+
The 2nd call is delayed by 50ms and executed at 125ms. The inputs were (2).
36+
37+
Example 2:
38+
39+
Input:
40+
t = 20
41+
calls = [
42+
{"t": 50, inputs: [1]},
43+
{"t": 100, inputs: [2]}
44+
]
45+
Output: [{"t": 70, inputs: [1]}, {"t": 120, inputs: [2]}]
46+
Explanation:
47+
The 1st call is delayed until 70ms. The inputs were (1).
48+
The 2nd call is delayed until 120ms. The inputs were (2).
49+
50+
Example 3:
51+
52+
Input:
53+
t = 150
54+
calls = [
55+
{"t": 50, inputs: [1, 2]},
56+
{"t": 300, inputs: [3, 4]},
57+
{"t": 300, inputs: [5, 6]}
58+
]
59+
Output: [{"t": 200, inputs: [1,2]}, {"t": 450, inputs: [5, 6]}]
60+
Explanation:
61+
The 1st call is delayed by 150ms and ran at 200ms. The inputs were (1, 2).
62+
The 2nd call is cancelled by the 3rd call
63+
The 3rd call is delayed by 150ms and ran at 450ms. The inputs were (5, 6).
64+
65+
*/
66+
67+
var debounce = function (fn, t) {
68+
let timer;
69+
return function (...args) {
70+
clearTimeout(timer);
71+
timer = setTimeout(() => fn(...args), t);
72+
};
73+
};
74+
75+
/*
76+
Why to use Debouncing?
77+
78+
Have you ever encountered a situation where a function gets called multiple times within a short amount of time, leading to performance issues or unexpected behavior?
79+
This is a common problem in JavaScript, especially when working with events like scrolling, resizing, or typing.
80+
81+
Fortunately, there's a simple technique called "debouncing" that can help you control the frequency of function calls and avoid these issues.
82+
What is Debouncing?
83+
84+
Debouncing is a method that limits the rate at which a function gets called.
85+
It works by delaying the execution of a function until a certain amount of time has passed without any additional function calls.
86+
If another function call happens within this time frame, the timer resets and the function execution is delayed again.
87+
88+
Debouncing is useful in situations where you want to prevent a function from being called too frequently, such as:
89+
90+
Handling user input events like keypresses, mouse movements, or button clicks
91+
92+
Handling expensive computations or network requests that don't need to be performed on every function call
93+
94+
95+
Intuition and Approach
96+
97+
debounce takes two arguments: fn and t.
98+
fn is the function that you want to debounce.
99+
t is the amount of time you want to wait before executing fn after the last time it was called.
100+
The debounce function returns a new function that takes any number of arguments (...args).
101+
Within the returned function, a timer is set using setTimeout. The timer is initially set to t milliseconds.
102+
Every time the returned function is called, the clearTimeout function is called to reset the timer to t milliseconds.
103+
Once the timer has elapsed without the returned function being called again, the timer's callback function is executed.
104+
The callback function calls fn with the arguments that were passed to the returned function.
105+
The debounce function returns the new function that was created in step 2.
106+
107+
In simpler terms, the debounce function creates a new function that can only be executed after a certain amount of time has passed without it being called again.
108+
This is achieved by creating a timer that is reset every time the debounced function is called.
109+
Once the timer has elapsed without the debounced function being called again, the function is executed.
110+
This is useful when you want to limit the frequency of some expensive operation, such as making an HTTP request or rendering a large number of elements on a page.
111+
*/

‎B2 LEETCODE-Medium/Linked List/sum-of-nodes.js

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
/*
2+
2. Add Two Numbers
3+
Solved
4+
Medium
5+
Topics
6+
Companies
7+
8+
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
9+
10+
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
11+
12+
13+
14+
Example 1:
15+
16+
Input: l1 = [2,4,3], l2 = [5,6,4]
17+
Output: [7,0,8]
18+
Explanation: 342 + 465 = 807.
19+
20+
Example 2:
21+
22+
Input: l1 = [0], l2 = [0]
23+
Output: [0]
24+
25+
Example 3:
26+
27+
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
28+
Output: [8,9,9,9,0,0,0,1]
29+
30+
*/
31+
32+
var addTwoNumbers = function (l1, l2) {
33+
function hasTensPlace(number) {
34+
return number >= 10;
35+
}
36+
37+
function getUnitsPlace(number) {
38+
return number % 10;
39+
}
40+
41+
let dummyNode = new ListNode(-1);
42+
let ans = dummyNode;
43+
44+
let carry = 0;
45+
46+
while (l1 || l2 || carry) {
47+
let sum = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + carry;
48+
49+
carry = hasTensPlace(sum) ? 1 : 0;
50+
51+
ans.next = new ListNode(getUnitsPlace(sum));
52+
ans = ans.next;
53+
if (l1) l1 = l1.next;
54+
if (l2) l2 = l2.next;
55+
}
56+
57+
return dummyNode.next;
58+
};

‎B2 LEETCODE-Medium/Trees/Good-Node.js

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
/*
2+
Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.
3+
4+
Return the number of good nodes in the binary tree.
5+
6+
7+
8+
Example 1:
9+
10+
Input: root = [3,1,4,3,null,1,5]
11+
Output: 4
12+
Explanation: Nodes in blue are good.
13+
Root Node (3) is always a good node.
14+
Node 4 -> (3,4) is the maximum value in the path starting from the root.
15+
Node 5 -> (3,4,5) is the maximum value in the path
16+
Node 3 -> (3,1,3) is the maximum value in the path.
17+
18+
Example 2:
19+
20+
Input: root = [3,3,null,4,2]
21+
Output: 3
22+
Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.
23+
24+
Example 3:
25+
26+
Input: root = [1]
27+
Output: 1
28+
Explanation: Root is considered as good.
29+
30+
31+
32+
Constraints:
33+
34+
The number of nodes in the binary tree is in the range [1, 10^5].
35+
Each node's value is between [-10^4, 10^4].
36+
37+
*/
38+
39+
var goodNodes = function(root) {
40+
41+
let count = 0
42+
43+
const dfs = (node, maxVal) => {
44+
45+
if(!node)
46+
return 0
47+
48+
if(node.val >= maxVal)
49+
count += 1
50+
51+
dfs(node.left, Math.max(maxVal , node.val))
52+
dfs(node.right, Math.max(maxVal , node.val))
53+
54+
}
55+
56+
dfs(root, root.val)
57+
58+
return count
59+
60+
};

0 commit comments

Comments
 (0)
0