数据结构小知识点及应用

string

用法
str.substr(weizhi, changdu);
int repeatTimes = stoi(stack.top()); 转化string to int
char转string用 string s(1,x)
存数字 to_string(number)
string.push_back()

str.erase (str.begin()+5, str.end()-9);
str.pop_back
str.back()
str.front()
str.substr(begin(num),length )
str.empty();
?? =tolower(?)
?? = toupper();
 myset.insert (mystring);                        // copy insertion
  myset.insert (mystring+"dish");                 // move insertion
  myset.insert (myarray.begin(), myarray.end());  // range insertion
  myset.insert ( {"purple","orange"} ); 
  isdigit(s[i])
  isalpha(s[i])

stack

stack<>haha;
haha.empty(）
haha.pop/top/push

queue(bfs)

bfs时使用

Q.pop();
Q.front();

Q.push()

priority queue

默认比较器为less 大顶堆
greater 小顶堆

priority_queue > smallHeap;
priority_queue , greater> largeHeap;

multiset

unordered_set 无序数组
set 有序数组
multiset 有序且可以重复
begin end rbegin rend 的区别
https://blog.csdn.net/love_fdu_llp/article/details/52602915

deque

Q.front(), Q.back(), push_back, push_front, pop_back, pop_front
在前后都需要进出的时候可以考虑deque

同时此题找最大值，可以类似用stack的方法找到当前数组中的最大值

维护一个que 里面只存储可能的最大值
逻辑：

while(!q.empty()&&q.back()<num){
    q.pop_back();
}
q.push_back(num);

362. Sliding Window Maximum

#include <deque>
class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @param k: An integer
     * @return: The maximum number inside the window at each moving.
     */
    void inQueue(deque <int> &Q, int k){
        while(!Q.empty() && Q.back() < k){
            Q.pop_back();
        }
        Q.push_back(k);
    }
    void outQueue(deque <int> &Q, int first){
        if (Q.front() == first){
            Q.pop_front();
        }
    }
    vector<int> maxSlidingWindow(vector<int> &nums, int k) {
        // write your code here
        deque <int> Q;
        vector <int> res;
        // init queue
        for (int i = 0; i < k - 1; i ++){
            inQueue(Q, nums[i]);
        }
        for (int i = k - 1; i < nums.size(); i ++){
            inQueue(Q, nums[i]);
            res.push_back(Q.front());
            outQueue(Q, nums[i - k + 1]);
        }
        return res;
    }
};

unordered_set

insert（）erase（）count（）>0 empty()

627. Longest Palindrome