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。