目录
423.有效的括号序列
题目详情：
给定一个字符串所表示的括号序列，包含以下字符：?'(', ')',?'{',?'}',?'['?and?']'， 判定是否是有效的括号序列。括号必须依照?"()"?顺序表示，?"()[]{}"?是有效的括号，但?"([)]"?则是无效的括号。
解题思路：
通过一个栈来放左边的括号，在与右边进行判断。
1、先写一个函数 用来判断左边括号必须与右边括号同时在一起
2、创建一个空栈，遍历字符串，如果为左边的括号，则将其放进栈中，在下一个遍历时就会进行判断，如果不符合 直接返回错误，如果匹配了一对符号后，需将之前栈中的左边括号删除，既出栈。这样循环即可判断。
源代码：
class Solution {
public:
/**
* @param s: A string
* @return: whether the string is a valid parentheses
*/
bool match(char a,char b){
return (a == '('&&b == ')'||(a == '['&& b == ']')|| (a == '{' && b == '}'));
}
bool isValidParentheses(string &s) {
// write your code here
stack<char>st;
for(int i =0;i < s.size();++i){
if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
if (st.empty() || !match(st.top(), s[i])) {
return false;
}
st.pop();
} else {
st.push(s[i]);
}
}
return st.empty();
}
};
?263.小括号匹配
题目详情：
给定一个字符串所表示的括号序列，包含以下字符：?'(', ')'， 判定是否是有效的括号序列。
括号必须依照?"()"?顺序表示，?"()"?是有效的括号，但?")("?则是无效的括号。
解题思路：?
思路：与上面的题大致相同，通过将将左边括号放在一个栈中，与之判断，但在这里的要求并不是左边与右边必须在一起，而是有与之相对应的右边括号，例如（（）），所以在这道题中，需要得到一个左边括号就将其放入栈中，然后直接用if进行判断，因为只有两个符号，不是左边就是右边，所以在这个题中，没有在定义函数来判断。
源代码：
class Solution {
public:
/**
* @param string: A string
* @return: whether the string is a valid parentheses
*/
bool matchParentheses(string &string) {
// write your code here
std::stack<char> xx;
if (string[0] == ')') return false;
else xx.push(string[0]);
for (int i = 1; i < string.size(); i++) {
if (string[i] == '(') {
xx.push(string[i]);
} else {
if (!xx.empty()) {
xx.pop();
} else{
return false;
}
}
}
return true;
}
};768.杨辉三角
题目描述：
给一整数?n, 返回杨辉三角的前?n 行
杨辉三角：
?解决思路：
先定义一个二维数组：
?vector<vector<int>>a;
第一步，令第一个数与最后一个数都为1，
第二步，令除了1之外的数都为它上面的两个数之和。
三个循环，
在**for (int i = 0; i < n; i++)这个大循环下**，有两个小循环，for (int j = 0; j < i + 1; j++)<这个循环中，将最后一列变为1，这时候第一位和最后一位都为1，因为一个数组的循环也是从1开始 temp.push_back(1)
? ? ? ? ? ?for (int j = 1; j < i; j++)<这个循环中将除了1之外的数的值变为上面两个数的和temp[j]=(a[i - 1][j - 1] + a[i - 1][j]);>
最后做完一个循环便拥有一个数组，将这个数组传给二维数组a
a.push_back(temp);
一个temp数组代表一行，在第一个大循环下，i<n次循环，就有前n行数组，最后返回数组a。
源代码：
class Solution {
public:
/**
* @param n: a Integer
* @return: the first n-line Yang Hui's triangle
*/
vector<vector<int>> calcYangHuisTriangle(int n) {
// write your code here
vector<vector<int>>a;
for (int i = 0; i < n; i++)
{
vector<int> temp;
for (int j = 0; j < i + 1; j++)
{
temp.push_back(1);//在Vector最后添加一个元素（参数为要插入的值），即在每一列的最后为1
}
for (int j = 1; j < i; j++)
{
temp[j]=(a[i - 1][j - 1] + a[i - 1][j]);
}
a.push_back(temp);
}
return a;
}
};