算法

二分查找

对于数字运算，左移一位相当于乘以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中是全部为１