算法
- 二分查找
对于数字运算，左移一位相当于乘以2，两位相当于乘以4，依次下去，右移相反是除以
public static int binarySearch(int[]A,int value) { int low = 0; int len = A.length; int high = len -1; while(low <= high) { int mid = (low + high)>>1; if(A[mid] == value) return mid; else if (A[mid] < value) low = mid +1; else high = mid -1; } return -1; } 二分查找易错的地方
循环退出的条件 注意是low <= high,而不是low<high.
mid的取值 如果写成 mid (low+high)/2是有问题,如果low和high比较大,两者的和可能会溢出改进的方案low+(high-low)/2,但是计算机位运算比除法快,故可改成low+((high-low)>>1)
- reverse(result.begin(),result.end())逆序
vector(result.rbegin(),result.rend());逆序
3.find() 函数
本质上是一个模板函数，用于在指定范围内查找和目标元素值相等的第一个元素。
另外，该函数会返回一个输入迭代器，当 find() 函数查找成功时，其指向的是在 [first, last) 区域内查找到的第一个目标元素；如果查找失败，则该迭代器的指向和 last 相同。
-
distance() 函数用于计算两个迭代器表示的范围内包含元素的个数,返回个数
5.c++在string末尾添加字符或字符串
append函数
#include using namespace std; int main() { string s1 = "1"; string s2 = "2"; string s3 = "0123456"; s1.append(s2); cout<<s1<<endl; s1.append(s3,3,6); cout<<s1<<endl; s1.append(5,'0'); cout<<s1<<endl; } //12 //123456 //12345600000 6.begin()和end()获取指针
7.重建二叉树（递归）
1、力扣上的一种解法
题目描述
好题 绝对的好题
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
需要首先熟悉二叉树先序遍历与中序遍历的规则。 先找到preorder中的起始元素作为根节点，在inorder中找到根节点的索引mid；那么，preorder[1:mid + 1]为左子树，preorder[mid + 1:]为右子树；inorder[0:mid]为左子树，inorder[mid + 1:]为右子树。递归建立二叉树。
TreeNode* reConstructBinaryTree(vector pre,vector vin) { if (pre.size() == 0 || vin.size() == 0) { return NULL; } TreeNode* treeNode = new TreeNode(pre[0]); int mid = distance(begin(vin), find(vin.begin(), vin.end(), pre[0])); vector left_pre(pre.begin() + 1, pre.begin() + mid + 1); vector right_pre(pre.begin() + mid + 1, pre.end()); vector left_in(vin.begin(), vin.begin() + mid); vector right_in(vin.begin() + mid + 1, vin.end());
treeNode->left = reConstructBinaryTree(left_pre, left_in);
treeNode->right = reConstructBinaryTree(right_pre, right_in);
return treeNode;
}
8. bitset用法
主要是将 n 转化为 32位表示，int 最大也就是 2^32次方，然后利用bitset。count（）函数，返回 其中 1 的数量
bitset<4> bitset1; //无参构造，长度为４，默认每一位为０
bitset<8> bitset2(12); //长度为８，二进制保存，前面用０补充
string s = "100101"; bitset<10> bitset3(s); //长度为10，前面用０补充
char s2[] = "10101"; bitset<13> bitset4(s2); //长度为13，前面用０补充
cout << bitset1 << endl; //0000 cout << bitset2 << endl; //00001100 cout << bitset3 << endl; //0000100101 cout << bitset4 << endl; //0000000010101
bitset<8> foo ("10011011");
cout << foo.count() << endl; //5 （count函数用来求bitset中1的位数，foo***有５个１ cout << foo.size() << endl; //8 （size函数用来求bitset的大小，一共有８位
cout << foo.test(0) << endl; //true （test函数用来查下标处的元素是０还是１，并返回false或true，此处foo[0]为１，返回true cout << foo.test(2) << endl; //false （同理，foo[2]为０，返回false
cout << foo.any() << endl; //true （any函数检查bitset中是否有１ cout << foo.none() << endl; //false （none函数检查bitset中是否没有１ cout << foo.all() << endl; //false （all函数检查bitset中是全部为１
