wordpress用户前端化,整站优化关键词排名,在什么网站做公司人员增减,长春网长春网站设计站建设这里写目录标题 枚举结 排序结 模拟结 二分题结 高精度加、乘题结 减题结 除题结 结 位运算#xff08;均是拷贝运算#xff0c;不会影响原数据#xff0c;这点要注意#xff09;、|、^位运算特性细节知识补充对于n-1的理解异或来实现数字交换找到只出现一次的数据均是拷贝运算不会影响原数据这点要注意、|、^位运算特性细节知识补充对于n-1的理解异或来实现数字交换找到只出现一次的数据其余数据出现偶数次 、二进制中相邻的位的特点找出某个排列的所有子集 栈题结 单链表题结 双链表题结 队列二级目录二级目录 哈希表题结 字符串哈希题结 枚举
结
此类题就是暴力解法即可大部分需要枚举题目范围的所有情况
排序
结
使用算法sort即可
模拟
结
题目说啥我们做啥就按照题目描述来
二分
题 结
二分就是对于一组单调的数据两边的性质不同二分可以找到某一边性质的最值 如果找红色区间则会找到满足红色性质的最大值如果是红色区间mid ( l r 1) 1 如果找绿色区间则会找到满足绿色性质的最小值绿色区间则正常mid (l r) 1
补充如果出错了考虑check函数是否写错是否疏忽了一些情况比如此题题目并没有说所有的巧克力原料都要用所以直接判断遍历所有的边长如果有些边长比x小则算出来是0表示不使用该巧克力
注意点最后 L R 跳出循环注意最后有用的不是在循环中定义的那个mid而是L R 或者num[L] num[R]
高精度
加、乘
题 结
二者的核心思想都是根据遍历将当前位的运算都加到 t 身上之后pusht % 10然后更新 t t / 10这一步很精妙表示如果 t 小于10那么就不用进位如果不是那么就拿出其十位加到 t 为下一位的计算储备材料
不同的是加法最后如果 t 不为0则补1乘法则补 t
减
题 减法要先进行A 和 B的大小判断看是A大还是B大我们统一假设A大也就是A大的话返回true所以才会有上面的函数且最后如果if和for都没有返回的话最后返回true表示AB所以相等的情况我们也是返回true所以该函数是判断是否AB
将大的传入div函数且如果题目规定求A-B但是我们判断出B比A大那么我们还是将B、A传入最后输出的时候输出负号即可
结
该题目也是每次根据情况将当前位的数 全部给到 t 之后压入直接压t小于0的情况t 10% 10 之后判断t是不是真的小于0如果是那么 t 赋值为1如果不是那么 t 拨乱反正改回0
最后要去除前导0
除
题 除法有三个参数第三个参数是余数且是引用说明可以通过引用来返回余数是多少
且除法与其他不同其他的函数内都是从0开始这里是从后面开始因为存入时数据的高位在后面除法要从高位开始 之后是将所有的当前的数据加到 r 身上然后pushr / b且更新 r r % b更新余数
最后要将其倒序要将数据的高位放到容器末尾这样方便去除前导0 传入时由于第三个参数是传出参数所以直接传入一个int型变量即可
结
且除法与其他不同其他的函数内都是从0开始这里是从后面开始因为存入时数据的高位在后面除法要从高位开始 之后是将所有的当前的数据加到 r 身上然后pushr / b且更新 r r % b更新余数
最后要将其倒序要将数据的高位放到容器末尾这样方便去除前导0
main函数传参时传入时由于第三个参数是传出参数所以直接传入一个int型变量即可
结
知识点1他们都是根据具体情况将当前的运算全部存入 t 或者 r 中然后拿着 t 或者 r 进行结果的压入并更新 t 和 r为下一次做准备 知识点2加和乘法要额外注意判断最后的 t 如果循环结束t还存在那么要压入 1或者t 知识点3减法和除法要额外注意for循环之后进行前导0的去除 知识点4为了方便记忆以及前导0的去除所以我们统一在main函数压入数据时将数据的低位先压入。也就是从string的末尾开始压入表现为vector与string是反着的。 而输出时由于我们统一将个位放在了C容器的栈底所以输出时是从C容器的尾部开始输出 知识点五在函数中加减乘都是从个位开始计算也就是for循环从0开始而除是从高位开始计算也就是从容器的末尾开始for循环所以在for循环结束后要将其倒序一方面是因为这样方便记忆另一方面这是去除前导0的前提要求
位运算均是拷贝运算不会影响原数据这点要注意
、|、^
位运算特性细节 首先我们尝试不使用递归来解决这道题他让我们判断是一个数是否为2的次幂。 尝试往位运算方面靠位运算是通过二进制来解决问题的而二进制就是2的次幂的表示且二进制从低位向高位依次是2的012345…次方所以我们可以知道二进制表示为10000的数即第一位是1后面全是0的数是2的次幂数 所以初步的认知已经建立了。之后寻找位运算的特性如果一个数是1000的话那么0111 1 就是 1000而1000与0111做位与运算可以得到0000所以可以通过该性质找到10000特点的数
注意点1小于等于0的数可以直接排除 注意点2进行位运算时要在做完位运算之后加一层括号因为位运算的优先级低于
知识补充 2的偶数次幂mod3等于1例如4、16等mod3 等于 1 而2的奇数次幂就是2的偶数次幂再乘2此时如8、32mod3等于2 所以在求4的次幂时因为2的偶次幂一定是4的次幂所以我们在找到2的次幂数的基础上再找到那些是2的偶次幂的数那些数mod31
对于n-1的理解 对于一个二进制 n 10000010000101010n - 1 10000010000101000n - 1会将一个数的二进制表达最右边的1变为0而其他不变利用该特点可以得到1的个数
或者使用lowbit见算法一栏“基础算法”lowbit的时间复杂度更低
异或来实现数字交换 首先a a ^ b此后我们可以将一个a看成是变化之后的a而如果a^b则是原数据a、b b a ^ b此时a是变化之后的a将其拆开a ^ b ^ b此时a是变化之前的a所以就等于a ^ 0最终等于原来的a 而到此时a除了在第一行做出了改变其他地方均无改变所以还是第一行的结论可以将一个a看成是变化之后的a而如果a^b则是原数据a、b 所以a a ^ ba是第一行代码执行后变化的ab是原来的a所以将a拆开得到原来的a 和 b并且将b换成原来的aa ^ b ^ a再使用交换律得到a ^ a ^ b最后等于原来的b 找到只出现一次的数据其余数据出现偶数次 首先定义res 0 之后将res与数组中的每个数进行异或运算 用到的知识点 1、0^a a 2、b^b 0 、
二进制中相邻的位的特点 判断相邻位数是否交替为0、1
也就是相邻的位数上不能是相同的即不能是00或者11 而00对应于十进制是011对应于十进制是3
所以如果 n3 3则表示当前n的右边两位是11 如果n3 0,则表示当前n的右边是00注意此处还是3即0011结果为00。逻辑上他还有个等价式是0000结果为11也就是n0 3但是如果0的话可能转为二进制就变成一位0而3的话铁定在二进制是两位所以0会导致某些数据点报错
每次判断完之后将n1右移一位并覆盖到n注意每次右移一位如果右移两位可能会出现0110这样的数据会出错
注意点1运算一次进行多位二进制判断时尽量避免0尽可能找其等效式 注意点2从此处我们也可以看出我们之前的x1就是利用的原始定义来求的最终求出x二进制的个位因为1表示成二进制就是…00001
找出某个排列的所有子集 我们以一个存有三个数的数组为例那么nums.size()就等于3而他的子集可能会是没有元素或者一个元素或者两个或者三个如果我们挨个遍历的话时间复杂度肯定会剧增所以我们利用二进制即利用位运算 我们可以将某个数在or不在表示为二进制上的1or0现在我们已经有了不同的子集与二进制的对应那么如何进行遍历呢我们可以让 i 从 0 遍历到 小于1 size()因为1左移size位就变成了1000他正好就是四位的第一个数所以小于他的就是所有0位1位2位3位的二进制也就是下图所示情况。这样每个 i 的二进制都标识了一种数组子集的情况 有了这些 i 的循环我们如何判断当前是哪个二进制位上为1呢我们可以在每个i循环步内定义一个 j 循环j 从 0 到小于size 他实际上数组下标判断 i 1 j是否为1而1 j的循环是 001、010、100如果结果不为0那么就是为1即当前循环步的 i的二进制标识与当前 j 二进制中为1的那一位都是1即表明i 中对应 j 为1 的位置是1则nums[ size - j - 1 ]就是当前子集的元素之一
但是注意他的顺序不是“先是单个元素然后两个三个”他会先输出两个单元素再输出一个双元素再输出一个单元素…无规则的因为3对应二进制11肯定会得到两个数
如果想要从左边开始判断适当修改 i 和 j 的循环方向
栈
题 结
知识点1tt初始化为0那么栈顶元素就是从1开始所以栈不为空的话就是tt0而下标0的位置没有被使用 当然我们也可以使得tt初始化为-1那么栈顶元素就是从0开始tt0时不空
知识点2栈可以解决那些需要一边进行输入一边进行匹配的问题 知识点3注意特判要保证 i 0时再进行check。所以说有时候并不一定要设计出多优雅全能的代码哪里有问题就解决哪里就好了
单链表
题 结
知识点1主要就是将一些插入手法头插、随机插删除初始化等等操作熟悉起来 知识点2要注意初始化如果一道题中已知了链表的全貌那么在一开始就可以把链表构造出来head表示头指针是头结点的下标。然后最后一个结点的ne数组值是-1 知识点3如果后续还要有新的节点加入进来那么初始化时head就可以初始化为-1。后续有节点插入后就会自然形成尾节点的ne数组值是-1 知识点4注意遍历方式 知识点5ne等这些与其他节点有联系的操作都是通过下标联系即地址只有少数情况会用到e数值 注意点1本题是在原本的链表内操作在把x插到头结点的同时还会把x从原来的地方删除所以每次操作涉及插入和删除两个动作
双链表
题 结
知识点1因为链表的优越性也就是其在物理位置上的顺序无所大谓他的顺序是由指针域决定的所以我们会将e数组的0号位置设置为头结点1号位置是尾节点但是这两个点在e数组上并没有值他们仅仅代表头指针和尾指针所指的位置且对于双链表我们设置了l【】和r【】数组所以初始化时r[0] 1, l[1] 0,表示头指针位置指向尾指针位置尾指针位置指向头指针位置
知识点2 在k的右边插入顺序是 先新建一个结点之后设置新节点的r 和 l 因为这个比较好设置 其次就是选择更新旧结点的r 和 l 了但是如何选呢有个好的记忆方法是因为让我们在k的右边插入所以r[k] 是我们拿到右边旧结点的关键信息他会贯穿整个过程所以他应该最后一个被更新所以在k的右边插入就最后更新r[k] 知识点3对于双向链表插入是需要注意顺序的但是删除不需要注意顺序 知识点4对于双链表的遍历从 i r[0]开始当 i ! 1时i r[ i ] 注意循环条件不要写成r[ i ] ! 1这样的话最后一个元素将不会输出 知识点5至于要不要构建循环双链表则视题目情况而定构建方式加一个l[0] 1, r[1] 0其他操作不变
队列
二级目录
二级目录
哈希表
题
结
可能是用于处理一些集合该集合的特点是数据少但是数据有很大的也有很小的将其哈希到一个比较紧凑的区域节省空间和效率 思考有没有可能可以使用set or multiset代替
字符串哈希
题 结
他主要是将前 i 个字符组成的子串哈希成一个ULL值再根据【l r】的哈希值是h[r] - h[l - 1]*p[r-(l - 1)]这个公式从而可以迅速的求出任意一段子串
知识点1该计算公式用于字符串从1位置开始存储所以我们在写程序时要写从1开始输入字符串但是如果题目要求从0开始输入且题目据此规则进行查询那么无需改动其他的只需要在读入l1r1l2r2后传入get函数l1 1r1 1l2 1r2 1即可
知识点2要注意大写P131小写p是数组表示p的某次方 知识点3预处理初始化在全局位置所以p[]和h[]都是0在预处理之前我们要修改p[0] 1不然所有的p都是0h不用修改预处理时处理 i 从1到N或者题目若给出了字符串长度n则是到等于n如果拿不准直接N也可以注意p和h的预处理都建立在i - 1之上别写错了
知识点4h数组和p数组都是ULL对于无符号整形的变量如果超出了其表示范围那么会对其进行自动取模所以这里存入ULL类型是为了自动取模2的64次方该自动取模只会使用与无符号整型且如果遇到负数 则还会将其先加上模数变为整数 再取模
