记录从零开始的幸福刷题生活
前言
记录刷题过程中遇到的对自己有启发的代码或是思维方式
水滴石穿，绳锯木断
数据总喜欢对自己有过多的要求！
-
数据需要保留1位（或多位x）小数（需要考虑四舍五入）
对于上述要求，可以在原有数据基础上乘以（*）相应的倍数，即先扩大为原来的多少倍，这样可以把需要的小数部分转到整数部分，再让该数据+0.5，然后int强制转换，将转换后的数据处以（/）之前扩大的倍数，这样得到的数据即满足上述要求。
例如在一次消费中，消费金额为 cost = 178.57 ，保留1位小数，此时：
double cost = 178.57; cost = int(cost*10+0.5)/10.0;由于/运算向下取整，且int强制转换只保留整数部分，因此在原数据基础上*10后，需要考虑进位的百分位到了十分位，此时在该数据基础上+0.5，如果不进位（<0.5），则加上0.5后，并不会向个位进位，如果进位（>=0.5），则此时的个位数+1，经过强制转换保留整数位再/10后，该数又回到十分位，并且已完成四舍五入（即保留了1位小数）。
最后得到的cost = 178.6。
-
在大量数据（整型）中统计某一个数字出现的次数
统计1-n个连续数字中，x（0<=x<=9）出现的次数，对于这种连续的数据，通过循环得到每一个数据，再不断的处理该数字的个位数，个位数与x判断完成后，数据/10，将原十位数转变为个位数继续进行判断。
for(i=1;i<=n;i++){ b = i; while(b!=0){ if(b%10 == x) count++; //比较个位数 b = b/10; //原十位数转到个位数，进行下一个循环比较 } } cout<<count<<endl; -
数据需要进行大小写转换
对于string类，
中有方法能够进行大小写转换。即： #include <iostream> #include <algorithm> string str; transform(str.begin(),str.end(),str.begin(),::tolower); //全部转换为小写 transform(str.begin(),str.end(),str.begin(),::toupper); //全部转换为大写除此之外，我们还可以自己写大小写转换的函数，即利用ASCII的差值，通过加减就能转换为另外一个字母所对应的ASCII值。
一切为了节省空间！
-
数值互换
现有a，b两个数据类型相同的变量，需要将这两个变量数值互换。
一般方法是构建一个中间变量c，通过c暂存其中一个数值，使得这两个数值可以在不丢失数值的前提下互换。
//以整型变量举例 int c; c = a; a = b; b = c;为了节省空间，可以通过加减运算来进行互换而不用引入一个新的变量。 通过加减运算，节省了1/3的空间！（滑稽
a = a + b; b = a - b; a = a - b;
灵活多变的vector！
-
字符串拆分
一串待输入的未知长度的字符串xxxxxx，我们在输入后还要对其进行拆分x x x x x，并对拆分后的字符进行处理，这种情况下使用char[]或者string型的数据类型，后续的处理都十分麻烦，这个时候使用vector就显得十分方便，因为vector本身并不会要求在初始时就定好空间大小，而是可以随着需要不断扩大或者缩小的。在此基础上，我们继续对输入进行识别、控制，就能够将一串字符输入到vector_1里，并且还能继续下一串字符vector_2，且双方的字符串并不会有冲突。
在这里除了用到了vector本身的特性，我们还会使用到cin.get()，这个函数能够将“回车”也保留下来，接着对接收到的字符串进行识别处理，就知道当前输入的字符串是否完毕了。
vector的部分使用
vector<char>::iterator it; vector<char> a, b; char c; while(cin.get(c)){ //将输入的所有字符全部保留在c中，包括"回车" if(c == '\n') //对字符c进行判别，如果识别到回车，则本次输入结束 break; a.push_back(c); //如果当然接收的字符不是“回车”，则将当然字符放入vector a中，继续接收下一字符 } while(cin.get(c)){ //同理，在上一串字符完全接收后（即识别到了“回车”），开始接收下一串字符 if(c == '\n') break; b.push_back(c); }vector中对自身的遍历
vector<char>::iterator it; vector<char> a; for(it = a.begin();it!=a.end();it++){ sum_a *= *it - 64;//这里减64是因为原题中A代表数值“1”，A的ASCII是“65” //因此A~Z减去64即为对应的数字 }
让我们快乐搜索吧！
-
深度优先搜索（DeepFirstSearch）
就像它的名字这样
简单易懂，我们搜索时总是以往更深层次的搜索为首要目的，即不断远离初始节点，离它越远越好，直到当前不能再继续往深了走了，我们再向上返回，每返回一层，我们就找找有没有其它路径能继续向下走，直到我们回到了初始节点，就将所有数据都遍历了一遍。排列组合中的深度优先搜索经常会用到标记符，标记该节点当前是否被遍历过，如果某一元素在前几层被遍历了，我们就可以直接选择放弃这一条支路，这样可以去重复，节省时间。让我们来使用一个vis[]数组保存它吧。如果vis[]=0，就表明它还没有被光临过，如果vis[]=1，就表示当前元素已经被光临过了。
并且vis[]=1,vis[]=0这两个标记经常嵌套使用，在我们进入下一层前，先把当前层标记上（vis[]=1），当从下一层退回来，并且要退回上一层时，我们就把当前层的标记解除(vis[]=0)，这样就能够保证所遍历的一条路中不会有重复的元素。
假如现在我们需要在n个数中寻找任意k个数的排列组合（k<n)，并求每一个组合本身的和。
这个问题在于我们需要找到所有的任意k个数的排列组合.
实例代码如下：
bool vis[25]; void dfs(int t,int sum){ //t代表现在select了多少个数 //sum表示当前的和 for(int i=0;i<n;i++){ if(vis[i])//如果被选过 continue;//直接进入下一次循环 vis[i]=true;//标记为选过 dfs(t+1,sum+a[i]);//递归 vis[i]=false;//要跳出当前元素了，解除标记 } return ;//这一个步骤下，所有的都枚举完了，直接返回去 }当然，排列组合中的深度优先搜索，除了使用vis[]进行已选择元素的标记外，还可以使用不降原则，这样选择到的下一元素的数组下角标，一定不是遍历过的。
那么什么是不降原则呢？
举个
例子栗子：我们在1 2 3 4 5 6六个数字中求其中任意三个数字的排列组合
根据不降原则，我们第一轮会得到：
1 2 3
1 2 4
1 2 5
1 2 6
那么第二轮，我们会从1 3 开始，
*号应该是什么数字呢
根据不降原则，*所选的数必须大于已经选择(1、3)的数字
即此时的*不能为1 2 3，
让我们看看第二轮的选择：
1 3 4
1 3 5
1 3 6
很明显，根据不降原则，我们筛选掉了“1 3 2”这个和第一轮中“1 2 3”重复的组合
再来第三轮：
1 4 5
1 4 6
//筛掉了“1 4 2”、“1 4 3”两个已重复的组合
第四轮：
1 5 6 至此，第一位是“1”的排列已经完全遍历完毕了
接着找第一个是“2”的排列
2 3 4
2 3 5
…
可以发现，越往后，我们筛选掉的重复组合越多，并且通过不降原则，在类似问题中我们甚至可以省略vis[]的标记，因为遵循不讲原则的情况下，我们是不会走重复路线的（仅所选元素无先后关系）
不降原则的代码实现
在不降原则的代码实现中，会多一个变量，这个变量用于控制在进入下一层后，开始循环时的起始下标：
void dfs(int t, int sum, int startx){//不降原则，去重复 //t代表现在select了多少个数 //sum表示当前的和 for(int i=startx;i<n;i++){ dfs(t+1, sum+a[i], i+1);//i+1采用不降原则，继续进入深搜的过程中要找角标比i大的那些数据 } return; //至此，所有组合已枚举完毕 //直接返回 }
