丑数

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. 思路

从头到尾遍历一遍，统计每个字符的出现次数，保存到哈希表中。