当前位置:网站首页>926. 将字符串翻转到单调递增
926. 将字符串翻转到单调递增
2022-06-11 22:16:00 【彼淇梁】
926. 将字符串翻转到单调递增【中等题】【每日一题】
思路:
【动态规划】
参考官解代码,并将解题思路写在注释里。
代码:
class Solution {
public int minFlipsMonoIncr(String s) {
int n = s.length();
//dp0和dp1分别表示当前下标i对应的字符翻转为0和1的情况下,使子串[0,i]递增的最小翻转次数,初值均为0
int dp0 = 0,dp1 = 0;
for (int i = 0; i < n; i++) {
//dp1的含义是,将i位置字符翻转为1时,保证子串[0,i]递增的最小翻转次数,但将i位置翻转为1有两种情况:i-1位置为 0 或者 为1
//因此,为了保证翻转次数最小,将dp1更新为dp0和dp1的较小值
dp1 = Math.min(dp0,dp1);
//取出当前下标i位置的字符
char c = s.charAt(i);
//如果当前实际字符是1,那么将其翻转为0后,dp0++,将其翻转为1后,dp1不变
if (c == '1'){
dp0++;
}else {
//如果当前实际字符是0,那么将其翻转为0,dp0不变,将其翻转为1,dp1++
dp1++;
}
}
//此时的dp0和dp1表示的是 将字符串s最后一个字符翻转为0或者翻转为1,使得整个子串保持递增的最小累计翻转次数,返回两者之间的较小值即可
return Math.min(dp0,dp1);
}
}
边栏推荐
猜你喜欢

How to view computer graphics card information in win11

Top - K problem

Daily question - Roman numeral to integer

Prefabricated dishes in the trillion market have also begun to roll inside. How can brands stand out in the fierce competition?

R语言书籍学习03 《深入浅出R语言数据分析》-第七章 线性回归模型

Explain asynchronous tasks in detail: the task of function calculation triggers de duplication

Popular science | what are the types of NFT (Part 1)

R语言相关文章、文献整理合集(持续更新)

Maze problem in C language

什么是死锁?(把死锁给大家讲明白,知道是什么,为什么用,怎么用)
随机推荐
Xshell不小心按到ctrl+s造成页面锁定的解决办法
SVN本地部署server和cleint 并用阿里云盘自动备份
Are you still using localstorage directly? It's time to raise the bar
[academic related] under the application review system, how difficult is it to study for a doctoral degree in a double first-class university?
Conception du Processeur superscalaire Yao yongbin chapitre 2 cache - - sous - section 2.4 extrait
Analysis of the implementation principle of an open source markdown to rich text editor
MATLAB点云处理(二十五):点云生成 DEM(pc2dem)
The device is in use when win10 ejects USB
一款开源的Markdown转富文本编辑器的实现原理剖析
Tkinter学习笔记(四)
One question of the day - delete duplicates of the ordered array
MATLAB点云处理(二十四):点云中值滤波(pcmedian)
Superscalar processor design yaoyongbin Chapter 2 cache -- Excerpt from subsection 2.3
Maze problem in C language
Superscalar processor design yaoyongbin Chapter 2 cache -- Excerpt from subsection 2.2
Dynamic memory management (1)
还在直接用 localStorage 么?该提升下逼格了
Unity3D getLaunchIntentForPackage 获取包返回null问题
3.2 naming rules of test classes
inner join执行计划变了