题目
题目链接:
https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2
核心
栈的思想
参考答案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;
}
};
参考答案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;
}
}
参考答案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
}
参考答案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;
}