蓝桥杯备赛(基础语法3)
·双指针
双指针简介
双指针算法是一种常用的算法技巧,它通常用于在数组或字符串中进行快速查找、匹配、排序或移动操作。
双指针并非真的用指针实现,一般用两个变量来表示下标(在后面都用指针来表示)。
双指针算法使用两个指针在数据结构上进行迭代,并根据问题的要求移动这些指针。双指针往往也和单调性、排序联系在一起,在数组的区间问题上,暴力法的时间复杂度往往是O(n^2)的,但双指针利用“单调性”可以优化到O(n)。常见的双指针模型有:
1)对撞指针
2)快慢指针
对撞指针
简介
指的是两个指针 left、right (简写为 l , r )分别指向序列第一个元素和最后一个元素。然后 l 指针不断递增,r不断递减,直到两个指针的值相撞或错开(即1>=r),或者满足其他要求的特殊条件为止。
对撞指针一般用来解决有序数组或者字符串问题(常见于区间问题):
查找有序数组中满足某些约束条件的一组元素问题:比如二分查找、数字之和等问题。
字符串反转问题:反转字符串、回文数、颠倒二进制等问题。
求解步骤
1.使用两个指针left,right。left指向序列第一个元素,即:left=1,right指向序列最后一个元素,即:right=n。
2.在循环体中将左右指针相向移动,当满足一定条件时,将左指针右移,left++。当满足另外一定条件时,将右指针左移,right--。
3.直到两指针相撞(即left==right),或者满足其他要求的特殊条件时,跳出循环体。
例题
对撞指针,每次判断s[l]和s[r]是否相等,如果相等就都移动一步,否则直接判断为“不是回文串”
快慢指针
简介
快慢指针一般比对撞指针更难想,也更难写。
指的是两个指针从同一侧开始遍历序列,且移动的步长一个快一个慢。
移动快的指针被称为快指针,移动慢的指针被称为慢指针。
为了方便理解,我们称快指针为r,慢指针为l,这样慢指针和快指针构成区间[l,r|。两个指针以不同速度、不同策略移动,直到快指针移动到数组尾端,或者两指针相交,或者满足其他特殊条件时为止。
求解步骤
1.使用两个指针l、r。l一般指向序列第一个元素,即:l=1,r一般指向序列第零个元素,即:r=0。即初始时区间[l,r] = [1,0]表示为空区间。
2.在循环体中将左右指针向右移动。当满足一定条件时,将慢指针右移,即l ++。当满足另外一定条件时(也可能不需要满足条件),将快指针右移,即 r++,保持[l,r]为合法区间。
3.到指针移动到数组尾端(即l == n且r == n),或者两指针相交,或者满足其他特殊条件时跳出循环体
例题
(1)
利用快慢指针,保持区间[ i, j ]尽可能小且和 >= S.在这里当[i, j]的sum >= S后,再增加j没有意义,所以i,j都不动了,当i增大后sum可能<S,此时j不可呢左移,所以只能右移,于是i, j都只能右移,
从来不会出现左移。
(2)
利用快慢指针,保持区间 [ i ,j ] 中大于等于k的个数至少有k个,且区间尽可能小,得到区间 [ I, j] 后,说明对于这个左端点i,有 n - j + 1 个右端点可取。思路和例题1类似,这里也是 i, j 都只能右移。
·构造
(1)
为使得序列乘积不为零,那么序列中就不能存在0,所以第一步就是将所有0先修改为1,这一步不可能省略,所以这一个操作的代价是0的数量。
在修改完成后,若序列之和不为零则直接输出答案:0的数量。若序列之和为零,说明序列中一定存在正数和负数(因为没有0了),只需要任意将一个正数+1即可,所以答案是0的数量+1。
(2)
x = y * y - z * z = ( y + z )( y - z )
不妨令 A = y + z , B = y - z ,设x,z均为非负整数,则有 A >= B , A - B = 2z.
说明AB之差是个偶数。
于是A,B只能是奇奇或偶偶的形式。
对于任何一个奇数x,我们都可以构造 B = 1 , A = x ,来使得x=A*B成立,
且 A - B 为偶数,满足条件。
对于一个偶数 x ,若其质因数分解之后的2的个数 >= 2,就一定可以写成两个偶数的乘积,反之一定不能。
最后结合前缀和思想O(1)求到答案。
方法一:
方法二:
(3)
容易想到二分,枚举一个mid,检查大小为mid的字符集能够使得这n个字符串字典序升序。难点在于check函数如何设计。若字符集大小为1很容易判断,只需要判断a序列是否是升序即可。但是ai最大可能到1e9,这里我们就要考虑如何存储下这些字符串,字符串中的元素应该要用数字来表示,但是我们肯定开不下长度为le9的数组,发现字符串中大部分都是0,于是我们可以用一个vector来描述当前的字符串,即除了0以外的所有位置。
例如字符串10000202可以描述为:[{1,1},{6,2},{8,2}],假设字符集大小为3(即超过3就要进位)。
当次数又来了一个长度为6的字符串,应该要在6的位置+1,并在变大的位置之后的所有位置全部置0(即从vector中删除),得到10001000,[{1,1},{5,1}],这个操作直接模拟即可。
·位运算
位运算简介
位运算的概念和作用
位运算是一种对二进制数的位进行操作的运算方式。
它直接对二进制数的每一位进行逻辑操作,而不考虑整个数的数值大小,一般情况下,位运算中每一位都相互独立,各自运算得出结果(左右移除外)。
在计算机科学和编程中,位运算常用于优化算法、位掩码操作、位字段处理等领域。在竞赛中,位运算经常考察异或的性质、状态压缩、与位运算有关的特殊数据结构、构造题等。
注意:位运算只能应用于整数,且一般为非负整数,不能应用于字符、浮点等类型。
整数的二进制表示
在计算机中,整数是通过补码表示的,但是一般情况下,我们对负数进行位运算意义不大,99%情况下都是对正整数进行处理,而正数的原码=补码,所以我们直接考虑二进制数的原
码,也就是直接地表示二进制数。
例如整数10,在计算机中存储如下(按照书写习惯,一般认为右边为低位,在左右移时尤为
重要):
常见的位运算
按位与AND(&)
按位与运算符(&)用于对两个操作数的对应位进行逻辑与操作。它的运算规则是,只有当两个位都为1时,结果位才为1,否则为0。两个数字做与运算,结果不会变大
按位或OR( | )
按位或运算符 ( | ) 用于对两个操作数的对应位进行逻辑或操作。它的运算规则是,只要两个位中有一个为1,结果位就为1,否则为0。两个数字做或运算,结果不会变小。
按位异或XOR( ^ )
按位异或运算符 ( ^ ) 用于对两个操作数的对应位进行逻辑异或操作。它的运算规则是,当两个位不同时,结果位为1,否则为0。两个数字做异或运算,结果可能变大也可能变小,也可能不变。
(两边同时异或y,抵消掉)
按位取反( ~ )
用于对操作数的每一位进行取反操作,即将0变为1,将1变为0。
按位取反操作通常用于无符号整数(unsigned int/long long),这是为了避免符号位取反造成干扰。
假设某个无符号整数只有4位,结果如下(长度不同结果也会不同,需要具体情况具体分析):
按位左移( << )
左移 ( << ) 操作将一个数的二进制表示向左移动指定的位数。
移动后,低位补0,如果数据类型为有符号整型,注意移动的时候不要移动到符号位上,或者干脆使用无符号整型。1会移动到符号位上。
左移操作相当于对原数进行乘以2的幂次方的操作。
例如,对于整数5(二进制表示为00000101),执行左移3位操作,相当于执行 5 * ( 2 ^ 3 ) 。
按位右移( >> )
左移(>>)操作将一个数的二进制表示向右移动指定的位数。
移动后,一般情况高位补0,如果数据类型为有符号整型,注意移动的时候让符号位为0,或者干脆使用无符号整型。如果符号位上有1不会被移走,这是负数位移的规则。
右移操作相当于对原数进行除以2的幂次方的操作。例如,对于整数13(二进制表示为00001101)执行左移2位操作,相当于执行13/4向下取整。
位运算技巧
判断数字奇偶性
获取二进制数的某一位
修改二进制中的某一位为1
快速判断一个数字是否为2的幂次方
获取二进制位中最低位的1
例题
(1)
(2)
拆位算贡献。
将整个问题划分为31个部分,分别表示数组元素二进制表示的第0位、第1位···第30位。
计算每一个部分的前缀和,对于每次询问,扫描每一个部分,判断这一位是否是1(即前缀和>0),如果是就算上这一位对答案的(求和的贡献)