浅谈二分
二分查找在程序设计中,是一个十分基础并且易错的功能。
现代CPU会使用大量的流水线,并配合分支预测进行运行效率的提升。
分支预测即就是通过对程序if else
等条件分支进行预测,并提前执行相关代码。如果预测正确,显然会提升效率,如果预测失败,那么将不得不清空流水线,重新来过,此时便会影响效率。
目前市面上主流CPU的分支预测,正确率可以达到90%以上。
https://leetcode.com/problems/special-binary-string/description/
定义Special Binary String:
现在给出一个Special Binary String,可以任意交换满足Special Binary String的子串,求满足条件的Special Binary String字典序最大的串。
Codeforces 1084C - The Fair Nut and String
给出一个字符串,查找有多少个被b隔开的a的子串。如a
、aba
,abba
,abbbba
等都是合法的,但aa
是非法的。
但要注意的是aba
,abba
,abbbbbba
等在统计的过程中只计算一个。
实现一个数据结构,以充当LRU缓存。
两种操作:
1. get(x): 查询key为x是否存在缓存中,如果存在,返回x所对应的value,否则返回-1.
2. put(key,value): 删除原有的key-value对,插入新的key-value对。如果LRU容量满了,删除最远的被访问到的元素。
luoguP2765魔术球问题,给出n个柱子,要求柱子每次只能从最上面放球,任意相邻两个球之和为完全平方数。球编号为1、2、3....,每个球都必须放,不能不放。求最后能放多少个球,每根柱子上的球分别是什么?