map,二分查找,状态压缩,暴力(假硬币)

一个键值对应一个值,值的初始为零

#include 
using namespace std;

int main()
{
    map a;
	//键值为 int ,值也为 int 的一个 map
	
    a[4]=5;
    //键值 4 的值 为 5
	
    //遍历
    for(auto i : a){
        cout << i.first << "t" << i.second << endl;
        // first 为键值  second 为对应的值
    }
    map,int> m;
	//键值两个int 的 map
    return 0;
}

要查一个数在不在数组里面 , 每次差中间的值 ,小了就看左边,大了就看右边

只能是有序数组才能使用二分查找

递归实现:

int find(int left, int right, int arr[], int k) {
    if (left == right) {
        return arr[left] == k ? left : -1;
    }
    if(arr[(left + right) / 2] < k){
        return find((left + right) / 2 + 1, right, arr, k);
    } else {
        return find(left, (left + right) / 2, arr, k);
    }
}

循环实现:

#include 
using namespace std;

int main()
{
    int arr[] = { 45,56,89,90,132,165 };
    int N = -1, k = 88, left = 0, right = 6;
    while(true) {
        if (left == right) {
            if (arr[left] == k) {
                N = left;
            }
            break;
        }
        if (arr[(left + right) / 2] < k) {
            left = (left + right) / 2 + 1;
        } else {
            right = (left + right) / 2;
        }
    }
    cout << N << endl;

    return 0;
}

给定一个字符串 全排列所有的子字符串

长度为n的字符串,求所有子集

状态压缩(递归):

void Compress(int n, char* s, int len, char* subset,int i) {
    if (n == len) {
        subset[i] = '';
        cout << subset << endl;
        return;
    }
    Compress(n + 1, s, len, subset, i);
    subset[i] = s[n];
    Compress(n + 1, s, len, subset, i + 1);
}

状态压缩(循环):

#include 
using namespace std;

int main()
{
    string s = "abcdefg";
    for (int i = 0; i < 128; i++) {
        string subset;
        for (int o = 0, j = i; o < s.length(); o++, j /= 2) {
            if (j % 2 == 1) {
                subset += s[o];
            }
        }
        cout << subset << endl;
    }

    return 0;
}

暴力模拟,假设第n枚硬币的重量,其他的初始化为0,第 n 枚两种可能 1 或者 -1 再求和与题目给出的条件进行判断即可,如果符合条件直接跳出循环

#include 
using namespace std;

int is_coin(int N, int k) {
    //两个参数 枚举的硬币 枚举的值
    //没有枚举的硬币重量都为 0


    return 0;
}

int main()
{
    int N = 40;
    for (int i = 1; i <= N; i++) {
        //枚举每一枚硬币
        //题目保证有唯一解 所以找到了就直接跳出
        if (is_coin(i, 1)) {
            cout << "第 " << i << " 枚重了" << endl;
            //枚举找到了
            break;
        }
        else if (is_coin(i, -1)) {
            cout << "第 " << i << " 枚轻了" << endl;
            break;
        }
    }

    return 0;
}