1. Trie
Implement Trie (prefix Tree) LeetCode
var Trie = function() {
this.root = {};
};
/**
* @param {string} word
* @return {void}
*/
Trie.prototype.insert = function(word) {
let node = this.root;
for(let ch of word){
if(!node[ch]){
node[ch] = {};
}
node = node[ch];
}
node.isEnd = true;
};
/**
* @param {string} word
* @return {boolean}
*/
Trie.prototype.search = function(word) {
let node = this.searchNode(word); // here you should not write Trie.searchNodoe()
if(node !== null && node.isEnd == true) return true;
else return false;
};
/**
* @param {string} prefix
* @return {boolean}
*/
Trie.prototype.startsWith = function(prefix) {
let node = this.searchNode(prefix);
if(node !== null) return true;
else return false;
};
Trie.prototype.searchNode = function(word){
let node = this.root;
for(let ch of word){
if(node[ch]){
node = node[ch];
}else return null;
}
return node;
}
/**
* Your Trie object will be instantiated and called as such:
* var obj = new Trie()
* obj.insert(word)
* var param_2 = obj.search(word)
* var param_3 = obj.startsWith(prefix)
*/
class UnionFind {
constructor(grid) {
this.rows = grid.length;
this.cols = grid[0].length;
this.parents = new Array(this.rows * this.cols);
this.size = new Array(this.rows * this.cols);
this.islands = 0;
for (let row = 0; row < this.rows; row++) {
for (let col = 0; col < this.cols; col++) {
if (grid[row][col] === '1') {
const idx = row * this.cols + col;
this.parents[idx] = idx;
this.size[idx] = 1;
this.islands++;
}
}
}
}
unionF(node1, node2) {
const p1 = this.root(node1);
const p2 = this.root(node2);
if (p1 !== p2) {
if (this.size[p1] < this.size[p2]) {
this.parents[p1] = p2;
this.size[p2] += this.size[p1];
} else {
this.parents[p2] = p1;
this.size[p1] += this.size[p2];
}
this.islands--;
}
}
root(node) {
if (node === this.parents[node])
return node;
return this.parents[node] = this.root(this.parents[node]);
}
}
/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function(grid) {
const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
const uf = new UnionFind(grid);
const rows = grid.length;
const cols = grid[0].length;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === '1') {
for (let d = 0; d < 4; d++) {
const x = r + dirs[d][0];
const y = c + dirs[d][1];
if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] === '1') {
const idx1 = r * cols + c;
const idx2 = x * cols + y;
uf.unionF(idx1, idx2);
}
}
}
}
}
return uf.islands;
};
/**
* @param {number[]} nums
*/
var NumArray = function(nums) {
const len = nums.length;
this.segmentTree = new Array(4*len);
this.lastIndex = len - 1;
this.buildSegmentTree(1, 0, this.lastIndex, nums);
};
NumArray.prototype.buildSegmentTree = function(node, start, end, nums){
if(start === end){
// leaf node
this.segmentTree[node] = nums[start];
}else{
let mid = start + Math.floor((end - start)/2);
this.buildSegmentTree(2*node, start, mid, nums);
this.buildSegmentTree(2*node + 1, mid + 1, end, nums);
this.segmentTree[node] = this.segmentTree[2*node] + this.segmentTree[2*node + 1];
}
}
/**
* @param {number} index
* @param {number} val
* @return {void}
*/
NumArray.prototype.update = function(index, val) {
this.updateHelper(1, 0, this.lastIndex, index, val);
};
NumArray.prototype.updateHelper = function(node, start, end, index, val) {
if(start == end){
this.segmentTree[node] = val;
} else{
let mid = start + Math.floor((end - start)/2);
// console.log(mid);
if(start <= index && index <= mid){
this.updateHelper(2*node, start, mid, index, val);
}else{
this.updateHelper(2*node + 1, mid + 1, end, index, val);
}
this.segmentTree[node] = this.segmentTree[2*node] + this.segmentTree[2*node + 1];
}
}
/**
* @param {number} left
* @param {number} right
* @return {number}
*/
NumArray.prototype.sumRange = function(left, right) {
return this.sumRangeHelper(1, 0, this.lastIndex, left, right)
};
NumArray.prototype.sumRangeHelper = function(node, start, end, left, right) {
/**
there are 3 case
1. if start and end is completely outside the left and right range => return 0
2. if start end completly inside my left and right => hence include that node
3. if start and end is partially inside and partially out side // calculate recursively
*/
if(start > right || end < left){
return 0;
}else if(start >= left && end <= right){
return this.segmentTree[node];
}else{
let mid = start + Math.floor((end - start)/2);
let p1 = this.sumRangeHelper(2*node, start, mid, left , right);
let p2 = this.sumRangeHelper(2*node + 1, mid+ 1, end, left, right);
return (p1 + p2);
}
}
/**
* Your NumArray object will be instantiated and called as such:
* var obj = new NumArray(nums)
* obj.update(index,val)
* var param_2 = obj.sumRange(left,right)
*/
/**
* @param {character[][]} grid
* @return {number}
*/
class Solution {
constructor() {
this.dx = [-1, 0, 1, 0];
this.dy = [0, 1, 0, -1];
}
dfs(grid, row, col) {
grid[row][col] = '0';
const rows = grid.length;
const cols = grid[0].length;
for (let i = 0; i < 4; i++) {
const cRow = row + this.dx[i];
const cCol = col + this.dy[i];
if (
cRow < rows && cRow >= 0 &&
cCol < cols && cCol >= 0 &&
grid[cRow][cCol] === '1'
) {
this.dfs(grid, cRow, cCol);
grid[cRow][cCol] = '0';
}
}
}
}
/**
* @param {character[][]} grid
* @return {number}
*/
function numIslands(grid) {
const solution = new Solution();
const rows = grid.length;
if (rows === 0) return 0;
const cols = grid[0].length;
let count = 0;
for (let row = 0; row < rows; row++) {
for (let col = 0; col < cols; col++) {
if (grid[row][col] === '1') {
solution.dfs(grid, row, col);
count++;
}
}
}
return count;
}
/**
* // Definition for a Node.
* function Node(val, left, right, next) {
* this.val = val === undefined ? null : val;
* this.left = left === undefined ? null : left;
* this.right = right === undefined ? null : right;
* this.next = next === undefined ? null : next;
* };
*/
/**
* @param {Node} root
* @return {Node}
*/
var connect = function(root) {
if(!root) return root;
let queue = [];
queue.push(root);
while(queue.length){
let size = queue.length;
let level = [];
for(let i = 0; i < size; i++){
let node = queue.shift();
level.push(node);
if(node.left)
queue.push(node.left);
if(node.right)
queue.push(node.right);
}
connectLevel(level);
}
return root;
};
var connectLevel = function(level){
let pre = level[0];
for(let i = 1; i < level.length; i++){
pre.next = level[i];
pre = level[i];
}
pre.next = null;
}
/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function(nums) {
const len = nums.length;
if(len === 1) return nums[0];
let start = 0, end = len - 1;
/*
int -4, 5
-3/2
*/
(start + end) =
while(start <= end){
// console.log(start, end);
// don't use floor, use round instead
let mid = start + Math.round((end - start)/2);
// use prev and next
let prev = (mid - 1 + len) % len;
let next = (mid + 1) % len;
// console.log(prev, next);
// use [4,5,6,7,0,1,2] to understand first if
if(nums[start] <= nums[end]) return nums[start];
if(nums[mid] <= nums[prev] && nums[mid] <= nums[next]){
return nums[mid];
}else if(nums[start] < nums[mid]){
start = mid + 1;
}else{
end = mid - 1;
}
}
};
7. Sliding Window
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
const len = nums.length;
let start = 0, end = 0, ans = [], list = [];
while(end < len){
// calculation
while(list.length > 0 && list[list.length - 1] < nums[end]){
list.pop();
}
list.push(nums[end]);
// increase the window
if(end - start + 1 < k){
end ++;
}
// hit the window
else{
// calculate the ans
ans.push(list[0]);
if(list[0] === nums[start]){
list.shift();
}
// slide the window
start ++;
end ++;
}
}
return ans;
};
/**
* @param {string} s
* @return {number}
*/
var addValue = function(map, key){
const currentValue = map.get(key) || 0;
map.set(key, currentValue + 1);
}
var removeValue = function(map, key){
const currentValue = map.get(key) || 0;
if(currentValue === 1){
map.delete(key);
} else{
map.set(key, currentValue - 1);
}
}
var lengthOfLongestSubstring = function(s) {
let start = 0, end = 0, maxLen = 0;
let uniqueMap = new Map();
while(end < s.length){
addValue(uniqueMap, s[end]);
// as there is no repeating character so calculate the ans and try to find max length by end ++
if(uniqueMap.size === end - start + 1){
maxLen = Math.max(maxLen, end - start + 1);
// console.log(uniqueMap, maxLen, end - start + 1);
end ++;
}else{
// as there are repeating character so remove the charactor
while(uniqueMap.size < end - start + 1){
removeValue(uniqueMap, s[start++]);
}
end ++;
}
}
return maxLen;
};
/**
* @param {number[]} nums
* @return {number[]}
*/
var nextGreaterElements = function(nums) {
let len = nums.length;
let res = new Array(len);
let stack = [];
for(let i = 2*len -1; i >= 0; i--){
let idx = i % len;
while(stack.length > 0 && (stack[stack.length - 1] <= nums[idx])){
stack.pop();
}
if(i < len){
if(stack.length == 0){
res[idx] = -1;
}else{
res[idx] = stack[stack.length - 1];
}
}
stack.push(nums[idx]);
}
return res;
};
9. Recursion
10. Dynamic Programming
11. Tree
12. Two Pointer
