当前位置: 首页 > article >正文

leetcode每日一题:使字符串平衡的最小交换次数

引言

        今天开始,打算做一个新的系列:leetcode每日一题的题解。预期每天用90分钟的时间,去写一篇当天的每日一题的题解,这个目标跟早起结合在一起,才有足够的时间完成。其实早在前几年,就开始断断续续做leetcode的每日一题,但每次连续坚持的时间都不长,可能坚持一个多月,就因为各种原因间断了。一鼓作气,再而衰,三而竭。这种需要长期坚持的事情,一旦间断,就很难再继续坚持了。今天选择再出发,先给自己定个小目标:至少坚持100天。

题目

1963. 使字符串平衡的最小交换次数

给你一个字符串 s下标从 0 开始 ,且长度为偶数 n 。字符串 恰好n / 2 个开括号 '['n / 2 个闭括号 ']' 组成。

只有能满足下述所有条件的字符串才能称为 平衡字符串

  • 字符串是一个空字符串,或者

  • 字符串可以记作 AB ,其中 AB 都是 平衡字符串 ,或者

  • 字符串可以写成 [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;
}
耗时


http://www.kler.cn/a/590674.html

相关文章:

  • 【软件工程】06_软件设计
  • Carto 无尽旅图 for Mac v1.0.7.6 (51528)冒险解谜游戏 支持M、Intel芯片
  • 微软 AI 发布 LongRoPE2:近乎无损地将大型语言模型上下文窗口扩展至 128K 标记,保持 97% 短上下文准确性
  • 14.使用各种读写包操作 Excel 文件:辅助模块
  • APB-清华联合腾讯等机构推出的分布式长上下文推理框架
  • 拦截网页中的 Fetch 和 XMLHttpRequest 请求方式方法
  • 谈谈你对前端工程化的理解,它包含哪些方面
  • 算法基础篇(蓝桥杯常考点)
  • 阿里云、腾讯云云主机如何提升远程桌面安全(VNC登录)
  • Oracle SQL*Loader 与 SQLULDR2 学习指南
  • UART转AHB模块ModelSim仿真
  • Qt 通过MSVC编译运行项目
  • 数据库:一文掌握 PostgreSQL 的各种指令(PostgreSQL指令备忘)
  • Linux环境使用jmeter做性能测试
  • Elastic Stack 8.16.0 日志收集平台的搭建
  • 智能合约:Solidity(基于以太坊或兼容链,如 Polygon、BSC)(仅供学习区块链知识,不可进行违法开发应用)
  • 使用 NetworkX 进行图论分析与可视化
  • 仿RabbitMQ的消息队列
  • hadoop集群配置-整体介绍
  • LSM-Tree(Log-Structured Merge-Tree)详解