【算法与数据结构】738、LeetCode单调递增的数字

2024-01-02 15:51:33

所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解

一、题目

在这里插入图片描述

二、解法

??思路分析:暴力解法如下,思路很简单,从右往左遍历,但是会超时。
??程序如下

class Solution {
private:
    bool func(int n) {
        int high_digit = 0, low_digit = 0;  // 高位数字和低位数字
        while (n != 0) {
            low_digit = n % 10;          // 最低位数字
            high_digit = n / 10 % 10;    // 高一位数字
            if (high_digit > low_digit) {
                return false;
            }
            else {
                low_digit = high_digit;   // 更新最低位
                n = n / 10;               // 舍去最低位
            }
        }
        return true;
    }    
public:
    int monotoneIncreasingDigits(int n) {
        // 1.提取数组(存入数组) 2.遍历数组,是否满足条件
        while (n>=0) {
            if (func(n)) return n;
            else n--;
        }
        return -1;
    }
};

复杂度分析:

  • 时间复杂度: O ( n ? m ) O(n*m) O(n?m), n为题目的数字,m为数字长度。
  • 空间复杂度: O ( 1 ) O(1) O(1)

??思路分析:我们从局部最优推出全局最优,因为题目要找小于等于n的最大单调递增数字,所以每当高位大于低位时,将低位置为9,高位减一就是最大的数字,例如83的最大单调数字为79,861最大单调递增数字为799,一共需要改两次861->859->799。由此写出如下贪心算法。程序当中将数字转为字符串,方便了操作,不需要挨个计算数字的每位数。
??程序如下

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string strNum = to_string(n);   // 转化成字符串更方便操作
        int flag = strNum.size();
        for (int i = strNum.size() - 1; i > 0; i--) {
            if (strNum[i - 1] > strNum[i]) {
                flag = i;
                strNum[i - 1]--;
            }
        }
        for (int i = flag; i < strNum.size(); i++) {
            strNum[i] = '9';
        }
        return stoi(strNum);
    }
};

复杂度分析:

  • 时间复杂度: O ( n ) O(n) O(n), n为题目的数字。
  • 空间复杂度: O ( n ) O(n) O(n), 需要一个字符串。

三、完整代码

# include <iostream>
# include <string>
using namespace std;

//class Solution { // 暴力解法:超时
//private:
//    bool func(int n) {
//        int high_digit = 0, low_digit = 0;  // 高位数字和低位数字
//        while (n != 0) {
//            low_digit = n % 10;          // 最低位数字
//            high_digit = n / 10 % 10;    // 高一位数字
//            if (high_digit > low_digit) {
//                return false;
//            }
//            else {
//                low_digit = high_digit;   // 更新最低位
//                n = n / 10;               // 舍去最低位
//            }
//        }
//        return true;
//    }    
//public:
//    int monotoneIncreasingDigits(int n) {
//        // 1.提取数组(存入数组) 2.遍历数组,是否满足条件
//        while (n>=0) {
//            if (func(n)) return n;
//            else n--;
//        }
//        return -1;
//    }
//};

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string strNum = to_string(n);   // 转化成字符串更方便操作
        int flag = strNum.size();
        for (int i = strNum.size() - 1; i > 0; i--) {
            if (strNum[i - 1] > strNum[i]) {
                flag = i;
                strNum[i - 1]--;
            }
        }
        for (int i = flag; i < strNum.size(); i++) {
            strNum[i] = '9';
        }
        return stoi(strNum);
    }
};

int main() {
    int n = 721528309;
    Solution s1;
    int result = s1.monotoneIncreasingDigits(n);
    cout << result << endl;
    system("pause");
    return 0;
}

end

文章来源:https://blog.csdn.net/qq_45765437/article/details/135339783
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。