剑指Offer JavaScript-哈希专题

剑指Offer JavaScript-哈希专题

Tags
哈希算法
CreatedTime
Aug 16, 2022 02:18 AM
Slug
2019-06-23-hash-ugly
UpdatedTime
Last updated August 17, 2022

丑数

1. 题目描述

把只包含因子 2、3 和 5 的数称作丑数(Ugly Number)。例如 6、8 都是丑数,但 14 不是,因为它包含因子 7。习惯上我们把 1 当做是第一个丑数。求按从小到大的顺序的第 1500 个丑数。

2. 解题思路

2.1 思路一

根据定义,将给定的数不断除 2、3、5,看看能不能除尽即可。然后从 1 遍历到 1500。

2.2 思路二

前面速度慢是因为计算了太多非丑数。根据丑数定义,每一个丑数都是根据前面一个丑数乘以 2、3 或者 5 得到的
在确保顺序的情况下,逐步计算即可。

3. 代码

3.1 思路一实现

// 判断是否符合丑数定义 function isUgly(number) { while (number % 2 === 0) { number /= 2; } while (number % 3 === 0) { number /= 3; } while (number % 5 === 0) { number /= 5; } return number === 1; } // 找出 [1, index) 之中的所有丑数 function getUglyNumber(index) { if (index <= 0) return 0; let number = 0, uglyFound = 0; while (uglyFound < index) { ++number; if (isUgly(number)) { ++uglyFound; } } return number; }

3.2 思路二实现

function getUglyNumber(index) { if (index <= 0) return 0; const uglyNum = [1]; // 存放丑数 // 2,3,5 三个因子各自的指针 let pointer2 = 0, pointer3 = 0, pointer5 = 0; for (let i = 1; i < index; ++i) { // 找出下一个丑数,确保顺序 uglyNum[i] = Math.min( uglyNum[pointer2] * 2, uglyNum[pointer3] * 3, uglyNum[pointer5] * 5 ); // 如果结果相同,移动指针,防止下次重复计算 if (uglyNum[i] == uglyNum[pointer2] * 2) ++pointer2; if (uglyNum[i] == uglyNum[pointer3] * 3) ++pointer3; if (uglyNum[i] == uglyNum[pointer5] * 5) ++pointer5; } return uglyNum[index - 1]; } /** * 测试代码 */ console.log(getUglyNumber(1500)); // 859963392

第一次只出现一次的字符

1. 题目描述

在字符串中找到第一个只出现一次的字符。

2. 思路

从头到尾遍历一遍,统计每个字符的出现次数,保存到哈希表中。
再重新遍历一遍,每次都检查哈希表中的次数是不是 1,是 1,直接返回,这就是第一个字符。

3. 代码实现

/** * * @param {String} str */ function findFirstNoRepeatChar(str) { const chars = str.split(""); const map = {}; for (let char of chars) { if (char in map) { map[char] += 1; } else { map[char] = 1; } } for (let char of chars) { if (map[char] === 1) { return char; } } } /** * 测试代码 */ console.log(findFirstNoRepeatChar("abaccdeff")); // output: 'b'