C++编程小技巧

蔚落 2022-05-14 00:24 436阅读 0赞

**1、整型越界问题**  
在编程过程中经常会遇到输出值在类型区间之外，越界的情况，解决方法如下

1.  转为log求解
2.  改变数据类型，如int转为long long扩大整型边界
    
    > long long本质上还是整型，只不过是一种超长的整型。  
    > int型：32位整型，取值范围为-2^31 ~ (2^31 - 1) .  
    > long：在32位系统是32位整型,取值范围为-2^31 ~ (2^31 - 1)；在64位系统是64位整型,取值范围为-2^63 ~ (2^63 - 1)  
    > long long：是64位的整型，取值范围为-2^63 ~ (2^63 - 1)
3.  使用大树方法进行运算（这个有点难，需要仔细琢磨）

**2、各种输入分析**

1、一行包括多个数据，数据个数知道，用空格分开

vector<int> input;
    while(n--)
    {
        int a;
        cin>>a;
        input.push_back(a);
    }

2、输入未知行数的字符串

string a;
    vector<string> aa;
    while(cin>>a)
    {
        aa.push_back(a);
        a.clear();
    }

3、输入行数已知的成对值

vector<pair<int,int>> input;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        input.push_back(make_pair(a,b));
    }

4、输入用空格隔开未知个数的数字

vector<int> input;
    int main()
    {
        int n;
        while (getchar()!='\n')
        {
            scanf_s("%d", &n);
            input.push_back(n);
        }
    }

上述方法因为使用getchar的原因，第一个输入的数字不会保存下来，改进代码如下：

vector<int> input;
    int main()
    {
        do 
        {
            int n;
            cin >> n;
            input.push_back(n);
        } while (getchar() != '\n');
        return 0；
    }

5、输入多行，多列的二维数组（相当于行列数给定已知，每一行的值用空格隔开，换行符表示下一行输入）

vector<vector<int>> all;
    vector<int> input;
    
    int main()
    {
        int r, c;
        cin >> r >> c;
        cin.ignore();
        while (r--)
        {
            int col = c;
            while (col--)
            {
                int x;
                cin >> x;
                input.push_back(x);
            }
            all.push_back(input);
            input.clear();
        }
        return 0;
    }

6、保存：输入行数已知，但列数未知，用空格隔开的数字，换行表示下一行的多维数组

vector<vector<int>> all;
    vector<int> input;
    
    int main()
    {
        string buf;
        int r;
        cin >> r;
        cin.ignore();
        while (r--)
        {
            getline(cin, buf);
            int len = buf.size();
            int j = 0;
            for (int i = 0; i < len; i++)
            {
                if (buf.at(i)==' ')
                    //aoti（字符串转为数字）+substr（取子字符串）+c_str（把string对象转换成c中的字符串样式）函数的使用
                    input.push_back(atoi(buf.substr(j, i - j).c_str()));
                    j = i + 1;
                }
            }
            input.push_back(atoi(buf.substr(j).c_str()));
    
            all.push_back(input);
            input.clear();
            buf.clear();
        }
        return 0;
    }

**3、vector等容器的各种处理**  
1、逆序

reverse(a.begin(),a.end())

2、sort函数实现排序（stable\_sort是稳定排序，即对比结果相等时相对位置不变，使用方法类似于sort函数）

sort(a.begin(),a.begin())

> 如果是pair类型的未指定排序方式时，默认按first从小到大排序

按给定排序function进行排序

bool cmp1(pair<string, int> a, pair<string, int> b)
    {
        return a.second < b.second;//按pair的第二个元素，从小到大升序
    }

3、查找某个特定字符出现的位置

int index = input.find('a');//从前往后的第一个
    查找失败则返回-1，查找成功返回第一个字符的下标
    int index = input.rfind('a')//从后往前查的倒数第一个

4、获得从某个字符开始的子串

string a,b;
    string input;
    //substr是左包右不包的区间，调用格式：substr(startindex,sublength)
    a = input.substr(index);//即从index开始往最后
    b = input.substr(0,index);//即[0,index)区间

5、查找最大值

int max = *max_element(a.begin(),a.end());//调用函数

6、删除第i个数据

a.erase(a.begin()+i);

7、在指定位置插入某个值（可用于逆序输出链表）

result.insert(result.begin()+i,head->val);//实现在容器的第i位插入头指针指向的数值

8、判断某个字符是否是数字  
直接调用isdigit()函数

string str;
    isdigit(str.at(i));//该字符是数字则输出true，不是数字则输出false

9、给vector< int >进行赋初值

vector<int> input(strlen(buf),0);//将长度为buf长度的input全部赋值为0

**4、杨辉三角的使用**  
杨辉三角的第i行第j个数值其实就是从i个数中提取j个数的所有情况（不考虑先后顺序），及Cij。构建杨辉三角：

int c[100][100]
    int init()
    {
        c[0][0]=1;
        for(int i=1;i<100;i++)
        {
        
            c[i][0]=1;
            for(int j=1;j<100;j++)
            {
        
                c[i][j]=c[i-1][j-1]+c[i-1]c[j]
            }
        }
    }

使用案例：  
在x个质量为A的苹果和y个质量为B的香蕉中挑选搭配出重量为k的水果，问有多少中方案？

for(int i=0;i<x;i++)
    {
        for(int j=0;j<y;j++)
        {
            if(A*i+B*j==k)
                count+=c[x][i]+c[y][j];
        }
    }

**5、进制字符串与整数之间的转换**

输入：一个字符串，是一个整数N表示成X进制和Y进制的字符串拼接
    输出：计算整数N是多少

问题简单化：先求从最左边到第i位的字符串对应整数的值xbase，同时求最右边到第i+1为的字符串对应的整数的值ybase；如果xbase==ybase，则N=xbase  
**难点：**  
从左到i，长度不知道，从右到i+1，长度也不知道，常规的进制转换为整数方法不可用

//常规已知进制数和进制结果转换为对应整数
    int main()
    {
        int x;
        string str;
        cin >> x >> str;
        int len = str.size();
        int sum = 0;
        for (int i = len-1; i >= 0; i--)
        {
            sum += pow(x, len - 1 - i)*(str.at(i) - '0');
        }
        cout << sum << endl;
        return 0;
    }

解决从left=0到left=i，即从高位往低位计算得到对应整数的方法

int main()
    {
        int x;
        string str;
        cin >> x >> str;
        int len = str.size();
        long xbase = str.at(0) - '0';
        for (int i = 1; i < len; i++)//这里的i相当于left不断像右移动，len相当于位置终点i
        {
            xbase = xbase*x + (str.at(i) - '0');//相当于用循环实现pow函数
        }
        cout << xbase << endl;
    }

解决从低位往高位，假设从尾到头计算进制表示的整数

int main()
    {
        int y;
        string str;
        cin >> y >> str;
        int len = str.size();
        long ybase = 0;
        int j = 0;//假设从右往左到头
        int ex = 1;//相当于y^0=1
        for (int i = len-1; i >= j; i--)
        {
            ybase = (str.at(i) - '0')*ex + ybase;
            ex = ex*y;//pow(y,count);
        }
        cout << ybase << endl;
    }

**6、大树运算（eg：实现两字符串的相乘）**

//大树实现两字符串相乘
    string BigIntAdd(string &tmp, string &ret)
    {
        int lena = tmp.length();
        int lenb = ret.length();
        const char* pa = tmp.c_str();
        const char* pb = ret.c_str();
        int i = lena - 1;
        int j = lenb - 1;
        int carry = 0;
        string addup;
        while (i >= 0 || j >= 0)
        {
            int sum = 0;
            if (i >= 0)
            {
                sum += pa[i] - 0x30;
                i--;
            }
            if (j >= 0)
            {
                sum += pb[j] - 0x30;
                j--;
            }
            sum += carry;
            addup = to_string(sum % 10) + addup;
            carry = sum / 10;
        }
        if (carry)
            addup = to_string(carry) + addup;
        return addup;
    }
    
    string BigIntTimes(string &a, string &b)
    {
        int lena = a.length();
        int lenb = b.length();
        int shoter = 0;
        int longer = 0;
        const char* pshoter;
        const char* plonger;
        if (lena > lenb)
        {
            shoter = lenb;
            longer = lena;
            pshoter = b.c_str();
            plonger = a.c_str();
        }
        else
        {
            shoter = lena;
            longer = lenb;
            pshoter = a.c_str();
            plonger = b.c_str();
        }
        string tmp;
        string ret = "0";
        int zero = 0;
        for (int i = shoter - 1; i >= 0; i--)
        {
            int blow = pshoter[i] - 0x30;
            int carry = 0;
            int product = 0;
            tmp.append(zero++, '0');
            for (int j = longer - 1; j >= 0; j--)
            {
                product = blow * (plonger[j] - 0x30) + carry;
                tmp = to_string(product % 10) + tmp;
                carry = product / 10;
            }
            if (carry)
                tmp = to_string(carry) + tmp;
            ret = BigIntAdd(tmp, ret);
            tmp.clear();
        }
        return ret;
    }
    
    int main()
    {
        string a;
        string b;
        while (getline(cin,a)&&getline(cin,b))
        {
            cout << BigIntTimes(a, b) << endl;
        }
        return 0;
    }

参考：[大树乘法][Link 1]

[Link 1]: https://blog.csdn.net/LucasDove/article/details/50728508