百度二面算法：合法的括号字符串（贪心解法）

目录标题

• 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是不是一个合法的括号字符串。合法括号字符串有如下规则:

1. 左括号’(‘必须有对应的右括号’)’
2. 右括号’)‘必须有对应的左括号’(’
3. 左括号必须在对应的右括号前面
4. *可以视为单个左括号，也可以视为单个右括号，或者视为一个空字符
   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(