题目描述

给定一个括号序列（可能非法），求能否通过移动最多一个字符，使得括号序列合法。

如果s为合法的括号序列，那么：

1. s 为空
2. s 为 "(t)"，且t为合法的括号序列
3. s 为 "t1t2"，且t1和t2为合法的括号序列

思路

1. 首先，判断一个括号序列是否合法，只需要从前往后遍历整个括号序列，同时维护一个计数器，遇到 '(' 计数器加1，遇到 ')' 计数器减 1。如果整个过程中计数器的数值为正数，且遍历完成后计数器的值为0，那么该括号序列合法；
2. 贪心的考虑，一方面，'(' 越靠前越好（整个遍历过程中计数器前面的数值会尽可能的大），另一方面，如果需要移动括号，要么将'('往前移动，要么是')'往后移动。如果某种情形下前一种方案可行，那么后一种方案也可行。如果 ')' 往后移动，可以直接移动到序列最后面（此为最优移动方案）；
3. 注意不需要移动括号的情况。

根据上述的分析，可以写出如下的代码。

代码 (Golang)

package main
 
import "fmt"
 
func main() {
    n := 0;
    name := "";
    fmt.Scanf("%d\n", &n);
    fmt.Scanf("%s\n", &name);
 
    op := 0;
    acc := 0;
    ok := true;
    for i:= 0; i < n; i++ {
        if name[i] == '(' {
            acc ++;
        } else {
            if acc == 0 {
                if op == 0 {
                    op = 1;
                } else {
                    ok = false;
                }
            } else {
                acc --;
            }
        }
    }
 
    acc -= op;
    if ok && acc == 0 {
        fmt.Printf("Yes");
    } else {
        fmt.Printf("No");
    }
}

有疑问加站长微信联系（非本文作者）