1.有效的字母异位词

class Solution {
public:
    bool isAnagram(string s, string t) {
        //利用一个哈希表，存储26个字母，遍历s与t，一个加字母次数一个减字母次数，最后遍历哈希表，如果出现不为0的数字
        //返回false
        int len1=s.length();
        int len2=t.length();
        if(len1!=len2)
            return false;
        int number[26]={0};
        for(int i=0;i<len1;i++)
        {
           number[s[i]-'a']++;
           number[t[i]-'a']--;
        }
        for(int j=0;j<26;j++)
        {
            if(number[j]!=0)
            return false;
        }
        return true;
    }
};

2. 字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        //利用一个哈希表，key用来存储单词，value作为res的行号，每个key对应一个value
        vector<vector<string>> res;
        map<string,int> word;
        int sub=0;//value值
        for(auto str:strs)
        {
            string cur=str;
            sort(cur.begin(),cur.end());//进行排序
            if(word.count(cur))
            {
                res[word[cur]].push_back(str);//如果存在相同的单词，就将原单词放入res中
            }
            else
            {
                vector<string> s(1,str);
                res.push_back(s);
                word[cur]=sub++;//如果不存在，res新push一行s，然后word的value++，因为res的行号是word的value值
            }
        }
        return res;       
    }
};

3.删除字符串中的所有相邻重复项

class Solution {
public:
    string removeDuplicates(string S) {
        if(S.length()==0) return S;
        string res="";
        stack<char> s1;
        s1.push(S[0]);
        for(int i=1;i<S.length();i++)
        {
            if(!s1.empty()&&S[i]==s1.top())
            {
                s1.pop();
            }
            else
            {
                s1.push(S[i]);
            }           
        }
        while(!s1.empty())
        {
            res+=s1.top();
            s1.pop();
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

4.删除最外层的括号

class Solution {
public:
    string removeOuterParentheses(string S) {
        //删除最外层的括号，利用一个堆栈，如果是左括号就放入栈，是右括号，就出栈一个左括号进行匹配。
        //当栈非空时，res记录栈顶元素
        string res = "";
        stack<char> mystack;
        for (int i = 0; i < S.size(); i++) {
            if (S[i] == ')')
                mystack.pop();
            if (!mystack.empty())
                res+=S[i];
            if (S[i] == '(')
                mystack.push('(');

        }
        return res;
    }
};

5.柱状图中最大的矩形

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
     //利用单调栈的思想https://blog.csdn.net/Zolewit/article/details/88863970
     heights.push_back(0);//最右面添加一个最小元素
     stack<int> stk;
     int maxArea = 0;
     for(int i = 0;i<heights.size();i++)
     {
         while(!stk.empty() && heights[i]<heights[stk.top()])
         {
             //如果出现小于栈顶元素的元素，就将栈顶元素出栈，此时的原栈顶元素右面第一个小于它的柱子下标是i
             //原栈顶元素左面第一个小于它的柱子下标是新栈顶元素
             int top= stk.top();
             stk.pop();
             maxArea = max(maxArea,heights[top]*(stk.empty()? i:(i - stk.top() -1)));
         }
         stk.push(i);
     }
     return maxArea;     
    }
};

6.接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

class Solution {
public:
int trap(vector<int>& height)
{
    int left = 0, right = height.size() - 1;
    int ans = 0;
    int left_max = 0, right_max = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            height[left] >= left_max ? (left_max = height[left]) : ans += (left_max - height[left]);
            ++left;
        }
        else {
            height[right] >= right_max ? (right_max = height[right]) : ans += (right_max - height[right]);
            --right;
        }
    }
    return ans;
}
};