当前位置：首页 > article >正文

Javascript数据结构——哈希表常见应用

article 2025/1/21 12:21:57

哈希表（Hash Table）是一种常见的数据结构，用于高效地存储和查找键值对。以下列出常见的7个与哈希表相关的算法题目，并附上代码示例和说明。

Javascript数据结构——哈希表-CSDN博客

1. 两数之和（Two Sum）

题目描述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。

代码示例：

function twoSum(nums, target) {  
    const map = new Map();  
    for (let i = 0; i < nums.length; i++) {  
        const complement = target - nums[i];  
        if (map.has(complement)) {  
            return [map.get(complement), i];  
        }  
        map.set(nums[i], i);  
    }  
    throw new Error("No two sum solution");  
}  
  
// 示例  
console.log(twoSum([2, 7, 11, 15], 9)); // 输出: [0, 1]

说明：利用哈希表存储已经遍历过的数字及其索引，对于每个数字，计算其补数（即 target - nums[i]），然后检查哈希表中是否存在该补数。

2. 字符串中的第一个唯一字符（First Unique Character in a String）

题目描述：给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

代码示例：

function firstUniqChar(s) {  
    const charMap = {};  
    for (let char of s) {  
        charMap[char] = (charMap[char] || 0) + 1;  
    }  
    for (let i = 0; i < s.length; i++) {  
        if (charMap[s[i]] === 1) {  
            return i;  
        }  
    }  
    return -1;  
}  
  
// 示例  
console.log(firstUniqChar("leetcode")); // 输出: 0

说明：使用哈希表记录每个字符出现的次数，然后遍历字符串找到第一个出现次数为1的字符。

3. 有效的字母异位词（Valid Anagram）

题目描述：给定两个字符串 s 和 t ，判断它们是否包含相同字符且字符出现的次数相同。

代码示例：

function isAnagram(s, t) {  
    if (s.length !== t.length) return false;  
    const charMap = {};  
    for (let char of s) {  
        charMap[char] = (charMap[char] || 0) + 1;  
    }  
    for (let char of t) {  
        if (!charMap[char]) return false;  
        charMap[char]--;  
        if (charMap[char] < 0) return false;  
    }  
    return true;  
}  
  
// 示例  
console.log(isAnagram("anagram", "nagaram")); // 输出: true

说明：使用哈希表记录字符串 s 中每个字符的出现次数，然后遍历字符串 t，逐步减少哈希表中对应字符的计数。

4. 容器中最多有多少水（Container With Most Water）

题目描述：给定 n 个非负整数 a1，a2，...，an，每个数代表一个坐标点 (i, ai)。在坐标内画 n 条垂直线，使得 i 垂直线的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴构成的容器可以容纳最多的水。

代码示例：

function maxArea(height) {  
    let maxArea = 0;  
    let left = 0, right = height.length - 1;  
    while (left < right) {  
        const currentArea = Math.min(height[left], height[right]) * (right - left);  
        maxArea = Math.max(maxArea, currentArea);  
        if (height[left] < height[right]) {  
            left++;  
        } else {  
            right--;  
        }  
    }  
    return maxArea;  
}  
  
// 示例  
console.log(maxArea([1,8,6,2,5,4,8,3,7])); // 输出: 49

说明：虽然这个题目没有直接使用哈希表，但这里展示了一个与双指针技巧相关的算法，因为双指针和哈希表在算法设计中常常一起出现。

5. 重复的子字符串（Repeated Substring Pattern）

题目描述：给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。

代码示例：

function repeatedSubstringPattern(s) {  
    const n = s.length;  
    for (let len = 1; len <= Math.floor(n / 2); len++) {  
        if (n % len === 0) {  
            const pattern = s.substring(0, len);  
            let repeated = '';  
            for (let i = 0; i < n / len; i++) {  
                repeated += pattern;  
            }  
            if (repeated === s) {  
                return true;  
            }  
        }  
    }  
    return false;  
}  
  
// 另一种利用哈希表的方法  
function repeatedSubstringPatternWithHash(s) {  
    const n = s.length;  
    const seen = new Set();  
    seen.add('');  
    let repeated = '';  
    for (let i = 0; i < n; i++) {  
        repeated = (repeated + s[i]);  
        if (seen.has(repeated)) {  
            if (repeated.length === n) return true; // 避免完全相同的字符串被误判  
            const pattern = repeated;  
            const patternLength = repeated.length;  
            let j = i + 1;  
            while (j < n) {  
                if (s[j] !== pattern[j % patternLength]) {  
                    break;  
                }  
                j++;  
            }  
            if (j === n) return true;  
            seen.clear(); // 重置集合，避免重复计算  
        } else {  
            seen.add(repeated);  
        }  
    }  
    return false;  
}  
  
// 示例  
console.log(repeatedSubstringPatternWithHash("abab")); // 输出: true

说明：第一个解法是简单的暴力解法，第二个解法利用哈希表来存储已经出现的子串，以提高效率。

6. 单词搜索（Word Search）

题目描述：给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的上下左右四个方向相连，同时字母在同一行或同一列中的相邻字母不能跳过。

代码示例：

function exist(board, word) {  
    if (!board || board.length === 0 || !word || word.length === 0) return false;  
    const rows = board.length;  
    const cols = board[0].length;  
    const visited = new Array(rows).fill(0).map(() => new Array(cols).fill(false));  
    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];  
  
    function dfs(row, col, index) {  
        if (index === word.length) return true;  
        if (row < 0 || row >= rows || col < 0 || col >= cols || visited[row][col] || board[row][col] !== word[index]) {  
            return false;  
        }  
        visited[row][col] = true;  
        for (const [dx, dy] of directions) {  
            const newRow = row + dx;  
            const newCol = col + dy;  
            if (dfs(newRow, newCol, index + 1)) {  
                return true;  
            }  
        }  
        visited[row][col] = false;  
        return false;  
    }  
  
    for (let i = 0; i < rows; i++) {  
        for (let j = 0; j < cols; j++) {  
            if (dfs(i, j, 0)) {  
                return true;  
            }  
        }  
    }  
    return false;  
}  
  
// 示例  
console.log(exist([  
    ['A','B','C','E'],  
    ['S','F','C','S'],  
    ['A','D','E','E']  
], "ABCCED")); // 输出: true

查看全文

http://www.kler.cn/a/370366.html