Java移除无效括号的方法实现

目录
  • 一、题目
  • 二、示例
  • 三、解法1
  • 四、解法2

一、题目

给你一个由 ‘('、')' 和小写字母组成的字符串 s。

你需要从字符串中删除最少数目的 ‘(' 或者 ‘)' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。

有效「括号字符串」应当符合以下 任意一条 要求：

空字符串或只包含小写字母的字符串
可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」

二、示例

))((  -》  

(leetode  -》  leetode
leetode)  -》  leetode

(lee(to)de  -》  lee(to)de
lee(to)de)  -》  lee(to)de

(lee(t(c)o)de  -》  lee(t(c)o)de
lee(t(c)o)de)  -》  lee(t(c)o)de

三、解法1

public class Test {

 public static void main(String[] args) {
  String s1 = "))((";
  System.out.println(s1 + "  -》  " + minRemoveToMakeValid(s1));

  String s2 = "(leetode";
  System.out.println(s2 + "  -》  " + minRemoveToMakeValid(s2));

  String s3 = "leetode)";
  System.out.println(s3 + "  -》  " + minRemoveToMakeValid(s3));

  String s4 = "(lee(to)de";
  System.out.println(s4 + "  -》  " + minRemoveToMakeValid(s4));

  String s5 = "lee(to)de)";
  System.out.println(s5 + "  -》  " + minRemoveToMakeValid(s5));

  String s6 = "(lee(t(c)o)de";
  System.out.println(s6 + "  -》  " + minRemoveToMakeValid(s6));

  String s7 = "lee(t(c)o)de)";
  System.out.println(s7 + "  -》  " + minRemoveToMakeValid(s7));
 }

 public static String minRemoveToMakeValid(String str) {
  // 初始化"("和")"的个数为0
  int left = 0;
  int right = 0;

  // 将字符串转换为char数组
  char[] chars = str.toCharArray();

  // 从左到右标记多余的")"右括号
  for (int i = 0; i < chars.length; i++) {
   if (chars[i] == '(') {
    left++;
   } else if (chars[i] == ')') {
    right++;
   }

   if (right > left) {
    chars[i] = '#';

    left = right = 0;
   }
  }

  left = right = 0;

  // 从右到左标记多余的"("左括号
  for (int i = chars.length - 1; i >= 0; i--) {
   if (chars[i] == '(') {
    left++;
   } else if (chars[i] == ')') {
    right++;
   }

   if (right < left) {
    chars[i] = '#';

    left = right = 0;
   }
  }

  return String.valueOf(chars).replaceAll("#", "");
 }
}

四、解法2

Stack.peek 与Sstack.pop 的区别

  • 相同点：大家都返回栈顶的值。
  • 不同点：peek 不改变栈的值(不删除栈顶的值)，pop会把栈顶的值删除。
public class Test {

 public static void main(String[] args) {
  String s1 = "))((";
  System.out.println(s1 + "  -》  " + minRemoveToMakeValid(s1));

  String s2 = "(leetode";
  System.out.println(s2 + "  -》  " + minRemoveToMakeValid(s2));

  String s3 = "leetode)";
  System.out.println(s3 + "  -》  " + minRemoveToMakeValid(s3));

  String s4 = "(lee(to)de";
  System.out.println(s4 + "  -》  " + minRemoveToMakeValid(s4));

  String s5 = "lee(to)de)";
  System.out.println(s5 + "  -》  " + minRemoveToMakeValid(s5));

  String s6 = "(lee(t(c)o)de";
  System.out.println(s6 + "  -》  " + minRemoveToMakeValid(s6));

  String s7 = "lee(t(c)o)de)";
  System.out.println(s7 + "  -》  " + minRemoveToMakeValid(s7));
 }

 public static String minRemoveToMakeValid(String str) {
  // 记录要删除括号的下标，然后从后往前删除坐标
  StringBuffer result = new StringBuffer(str);

  Stack<Integer> stack = new Stack<>();
  ArrayList<Integer> deleteRes = new ArrayList<>();

  for (int i = 0; i < str.length(); i++) {
   if (str.charAt(i) == '(') {
    stack.push(i);
   } else if (str.charAt(i) == ')') {
    if (stack.empty()) {
     deleteRes.add(i);
    } else if (str.charAt(stack.peek()) == '(') {
     stack.pop();
    }
   }
  }

  while (!stack.empty()) {
   int temp = stack.peek();
   stack.pop();
   deleteRes.add(0, temp);
  }

  deleteRes.sort(Integer::compareTo);

  for (int i = deleteRes.size() - 1; i >= 0; i--) {
   result.deleteCharAt(deleteRes.get(i));
  }

  return result.toString();
 }
}

到此这篇关于Java移除无效括号的方法实现的文章就介绍到这了,更多相关Java移除无效括号内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • JAVA中使用双括号来初始化静态常量的小技巧

    这貌似是个不为人知的语言技巧.我看到一般人写Java里初始化静态常量都是 复制代码 代码如下: public static final Map<String, String> DATA = new TreeMap<String, String>(); static{ DATA.put("a", "A"); //blah blah blah} 使用所在类的static块来初始化DATA,其实还有另外一种写法: 复制代码 代码如下: public

  • Java Json字符串的双引号("")括号如何去掉

    我就废话不多说了,大家还是直接看代码吧~ //自己copy试一下比什么都好 public static void main(String[] args) { String json = "[\"name\":\"value\",\"value1\"]"; String t = json.replaceAll("\\\"",""); System.out.println(&quo

  • java括号匹配算法求解（用栈实现）

    如何使用栈来判定括号是否匹配 对于给定的表达式,可以使用栈来实现括号匹配判定,这个算法在编译器中非常重要,解析器每次读入 一个字符,如果字符是一个开分隔符,如(,[,{,入栈,若读入的是闭分隔符),],},出栈,如果两者匹配,继续解析字符串,如果不匹配,解析器错误 算法思路 1.创建一个栈 2.当(当前字符不等于输入的结束字符) (1)如果当前字符不是匹配的字符,判断栈内是否为空,如果栈为空,括号必然不完整 (2)如果字符是一个开分隔符,那么将其入栈 (3)如果字符是一个闭分隔符,,且栈不为空,

  • Java List集合返回值去掉中括号(''[ ]'')的操作

    如下所示: 调用StringUtils工具类的strip()方法去掉中括号"[ ]": StringUtils.strip(word.toString(),"[]") //第一个参数放集合,第二个参数去掉中括号"[]" StringUtils工具类代码: package com.ktamr.common.utils; import com.ktamr.common.core.text.StrFormatter; import java.util.

  • Java栈的应用之括号匹配算法实例分析

    本文实例讲述了Java栈的应用之括号匹配算法.分享给大家供大家参考,具体如下: 1.LeetCode官网 美网:https://leetcode.com/ 中文网 :https://leetcode-cn.com/ 英语不咋地,所以选择此处选择中文网来进行测试. 2.LeetCode中获取第20号题目 (1)搜索20号题目 (2)查看题目 (3)根据题目要求,首先在本地编辑器中完善20号题目的代码--使用java提供的Stack类,代码如下: class Solution { public bo

  • Java正则提取中括号中的内容操作示例

    本文实例讲述了Java正则提取中括号中的内容操作.分享给大家供大家参考,具体如下: 曾经在工作中遇到一个问题,就是需要提取字符串中每一个中括号里的内容,在网上搜了一下,发现用正则表达式可以提取中括号中的内容,具体实现如下: import java.util.ArrayList; import java.util.List; import java.util.regex.Matcher; import java.util.regex.Pattern; public class ExtractMes

  • Java移除无效括号的方法实现

    目录 一.题目 二.示例 三.解法1 四.解法2 一.题目 给你一个由 '('.')' 和小写字母组成的字符串 s. 你需要从字符串中删除最少数目的 '(' 或者 ')' (可以删除任意位置的括号),使得剩下的「括号字符串」有效. 有效「括号字符串」应当符合以下 任意一条 要求: 空字符串或只包含小写字母的字符串 可以被写作 AB(A 连接 B)的字符串,其中 A 和 B 都是有效「括号字符串」 可以被写作 (A) 的字符串,其中 A 是一个有效的「括号字符串」 二.示例 ))(( -> (le

  • java实现文件变化监控的方法(推荐)

    一. spring配置文件:application.xml <?xml version="1.0" encoding="UTF-8"?> <beans xmlns="http://www.springframework.org/schema/beans" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:tx="http://ww

  • java实现清理DNS Cache的方法

    本文实例讲述了java实现清理DNS Cache的方法.分享给大家供大家参考.具体分析如下: 一.测试环境 OS:Windows7 x64 JDK:1.6.0_45 二.本人找到四种方式清理jvm的DNS缓存,大家可以根据自己的情况选用. 1. 在首次调用InetAddress.getByName()前,设置java.security.Security.setProperty("networkaddress.cache.ttl", "0"); 2. 修改jre/li

  • java arrayList遍历的四种方法及Java中ArrayList类的用法

    java arrayList遍历的四种方法及Java中ArrayList类的用法 package com.test; import java.util.ArrayList; import java.util.Iterator; import java.util.List; public class ArrayListDemo { public static void main(String args[]){ List<String> list = new ArrayList<String

  • Java使用代理进行网络连接方法示例

    需求是这样的: 一.界面上要有这样几种代理类型可以选. 1.HTTP代理 2.Socks代理 3.不使用代理(直连) 4.使用浏览器设置(浏览器也是HTTP.Socks.直连三种). 可参考QQ登录设置里的代理能,其实跟qq的代理功能是一样的. 二.测试使用所填写的代理配置信息是否可连接 三.记录用户上次选择的代理配置,默认使用用户上次使用的代理配置进行网络连接. 程序运行环境是WindowsXP.Windows7.Windows8系统. 使用的技术为Java7,Swing,CXF. 难点: 1

  • js 动态给元素添加、移除事件的实现方法

    最近项目中要要到 js动态给给元素绑定事件,刚好之前没用到过这些,顺便学习一下,于是google了一下 事件,写了如下两个事件 一个添加事件 ,一个是移除事件 /addEventListener(),removeEventListener()用于处理指定和删除事件处理程序的操作 //作用域:事件处理程序会在其所属元素的作用域内运行 //addEventListener(event,function,capture/bubble);removeEventListener(event,functio

  • Java一些常见的出错异常处理方法总结

    Java一些常见的出错异常处理方法总结

    一些平时常见的错误及解决办法,我 是新手,每次遇到的错误都记录了下来. 1. 404错误 description The requested resource (/Struts2_0100_Introduction/hello.action) is not available. 先检查Manager Deployments,使之能打开(出现NullPointerException不能打开),主要是服务器在每次允许前备份,再修改了错误后不能及时更正.(如果是勾选的Backup,要改成delete)

  • Java获取随机数的3种方法

    主要介绍了Java获取随机数的3种方法,主要利用random()函数来实现 方法1 (数据类型)(最小值+Math.random()*(最大值-最小值+1))例: (int)(1+Math.random()*(10-1+1)) 从1到10的int型随数 方法2 获得随机数 for (int i=0;i<30;i++) {System.out.println((int)(1+Math.random()*10));} (int)(1+Math.random()*10) 通过java.Math包的ra

  • Java集合Iterator迭代的实现方法

    我们常常使用 JDK 提供的迭代接口进行 Java 集合的迭代. Iterator iterator = list.iterator(); while(iterator.hasNext()){ String string = iterator.next(); //do something } 迭代其实我们可以简单地理解为遍历,是一个标准化遍历各类容器里面的所有对象的方法类,它是一个很典型的设计模式.Iterator 模式是用于遍历集合类的标准访问方法.它可以把访问逻辑从不同类型的集合类中抽象出来

  • Java 中运行字符串表达式的方法

    在日常的开发中,偶尔会遇到运行字符串表达式的情况,通常这样的需求会对需求进行进一步分析,然后进行进一步 "特殊化",最后直接写到硬代码中,这样做的话,就不太好扩展了:也有另外的处理方式是采用 Java 内置的 JavaScript 引擎等运行字符串表达式,但是内置引擎也有弊端,比如频繁运行片段式的字符串的效率非常低,并且与 Java 之间的数据交互比较麻烦,于是,便产生了写一个"字符串表达式计算引擎"的想法... 写的过程其实没想象中那么麻烦,最初版大概在今年 5

随机推荐