代码随想录算法训练营第36期DAY39

本文主要是介绍代码随想录算法训练营第36期DAY39，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

道心破碎的一天，继续加油吧，坚持努力。

DAY39

738单调递增的数字

暴力法：

没有想到用int i=n;i>0;i--来遍历。

class Solution {
private:
bool checknum(int num){
if(num<10) return true;
while(num/10!=0){
int low=num%10;
num/=10;
if(num%10>low) return false;
}
return true;
}
public:
//先试试暴力法。
int monotoneIncreasingDigits(int n) {
for(int i=n;i>0;i--){
if(checknum(i)) return i;
}
return 0;
}
};

力扣优质题解--Sweetiee

自己写了一遍，写不出来。。。

整理一下题解的思路：

既然要尽可能的大，那么这个数从高位开始要尽可能地保持不变。我们要找到从高到低第一个满足str[i]>str[i+1]的位置，然后把str[i]-1,再把后面的位置都变成9即可。

但是由于减小了str[i]之后，可能不满足str[i-1]<=str[i]了，若发生了这种情况，一定是str[i-1]==str[i]，此时就需要再str[i-1]-1,递归地会处理到某个位置idx，我们发现：str[idx]==str[idx+1]==...==str[i]。然后只要str[idx]-1，然后后面都补上9即可。

所以：遍历时候，求当前最大数字max，只在max<arr[i]的时候才更新max对应的idx（类似于：查找数组中最大的元素，返回最小的下标）。**接着判断是否有arr[i]>arr[i+1]**，如果是，那么idx位置数字减1，后面位置全部为9即可。

很多细节。也算是锻炼到了。加油。

class Solution {
public:
int monotoneIncreasingDigits(int n) {
int max=-1,idx=-1;
auto s=to_string(n);
//注意不要越界
for(int i=0;i<s.size()-1;i++){
if(max<s[i]){
max=s[i];
idx=i;
}
if(s[i]>s[i+1]){
s[idx]-=1;
for(int j=idx+1;j<s.size();j++) s[j]='9';
break;
}
}
return stoi(s);
}
};

代码随想录官方题解

这个贪心就稍微好想到，也容易理解和实现了：

思路：遇到非递增，就让大数减1，声明变量记录需要置为9的位置。为了利用局部信息，需要从后向前遍历。

class Solution {
public:
int monotoneIncreasingDigits(int n) {
auto s=to_string(n);
int flag=s.size();
for(int i=s.size()-1;i>0;i--){
if(s[i-1]>s[i]){
flag=i;
s[i-1]--;
}
}
for(int i=flag;i<s.size();i++){
s[i]='9';
}
return stoi(s);
}
};

除此之外，你还需要掌握函数名及手写它们：

to_string()

std::string my_to_string(int num){
bool isNegative=false;
std::string str;
if(num==0) return "0";
if(num<0){
isNegative=true;
num*=-1;
}
while(num>0){
//不知道+'0'和减'0'有什么区别，还是写+吧。
str+=(num%10)+'0';
num/=10;
}
if(isNegative) str+='-';
reverse(str.begin(),str.end());
return str;
}

stroi()

int my_stoi(std::string str){
int result=0;
bool isNegative=false;
int i=0;
if(str[0]=='-'){
isNegative=true;
i=1;
}
for(;i<str.size();i++){
if(str[i]<'0'||str[i]>'9'){
throw std::invalid_argument("Invalid input string");
}
//记住这句模版
result=result*10+(str[i]-'0');
}
if(isNegative) result*=-1;
return result;
}

stol

968监控二叉树,困难

看代码随想录题解过的：

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int result=0;
int getres(TreeNode* root){
//递归终止逻辑
if(root==nullptr) return 2;
int l=getres(root->left);
int r=getres(root->right);
if(l==2&&r==2) return 0;
if(l==0||r==0){
result++;
return 1;
}
if(l==1||r==1){
return 2;
}
return -1;
}
int minCameraCover(TreeNode* root) {
if(getres(root)==0) result++;
return result;
}
};