栈(Stack)-其他
栈(Stack)
今天的算法内容是：栈
一、 每日一题
- 用栈构建数组
- 这道题的n好像没什么用
- 这道题是单调递增的
- 哈希表：先创建一个哈希表并初始化为0，每一个在target当中出现的数字标记为1
- 先全部’push’一遍，然后哈希表中为0的值’pop’
class Solution {
public:
vector<string> buildArray(vector<int>& target, int n) {
int index = 0;
int limit = target.back();//target的最后一个元素
int hash[101];
memset(hash, 0, sizeof(hash));
vector<string> ret;
for(int i = 0; i < target.size(); ++i) {
hash[target[i]] = 1;
}
for(int i = 1; i <= limit; ++i) {
ret.push_back("Push");
if(!hash[i]) {
ret.push_back("Pop");
}
}
return ret;
}
};
- 删除最外层括号
- 用stktop变量去判断是不是完整的一组括号
- 如果是完整的一组括号，只取内层的括号。内层如果没有就是空字符串
- pre = i+1 跳到下一组括号，再进行判断，最后返回答案
class Solution {
public:
string removeOuterParentheses(string s) {
string ans;
int stktop = 0;
int pre = 0;
for(int i = 0; i < s.size(); ++i) {
if(s[i] == '(') {
++stktop;
}else {
--stktop;
}
//当碰到完整的括号的时候
if(stktop == 0) {
for(int j = pre+1; j <= i-1; ++j) {
ans += s[j];
}
//判断下一组括号
pre = i+1;
}
}
return ans;
}
};
- 无法吃午餐的学生数量
- 两个变量istu和isand分别记录学生和三明治数组的索引
- 如果索引值相等，就都加1再比较下一组数据；如果不相等，就把学生的索引值的值加到学生数组的尾端，并且索引值加1.
- 要注意的是，需要添加一个limit，用来跳出循环，否则会无限循环下去
- 返回值是学生数组的长度减去学生的索引值。
class Solution {
public:
int countStudents(vector<int>& students, vector<int>& sandwiches) {
int istu = 0;
int isand = 0;
int limit = 0;
while(istu < students.size() && isand < sandwiches.size()) {
if(students[istu] == sandwiches[isand]) {
isand++;
istu++;
}else{
students.push_back(students[istu]);
istu++;
if(limit++>200) break;
}
}
return students.size()-istu;
}
};
- 设计一个支持增量操作的栈
- 用一个数组表示栈的思想
- 用变量top表示栈顶，变量size表示栈的最大长度
class CustomStack {
public:
int top, size;
int *stk;
CustomStack(int maxSize) {
stk = new int[maxSize+1];
size = maxSize;
top = 0;
}
void push(int x) {
if(top < size) {
stk[top++] = x;
}
}
int pop() {
if(top == 0) {
return -1;
}
top--;
return stk[top];
}
void increment(int k, int val) {
if(top < k) {
for(int i = 0; i < top; ++i) {
stk[i] += val;
}
} else {
for(int i = 0; i < k; ++i) {
stk[i] += val;
}
}
}
};
————————
Today’s algorithm content is: < strong > stack < / strong >
1、 One question per day
- Building arrays with stacks
- The n of this problem seems to be of no use
- The problem is monotonically increasing
- Hash table: first create a hash table and initialize it to 0. Each number appearing in the target is marked as 1
- First ‘push’ all, and then ‘pop’ the value of 0 in the hash table
class Solution {
public:
vector<string> buildArray(vector<int>& target, int n) {
int index = 0;
int limit = target.back();//target的最后一个元素
int hash[101];
memset(hash, 0, sizeof(hash));
vector<string> ret;
for(int i = 0; i < target.size(); ++i) {
hash[target[i]] = 1;
}
for(int i = 1; i <= limit; ++i) {
ret.push_back("Push");
if(!hash[i]) {
ret.push_back("Pop");
}
}
return ret;
}
};
- Remove outermost parentheses
- Use the stktop variable to determine whether it is a complete set of parentheses
- If it is a complete set of parentheses, take only the inner parentheses. If there is no inner layer, it is an empty string
- Pre = I + 1 jump to the next set of parentheses, judge again, and finally return to the answer
class Solution {
public:
string removeOuterParentheses(string s) {
string ans;
int stktop = 0;
int pre = 0;
for(int i = 0; i < s.size(); ++i) {
if(s[i] == '(') {
++stktop;
}else {
--stktop;
}
//当碰到完整的括号的时候
if(stktop == 0) {
for(int j = pre+1; j <= i-1; ++j) {
ans += s[j];
}
//判断下一组括号
pre = i+1;
}
}
return ans;
}
};
- Number of students unable to eat lunch
- The two variables istu and isand record the index of the student and sandwich array respectively
- If the index values are equal, add 1 to both and compare the next group of data; If they are not equal, the value of the student’s index value is added to the end of the student array, and the index value is added by 1
- Note that you need to add a limit to jump out of the loop, otherwise it will go on indefinitely
- The return value is the length of the student array minus the index value of the student.
class Solution {
public:
int countStudents(vector<int>& students, vector<int>& sandwiches) {
int istu = 0;
int isand = 0;
int limit = 0;
while(istu < students.size() && isand < sandwiches.size()) {
if(students[istu] == sandwiches[isand]) {
isand++;
istu++;
}else{
students.push_back(students[istu]);
istu++;
if(limit++>200) break;
}
}
return students.size()-istu;
}
};
- Design a stack that supports incremental operation
- The idea of using an array to represent the stack
- The variable top represents the top of the stack, and the variable size represents the maximum length of the stack
class CustomStack {
public:
int top, size;
int *stk;
CustomStack(int maxSize) {
stk = new int[maxSize+1];
size = maxSize;
top = 0;
}
void push(int x) {
if(top < size) {
stk[top++] = x;
}
}
int pop() {
if(top == 0) {
return -1;
}
top--;
return stk[top];
}
void increment(int k, int val) {
if(top < k) {
for(int i = 0; i < top; ++i) {
stk[i] += val;
}
} else {
for(int i = 0; i < k; ++i) {
stk[i] += val;
}
}
}
};