慢慢把一些要老忘记但是很有用的一些东西放这里
1、lower_bound是找第一个大于等于的数
2、upper_bound是找第一个大于的数
3、stringstream ssin(str) 为读取str中的单字，比如hello world ,就会读取hello和world
while (ssin >> str) v.push_back(str); v里就是各个单字
4、把string s 转大小写
transform(s.begin(), s.end(), s.begin(), ::tolower);
transform(s.begin(), s.end(), s.begin(), ::toupper);
5、string 用 int m = s.find(t), 判断是 p != string::npos 或者 p != -1
vector 是vector<int>::iterator it; it = find(v.begin(), v.end(), x), 判断是 it != v.end(), 要得位置为 int m = it – v.begin();
6、后缀转中缀：后缀没括号，但是转中缀可以加括号
7、找连通图两点的最长距离：
可以先dfs其中一个点，找到最长距离的点，再dfs这个最长距离的点后，再找的最长距离就是整个图的最长距离，
也可以bfs
8、逆序对的数量：
利用归并排序操作
void merge_sort(int q[], int l, int r) { if (l >= r) return; int mid = l + r >> 1; merge_sort(q, l, mid), merge_sort(q, mid + 1, r); int i = l, j = mid + 1,k = 0; while (i <= mid && j <= r)//合并操作，左右两边已经排好序 { if (q[i] <= q[j]) { cmp[k ++] = q[i ++]; } else { res += mid - i + 1;//当左边有个数下标i比右边的一个数大，那有mid - i + 1个逆序对 cmp[k ++] = q[j ++]; } } while (i <= mid) cmp[k ++] = q[i ++]; while (j <= r) cmp[k ++] = q[j ++]; for (int i = l, j = 0; i <= r; i ++, j ++) q[i] = cmp[j]; }
9、结构体内重载
注意是 d < x.d
struct node { int d, e; bool operator < (const node x) const { return d < x.d; //从小到大排序 } };
10、判断闰平年
int leaf = year % 100 && year % 4 == 0 || year % 400 == 0;
leaf = 1 就是2 月 29天的那个年，也就是闰年
11、上下取整
a / b 的上取整就是 (a + b – 1) / b 的下取整, a / b 的下取整就是a / b.
12、判断数字回文
比如8个数字的，只要判断前4个就ok了
for(int i = 1000; i < 10000; i ++ ){ int r = i, x = i; for(int i = 0; i < 4; i ++ ) r = r * 10 + x % 10, x /= 10; }
r 就是它的回文，奇数个的话eg 9取左4由4个.
13、二分模板
//浮点数二分 double search_0(int l, int r){ while(r - l > int_min){//int_min根据小数点位数定，eg.小数点3位，int_min = 1e-4 double mid = (l + r) / 2; if(mid * mid * mid >= n)r = mid; else l = mid; } return l; } //整数二分 int search_1(int l, int r){ while(l < r){ int mid = l + r >> 1; if(array[mid] >= find_num)r = mid; else l = mid + 1; } return r;//return l;此时l == r,为最左边的find_num下标 } int search_2(int l, int r){ while(l < r){ int mid = l + r + 1 >> 1; if(array[mid] <= find_num)l = mid; else r = mid - 1; } return l;//return r;此时l == r,为最右边的find_num下标 }
14、老会忘的二叉树遍历建树输出
前中输出后
#include<iostream> using namespace std; int pre[] = {1, 2, 3, 4, 5, 6}; int mid[] = {3, 2, 4, 1, 6, 5}; void post(int root, int start, int end) { if(start > end) return ; int i = start; while(i < end && mid[i] != pre[root]) i++; //定位根在中序的位置 post(root + 1, start, i - 1); //递归处理左子树 post(root + 1 + i - start, i + 1, end); //递归处理右子树 //cout<<pre[root]; //访问当前树的根 cout<<mid[i]; } int main() { post(0, 0, 5); return 0; }
后中输出前
#include<iostream> using namespace std; int post[] = {3, 4, 2, 6, 5, 1}; int mid[] = {3, 2, 4, 1, 6, 5}; void pre(int root, int start, int end) { if(start > end) return ; int i = start; while(i < end && mid[i] != post[root]) i++; //定位根在中序的位置 cout<<mid[i]; //访问当前处理的树的根 pre(root-1-(end-i), start, i - 1); //递归处理左子树 pre(root-1, i + 1, end); //递归处理右子树 } int main() { pre(5, 0, 5); return 0; }
先中序建树
treenode reconstructbinarytree(int[] pre, int prestart, int preend, int[] in, int instart, int inend) { if (prestart > preend || instart > inend) { //到达边界条件时返回null return null; } treenode treenode = new treenode(pre[prestart]); //新建一个treenode for (int i = instart; i <= inend; i++) { if (in[i] == pre[prestart]) { //在中序中找到根节点的位置，【依次】将先序序列和中序序列分成左右字树，分别构建左右子树。 // 重构左子树，注意边界条件 treenode.left = reconstructbinarytree(pre, prestart + 1, prestart + i - instart, in, instart, i - 1); // 重构右子树，注意边界条件 treenode.right = reconstructbinarytree(pre, prestart + i - instart + 1, preend, in, i + 1, inend); } } return treenode; }
后中序建树
treenode reconstructbinarytree2(int[] in, int instart, int inend, int[] last, int laststart, int lastend) { if (instart > inend || laststart > lastend) return null; treenode treenode = new treenode(last[lastend]); for (int i = instart; i <= inend; i++) { if (in[i] == last[lastend]) { treenode.left = reconstructbinarytree2(in, instart, i - 1, last, laststart, laststart + i - instart - 1); treenode.right = reconstructbinarytree2(in, i + 1, inend, last, laststart + i - instart, lastend - 1); } } return treenode; }
二叉搜索树前序输出后序
vector<int> v; void getpost(int root, int last) { int i = root + 1, j = last; while (a[i] < a[root] && i <= last)i++;//找当前根节点左子节点边界 while (a[j] >= a[root] && j > root)j--;//找当前根节点右子节点边界 if (i - j != 1)return; getpost(root + 1, j);//遍历左子节点 getpost(i, last);//遍历右子节点 v.push_back(a[root]);//pb根节点(左右根) }
*给出二叉搜索树的一个遍历，只要从小到大排序就是其中序遍历，根据中序遍历从0下标开始在进行左根右遍历得到层序遍历
二叉树后中序输出层序
int post[1005], in[1005]; map<int, int> ma, le; void level(int root, int l, int r, int index) { if (l > r)return; int p = ma[post[root]];//当前后序所在根节点前序位置 le[index] = post[root];//index为节点下标 level(root - r + p - 1, l, p - 1, 2 * index);//root - (r - p) - 1是当前后序根节点位置减去(其右子树节点个数)再减一位 level(root - 1, p + 1, r, 2 * index + 1); } int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> post[i]; } for (int i = 1; i <= n; i++) { cin >> in[i]; ma[in[i]] = i; } level(n, 1, n, 1); }
15、优先列队
//对于基础类型 默认是大顶堆 priority_queue<int> a; //等同于 priority_queue<int, vector<int>, less<int> > a; priority_queue<int, vector<int>, greater<int> > c; //这样就是小顶堆
0 条评论