1、有效的括号
(1)题目描述以及输入输出
( 1 ) 题目描述:
给定一个只包括 '(' ,')' ,'{' ,'}' ,'[' ,']' 的字符串 s ,判断字符串是否有效。( 2 ) 输入输出描述:
输入:s = "()"
输出:true关键思路:
遍历字符串,如果是左括号就将对应的右括号入栈
如果是右括号,假如栈为空或者与栈顶元素不匹配,则认为不匹配,否则出战匹配成功
遍历完,栈为空则匹配
(2)代码块
class Solution {
public : bool isValid ( string s) { stack< int > sta; if ( s. size ( ) % 2 != 0 ) return false ; for ( int i = 0 ; i < s. size ( ) ; i++ ) { if ( s[ i] == '(' ) sta. push ( ')' ) ; else if ( s[ i] == '[' ) sta. push ( ']' ) ; else if ( s[ i] == '{' ) sta. push ( '}' ) ; else if ( sta. empty ( ) || s[ i] != sta. top ( ) ) return false ; else sta. pop ( ) ; } return sta. empty ( ) ; }
} ;
2、字符串解码
(1)题目描述以及输入输出
( 1 ) 题目描述:
给定一个经过编码的字符串,返回它解码后的字符串。( 2 ) 输入输出描述:
输入:s = "3[a]2[bc]"
输出:"aaabcbc" 关键思路:
( 1 ) 碰到数字,num记录
( 2 ) 碰到字符,res记录
( 3 ) 碰到‘[ ’,num和res进栈
( 4 ) 碰到‘] ’,取出栈顶数字,将res以倍数形式追加到栈顶字符串
(2)代码块
class Solution {
public : string decodeString ( string s) { int num = 0 ; string res = "" ; stack< int > nums; stack< string> str; for ( int i = 0 ; i< s. size ( ) ; i++ ) { if ( s[ i] >= '0' && s[ i] <= '9' ) num = s[ i] - '0' ; else if ( ( s[ i] >= 'a' && s[ i] <= 'z' ) || ( s[ i] >= 'A' && s[ i] <= 'Z' ) ) res = res + s[ i] ; else if ( s[ i] == '[' ) { nums. push ( num) ; num = 0 ; str. push ( res) ; res = "" ; } else if ( s[ i] == ']' ) { int times = nums. top ( ) ; nums. pop ( ) ; for ( int i = 0 ; i< times; i++ ) { str. top ( ) += res; } res = str. top ( ) ; str. pop ( ) ; } } return res; }
} ;
3、每日温度
(1)题目描述以及输入输出
( 1 ) 题目描述:
给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[ i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。( 2 ) 输入输出描述:
输入: temperatures = [ 73,74 ,75,71,69,72,76,73]
输出: [ 1,1 ,4,2,1,1,0,0] 关键思路:
暴力循环
(2)代码块
# include <vector> class Solution {
public : vector< int > dailyTemperatures ( vector< int > & temperatures) { int n = temperatures. size ( ) ; vector< int > result ( n, 0 ) ; for ( int i = 0 ; i < n; i++ ) { for ( int j = i + 1 ; j < n; j++ ) { if ( temperatures[ j] > temperatures[ i] ) { result[ i] = j - i; break ; } } } return result; }
} ;