一些自己用得比较顺手的代码
定义 Compare
排序有时需要自己指定比较器 (Comparator)
# 指定std::greater<> 作为比较器，将vector或者别的容器降续排列
#include<functional> //greateer#include<iostream>#include<vector>#include<queue>#include<algorithm>int main(){int A[] = {6, 9, 1, 5, 2};std::vector<int> vec(A, A+sizeof(A)/sizeof(A[0])); std::sort(vec.begin(), vec.end(), std::greater<int>()); //将vector降续排列，注意这里greater<int> 后有要加括号()for(int i = 0; i < vec.size(); std::cout << vec[i++] << ' '); //9 6 5 2 1std::cout << std::endl;std::priority_queue<int, std::vector<int>, std::greater<int> > pqueue(A, A+sizeof(A)/sizeof(A[0])); //定义最小堆，注意这里greater<int> 后没有括号while(!pqueue.empty()){std::cout << pqueue.top() << ' '; //1 2 5 6 9 pqueue.pop();}std::cout << std::endl;return 0;}
# 自定义比较器，让优先队列 可以存储特殊struct。
#include<iostream>#include<vector>#include<queue>#include<utility> //pairusing namespace std;typedef pair<int, int> Node;class Comparator{public:bool operator()(const Node &a, const Node &b){return a.second < b.second; //升序，队头元素最小 }};int main(){int A[] = {9, 2, 8, 7, 0, 6};priority_queue<Node, vector<Node>, Comparator> pqueue;for(int i = 0; i < sizeof(A) / sizeof(int); pqueue.push(Node(i, A[i])), ++i);while(!pqueue.empty()){cout << pqueue.top().second << ", orginal index: " << pqueue.top().first << endl;pqueue.pop();}return 0;}/*输出：9, orginal index: 08, orginal index: 27, orginal index: 36, orginal index: 52, orginal index: 10, orginal index: 4*/
max_element() 与 min_element()
max_element() 可以得出序列中最大值所在的iterator
#include <iostream>// std::cout#include <algorithm> // std::min_element, std::max_elementbool myfn(int i, int j) { return i<j; }struct myclass {bool operator() (int i,int j) { return i<j; }} myobj;int main () {int myints[] = {3,7,2,5,6,4,9};// using default comparison:std::cout << "The smallest element is " << *std::min_element(myints,myints+7) << '\n';std::cout << "The largest element is " << *std::max_element(myints,myints+7) << '\n';// using function myfn as comp:std::cout << "The smallest element is " << *std::min_element(myints,myints+7,myfn) << '\n';std::cout << "The largest element is " << *std::max_element(myints,myints+7,myfn) << '\n';// using object myobj as comp:std::cout << "The smallest element is " << *std::min_element(myints,myints+7,myobj) << '\n';std::cout << "The largest element is " << *std::max_element(myints,myints+7,myobj) << '\n';return 0;}
链表类
# 需要一个指针走一步，一个指针走两步。
for(; p2 != NULL; p1 = p1 -> next, p2 = p2 -> next){p2 = p2 -> next;if(p2 == NULL) break;}
格式的特点是p1 = p1 -> next, p2 = p2 -> next 写在 for 的里面，为了防止空指针引用，for循环体里要加上if(p2 == NULL)break;
场景(1) 将链表分为两段，前半段长度 n - n/2， 后半段长度n/2
ListNode *p1 = head; ListNode* p2 = head -> next;for(; p2 != NULL;p1 = p1 -> next, p2 = p2 -> next){p2 = p2 -> next;if(p2 == NULL) break;}ListNode* temp = p1;p1 = p1 -> next;temp -> next = NULL;
场景(2) 除了分两段，判断环链表也需要这种格式的代码，之所以要从head -> next出发，是因为如果要接着找出环入口的话，相遇点的位置是正确的。
bool hasCycle(ListNode *head) {if(NULL == head) return false;ListNode* p1 = head -> next; ListNode* p2 = head -> next;for(; p2 != NULL; p1 = p1 -> next, p2 = p2 -> next){p2 = p2 -> next;if(p2 == NULL || p1 == p2) break;}if(p2 == NULL) return false;return true;}
话说回来，这样写稍微有点非主流，清晰一点的写法是这样：
ListNode *FindCircleStart(ListNode *head){if(!head) return NULL;ListNode *p = head, *q = head;while(q -> next){p = p -> next;q = q -> next -> next;if(!q || q == p) break;}if(!q) return NULL; //无环for(p = head; p!= q; p = p -> next, q = q -> next); //找出相遇点return p;}
看似简单，但是其实考虑到了几种边界情况，比如只有一个节点的环链表。
BIT 类
返回一个整数转化为二进制后，1 的个数
int __builtin_popcount(unsigned int)int __builtin_popcountl(unsigned long int)int __builtin_popcountll(unsigned long long)
这三个函数是GCC提供的函数，不属于std
要想自己实现的话，有一个效率比较高的方法
/felixfang/category/535191.html 后半部分
数组类
排好序的数组中去重
Given input array A =[1,1,2],
Your function should return length =2, and A is now[1,2].
int removeDuplicates(int A[], int n) {if(n <= 1) return n;int p = 0, q = 1;while(q < n){if(A[p] == A[q]) ++q;else A[++p] = A[q++];}return p+1;}
如果重复数字允许出现两次
Given sorted array A =[1,1,1,2,2,3],
Your function should return length =5, and A is now[1,1,2,2,3].
只要在++q的条件上增加两项即可。
int removeDuplicates(int A[], int n) {if(n <= 1) return n;int p = 0, q = 1;while(q < n){if(A[p] == A[q] && p > 0 && A[p] == A[p-1]) ++q;else A[++p] = A[q++];}return p+1;}
字符串处理类
string a;char* chs = a.c_str(); //string to char*int num = atoi(a.c_str()) //string to int
#include <string>#include <sstream>string convert(int v){ostringstream convert; // stream used for the conversionconvert << v;// insert the textual representation of 'Number' in the characters in the streamreturn convert.str(); // set 'Result' to the contents of the stream}
