1:atoi string.c_str()函数的基本使用
string str = "10"; //string转数字
int res = atoi(str.c_str());
2:  链表快速排序和插入排序问题
    2.1 单链表快速排序
    //1216 leetcode 148
    //这个也是链表排序 但是要求 在 O(n log n) 时间复杂度和常数级空间复杂度下
    ListNode* sortList_Leetcode148(ListNode* head) {
        if((head == NULL) || (head != NULL && head->next == NULL)) return head;   
        quickSort_Leetcode148(head,NULL);
        return head;
    }

    ListNode* partitions_QuickSortListNodeLeetcode148(ListNode* start,ListNode* end)
    {
        ListNode* p = start;
        ListNode* q = p->next;
        int value = p->val;
        while (q != end)
        {
            if(q->val < value)
            {
                p = p->next;

                int tmp = p->val;
                p->val = q->val;
                q->val = tmp;
            }
            q = q->next;
        }

        int tmp = p->val;
        start->val = tmp;
        p->val = tmp;
        return p;
    }

    void quickSort_Leetcode147(ListNode* start,ListNode* end)
    {
        if(start != NULL && start->next != NULL && start != end)
        {
            ListNode* mid = partitions_QuickSortListNodeLeetcode148(start,end);
            quickSort_Leetcode148(start,mid);
            quickSort_Leetcode148(mid->next,end);
        }
    }
    2.2  单链表插入排序
    ListNode* sortList(ListNode* head) {
        if((head == NULL) || (head != NULL && head->next == NULL)) return head;   
        ListNode* dumy = new ListNode(0);
        dumy->next = new ListNode(head->val);
        ListNode* cur = dumy->next;
        ListNode* pre = dumy;
        while (head->next != NULL)
        {
            pre = dumy;
            cur = pre->next;
            ListNode* tmp = new ListNode(head->next->val);
            if(tmp->val < cur->val)
            {
                tmp->next = cur;
                pre->next = tmp;
            }
            else
            {
                while ((cur != NULL) && (cur->val < tmp->val))
                {
                    cur = cur->next;
                    pre = pre->next;
                }
                pre->next = tmp;
                tmp->next = cur;
            }
            head = head->next;
        }
        return dumy->next;

    }
3:
unordered_map迭代器失效
    unordered_map<int,int> unmap;
    unmap.insert(pair<int,int>(1,2));
    unmap.insert(pair<int,int>(3,6));
    unmap.insert(pair<int,int>(5,9));

    for(auto it = unmap.begin();it != unmap.end();it++)
    {
        cout<<it->first<<" "<<it->second<<endl;
    }

    for(auto it = unmap.begin();it != unmap.end();)
    {
        if(it->first == 3) unmap.erase(it++); //unordered_map 迭代器失效
        else
        {
            it++;
        }
        
    }
    cout<<"after erase"<<endl;
    for(auto it = unmap.begin();it != unmap.end();it++)
    {
        cout<<it->first<<" "<<it->second<<endl;
    }
4: LRU缓存机制 leetcod 146
先放测试用例
   /*
    cout<<"null ";
    LRUCache* lru = new LRUCache(10);
    lru->put(10,13);
    lru->put(3,17);
    lru->put(6,11);
    lru->put(10,5);
    lru->put(9,10);
    lru->get(13);
    lru->put(2,19);
    lru->get(2);
    lru->get(3);
    lru->put(5,25);
    lru->get(8);
    lru->put(9,22);
    lru->put(5,5);
    lru->put(1,30);
    lru->get(11);
    lru->put(9,12);
    lru->get(7);
    lru->get(5);
    lru->get(8);
    lru->get(9);
    lru->put(4,30);
    lru->put(9,3);
    lru->get(9);
    lru->get(10);
    lru->get(10);
    lru->put(6,14);
    lru->put(3,1);
    lru->get(3);
    lru->put(10,11);
    lru->get(8);
    lru->put(2,14);
    lru->get(1);
    lru->get(5);
    lru->get(4);
    lru->put(11,4);
    lru->put(12,24);
    lru->put(5,18);
    lru->get(13);
    lru->put(7,23);
    lru->get(8);
    lru->get(12);
    lru->put(3,27);
    lru->put(2,12);
    lru->get(5);
    lru->put(2,9);
    lru->put(13,4);
    lru->put(8,18);
    lru->put(1,7);
    lru->get(6);
    lru->put(9,29);
    lru->put(8,21);
    lru->get(5);
    lru->put(6,30);
    lru->put(1,12);
    lru->get(10);
    lru->put(4,15);
    lru->put(7,22);
    lru->put(11,26);
    lru->put(8,17);
    lru->put(9,29);
    lru->get(5);
    lru->put(3,4);
    lru->put(11,30);
    lru->get(12);
    lru->put(4,29);
    lru->get(3); //从这个地方开始错的
    lru->get(9);
    lru->get(6);
    lru->put(3,4);
    lru->get(1);
    lru->get(10);
    lru->put(3,29);
    lru->put(10,28);
    lru->put(1,20);
    lru->put(11,13);
    lru->get(3);
    lru->put(3,12);
    lru->put(3,8);
    lru->put(10,9);
    lru->put(3,26);
    lru->get(8);
    lru->get(7);
    lru->get(5);
    lru->put(13,17);
    lru->put(2,27);
    lru->put(11,15);
    lru->get(12);
    lru->put(9,19);
    lru->put(2,15);
    lru->put(3,16);
    lru->get(1);
    lru->put(12,17);
    lru->put(9,1);
    lru->put(6,19);
    lru->get(4);
    lru->get(5);
    lru->get(5);
    lru->put(8,1);
    lru->put(11,7);
    lru->put(5,2);
    lru->put(9,28);
    lru->get(1);
    lru->put(2,2);
    lru->put(7,4);
    lru->put(4,22);
    lru->put(7,24);
    lru->put(9,26);
    lru->put(13,28);
    lru->put(11,26);
    */

再放源代码,这个我这个超时了。
//20_1216 LRU
class LRUCache {
public:
    // 这个超时了。/
    LRUCache(int capacity) {
        capacitys = capacity;
        count = 0;
        matches.clear();
    }
    
    int get(int key) {
        if(matches.find(key) == matches.end()) 
        {
            cout<<-1<<" ";
            return -1;
        }
        queue<int> q1;

        int cur = key;
        while (!q.empty())
        {
            int tmp = q.front();
            q.pop();
            if(tmp == cur) continue;
            else
            {
                q1.push(tmp);
            }
            
        }
        q1.push(cur);
        q = q1;
        
        cout<<matches[key]<<" ";
        return matches[key]; 
    }
    
    void put(int key, int value) {
        queue<int> q1;
        int cur = key;

        if(matches.find(key) == matches.end())
        {
            count++;
            if(count > capacitys) count = capacitys+1;
        }

        if(count > capacitys)
        {
            int tmp = q.front();
            q.pop();
            q.push(key);
            matches[key] = value;
            for(auto it = matches.begin(); it != matches.end();)
            {
                if(it->first == tmp) matches.erase(it++);
                else it++;
            }
            count--;
        }
        else
        {
            matches[key] = value;
            
            while (!q.empty())
            {
                int tmp = q.front();
                q.pop();
                if(tmp == cur) continue;
                else
                {
                    q1.push(tmp);
                }
                
            }
            q1.push(cur);
            q = q1;

        }
        cout<<"null "; 
    }

    int count;
    int capacitys;
    unordered_map<int,int> matches;
    queue<int> q;

};

5:非递归遍历二叉树,前序遍历和中序,非递归后序有点难,暂时不写
先放用例
    Solution solution;
    TreeNode* tree10 = new TreeNode(7);
    TreeNode* tree12 = new TreeNode(10);
    TreeNode* tree11 = new TreeNode(9,NULL,tree12);

    TreeNode* tree1 = new TreeNode(4,tree10,tree11);
    TreeNode* tree2 = new TreeNode(5);
    TreeNode* tree3 = new TreeNode(6);
    TreeNode* tree4 = new TreeNode(2,tree1,tree2);
    TreeNode* tree5 = new TreeNode(3,NULL,tree3);
    TreeNode* tree6 = new TreeNode(1,tree4,tree5);
    TreeNode* root = tree6;

    

    vector<vector<int>> travelFloorRes = solution.travelTreeNodeByFloor(root);
    for(int i =0;i<travelFloorRes.size();i++)
    {
        for(int j =0;j<travelFloorRes[i].size();j++)
        {
            cout<<travelFloorRes[i][j]<<" ";
        }
        cout<<endl;
    }

    cout<<"middle travel TreeNode by stack is "<<endl;
    vector<int> middleTravelRes = solution.middleTravel(root);
    for_each(middleTravelRes.begin(),middleTravelRes.end(),[](auto x){cout<<x<<" ";});
    cout<<endl;

    cout<<"pre travel TreeNode by stack is "<<endl;
    vector<int> preTravelRes = solution.preorderTraversal(root);
    for_each(preTravelRes.begin(),preTravelRes.end(),[](auto x){cout<<x<<" ";});
    cout<<endl; 
然后是代码
    //1218 非递归解法前序遍历
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root == NULL) return res;
        stack<TreeNode*> s;
        TreeNode* p = root;
        while (!s.empty() || p)
        {
            while (p)
            {
                //cout<<"cur val is "<<p->val<<endl;
                res.push_back(p->val);
                s.push(p);
                p = p->left;
            }
            if(!s.empty())
            {
                TreeNode* tmp = s.top();
                s.pop();
                p = tmp->right;
            }
            
        }
        
        return res;
    }

    vector<int> middleTravel(TreeNode* root)
    {
        vector<int> res;
        if(root == NULL) return res;
        stack<TreeNode*> s;
        TreeNode* p = root;
        while (!s.empty() || p != NULL)
        {
            while (p != NULL)
            {
                s.push(p);
                p = p->left;
            }

            if(!s.empty())
            {
                TreeNode* tmp = s.top();
                s.pop();
                res.push_back(tmp->val);
                p = tmp->right;
            }
        }
        return res;
    }

3. STL巧妙小函数使用
    判断vector等容器是否含有某个数,代码如下
    
    cout<<"In main test "<<endl;
    vector<int> v2 = {10,12,14,16};
    auto pos = std::find(v2.begin(),v2.end(),100);
    if(pos != v2.end()) cout<<"v2 find yes"<<endl;
    else cout<<"v2 no"<<endl;
4. 

map的key如果是结构体需要注意什么问题

map中的key默认是以less<>升序对元素排序(排序准则也可以修改),也就是说key必须具备operator<对元素排序,而平常我们的用的基本上都是基本类型元素作为key,所以就不存在这个问题了

所以要对结构体中<号进行重载操作才行

重载运算符应该注意重载小于号要有2个const,注意后面的const。