机试知识点记录（一）

C++语言基础

cstring库

MEMSET函数

void memset(void *str, int ch, size_t n)
将str中当前位置后面的n个字节用ch替换并返回s，也就是说这个函数的作用是将数字以单个字节逐个拷贝的方式放到指定的内存中

memset(a, 127, sizeof(a))
127的二进制表示是01111111，在数组里存放的就是四个01111111，十进制数里是2139062143（小于int类型的范围）

memset(a, 127, sizeof(a))
128二进制是10000000，四个10000000就是-2139062144，就是初始化为一个很小的数

memset是按字节赋值的，因此char类型的数组可以赋任意值。
因此memset的正规用法是用来初始化char类型的数组的，也就是说它只会接受0x00-0xFF的值。

因为0的二进制是32个0，-1的二进制是三十二个1，所以使用memset可以直接初始化0和-1。
如果要初始最大化，第一位是符号位为0，剩下为1，01111111化十六进制正好为0x7f，所以memset(arr, 0x7f, sizeof())就是初始最大化了。

但是这个数不能满足“无穷大加无穷大依然是无穷大”的性质，相加后它是一个很小的负数。

所以一般无穷大常量取值是0x3f3f3f3f。

0x3f3f3f3f十进制是1061109567，是10^9级别。
0x3f3f3f3f + 0x3f3f3f3f = 2122219134，没有超过32位int的范围，所以相加也满足“无穷大加无穷大依旧是无穷大”的性质

输入输出

C语言风格

1 2	scanf("%d",&x); `printf("%d",x);`

1	puts("str")直接输出一串字符并换行

C++风格

1 2	cin>>x; cout<<x<<endl;

加快cin读取

原理：取消cin和stdin的同步

1 2	cin.tie(0)//取消cin和cout的关联 std::ios::syn_with_stdio(false);//取消C++标准I/O流和C标准I/O函数的

按精度输出

需要添加iomanip头文件
#include <iomanip>
cout<<fixed<<setprecision(n)<<num<<" " ; //按照指定十进制格式输出

cout<<setprecision(n)<<num; //输出小数点后的有效位数

string容器

// 1.初始化
string s1;
string s2 = "hello";
string s3("world")
string s4(5,'a');
stirng s5(s2);

// 2.访问字符
char c = s2[0];
char c2 = s2.at(1); //访问第二个字符

// 3. 修改字符串
s2 += " world";         // 拼接字符串
s2.append("!");         // 追加字符串
s2.push_back('!');      // 追加单个字符
s2.insert(5, " dear");  // 在指定位置插入字符串
s2.erase(5, 5);         // 删除从位置 5 开始的 5 个字符
s2.replace(6, 5, "there"); // 替换从位置 6 开始的 5 个字符

// 4. 查找和子串
s2.find("world") //如果找到了就返回位置，如果没找到就返回string.end()
string sub = s2.substr(6, 5); // 截取子串（从位置 6 开始，长度为 5

// 5.大小和容量
cout << "Length: " << s2.size() << endl;    // 字符串长度
cout << "Capacity: " << s2.capacity() << endl; // 当前分配的存储空间
s2.resize(10); // 调整字符串大小
s2.reserve(100); // 预留存储空间

// 6.清空
s2.clear()

vector容器

特点

动态大小
连续存储
可迭代
元素类型

创建

vector<int> myVector

vector<int myVector(5); //创建一个包含五个整数的vector，每个值为0

vector<int> myVector(5,10);//创建一个包含五个整数的vector,每个位置为10

vector<vector<int>> array(3, vector<int>(4, 0)); 创建一个二维数组

添加元素

myVector.push_back(7)

访问元素

int x= myVector[0];

int y= myVecot.at(1);

获取大小

int size = myVector.size();

迭代访问

1
2
3

for(int element :myVector){
	cout<< element << " ";
}

清空Vector

myVector.clear();

消除元素

myVector.erase()

去除重复值

myVector.erase(unique(myVector.begin(), myVector.end()), myVector.end())

unique(myVector.begin(),myVector.end())会将容器中重复元素移到末尾，并返回唯一元素序列的末尾，

erase这里会从唯一元素序列末尾开始，删除所有重复元素

algorithm库

介绍一些algorithm中常用到的功能函数

reverse(begin,end) // 将迭代器从头到尾逆向

sort函数

sort(begin,end,cmp_fuction) begin和end是数组的首尾，如果begin和end不是通用的数据类型，而是自定义的一些数据类型比如结构体，需要给出对应的比较函数，最好使用lamda函数，数据由编译器自动填入。

queue库

队列

priority_queue<数据类型，数据结构（一般为数组），比较函数> pq功能，将数组按照给定的比较函数自动排序，常用于建立堆

STL标准函数

unordered_set

集合

基本语法和vector类似

但查找效率高于vector

比vector多一个find函数

auto函数

auto C = sub (A,B);自动判断C的数据类型

pair函数

将两个数据项组合为一个单元，这两个数据项可以是相同类型或者不同类型的。

用途：在需要同时返回两个值的函数中，在关联容器map或multimap作为元素存储键值对。

pair.first和pair.second访问获取组合中的两个值。

//STL一些常用数据结构和函数
vector, 变长数组，倍增的思想
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算，按字典序

pair<int, int>
    first, 第一个元素
    second, 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

string，字符串
    size()/length()  返回字符串长度
    empty()
    clear()
    substr(起始下标，(子串长度))  返回子串
    c_str()  返回字符串所在字符数组的起始地址

queue, 队列
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素

priority_queue, 优先队列，默认是大根堆
    size()
    empty()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;

stack, 栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素

deque, 双端队列
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
    size()
    empty()
    clear()
    begin()/end()
    ++, -- 返回前驱和后继，时间复杂度 O(logn)

    set/multiset
        insert()  插入一个数
        find()  查找一个数
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x，删除所有x   O(k + logn)
            (2) 输入一个迭代器，删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器
    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代器
        find()
        []  注意multimap不支持此操作。 时间复杂度是 O(logn)
        lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
    和上面类似，增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound()， 迭代器的++，--

bitset, 圧位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()  返回有多少个1

    any()  判断是否至少有一个1
    none()  判断是否全为0

    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反

算法模板

快排

注意点

该模板的左指针和右指针分别是从l-1和r+1开始取的。因为该模板是先移动指针再开始比较的
pivot最好从中间取或随机取某个位置的
pivot是以值为区分点的

#include <iostream>
using namespace std;
#define MAXSIZE 1000000    
void quick_sort(int q[], int l ,int r)
{
    if(l>=r) return;
    
    int i = l-1 ,j = r+1;
    int pivot = q[(l+r) >> 1];
    while(i<j)
    {
        do i++; while (q[i] < pivot);
        do j--; while (q[j] > pivot);
        if(i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j+1 ,r);
}

int main()
{
    int n;
    cin>>n;
    int a[MAXSIZE];
    for (int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    quick_sort(a, 0,n-1);
    for (int i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    return 0;
}

归并排序

主要的思想是分治和归并

采取了类似双指针的方法。

先将所有的元素分成最基础的部分，再用双指针方法进行合并

要注意的点

右边界的取值为mid+1;

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 k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

#include <iostream>
using namespace std;
const int N = 100010;

int n;
int q[N],tmp[N];

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 k=0, i=l, j=mid+1;
    while(i<=mid && j<=r)
    {
        if(q[i]<=q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }
    while(i<=mid) tmp[k++] = q[i++];
    while(j<=r) tmp[k++] = q[j++];
    
    for(int i=l, j=0; i<=r; i++,j++) q[i] = tmp[j];
    
}
int main(){
    scanf("%d", &n);
    for(int i = 0; i<n; i++)
    {
        scanf("%d",&q[i]);
    }
    merge_sort(q, 0 , n-1);
    for(int i = 0; i<n; i++)
    {
        printf("%d ", q[i]);
    }
    
    return 0;
}

整数二分

一般应用情况

找大于等于数的第一个位置（满足某个条件的第一个数）
找小于等于数的最后一个位置（满足某条件的最后一个数）
查找最大值（满足该边界的有边界）
查找最小值（满足该边界的左边界）

注意点

有加必有减
check函数的选取

如果是左边界就取大于等于对应数

bool check(int x){/* .... */}  //检查x是否满足某种性质

//区间[l,r]划分为[l,mid]和[mid+1, r]时使用;
//寻找左区间的右边界
int SL(int l ,int r)
{
	while(l < r)
	{
		int mid = l + r >>1;
		if(check(mid)) r =mid; //判断mid是否满足性质
		else l = mid + 1;
	}
	return 1;
}

//寻找右区间的左边界
int SR(int l, int r)
{
	while(l<r)
	{
		int mid = l + r + 1 >>1
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	return 1;
}

#include <iostream>
using namespace std;

const int N = 100005;
int a[N];

int SL (int l ,int r, int x){
    while(l < r)
    {
        int mid = (l + r) >>1;
        if(a[mid] >= x ) r = mid;
        else l = mid + 1;
    }
    return l;
}
int SR(int l, int r, int x){
    while(l < r)
    {
        int mid = (l + r + 1)>>1;
        if(a[mid] <= x) l = mid;
        else r = mid - 1;
    }
    return l;
}
int main(){
    int n,q;
    int x;
    int l,r;
    scanf("%d%d", &n,&q);
    for(int i = 0; i< n;i++)    
    {
        scanf("%d", &a[i]);
    }
    while(q--){
        scanf("%d",&x);
        l = SL(0,n-1,x);
        
        if(a[l]==x)
        {
            r = SR(0,n-1,x);
            printf("%d %d\n",l,r);
        }
        else printf("-1 -1\n");
            
    }
    return 0;
}

浮点数二分

注意取得等号
注意mid大于n缩小右边界，小于n时缩小左边界

bool check(double x){}

double bsearch(double l, double r)
{
	const double eps = 1e-6; //eps表示精度，取决于题目对精度的的要求
	while(r - 1 > eps)
	{
		double mid = (l + r) / 2;
		if (check(mid)) r = mid;
		else l = mid;
	}
	return l;
}

#include<iostream>
#include<iomanip>
using namespace std;
double n, l , r, mid;

double q(double a){return a*a*a;}
int main(){
    cin>>n;
    l = -100000;
    r = 100000;
    double eps = 1e-8;
    while(r-l >= eps){
        mid = (l + r) / 2;
        if(q(mid)>=n) r = mid;
        else l = mid;
    }
    cout<<fixed<<setprecision(6)<<l;
    return 0;
}