signed

QiShunwang

“诚信为本、客户至上”

leetcode刷题 数学运算及其他 C++(剑指offer10个)

2021/4/26 22:19:03   来源:

目录

剑指 Offer 16. 数值的整数次方  50. Pow(x, n)

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

54. 螺旋矩阵  剑指 Offer 29. 顺时针打印矩阵

59. 螺旋矩阵 II 

剑指 Offer 43. 1~n 整数中 1 出现的次数  数学法

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

剑指 Offer 61. 扑克牌中的顺子  集合 Set / 排序

剑指 Offer 64. 求1+2+…+n  递归 逻辑运算符 

剑指 Offer 65. 不用加减乘除做加法  

剑指Offer(五十四):字符流中第一个不重复的字符 牛客网没找到


剑指 Offer 16. 数值的整数次方  50. Pow(x, n)

难度中等633

实现 pow(xn) ,即计算 x 的 n 次幂函数(即,xn)。

递归提前铺垫  通过一道面试题目,讲一讲递归算法的时间复杂度!

class Solution {
public:
    double quickMul(double x, long long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }

    double myPow(double x, int n) {
        long long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
};

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

https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/solution/jian-zhi-offer-17-da-yin-cong-1dao-zui-d-ngm4/

https://zhuanlan.zhihu.com/p/364571011

https://www.bilibili.com/video/BV1nX4y1M7FM?from=search&seid=17493246989948908995

54. 螺旋矩阵  剑指 Offer 29. 顺时针打印矩阵

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return {};
        }

        int rows = matrix.size(), columns = matrix[0].size();
        vector<int> order;
        int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++) {
                order.push_back(matrix[top][column]);
            }
            for (int row = top + 1; row <= bottom; row++) {
                order.push_back(matrix[row][right]);
            }
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--) {
                    order.push_back(matrix[bottom][column]);
                }
                for (int row = bottom; row > top; row--) {
                    order.push_back(matrix[row][left]);
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return order;
    }
};

59. 螺旋矩阵 II 

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int num = 1;
        vector<vector<int>> matrix(n, vector<int>(n));
        int left = 0, right = n - 1, top = 0, bottom = n - 1;
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++) {
                matrix[top][column] = num;
                num++;
            }
            for (int row = top + 1; row <= bottom; row++) {
                matrix[row][right] = num;
                num++;
            }
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--) {
                    matrix[bottom][column] = num;
                    num++;
                }
                for (int row = bottom; row > top; row--) {
                    matrix[row][left] = num;
                    num++;
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return matrix;
    }
};

剑指 Offer 43. 1~n 整数中 1 出现的次数  数学法

//LL 表示long long,64位长整型,C++11标准中新定义的,用法就是范围更大的整型
int countDigitOne(int n)
{
    int countr = 0;
    for (long long i = 1; i <= n; i *= 10) {
        long long divider = i * 10;
        countr += (n / divider) * i + min(max(n % divider - i + 1, 0LL), i);
    }
    return countr;
}

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

https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/solution/zhe-shi-yi-dao-shu-xue-ti-ge-zhao-gui-lu-by-z1m/

class Solution {
public:
    int findNthDigit(int n) {
        // 计算该数字由几位数字组成,由1位:digits = 1;2位:digits = 2...
        long base = 9,digits = 1;
        while (n - base * digits > 0){
            n -= base * digits;
            base *= 10;
            digits ++;
        }

        // 计算真实代表的数字是多少
        int idx = n % digits;  // 注意由于上面的计算,n现在表示digits位数的第n个数字
        if (idx == 0)idx = digits;
        long number = 1;
        for (int i = 1;i < digits;i++)
            number *= 10;
        number += (idx == digits)? n/digits - 1:n/digits;

        // 从真实的数字中找到我们想要的那个数字
        for (int i=idx;i<digits;i++) number /= 10;
        return number % 10;
    }
};

剑指 Offer 61. 扑克牌中的顺子  集合 Set / 排序

剑指 Offer 64. 求1+2+…+n  递归 逻辑运算符 

class Solution {
public:
    int sumNums(int n) {
        n && (n += sumNums(n-1));
        return n;
    }
};

剑指 Offer 65. 不用加减乘除做加法  

https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/solution/di-gui-he-fei-di-gui-liang-chong-fang-sh-as4v/

剑指Offer(五十四):字符流中第一个不重复的字符 牛客网没找到