栈(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;
            }
        }
    }
};