【算法与数据结构】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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!