#include #include #include #include #include #include #include #include using namespace std; (1) // 分区，数字大的在分区右侧，小的在左侧 int do_part(int data[], int length, int start, int end) { if (data == nullptr || length <= 0 || start < 0 || end >= length) { return -1; } int index = 5; // 此处为标兵设置，可为长度范围内随机值 swap(data[5], data[end]); int small = -1; for (index = start; index < length; index++) { if (data[index] < data[end]) { small++; if (small != index) { swap(data[index], data[small]); } } } small++; swap(data[small], data[end]); return small; } (2) // 二分搜索 int binary_search(int nums[], int target, int length) { int left = 0, right = length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] == target) { // 直接返回 return mid; } } // 直接返回 return -1; } (3) // 应用二分算法的查找函数 vector target = {1,2,3,3,3,4,5}; lower_bound(begin(), end(), target); //查找>=目标值的第一个元素，查找3，返回2，对应元素3 upper_bound(begin(), end(), target); //查找>目标值的第一个元素，查找3，返回5，对应元素4 binary_search(begin(), end(), target); //判断是否存在 set available; available.lower_bound(target); //注意set中lower_bound参数只有1个 //先排序 vector v= {3,4,1,2,8}; sort(v.begin(),v.end()); // 1 2 3 4 8 // 定义两个迭代器变量 vector::iterator iter1; vector::iterator iter2; iter1 = lower_bound(v.begin(),v.end(),3);//迭代器指向3 iter2 = lower_bound(v.begin(),v.end(),7);//迭代器指向8（因为第一个大于等于8） max_element(v.being(), v.end()); //寻找最大值，有多个最大值或者最小值，返回的是第一次出现的位置,返回的也是迭代器 (4) //找到 [first, last) 范围内所有等于 val 的元素 //第 1 个迭代器指向的是 [first, last) 区域中第一个等于 val 的元素； //第 2 个迭代器指向的是 [first, last) 区域中第一个大于 val 的元素。 //反之如果查找失败，则这 2 个迭代器要么都指向大于 val 的第一个元素（如果有），要么都和 last 迭代器指向相同。 pair equal_range (ForwardIterator first, ForwardIterator last, const T& val, Compare comp); int test () { map mymap; pair::iterator,map::iterator> ret; mymap['a']=10; mymap['b']=20; mymap['c']=30; ret = mymap.equal_range('b'); cout << "lower bound points to: "; cout << ret.first->first << " => " << ret.first->second << endl; cout << "upper bound points to: "; cout << ret.second->first << " => " << ret.second->second << endl; return 0; } (5) equal()函数，返回类型为bool vector a{ 1,2,3 }, b{ 1,2,3,4 }; cout << "以a为比较范围,判断a,b是否相同:" << equal(a.begin(),a.end(),b.begin()) << endl; //结果为1 cout << "要求容器相同,判断a,b是否相同:" << equal(a.begin(), a.end(), b.begin(), b.end()) << endl; //结果为0 (6) //map排序 // 按key排序 <1> map name_score_map1; // 默认按照less排序 <2> map > name_score_map2; // 修改为大于 //重载()运算符 //less和greater template struct less : binary_function { bool operator () (const T &x, const T &y) const { return x < y; } }; template struct greater : binary_function { bool operator () (const T &x, const T &y) const { return x > y; } }; <3>//重载operator运算符 map name_score_map3; struct CmpByKeyLength { bool operator () (const string &k1, const string &k2) { return k1.length() < k2.length(); } }; <4> //采用函数对象 // 按value排序 // 对pair重构一个vector来承载，确保sort函数可使用 typedef pair PAIR; // 比较函数 bool cmp_by_value(const PAIR &lhs, const PAIR &rhs) { return lhs.second < rhs.second; } // 函数对象 struct CmpByValue { bool operator () (const PAIR &lhs, const PAIR &rhs) { return lhs.second < rhs.second; } }; // 使用 map name_score_map; // 把map中元素转存到vector中 vector name_score_vec(name_score_map.begin(), name_score_map.end()); // 函数对象 sort(name_score_vec.begin(), name_score_vec.end(), CmpByValue()); // 比较函数 sort(name_score_vec.begin(), name_score_vec.end(), cmp_by_value); <5> sort(people.begin(), people.end(), [](const vector& u, const vector& v) { return u[0] < v[0] || (u[0] == v[0] && u[1] > v[1]); }); (7) //全排列 void core_permutation(string &s, vector &result, int begin) { if (begin == s.size()) { result.push_back(s); return; } else { for (int i = begin; i < s.size(); i++) { bool flag = true; // 交换中，重复节点不交换，不输出，即“剪枝” for (int j = begin; j < i; j++) { if (s[j] == s[i]) { flag = false; } } if (flag) { // 锁定第一个节点，交换第一个与之后的节点 swap(s[i], s[begin]); // 再锁定第二个节点，交换第二个与之后的节点，因此递归 // 交换后，输出结果 core_permutation(s, result, begin + 1); // 交换完成后，再换回来，保证s不变 swap(s[i], s[begin]); } } } } (8) // multiset用法 multiset> intSer; //按照从小到大顺序存放 (9) //展现出来的是最大或最小，和map相反 //升序队列，小顶堆，存储元素类型，基础容器，排序规则 priority_queue ,greater > q; //默认，降序队列，大顶堆 priority_queue ,less >q; //greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了） (10) //c++中的make_heap(), pop_heap()的头文件为algorithm。作用与priority_queue中的成员函数相同，可以单独使用。 //使用方法 make_heap() //在容器范围内，就地建堆，保证最大值在所给范围的最前面，其他值的位置不确定 pop_heap() //将堆顶(所给范围的最前面)元素移动到所给范围的最后，并且将新的最大值置于所给范围的最前面 push_heap() //当已建堆的容器范围内有新的元素插入末尾后，应当调用push_heap将该元素插入堆中。 int test2() { vector nums = {4, 5, 1, 3, 2}; // generate heap in the range of numsector make_heap(nums.begin(), nums.end()); cout << "initial max value : " << nums.front() << endl; // pop max value pop_heap(nums.begin(), nums.end()); nums.pop_back(); cout << "after pop, the max vsalue : " << nums.front() << endl; // push a new value nums.push_back(6); push_heap(nums.begin(), nums.end()); cout << "after push, the max value : " << nums.front() << endl; system("pause"); return 0; } // initial max value : 5 // after pop, the max vsalue : 4 // after push, the max value : 6 (11) //自定义比较函数 auto cmp = [](const int x, const int y) { return x > y;}; (12) //返回值：(1) 成功找到，返回在父串中第一次出现的位置的 char *指针 (2) 若未找到，即不存在这样的子串，返回 NULL。 strstr() //strtok函数第一次调用时会把s字符串中所有在delim中出现的字符替换为NULL。然后通过依次调用strtok(NULL, delim)得到各部分子串 strtok(char *__restrict _Str, const char *__restrict _Delim) strcat(char *__restrict _Dest, const char *__restrict _Source) strcpy_error(char *strDest, size_t destMax, const char *strSrc) sscanf() //判断拼接数据大小时，可以采用拼接字符比大小 (13) //dfs前序遍历 class Solution { public: vector ans; vector preorder(Node* root) { dfs(root); return ans; } void dfs(Node * root) { if (root == nullptr) { return; } // 前序遍历，记得添加 ans.emplace_back(root->val); for (auto node : root->children) { dfs(node); } } }; (14) //int类型最大值最小值用法，头文件#include INT_MAX,INT_MIN (15) //bfs class Solution { public: int minDiffInBST(TreeNode* root) { queue q; vector ans; q.push(root); //此处不需要重复添加 while (!q.empty()) { TreeNode* tmp = q.front(); q.pop(); if (tmp->left) { q.push(tmp->left); } if (tmp->right) { q.push(tmp->right); } ans.push_back(tmp->val); } sort(ans.begin(), ans.end()); int res = INT_MAX; for (int i = 1; i < ans.size(); i++) { res = min(res, ans[i] - ans[i - 1]); } return res; } }; (16) // 字符串部分函数操作 list::iterator it = find(lst.begin(), lst.end(), 10); auto pos = std::find_if(tmp.begin(), tmp.end(), [](const auto& s) { return s == '+' || s == '-'; }) string sub1 = s.substr(5); //只有一个数字5表示从下标为5开始一直到结尾：sub1 = “56789” string sub2 = s.substr(5, 3); //从下标为5开始截取长度为3位：sub2 = “567” ForwardIterator1 find_first_of ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2 ); //它从第一个范围里面寻找任何一个是第二个范围里的一个元素，返回第一次匹配的迭代器。如果找不到，返回第一个范围的最后一个迭代器。 str.find_last_of(str1) //说明：从后向前在str中找到str1,并返回其从后向前的索引值，否则返回-1 str.find_first_of(str1) //说明：从前向后在str中找到str1,并返回其索引值，否则返回-1 str.find(str1) //说明：从前向后在str中找到str1,并返回其索引值，否则返回-1 string::npos = -1; (17)滑窗模板 int findSubArray(vectir &nums) { int n = nums.size(); // 数组/字符串长度 int left = 0, right = 0, sum = 0, res = 0; // 当右边的指针没有搜索到 数组/字符串 的结尾 while (right < n) { sum += nums[right]; // 增加当前右边指针的数字/字符的求和/计数 // 此时需要一直移动左指针，直至找到一个符合题意的区间 while (区间[left, right]不符合题意) { sums -= nums[left]; // 移动左指针前需要从counter中减少left位置字符的求和/计数 left += 1; // 真正的移动左指针，注意不能跟上面一行代码写反 } // 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串 res = max (res, right - left + 1); right += 1; } } (18) // 头文件 #include vector> roomsystem; (19) //双优先队列获取中位数 class MedianFinder { public: priority_queue, less> queMin; priority_queue, greater> queMax; MedianFinder() {} void addNum(int num) { if (queMin.empty() || num <= queMin.top()) { queMin.push(num); if (queMax.size() + 1 < queMin.size()) { queMax.push(queMin.top()); queMin.pop(); } } else { queMax.push(num); if (queMax.size() > queMin.size()) { queMin.push(queMax.top()); queMax.pop(); } } } double findMedian() { if (queMin.size() > queMax.size()) { return queMin.top(); } return (queMin.top() + queMax.top()) / 2.0; } };
上一篇 Java对接云mas发送短信（https方式）
下一篇 完全背包问题以及优化小技巧
版权所有 (c)2021-2022 MSHXW.COM
ICP备案号：晋ICP备2021003244-6号
