atoi等各种小函数的用法需要学习，及时更新在这个贴子里
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。
