百度二面算法:合法的括号字符串(贪心解法)
目录标题
- 1.题目
- 1.1示例
- 2.利用贪心算法求解
- 2.1 代码结构分析
- 2.1.1 代码优缺点
- 2.1.2 星号的角色分析
- 2.1.2.1 处理星号的逻辑
- 2.1.2.2 整体逻辑
- 2.1.2.3 代码逻辑总结
- 2.2 贪心的策略体现
- 2.2.1 贪心策略的应用
1.题目
给定一个字符串s,字符串s只包含以下三种字符: (,*,),请你判断 s是不是一个合法的括号字符串。合法括号字符串有如下规则:
- 左括号’(‘必须有对应的右括号’)’
- 右括号’)‘必须有对应的左括号’(’
- 左括号必须在对应的右括号前面
- *可以视为单个左括号,也可以视为单个右括号,或者视为一个空字符
5.空字符串也视为合法的括号字符串
1.1示例
示例1
输入:"()()"
返回值:true
示例2
输入:"((*)"
返回值:true
示例3
输入:"(((*)"
返回值:false
2.利用贪心算法求解
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param s string字符串* @return bool布尔型*/public boolean isValidString (String s) {//待消除左括号的最小个数int minCount=0;//待消除左括号的最大个数int maxCount=0;int n=s.length(