(蓝桥杯C/C++）——底子算法(上）

目次

一、二分法
1.二分法简介
二分法简介-解题步调
2.整数二分-简介            
整数二分-模板
3.浮点二分-简介
  浮点二分-模板
4.二分答案-简介
二分答案-模板​​​​​​​
二、位运算
1.位运算简介
2.常见的位运算
按位与AND(&)
按位或OR( | )
按位异或XOR(^)
按位取反(~)
按位左移(<<)
按位右移(>>)
3.位运算本领
1.判定数字奇偶性
2.取二进制数的某一位
3.修改二进制中的某一位为1
4.快速判定一个数字是否为2的幂次方
5.获取二进制位中最低位的1
三、贪婪算法
1.贪婪算法先容
2.贪婪算法实现步调
3.常见贪婪模子和例题
四、模拟算法
1.模拟算法先容
2.例题解说
五、双指针
1.双指针先容
2.对撞指针
3.快慢指针

六、构造
1.构造先容
2.构造标题标特点
3.构造的应用场景
4.构造例题分析
七、​​​​​​​进制的转换
1.进制的本质
2.将恣意进制转换为十进制
3.将十进制转换为恣意进制

---

一、二分法

1.二分法简介

二分法是一种高效的查找方法，它通过将标题标搜索范围一分为二(两边具有显着的区别)，迭代地缩小搜索范围，直到找到目的或确定目的不存在。
分法实用于有序数据聚集，而且每次迭代可以将搜索范围缩小一半。
分法本质上也是罗列，但和暴力罗列差异，二分法利用数据结构的单调性镌汰了很多不须要的罗列，从而极大地进步了服从，一样平常可以将O(n)的罗列优化到O(logn)。
常见的二分范例有:
(1)整数二分
(2)浮点二分
(3)二分答案(最常见)
二分法简介-解题步调

1.研究并发现数据结构(或答案变量)的单调性。
2.确定最大区间[L,R]，确保分界点肯定在内里，详细有一些细节:若以r作为答案，那么答案区间在[L+1,R]，若以L作为答案，那么答案区问在[L,R-1]。
3.确定check函数，一样平常为传入mid(区间中某个下标)，返回mid所属地区或返回一个值，当check函数较简朴时可以直接判定。
4.盘算中点mid =(L+R)/2，用check判定该移动L或R指针，详细移动哪个必要根据单调以及要求的答案来判定。
5.返回L或R，根据题意判定。

2.整数二分-简介

整数二分就是在一个有的有序数组上，举行二分查找，一样平常为找出某个值的位置)大概是找出分界点。
这个数组肯定是开的下的，其数组巨细一样平常在1e6（1e6 = 1000000）以内。
地区分别如下图。
                                   找第一个>=6的，即6的左界限，返回right

2	4	4	6	6	10	18
a1	a2	a3	a4	a5	a6	a7
		↑ left	↑ right

                                       

                                     找末了一个<=6的，即6的右界限，返回right

2	4	4	6	6	10	18
a1	a2	a3	a4	a5	a6	a7
				↑ left	↑ right

整数二分-模板

找到升序数组a中的x第一次出现的位置
int L=0,R=1e9;
//留意这里的判定条件，如允许以包管L，L终极肯定收敛到分界点代码如下（示例）：
while(L + 1 != r)           //L和R相邻时推出
{  
         int mid =(L + R) / 2;
//假如a为升序，阐明mid偏大了，必要减小mid，就只能将r变小，即r = mid
if (a[mid] >= x)
R = mid            //保持在所属地区
else L = mid;  
}
cout << r << '\n'；

3.浮点二分-简介

浮点二分不再是在有序数组上做二分查找，而是在某个实数范围内举行查找，由于实数域自己是单调的，以是也满意单调性，和整数二分的紧张区别在于利用的变量范例、退出的判定条件差异。


浮点二分-模板

eps是一个非常小的浮点数，用于处置处罚浮点数比力时的毛病或精度标题。
//盘算单调函数f(x)的零点
double L = 0; R = 1e9, eps = 1e-6
//留意这里的判定条件，r终极肯定收敛到分界点
while(R-1>= eps)             //eps足一个极小量，设置为1e-6较符合
{  
       double mid = (1+R) / 2;
      //f(x)单调递增，f (mid) >= 0，阐明mid偏大了，必要减小mid，就只能将R变小，即r=mid
           if (f (mid) >= 0)
            R = mid;
        else L = mid;
}
//末了返回L，R差异不大
cout << R << '\n';

4.二分答案-简介

二分答案是二分法中最常见也最紧张的题型，观察的比力机动，必要选手从标题中发现某个单调的函数，然后对其举行二分。
常见的模子是:
二分框架(时间复杂度O(logm)) + check兩数(时间复杂度O(n))
一样平常情况下，我们会将答案举行二分，然后在举出某个大概解后判定其是否可以更优或是否正当，从而不绝迫近最优解。
二分答案的题的特性:假如已知某个答案，很轻易判定其是否正当或更优。某些贪婪标题大概可以转化成二分答案标题。


二分答案-模板
  

bool check(int mid)
{  
       bool res = true;
       //do somtnin to check the authority of mid ...
       return res;
}
int main()
{  
      int L = 0; R = 1e9;
        while(1 + L !=R)
     {  
        int mid = (L + R）/ 2;
       //详细写法必要根据题意修改
        if (check (mid)) L = mid;
        else R= mid;
     }
cout<<  L <<'\n';//详细输出的内容必要根据题意判定
}


二、位运算

位运算是一种对二进制数的位举行操纵的运算方式。
它直接对二进制数的每一位举行逻辑操纵，而不思量整个数的数值巨细，一样平常情况下，位运算中每一位都相互独立，各自运算得出效果(左右移除外)在盘算机科学和编程中，位运算常用于优化算法、位掩码操纵、位字段处置处罚等范畴。
在比赛中，位运算经常观察异或的性子、状态压缩、与位运算有关的特别数据结构、构造题等。
留意:位运算只能应用于整数，且一样平常为非负整数，不能应用于字符、浮点等范例
1.位运算简介

在盘算机中，整数是通过补码表现的，但是一样平常情况下，我们对负数举行位运算意义不大，99%情况下都是对正整数举行处置处罚，而正数的原码=补码，以是我们直接思量二进制数的原码，也就是直接地表现二进制数。
比方整数10，在盘算机中存储如下(按照誊写风俗，一样平常以为右边为低位，在左右移时尤为紧张):

val	0	0	0	0	...	1	0	1	0
idx	31	30	29	28		3	2	1	0
int 32位

2.常见的位运算

按位与AND(&)

按位与运算符(&)用于对两个操纵数的对应位举行逻辑与操纵。它的运算规则是，只有当两个位都为1时，效果位才为1，否则为0。两个数字做与运算，效果不会变大。
同一为一，有零为零

x	y	x&y
0	0	0
0	1	0
1	0	0
1	1	1

按位或OR( | )

按位或运算符(1)用于对两个操纵数的对应位举行逻辑或操纵。
它的运算规则是，只要两个位中有一个为1，效果位就为1，否则为0。
两个数字做或运算，效果不会变小。
同零为零，有一为一

x	y	x|y
0	0	0
0	1	1

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金