Neetcode 150問ロードマップに挑戦する

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.

Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

function twoSum(nums: number[], target: number): number[] {
    let output: Map<number, number> = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (output.has(complement)) {
            return [output.get(complement), i];
        }
        output.set(nums[i], i);
    }
    return []
}

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[]}
     */
    twoSum(nums, target) {
        const map = new Map();

        for (let index = 0; index < nums.length; index++) {
            const num = nums[index];
            const complement = target - num;
            const sumIndex = map.get(complement);

            const isTarget = map.has(complement);
            if (isTarget) {
                return [index, sumIndex];
            }

            map.set(num, index);
        }

        return [-1, -1];
    }
}

function groupAnagrams(strs) {
    const anagrams = {};
    for (let str of strs) {
        const key = str.split('').sort().join('');
        if (!anagrams[key]) {
            anagrams[key] = [];
        }
        // Append the original string to the array corresponding to the sorted key
        anagrams[key].push(str);
    }
    return Object.values(anagrams);
}

        const ans = {};
        for (const s of strs) {
            const count = Array(26).fill(0);
            for (const c of s) {
                count[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
            }
            const key = count.join('#');
            if (!ans[key]) {
                ans[key] = [];
            }

            ans[key].push(s);
        }
        return Object.values(ans);
    }

    topKFrequent(nums, k) {
        const anagrams = {};
        const counts = []
        for (let num of nums) {
            const key = `key-${num}`
        if (!anagrams[key]) {
            anagrams[key] = [];
        }
        anagrams[key].push(num);
        }
        Object.values(anagrams).sort((a,b) => b.length - a.length).forEach((array, i) => {
            if(i + 1 <= k) {
                counts.push(array[0])
                }
            })
        return counts

class Solution {
    /**
     * @param {string[]} strs
     * @returns {string}
     */
     encode(strs) {
        let result = '';
        for (let s of strs) {
            result += ${s.length}#${s};
        }
        return result;
    }

    /**
     * @param {string} str
     * @returns {string[]}
     */
    decode(str) {
        let result = [];
        let i = 0;

        while (i < str.length) {
            let j = i;
            while (str[j] !== '#') {
                j++;
            }
            let length = parseInt(str.substring(i, j), 10);
            i = j + 1;
            j = i + length;
            result.push(str.substring(i, j));
            i = j;
        }
        return result;
    }

    productExceptSelf(nums) {
        let allExceptNums = []
        for (let i = 0; i < nums.length; i++) {
            let initialValue =   1
            nums.map((v, index) => {
                if(i ===  index) return 
                initialValue *= v
            })
            if(Number.isInteger(initialValue) && initialValue >= -2147483648 && initialValue <= 2147483647) {
                allExceptNums.push(initialValue)
            }
        }
        return allExceptNums
    }

    isValidSudoku(board) {
        for (let i = 0; i < board.length; i++) {
            const pickedRow = new Set()
            const pickedColumn = new Set()
            const squares = new Set()

            for (let j = 0; j < board.length; j++) {
            // Row
            const NoCommaRo = board[i].filter((d) => d !== '.')
            if(pickedRow.has(NoCommaRo)) return false
            pickedRow.add(NoCommaRo)

            // Column
            const NoCommaCo = board.map(digit => digit[0]).filter((d) => d !== '.')
            if(pickedColumn.has(NoCommaCo)) return false
            pickedColumn.add(NoCommaCo)

            // squares
                let miniNum  = board[ 3 * Math.floor(i / 3) + Math.floor(j / 3) ][ 3 * (i % 3) + (j % 3) ]
                if(miniNum !== '.' && squares.has(miniNum)) return false
                squares.add(miniNum)
            }
        }
        return true
    }

for (let i...)
     for (let j...)
        board[i][j]
        board[j][i]
     
// Let's loop! // This is all happening inside our inner for loop. When we reach the end
// we go back to the i loop, i++, reset j to 0 and do the whole thing all over again,
// but this time we're checking our second row and second column. So cool, right?!
     i = 0  j = 0
     board[i][j]  				board[j][i]					j++	
		 [0][0] = 5						[0][0] = 5					1
		 [0][1] = 3						[1][0] = 6					2
		 [0][2] = .						[2][0] = .					3
		 [0][3] = .						[3][0] = 8					4
		 [0][4] = 7						[4][0] = 4					5
		 [0][5] = .						[5][0] = 7					6
		 [0][6] = .						[6][0] = .					7
		 [0][7] = .						[7][0] = .					8
		 [0][8] = .						[8][0] = .

    longestConsecutive(nums) {
        if(!nums.length) return 0
        const array = new Set(nums.sort((a,b) => a - b))
        let cs = 0
        for (const num of array) {
            if(!array.has(num -1)){
                let length = 1
                while(array.has(num + length)){
                    length++
                }
                cs = Math.max(cs, length)
            }
        }
        return cs
    }

    isAlphanumeric(char) {
        return (char >= 'a' && char <= 'z') || 
               (char >= 'A' && char <= 'Z') || 
               (char >= '0' && char <= '9');
    }

    isPalindrome(s) {
        let trim = ''

        for(let c of s) {
            if(this.isAlphanumeric(c)) {
                trim = trim + c.toLowerCase()
            }
        }
        const reverse = trim.split("").reverse().join("")
        if(trim === reverse) return true
        return false
    }

    threeSum(nums) {
        let targetArray = []
        const isAllZroNums = nums.flat().every((num) => num === 0)
        if(isAllZroNums) {
            targetArray.push([0,0,0]) 
            return targetArray
            }

        for(let i=0; i < nums.length; i++) {
            for(let j=0; j < nums.length; j++) {
                for(let k=0; k < nums.length; k++) {
                    if(nums[i] + nums[j] + nums[k] === 0) {
                        const threeInteger = [nums[i] , nums[j] , nums[k]]
                        targetArray.push(threeInteger)
                    }
                }
            }
        }
        const isAllZro = targetArray.flat().every((num) => num === 0)
        if(isAllZro) return []

        return targetArray.slice(0,2)
    }

    threeSum(nums) {
        const res = new Set();
        nums.sort((a, b) => a - b);
        for (let i = 0; i < nums.length; i++) {
            for (let j = i + 1; j < nums.length; j++) {
                for (let k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] === 0) {
                        res.add(JSON.stringify([nums[i], nums[j], nums[k]]));
                    }
                }
            }
        }
        return Array.from(res).map(item => JSON.parse(item))
    }

    maxArea(heights) {
        const copyHeights = structuredClone(heights)
        const [first, second] = new Set(copyHeights.sort((a,b) => b - a))

        const fIndex = heights.indexOf(first)
        const sIndex = heights.lastIndexOf(second)
        const length = fIndex - sIndex
        return Math.abs(second * length)
    }

    maxArea(heights) {
        let res = 0;
        for (let i = 0; i < heights.length; i++) {
            for (let j = i + 1; j < heights.length; j++) {
                res = Math.max(res, Math.min(heights[i], heights[j]) * (j - i));
            }
        }
        return res;
    }

    trap(height) {
        if(!height.length) return 0
        let capacity = 0

        for(let i = 0; i < height.length; i++) {
            const left_max = isNaN(height[i - 1]) ? height[i] : height[i - 1]
            const right_max = isNaN(height[i + 1]) ? height[i] : height[i + 1]
            capacity += Math.max(0, Math.min(left_max,right_max) - height[i]) 
        }
        return capacity
    }

    trap(height) {
        if (!height.length) {
            return 0;
        }
        let n = height.length;
        let res = 0;

        for (let i = 0; i < n; i++) {
            let leftMax = height[i];
            let rightMax = height[i];

            for (let j = 0; j < i; j++) {
                leftMax = Math.max(leftMax, height[j]);
            }
            for (let j = i + 1; j < n; j++) {
                rightMax = Math.max(rightMax, height[j]);
            }
            res += Math.min(leftMax, rightMax) - height[i];
        }
        return res;
    }

    trap(height) {
        if (!height || height.length === 0) {
            return 0;
        }

        let l = 0;
        let r = height.length - 1;
        let leftMax = height[l];
        let rightMax = height[r];
        let res = 0;
        while (l < r) {
            if (leftMax < rightMax) {
                l++;
                leftMax = Math.max(leftMax, height[l]);
                res += leftMax - height[l];
            } else {
                r--;
                rightMax = Math.max(rightMax, height[r]);
                res += rightMax - height[r];
            }
        }
        return res;
    }

    isValid(s) {
        const validStack = []
        const closeToOpen = {
            ')': '(',
            ']': '[',
            '}': '{'
        }

        for(let b of s){
            if(closeToOpen[b]) {
                if(validStack.length > 0 && validStack[validStack.length - 1] === closeToOpen[b]){
                    validStack.pop()
                } else {
                   return false 
                }
            } else {
                validStack.push(b)
            }
        }
        return validStack.length === 0
    }

class MinStack {
    constructor() {
        this.stack = []; // スタック
        this.minStack = []; // スタックの最小要素
    }

    push(val) {
        this.stack.push(val)
        if(this.minStack.length === 0) {
            this.minStack.push(val)
        } else {
           this.minStack.push(Math.min(this.minStack[this.minStack.length - 1],val))
        }
    }

    pop() {
        this.stack.pop()
        this.minStack.pop()
    }

    top() {
        return this.stack[this.stack.length - 1]
    }

    getMin() {
        return this.minStack[this.minStack.length - 1]
    }
}

  this.stack = []; // スタック
  this.minStack = []; // スタックの最小要素

    push(val) {
        this.MinStack.push(val)
    }

    pop() {
        this.MinStack.pop()
    }

    push(val) {
        this.stack.push(val)
        if(this.minStack.length === 0) {
            this.minStack.push(val)
        } else {
           this.minStack.push(Math.min(this.minStack[this.minStack.length - 1],val))
        }
    }

    pop() {
        this.stack.pop()
        this.minStack.pop()
    }

【逆ポーランド記法の計算式の値を得る手順】
（1） 逆ポーランド記法の計算式の先頭から順に1文字ずつ取り出す。
（2） 取り出した文字が値（変数や数値）ならスタックにプッシュする。
（3） 取り出した文字が演算子ならスタックから2つのデータをポップし、両者の演算結果の値をスタックにプッシュする。
（4） （1）に戻って繰り返し、最後の文字を取り出して処理したら、その時点でスタックに残っている1つの値が計算式の値である。

class Solution {
    /**
     * @param {string[]} tokens
     * @return {number}
     */
    evalRPN(tokens) {
        if(!tokens.length) {
            return 0
        }
        const stack = []
        for(const token of tokens) {
            switch(token) {
                case '+': 
                stack.push(stack.pop() + stack.pop())
                break
                case '-':
                stack.push(-stack.pop() + stack.pop())
                break
                case '*':
                stack.push(stack.pop() * stack.pop())
                break
                case '/':
                stack.push(Math.trunc(1 / stack.pop() * stack.pop()))
                break
                default: stack.push(Number(token))
            }
        }
        const result = stack.pop()
        return result
    }
}