[leetcode]贪心算法之Monotone Increasing Digits

淩亂°似流年 2021-09-28 12:00 337阅读 0赞

贪心算法之Monotone Increasing Digits

  • 题干
  • 答案
  • 反思

题干

Given a non-negative integer N, find the largest number that is less than or equal to N with monotone increasing digits.

(Recall that an integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.)

Ex1:

Input: N = 10
Output: 9

Ex2:

Input: N = 1234
Output: 1234

Ex3:

Input: N = 332
Output: 299

答案

  1. class Solution { 
  2. public:
  3.     int monotoneIncreasingDigits(int N) { 
  4.         string s="";
  6.         while(N){ 
  7.             s.push_back('0'+N%10);
  8.             N/=10;
  9.         }
  10.         reverse(s.begin(),s.end());
  12.         int size=s.size();
  14.         for(int i=size-2;i>=0;i--){ 
  16.             if(s[i]>s[i+1]){ 
  17.                 s[i]=s[i]-1;
  19.                 for(int j=i+1;j<size;j++){ 
  20.                     s[j]='9';
  21.                 }
  22.             }
  23.         }
  25.         return stoi(s);
  26.     }
  27. };

反思

monotone Increasing的意思是单调上升，是不严格，意思是<=

因此从最后一位比较，逐渐降低位数，当降低位数后，后面的位数都可以填充’9’

解题过程中遇到的坑: 要把字符串而不是整数push_back到字符串里

学习了函数
stoi() 和 reverse()的用法

复习字符串和数字相互转换的方法：

数字->字符串

  1. sprintf
  2. stringstream
  3. itoa
  4. itos

字符串转数字：

  1. stringstream
  2. atoi
  3. stoi

发表评论

表情：
评论列表 （有 0 条评论，337人围观）

还没有评论，来说两句吧...

相关阅读