剑指Offer题解——数学-蒲公英云

文章目录

- 剑指 Offer 17. 打印从1到最大的n位数
- - 回溯解法
- 剑指 Offer 20. 表示数值的字符串
- - 解法
- 剑指 Offer 43. 1～n整数中1出现的次数
- - 解法
- 剑指 Offer 44. 数字序列中某一位的数字
- - 解法
- 剑指 Offer 49. 丑数
- - 解法
  - - 推荐阅读

剑指 Offer 17. 打印从1到最大的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

示例 1:
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
说明：
用返回一个整数列表来代替打印
n 为正整数

回溯解法

此题应该主要考察大数越界的情况，详解见leetcode

class Solution {
    int[] res;
    int nine = 0, count = 0, start, n;
    char[] num, loop = {
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    public int[] printNumbers(int n) {
        this.n = n;
        res = new int[(int)Math.pow(10, n) - 1];
        num = new char[n];
        start = n - 1;
        dfs(0);
        return res;
    }
    void dfs(int x) {
        if (x == n) {
            String s = String.valueOf(num).substring(start);
            if (!s.equals("0")) {
                res[count++] = Integer.parseInt(s);
            }
            if (n - start == nine) {
                start--;
            }
            return;
        }
        for (char i : loop) {
            if (i == '9') {
                nine++;
            }
            num[x] = i;
            dfs(x + 1);
        }
        nine--;
    }
}

剑指 Offer 20. 表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”、“5e2”、”-123”、“3.1416”、“0123”都表示数值，但”12e”、“1a3.14”、“1.2.3”、“±5”、”-1E-16”及”12e+5.4”都不是。

解法

class Solution {
    public boolean isNumber(String s) {
        if (s == null || s.length() == 0) {
            return false;
        }
        // 标记是否遇到数位、小数点、‘e’或'E'
        boolean numFlag = false, dotFlag = false, eFlag = false;
        char[] str = s.trim().toCharArray();
        for (int i = 0; i < str.length; i++) {
            if (str[i] >= '0' && str[i] <= '9') {
                numFlag = true;
            } else if (str[i] == '.') {
                // 小数点之前可以没有整数，但是不能重复出现小数点、或出现‘e’、'E'
                if (eFlag || dotFlag) {
                    return false;
                }
                dotFlag = true;
            } else if (str[i] == 'e' || str[i] == 'E') {
                if (!numFlag || eFlag) {
                    return false;
                }
                eFlag = true;
                // 重置numFlag，因为‘e’或'E'之后也必须接上整数，防止出现 123e或者123e+的非法情况
                numFlag = false;
            } else if (str[i] == '-' || str[i] == '+') {
                // 正负号只可能出现在第一个位置，或者出现在‘e’或'E'的后面一个位置
                if (i != 0 && str[i - 1] != 'e' && str[i - 1] != 'E') {
                    return false;
                }
            } else {
                return false;
            }
        }
        return numFlag;
    }
}

剑指 Offer 43. 1～n整数中1出现的次数

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例 1：
输入：n = 12
输出：5
示例 2：
输入：n = 13
输出：6
限制：
1 <= n < 2^31

解法

详解见leetcode

class Solution {
    public int countDigitOne(int n) {
        int digit = 1, res = 0;
        int high = n / 10, cur = n % 10, low = 0;
        while (high != 0 || cur != 0) {
            if (cur == 0) {
                res += high * digit;
            }
            else if (cur == 1) {
                res += high * digit + low + 1;
            }
            else {
                res += (high + 1) * digit;
            }
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return res;
    }
}

剑指 Offer 44. 数字序列中某一位的数字

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

示例 1：
输入：n = 3
输出：3
示例 2：
输入：n = 11
输出：0
限制：
0 <= n < 2^31

解法

class Solution {
    public int findNthDigit(int n) {
        int digit = 1;
        long start = 1;
        long count = 9;
        while (n > count) {
     // 1.
            n -= count;
            digit += 1;
            start *= 10;
            count = digit * start * 9;
        }
        long num = start + (n - 1) / digit; // 2.
        return Long.toString(num).charAt((n - 1) % digit) - '0'; // 3.
    }
}

剑指 Offer 49. 丑数

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:  
1 是丑数。
n 不超过1690。

解法

class Solution {
    public int nthUglyNumber(int n) {
        int a = 0, b = 0, c = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n4 = dp[c] * 5;
            dp[i] = Math.min(n2, Math.min(n3, n4));
            if(dp[i] == n2) a++;
            if(dp[i] == n3) b++;
            if(dp[i] == n4) c++;
        }
        return dp[n - 1];
    }
}