牛客NC52 有效括号序列【简单 栈 C++/Java/Go/PHP】

题目

题目链接：
https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2

核心

 栈的思想
1

参考答案C++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return bool布尔型
     */
    bool isValid(string s) {
        //本答案用vector模拟栈
        vector<char> stack(s.size());
        int idx = 0;
        for (int i = 0; i < s.size(); i++) {
            char c = s[i];
            if (c == '(' || c == '[' || c == '{') {
                stack[idx++] = c;
            } else {
                char pop = '1';
                if (idx > 0) {
                    pop = stack[--idx];
                }

                if (c == ')' && pop != '(') return false;
                if (c == ']' && pop != '[') return false;
                if (c == '}' && pop != '{') return false;
            }
        }
        if (idx > 0) return false;
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

参考答案Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        //栈,本答案用数组模拟栈
        //Stack<Character> stack = new Stack<>();
        char[] arr = new char[s.length()];
        int idx = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c == '(' || c == '[' || c == '{') {
                //stack.add(c);
                arr[idx++] = c;
            } else {
                //char pop = stack.pop();
                char pop = idx>0 ? arr[--idx]:'1';
                if (c == ')' && pop != '(') return false;
                if (c == ']' && pop != '[') return false;
                if (c == '}' && pop != '{') return false;
            }
        }
        //if(stack.size()>0) return false;
        if (idx > 0) return false;
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

参考答案Go

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param s string字符串
 * @return bool布尔型
 */
func isValid(s string) bool {
	//栈，本答案用切片模拟栈
	stack := make([]byte, len(s))
	idx := 0

	for i := 0; i < len(s); i++ {
		c := s[i]
		if c == '(' || c == '[' || c == '{' {
			stack[idx] = c
			idx++
		} else {
			var pop byte = '1'
			if idx > 0 {
				idx -= 1
				pop = stack[idx]
			}

			if c == ')' && pop != '(' {
				return false
			}

			if c == ']' && pop != '[' {
				return false
			}

			if c == '}' && pop != '{' {
				return false
			}
		}
	}

	if idx > 0 {
		return false
	}

	return true
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

参考答案PHP

<?php


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return bool布尔型
 */
function isValid( $s )
{
    //本答案用数组模拟栈
    $stack = [];
    $idx=0;
    for($i=0;$i<strlen($s);$i++){
        $c = $s[$i];

        if($c=='(' || $c =='[' || $c =='{'){
            $stack[$idx++] = $c;
        }else{
            $pop = '1';
            if($idx>0){
                $idx--;
                $pop=$stack[$idx];
            }

            if($c ==')' && $pop!='(') return false;
            if($c ==']' && $pop!='[') return false;
            if($c =='}' && $pop!='{') return false;
        }
    }
    if($idx >0) return false;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35