哈希表集合映射算法题

映射表储存储存需要快速查找的数据

key值直接大胆使用扁平化的数据

1. 两数之和（ LeetCode 1 ）

leetcode

var twoSum = function (nums, target) {
    const map = new Map()
    const l = nums.length
    for (let i = 0; i < l; i++) {
        if(map.has(nums[i])) {
           return [map.get(nums[i]), i] 
        }
        map.set(target - nums[i], i)
    }
};

2. 模拟行走机器人（ LeetCode 874 ）

leetcode

映射表储存储存需要快速查找的坐标，key值直接大胆使用扁平化的数据

var robotSim = function (commands, obstacles) {
    let result = 0
    let x = y = 0
    let direction = 0
    const arrow = [[0, 1], [1, 0], [0, -1], [-1, 0]]

    const obstaclesMap = {}
    for (let i = 0; i < obstacles.length; i++) {
        obstaclesMap[obstacles[i]] = true
    }

    const l = commands.length
    for (let command of commands) {
        if (commands[i] === -2) {
            direction = direction === 0 ? 3 : direction - 1
        } else if (commands[i] === -1) {
            direction = direction === 3 ? 0 : direction + 1
        } else {
            const addX = arrow[direction][0]
            const addY = arrow[direction][1]
            while (command-- > 0 && !obstaclesMap[`${x + addX},${y + addY}`]) {
                x += addX;
                y += addY;
            }
            result = Math.max(result, x * x + y * y)
        }
    }
    return result
};

3. 字母异位词分组（ LeetCode 49 ）

leetcode

var groupAnagrams = function(strs) {
    const map = {}
    for(const s of strs) {
        const count = new Array(26).fill(0)
        for(const c of s) {
            count[c.charCodeAt() - 'a'.charCodeAt()]++
        }
        map[count] ? map[count].push(s) : map[count] = [s]
    }
    return Object.values(map)
};

4. 串联所有单词的子串（ LeetCode 30 ）

leetcode

此题属于leetcode 438的进阶版

var findSubstring = function (s, words) {
    const result = []
    const len = s.length
    const wordNum = words.length // 有效单词数count === wordNum时,代表可以放进result
    const wordLen = words[0].length
    const wordMap = new Map()

    for (const word of words) {
        wordMap.set(word, (wordMap.get(word) || 0) + 1)
    }

    // 只需要找一个单词的身位就行，大于一个单词的身位都在while里循环了,小于单词身位的都无意义
    for (let i = 0; i < wordLen; i++) {
        let left = right = i
        let count = 0 // 符合要求的单词个数
        const validMap = new Map()

        while (right + wordLen <= len) {
            const add = s.slice(right, right + wordLen)
            right += wordLen
            
            if (wordMap.has(add)) {
                validMap.set(add, (validMap.get(add) || 0) + 1)
                count++
                // 滑动窗口容量超标 不应以 长度> totalLen为标准。而应以某单词数是否超标为标准，如下。
                while (validMap.get(add) > wordMap.get(add)) {
                    // 一直弃置左侧单词，直到符合。
                    const del = s.slice(left, left + wordLen)
                    validMap.set(del, validMap.get(del) - 1)
                    left += wordLen
                    count--
                }
            } else {
                left = right
                validMap.clear()
                count = 0
            }

            if (count === wordNum) result.push(left)
        }
    }
    return res
};

5. 子域名访问计数（ LeetCode 811 ）

leetcode

var subdomainVisits = function(cpdomains) {
    const result = []
    const map = {}
    for(const cpdomain of cpdomains) {
        const temp = cpdomain.split(' ')
        const count = Number(temp[0])
        const domain = temp[1]
        const array = domain.split('.')
        while(array.length) {
            map[array.join('.')] = (map[array.join('.')] || 0) + count
            array.shift()
        }
    }
    for (const key in map) {
        result.push(map[key] + ' ' + key)
    }
    return result
};

6. 子数组的度（ LeetCode 697 ）

leetcode

var findShortestSubArray = function (nums) {
    const map = {}
    for (let i = 0; i < nums.length; i++) {
        const c = nums[i]
        if (map[c]) {
            map[c][0]++
            map[c][2] = i
        } else {
            map[c] = [1, i, i]
        }
    }
    let maxNum = minLen = 0
    Object.values(map).map(item => {
        if(item[0] > maxNum) {
            maxNum = item[0]
            minLen = item[2] - item[1] + 1
        } else if(item[0] === maxNum) {
            minLen = Math.min(item[2] - item[1] + 1, minLen)
        }
    })
    return minLen
};