Leetcode每日一题 —— 1291. 顺次数

明显一共就没几个。

class Solution {

public:

    vector<int> sequentialDigits(int low, int high) {

        vector<int> res;

        for(int bit = 2; bit < 10; bit++) {

            for(int bg = 1; bg + bit - 1 < 10; bg++) {

                int temp = bg;

                long long sum = 0;

                for(int i = 0; i < bit; i++,temp++) {

                    sum = sum * 10 + temp;

                }

                if(sum >= low && sum <= high) {

                    res.push_back(sum);

                }

                if(sum > high) {

                    return res;

                }

            }

        }

        

        return res;

    }

};

算术评级4 第 167 场周赛Q2 难度分 1374

class Solution:

    def sequentialDigits(self, low: int, high: int) -> List[int]:

        all_list = [12, 23, 34, 45, 56, 67, 78, 89, 123, 234, 345, 456, 567, 678, 789, 1234, 2345, 3456, 4567, 5678, 6789, 12345, 23456, 34567, 45678, 56789, 123456, 234567, 345678, 456789, 1234567, 2345678, 3456789, 12345678, 23456789, 123456789]

        return all_list[bisect_left(all_list,low):bisect_right(all_list,high)]

Kotlin实现（递推+预处理+二分查找）双百：

class Solution {

    companion object {

        val nums = mutableListOf<Int>()



        init {

            var startNum = 1

            var offset = 1

            for (digitCount in 2..9) {

                startNum = startNum * 10 + digitCount

                offset = offset * 10 + 1



                var curNum = startNum

                nums.add(startNum)

                for (i in 1..(9 - digitCount)) {

                    curNum += offset

                    nums.add(curNum)

                }

            }

        }



        fun lowerBound(target: Int): Int {

            var left = 0

            var right = nums.lastIndex

            while (left < right) {

                val mid = left + ((right - left) shr 1)

                if (nums[mid] < target) {

                    left = mid + 1

                } else {

                    right = mid

                }

            }

            return left

        }

    }



    fun sequentialDigits(low: Int, high: Int): List<Int> {

        val firstIndex = lowerBound(low)

        if (nums[firstIndex] < low) {

            return emptyList()

        }



        val result = mutableListOf<Int>()

        for (i in firstIndex..nums.lastIndex) {

            if (nums[i] > high) {

                break

            }

            result.add(nums[i])

        }

        return result

    }

}

写得比较麻烦了，但是还挺快，按数值移位处理做感觉要注意的细节还挺多的。

class Solution {

public:

    vector<int> sequentialDigits(int low, int high) {

        // 这题的数据规模，暴力看上去不太行

        // 既然是每一位都要比前一位大 1，其实从十位开始枚举就行

        // 12, 23, 34, 45, ..., 123, 234, 345, ... 这样枚举下去

        

        vector<int> res;

        // 补充：首个 low 是合规的也要加入

        bool isSeq=true; // 标记当前数是不是符合要求的

        int prev=-1;

        int temp=low;

        while(temp>0){

            if(prev!=-1&&prev-temp%10!=1){

                isSeq=false;

                break;

            }

            prev=temp%10;

            temp/=10;

        }

        if(isSeq){

            res.emplace_back(low);

        }

        // nextOne 方法获取下一个

        auto nextOne=[&](int curr)->int{

            // 先计算位数和对应倍数

            int numDigits=0;

            int factor=1;

            int prev=-1;

            int temp=curr;

            bool notSeq=false; // 标记当前数是不是符合要求的

            while(temp>0){

                if(prev!=-1&&prev-temp%10!=1){

                    notSeq=true;

                }

                prev=temp%10;

                temp/=10;

                numDigits++;

                factor*=10;

            }

            // factor 会多算一次

            factor/=10;

            if(!notSeq){

                // 当前数已经符合要求，寻找下一个

                curr = curr % factor * 10;

            }

            // 无论 curr 原本是否为顺次数，都要判断当前位数是否装得下

            if(curr / factor + numDigits - 1 > 9){

                numDigits++;

                factor *= 10;

                curr = factor;

            }

            // 从最高位开始推

            int res=curr/factor;

            int digit=res;

            for(int i=1;i<numDigits;i++){

                res=res*10+(digit+1);

                digit++;

            }

            return res;

        };

        int current=low;

        while(current<=high){

            current=nextOne(current);

            if(current>=low&&current<=high){

                res.emplace_back(current);

            }

        }

        return res;

    }

};