「算法刷题」数学情景专项汇总（力扣版）

本文记录作者刷题过程中与数学情景相关的题目。

一、实现函数

50. Pow(x, n)（中等函数）

剑指 Offer 16. 数值的整数次方（中等函数）

class Solution {
public:
    // x的n次幂等于n个x相乘,请注意，n可能为负数
    // 直接使用while循环，n非常大时会超时,所以需要用快速幂的位运算
    // 同时注意n可能是一个极大的负数，转换为long
    double myPow(double x, int n) {
        if(x==0.0f) return 0.0f;// 0的任何幂都设为0
        if(x==1.0f) return 1.0f;// 1的任何幂都设为1
        double res=1.0f;
        // 特殊情况:n为负数
        long b = n;//排除n为极大的负数
        if(b<0){
            x=1/x;
            b=-b;
        }
        // 快速幂算法的位运算版本
        while(b){
            if(b&1==1) res=res*x;//如果b是奇数，则res直接*x
            x=x*x;//x自乘
            b>>=1;//b右移1位，相当于/2
        }
        return res;
    }
};

剑指 Offer 67. 把字符串转换成整数（中等难度）

8. 字符串转换整数 (atoi)（中等难度）

class Solution {
public:
    /*本题是要将字符串转为有符号的32位整数。
    根据示例，字符串可能存在前端空格、正负号、后缀字母、首字符非数字、数字越界共计5种情况，
    这也是本题的难点*/
    bool isDigit(char c){
        return c-'0'>=0&&c-'0'<=9;
    }
    int strToInt(string str) {
        int n=str.length();
        if(n==0) return 0;//非有效转换输出0
        int start=0;
        int negative=false;
        // 去掉前端空格
        for(char c:str){
            if(c==' ') start++;
            else break;
        }
        if(start==n)return 0;//去掉前导空格后到了末尾
        // // 判断非空首字符
        if (str[start] == '-') {
            negative = true;
            start++;
        }
        else if (str[start] == '+') 
        {
            negative = false;
            start++;
        }
        else if (!isDigit(str[start])){
            return 0;//非数字
        } 
        // 判断
        int ans = 0;
        while (start < n && isDigit(str[start])) {
            int digit = str[start] - '0';
            if (ans > (INT_MAX - digit) / 10) {
                // 本来应该是 ans * 10 + digit > Integer.MAX_VALUE
                // 但是 *10 和 + digit 都有可能越界，所有都移动到右边去就可以了。
                return negative? INT_MIN : INT_MAX;
            }
            ans = ans * 10 + digit;
            start++;
        }
        return negative? -ans : ans;
    }
};

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

二、N位数

剑指 Offer 17. 打印从1到最大的n位数（简单难度）

class Solution {
public:
    /*本题的难点在于n的增加，会让结果数组指数级增加：
    n=1，只有9个数；n=2，就有99个数；n=3，就有999个数
    所以n=n时，推理有n个9位数的数
    这道题返回一个int数组，测试数据也没有溢出
    如果让返回一个int数，可能存在溢出的情况，则难度会提升。
    */
    vector<int> printNumbers(int n) {
        // 计算需要多少个数
        int sum = 1;
        for (int i = 0; i < n; i++) sum *= 10;
        // 向结果数组中添加数字
        vector<int> res(sum - 1);
        for(int i = 0; i < sum - 1; i++) res[i] = i + 1;
        return res;
    }
};

400. 第 N 位数字

class Solution {
public:
    /*题意：将整数序列看做一个大整数，返回其第n位的数字*/
    int findNthDigit(int n) {
        if(n<=9) return n;
        //先确定第n位数字到了几位数，每种数字分别占用字符：9*1,90*2，900*3 等等
        long num=9;
        int d=1;//第n位所在的数字的位数
        while(n>num*d){
            n-=num*d;
            d++;
            num*=10;
        }
        //即为d位数，注意n此时一定大于0，因为若n归0，则在上一while循环不会减
        int m=(n-1)/d+1;
        int p=n-(m-1)*d;//所求即为d位数的第m个数字的第p位
        int k=(int)(num/9+m-1);//所求数字所在的那个数
        return (k/(int)pow(10,d-p))%10;
    }
};

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

233. 数字 1 的个数

class Solution {
public:
    int countDigitOne(int n) {
        return dfs(n);
    }
    //下面我们都用 1234 和 2345 来举例
    long dfs(int n){
        // 上一级递归 n = 20、10之类的整十整百之类的情况；以及n=0的情况
        if(n== 0) return 0;
        // n < 10 即为个位，这样子只有一个1
        if(n < 10) return 1;
        string s = to_string(n);
        //长度：按例子来说是4位
        int length = s.length();
        //这个base是解题速度100%的关键，本例中的是999中1的个数：300
        // 99的话就是20 ; 9的话就是1 ；9999就是4000 这里大家应该发现规律了吧。
        long base = (length-1)*(int)pow(10,length-2);

        //high就是最高位的数字
        int high = s[0] - '0';
        //cur就是当前所数量级，即1000
        int cur = (int)pow(10,length -1);
        if(high == 1){
            // 最高位为1，1+n-cur就是1000~1234中由千位数提供的1的个数
            // 剩下的f函数就是求1000~1234中由234产生的1的个数
            return base + (1+n-cur)+dfs(n-high*cur); 
        }else{
            // 这个自己思考
            return base*high+cur+dfs(n-high*cur);
        }
    }
};

一、扑克牌相关

剑指 Offer 61. 扑克牌中的顺子（简单难度）

class Solution {
public:
    /*解析：本题要求判断一个5个元素的数组是否是顺子
    稍微思考下，明白首先要从小到大排序，然后判断是否有除0以外的重复数，有则肯定不是顺子
    难点在于0可以看做然后数来填补顺子，如何判断几张0填补顺子是算法的难点?
    解决方案：找到minVal（非0）和maxVal，通过maxVal-minVal的差来判断需要几张0填补
    */
    bool isStraight(vector<int>& nums) {
        int zeroCnt=0;//0的数组
        int n=nums.size();//此题固定为5
        sort(nums.begin(),nums.end());//从小到大排序
        // 遍历数组，记录0的个数并判断是否存在重复数
        for(int i=0;i<n;i++){
            if(nums[i]==0)zeroCnt++;
            else if(i+1<n&&nums[i]==nums[i+1]) return false;
        }
        // maxVal-minVal<5时必定可以
        return nums[n-1]-nums[zeroCnt]<5;
    }
};