剑指Offer题解——数学

女爷i 2022-11-25 10:28 163阅读 0赞

### 文章目录 ###

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

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

[剑指 Offer 17. 打印从1到最大的n位数][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. 表示数值的字符串 ##

[剑指 Offer 20. 表示数值的字符串][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出现的次数 ##

[剑指 Offer 43. 1～n整数中1出现的次数][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][leetcode 1]

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. 数字序列中某一位的数字 ##

[剑指 Offer 44. 数字序列中某一位的数字][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. 丑数 ##

[剑指 Offer 49. 丑数][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];
        }
    }

--------------------

#### 推荐阅读 ####

*  [机器学习资料汇总][Link 1]
 *  [吴恩达《机器学习》视频、作业、源码][Link 2]
 *  [106页《Python进阶》中文版正式发布][106_Python]
 *  [李航《统计学习方法》第二版完整课件][Link 3]
 *  [机器学习数学全书，1900页PDF下载][1900_PDF]

--------------------

![format_png][]

[Offer 17. _1_n]: https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/
[leetcode]: https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/solution/mian-shi-ti-17-da-yin-cong-1-dao-zui-da-de-n-wei-2/
[Offer 20.]: https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/
[Offer 43. 1_n_1]: https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/
[leetcode 1]: https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/
[Offer 44.]: https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/
[Offer 49.]: https://leetcode-cn.com/problems/chou-shu-lcof/
[Link 1]: https://mp.weixin.qq.com/s/3nOkk_Yt9D7Qp1WaWEjyZQ
[Link 2]: https://mp.weixin.qq.com/s/dErZNtBYbVA7ItPm7T_HIw
[106_Python]: https://mp.weixin.qq.com/s/_WEuuxj-QgihijjLz7NJ9g
[Link 3]: https://mp.weixin.qq.com/s/xah47OWuu8ahAUa1aFFo4Q
[1900_PDF]: https://mp.weixin.qq.com/s/9BuyhdwuHiHH3ksVUe44ZQ
[format_png]: /images/20221124/a1a4a8f25f62484eb80425d4b498c0bc.png