丑数
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 思路一实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
function isUgly(number) {
while (number % 2 === 0) {
number /= 2;
}
while (number % 3 === 0) {
number /= 3;
}
while (number % 5 === 0) {
number /= 5;
}
return number === 1;
}
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 思路二实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| function getUglyNumber(index) {
if (index <= 0) return 0;
const uglyNum = [1];
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));
|
第一次只出现一次的字符
1. 题目描述
在字符串中找到第一个只出现一次的字符。
2. 思路
从头到尾遍历一遍，统计每个字符的出现次数，保存到哈希表中。
再重新遍历一遍，每次都检查哈希表中的次数是不是 1，是 1，直接返回，这就是第一个字符。
3. 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
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"));
|