c++

Learn C++ With Object Oriented

今天 你面向对象了吗？

咱就是说 也想感受感受c++的魔力

learn from scratch

do while语句

do
{
   statement(s);
    
}while( condition );

在循环尾部检查条件 至少执行一次循环

switch语句

switch(a){
	case 1:
		//...
		break;
	case 2:
		//...
		break;
	default:
		//...
		break;
}

不能直接用于string，可用map将string对应于int型再用switch

vector容器

能够存放任意类型的动态数组 线性有序

#include<vector>

vector<elem_type> obj; //创建一个向量存储容器 元素类型为elem_type
obj.size()  //返回容器中元素个数
obj.empty() //判断是否为空 返回bool值
obj.push_back(elem) //在数组最后添加数据 
obj.pop_back() //弹出数组最后一个元素
obj.clear() //清零
obj.insert(obj.begin(), x) //在开头插入元素x

stack

栈 先进后出

#include<stack>

stack<int> s;
int x;
s.push(x); //入栈
s.top(); //返回栈顶元素
s.pop(); //删除栈顶元素 并不返回该元素
s.size(); //返回栈中元素个数
s.empty(); //判断栈是否为空 返回bool值

unordered_map

#include<unordered_map>

unordered_map<char, int> myMap; // <key, value>
//插入元素
myMap['a'] = 1;//已存在则修改 不存在则插入
myMap.insert( { {'b', 2},
                {'c', 3} } );
//修改元素
myMap['a'] = 0;
//删除元素
myMap.erase('a'); //删除key为a的元素
myMap.erase(myMap.begin()); //删除第一个元素
//查询指定key的元素的个数 在unordered_map中非0即1
map.count('a')

myMap.clear();//清空
myMap.empty();//判空
myMap.size();//查询键值对数量

排序算法

快速选择排序

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止 。

code

#include<iostream>

using namespace std;

const int N = 100010;

int n;
int q[N];

void quick_sort(int q[], int l, int r)
{
    if(l >= r)
        return;
    
    int i=l-1, j=r+1;   
    int x = q[(l+r)/2];
    while(i < j)
    {
        do i++; while(q[i] < x); //先++
        do j--; while(q[j] > x);
        
        if(i < j) swap(q[i], q[j]);
        
        
    }
    quick_sort(q, l, j);
    quick_sort(q, j+1, r);
    
}

int main(){
   scanf("%d ", &n);
   
   for(int i; i < n; i ++)
       scanf("%d", &q[i]);
   
   quick_sort(q, 0, n-1);
   
   for(int i; i < n; i ++)
       printf("%d ", q[i]);
   
   return 0;
}

归并排序

将两个有序数组合并

1. 确定分界点 mid = (l + r) / 2
2. 递归排序左右部分
3. 合并

code

#include<iostream>

using namespace std;

const int N = 100010;

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

    return ;
}

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;
}

整数二分法

code

// 区间[l, r]被划分成[l, mid]和[mid+1, r]时使用：
int bsearch_1(int l, int r)
{
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid)) r = mid;   //check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}

//区间[l, r]被划分成[l, mid-1]和[mid, r]时使用：
int bsearch_2(int l,int r){
    while(l<r)
    {
        int mid = l+r+1>>1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    return 1;
}