LeetCode 1963. Minimum Number of Swaps to Make the String Balanced
2022/5/1 6:12:52
本文主要是介绍LeetCode 1963. Minimum Number of Swaps to Make the String Balanced,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
原题链接在这里:https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/
题目:
You are given a 0-indexed string s
of even length n
. The string consists of exactly n / 2
opening brackets '['
and n / 2
closing brackets ']'
.
A string is called balanced if and only if:
- It is the empty string, or
- It can be written as
AB
, where bothA
andB
are balanced strings, or - It can be written as
[C]
, whereC
is a balanced string.
You may swap the brackets at any two indices any number of times.
Return the minimum number of swaps to make s
balanced.
Example 1:
Input: s = "][][" Output: 1 Explanation: You can make the string balanced by swapping index 0 with index 3. The resulting string is "[[]]".
Example 2:
Input: s = "]]][[[" Output: 2 Explanation: You can do the following to make the string balanced: - Swap index 0 with index 4. s = "[]][][". - Swap index 1 with index 5. s = "[[][]]". The resulting string is "[[][]]".
Example 3:
Input: s = "[]" Output: 0 Explanation: The string is already balanced.
Constraints:
n == s.length
2 <= n <= 106
n
is even.s[i]
is either'['
or']'
.- The number of opening brackets
'['
equalsn / 2
, and the number of closing brackets']'
equalsn / 2
.
题解:
Disregard all the solid pairs.
Find out the number of unsolid pairs count.
The minimum swap number is the ceiling of count/2.
Time Complexity: O(n). n = s.length().
Space: O(1).
AC Java:
1 class Solution { 2 public int minSwaps(String s) { 3 if(s == null || s.length() == 0){ 4 return 0; 5 } 6 7 int count = 0; 8 for(int i = 0; i < s.length(); i++){ 9 char c = s.charAt(i); 10 if(c == '['){ 11 count++; 12 }else if(count > 0){ 13 count--; 14 } 15 } 16 17 return (count + 1) / 2; 18 } 19 }
类似Minimum Add to Make Parentheses Valid, Minimum Remove to Make Valid Parentheses.
这篇关于LeetCode 1963. Minimum Number of Swaps to Make the String Balanced的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!
- 2024-05-08今天开始程序员不用再发愁写commit message了,全部由CodeGeeX自动完成!