leetcode每日一题:使字符串平衡的最小交换次数
引言
今天开始,打算做一个新的系列:leetcode每日一题的题解。预期每天用90分钟的时间,去写一篇当天的每日一题的题解,这个目标跟早起结合在一起,才有足够的时间完成。其实早在前几年,就开始断断续续做leetcode的每日一题,但每次连续坚持的时间都不长,可能坚持一个多月,就因为各种原因间断了。一鼓作气,再而衰,三而竭。这种需要长期坚持的事情,一旦间断,就很难再继续坚持了。今天选择再出发,先给自己定个小目标:至少坚持100天。
题目
1963. 使字符串平衡的最小交换次数
给你一个字符串 s
,下标从 0 开始 ,且长度为偶数 n
。字符串 恰好 由 n / 2
个开括号 '['
和 n / 2
个闭括号 ']'
组成。
只有能满足下述所有条件的字符串才能称为 平衡字符串 :
-
字符串是一个空字符串,或者
-
字符串可以记作
AB
,其中A
和B
都是 平衡字符串 ,或者 -
字符串可以写成
[C]
,其中C
是一个 平衡字符串 。
你可以交换 任意 两个下标所对应的括号 任意 次数。
返回使 s
变成 平衡字符串 所需要的 最小 交换次数。
示例 1:
输入:s = "][][" 输出:1 解释:交换下标 0 和下标 3 对应的括号,可以使字符串变成平衡字符串。 最终字符串变成 "[[]]" 。
示例 2:
输入:s = "]]][[[" 输出:2 解释:执行下述操作可以使字符串变成平衡字符串: - 交换下标 0 和下标 4 对应的括号,s = "[]][][" 。 - 交换下标 1 和下标 5 对应的括号,s = "[[][]]" 。 最终字符串变成 "[[][]]" 。
示例 3:
输入:s = "[]" 输出:0 解释:这个字符串已经是平衡字符串。
提示:
-
n == s.length
-
2 <= n <= 106
-
n
为偶数 -
s[i]
为'['
或']'
-
开括号
'['
的数目为n / 2
,闭括号']'
的数目也是n / 2
思路
题目中描述的“平衡字符串”,其实可以用一句话来概括:合法的括号。即对于每个右括号而言,都可以在它的左侧找到唯一的一个只匹配给它的左括号。
栈
提到合法的括号,很多同学第一反应就是栈。我们在判断一个字符串是否是合法的括号,就是栈的做法:
-
遇到左括号,压栈
-
遇到右括号,出栈,如果栈为空,那么此时肯定不是合法的括号
不过本题有一些差异,并不是要判断这个字符串是不是合法的括号,而是要求出,最小交换几对,使得这个字符串变成合法的括号。所以,我们这里处理上,也有一些小差异:可以把压栈和出栈的操作看到最合法括号的对消,类似消消乐,那么当我们遇到当前是右括号且空栈的情况下,没有左侧括号可以匹配,可以把这个单独的右括号记录下来。由于整体来看,左右括号的数量必然是相等的,所以我们把合法的括号都消除后,留下来的必然是这样的形式:“]]]...[[[”,k个']'开头,后面跟着k个‘[’。不难想到,我们拿最前面的(k+1)/2
个右括号‘]’去跟最后面的(k+1)/2
个左括号‘[’交换后,整个字符串就是合法的括号了。
图解
代码
public int minSwaps0(String s) { int right = 0; Stack<Character> stack = new Stack<>(); for (char c : s.toCharArray()) { if (c == '[') { stack.push(c); } else if (c == ']') { if (!stack.isEmpty()) { stack.pop(); } else { right++; } } } return (right + 1) >> 1; }
注意:这里最后使用了xxx >> 1
这样的位移操作来代替除以2的操作,是对于整数 乘以2 或者 除以2 运算的常见优化,提高执行效率。
耗时
优化
进一步想,我们这里其实并不需要真正操作压栈和出栈,直接用一个整形变量cnt代替,压栈操作转换为+1,出栈操作转换为-1,判断栈是否为空可以转换为cnt == 0
。
代码
public int minSwaps(String s) { int right = 0; int cnt = 0; for (char c : s.toCharArray()) { if (c == '[') { cnt++; } else if (c == ']') { if (cnt != 0) { cnt--; } else { right++; } } } return (right + 1) >> 1; }