当前位置:网站首页>1529. Minimum number of suffix flips
1529. Minimum number of suffix flips
2022-07-06 16:08:00 【mrbone9】
Address :
Power button https://leetcode-cn.com/problems/minimum-suffix-flips/
subject :
Give you a length of n 、 Subscript from 0 Starting binary string target . You have another length of n Binary string of s , At first, everyone was 0 . You want to make s and target equal .
In one step , You can choose the subscript i(0 <= i < n) And flip on Closed interval [i, n - 1] All bits in . Flipping means '0' Turn into '1' , and '1' Turn into '0' .
Return to make s And target Equal the minimum number of flips required .
Example 1:
Input :target = "10111" Output :3 explain : first ,s = "00000" . Select subscript i = 2: "00000" -> "00111" Select subscript i = 0: "00111" -> "11000" Select subscript i = 1: "11000" -> "10111" To achieve the goal , You need at least 3 Time flip . |
Example 2:
Input :target = "101" Output :3 explain : first ,s = "000" . Select subscript i = 0: "000" -> "111" Select subscript i = 1: "111" -> "100" Select subscript i = 2: "100" -> "101" To achieve the goal , You need at least 3 Time flip . |
Example 3:
Input :target = "00000" Output :0 explain : because s Already equal to the goal , So no operation is required |
Tips :
n == target.length 1 <= n <= 105 target[i] by '0' or '1' |
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/minimum-suffix-flips
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Ideas :
First of all, flip the figure under the hand animation , Finding the law
such as :10111
00000
00111
01000
10111
If you can't see clearly for the time being , On the contrary, you can see clearly , Change the topic to how to change a string into 0 The number of times
Then from left to right , We saw 1, You have to do a flip , Then next , It happens to be in reverse order
But how to implement the code ? A little bit of a problem
Then watch , If the intermediate element is adjacent and of the same type , Such as fellow 1, Or both 0
When we flip, we actually flip together , Then we can regard these same types as only one
such as :1010001, Let's reverse the order
1010001 | 0101110 |
0101110 | 0010001 |
0010001 | 0001110 |
0001110 | 0000001 |
0000001 | 0000000 |
After optimization, it is :10101 Flip of
The exact number of flips is Of this string 1 Starting length ,
If it is 0 Opening remarks :00110, In fact, it is seen as 10, The length is 2
If you don't believe it, you can try
When such a rule is found, it is much easier to implement the code
Method 1 、 Count the number of strings
int minFlips(char * target){
char *s = target;
int cnt = 0;
int i =0;
char prev = '0';
while(s[i])
{
if(s[i] != prev)
{
cnt++;
prev = s[i];
}
i++;
}
return cnt;
}
边栏推荐
- 7-1 懂的都懂 (20 分)
- Luogu P1102 A-B number pair (dichotomy, map, double pointer)
- C language is the watershed between low-level and high-level
- 【高老师UML软件建模基础】20级云班课习题答案合集
- HDU - 6024 Building Shops(女生赛)
- C language learning notes
- 1903. Maximum odd number in string
- [exercise-9] Zombie's Treasury test
- Find 3-friendly Integers
- Truck History
猜你喜欢
Information security - threat detection - Flink broadcast stream broadcaststate dual stream merging application in filtering security logs
Information security - Epic vulnerability log4j vulnerability mechanism and preventive measures
Pyside6 signal, slot
Programmers, what are your skills in code writing?
STM32 learning record: LED light flashes (register version)
PySide6 信号、槽
快速转 TypeScript 指南
Penetration test (3) -- Metasploit framework (MSF)
628. Maximum product of three numbers
Ball Dropping
随机推荐
Analysis of protobuf format of real-time barrage and historical barrage at station B
最全编程语言在线 API 文档
Opencv learning log 24 -- Hough transform 2 (maximum interval and minimum length can be limited)
Opencv learning log 13 corrosion, expansion, opening and closing operations
Penetration testing (5) -- a collection of practical skills of scanning King nmap and penetration testing tools
渗透测试 2 --- XSS、CSRF、文件上传、文件包含、反序列化漏洞
Interesting drink
mysql导入数据库报错 [Err] 1273 – Unknown collation: ‘utf8mb4_0900_ai_ci’
Analyse du format protobuf du rideau en temps réel et du rideau historique de la station B
China exterior wall cladding (EWC) market trend report, technical dynamic innovation and market forecast
1903. Maximum odd number in string
【练习-10】 Unread Messages(未读消息)
C basic grammar
JS调用摄像头
Nodejs crawler
对iptables进行常规操作
Opencv learning log 16 paperclip count
Information security - Analysis of security orchestration automation and response (soar) technology
Information security - threat detection engine - common rule engine base performance comparison
Penetration test (4) -- detailed explanation of meterpreter command