44-数字序列中某一位的数字

题目描述

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

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

解法

找规律，解释都在注释中，多看几遍就明白了。

代码如下：

class Solution {
public:

    int getBit(int num, int index) {
        // 2457 第一位是2，第二位是4，以此类推
        vector<int> res;
        // printf("%d", num);
        while(num) {
            res.push_back(num % 10);
            num /= 10;
        }
        return res[res.size() - index];
        
    }
    int findNthDigit(int n) {
        
        if (n <= 9) {
            return n;
        }
        // 统计多少位
        // 一位数，有10个比较特殊，占10位
        // 二位数，有10-99共90个，占90*2=180位
        // 三位数，有100-999，共900个，占900*3=2700位
        // i位数，有9*pow(10, i-1)个，占9*pow(10, i-1)*i位

        // 这个值设为int会越界，需要特别注意下
        long long cummulate = 10;
        int pre = 0;
        int i;
        for (i = 1; ; i++) {
            // 统计到当前i位数，一共占多少位，如果超过n，直接退出循环，那第n位一定在i位数中
            cummulate += 9 * pow(10, i) * (i + 1);
            // 统计当前i位数之前，一共占了多少位，便于计算偏移
            pre += 9 * pow(10, i - 1) * i;
            if (cummulate > n) {
                break;
            }
        }
        // i此时的含义是到i位数的时候，可以包括第n个位

        // i位数的第一个值
        int start = pow(10, i);
        int offset;
        // offset偏移记录了当前i位数*有多少位（扣除前面的）
        if (i == 1) {
            offset = n - 10;
        } else {
            offset = n - pre - 1;
        }
        // i位数中的第几个数
        int index = offset / (i + 1);
        // 一共有多少位（offset从零开始）
        int totalNumBits = offset + 1;
        // 第n位数就存在于end中
        int end = start + index;
        // 找到是end中的第几位数
        int a = totalNumBits - index * (i + 1);
        // 利用函数找到这个位
        int ans = getBit(end, a);
    
        return ans;
    }
};

45-把数组排成最小的数

题目描述

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

解法

定义一个规则，对拼接后的字符串进行比较。

排序规则如下：

若ab > ba 则 a 大于 b，
若ab < ba 则 a 小于 b，
若ab = ba 则 a 等于 b；
根据上述规则，我们需要先将数字转换成字符串再进行比较，因为需要串起来进行比较。比较完之后，按顺序输出即可。

代码如下：

class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {
        int length = numbers.size();
        if(length == 0){
            return "";
        }
        sort(numbers.begin(), numbers.end(), cmp);
        string res;
        for(int i = 0; i <　length; i++){
            res += to_string(numbers[i]);
        }
        return res;
    }
private:
    // 升序排序
    static bool cmp(int a, int b){
        string A = to_string(a) + to_string(b);
        string B = to_string(b) + to_string(a);
        return A < B;
    }
};