首页 > 其他分享 >20230724日报

20230724日报

时间:2023-07-24 15:25:31浏览次数:57  
标签:map right 日报 元素 first left 20230724 指针

简单的求和

做题原因

之前TLE30和TLE60,一直没有做出来

做题过程

  1. 想到了尺取法,重新听了尺取法的课,看了尺取法的模板。
  2. 看了之前错误的代码,决定沿用之前使用map的方法,但是在找不出之前的错误,重新写了一遍代码
  3. 交上去AC

解题思路

  • 首先输入的元素是不需要按照它本来的顺序的(可以重新排序)

  • 需要给元素进行排序(set或者map,但是set会去重,所以选择map)

  • 因为是计算加法,所以只要计算过一次,所有相同的元素都使用(map)

  • 需要记录元素的个数(map)
    根据以上三点,我选用了map

  • 相加刚好等于k,所以比k大或者比k小都需要调整范围

  • 元素是排好序的
    根据以上两点,我选择了尺取法

代码实现

auto left = mp.begin();//设置左指针,map的第一个元素  
auto right = mp.end(); right--;//设置右指针,map的最后一个元素  
while (left != right) {//当左指针和右指针不相等时(相等考虑的情况不一样)  
if (left->first + right->first == k) {//如果相加等于k  
ans += left->second * right->second;//做指针的元素任意取出一个和右指针的元素任意取出一个进行搭配都可以,所以时乘法  
left++;//将左指针后移  
if (left == right) {//如果相等,循环结束,和上面的判断条件一样  
break;  
}  
right--;//因为这两个数相加刚好等于k,所以任何一个数加减都不会再等于k,所以这里面右指针也要向前移动  
} else if (left->first + right->first > k) {//如果大于  
right--;//那么右指针向前移动,减少其中一个数  
} else if (left->first + right->first < k) {//如果小于  
left++;//那么左指针向后移动,增大第一个数  
}  
}  
if (2 * left->first == k) {//如果相等,那么要考虑的就是这个数乘2是否等于k  
ans += left->second * (left->second - 1) / 2;//从这个数里面取出任意一个,这个数的数量减少1,然后再从这些数里面取出一个,但为了避免同样的a和b,第一次取出a然后取出b,第二次取出b然后取出a的情况,需要除以2  
}

长度最小的子数组

做题原因

练习尺取法

做题思路

因为数据范围为\(1\le n\le 3\times 10^{5}\),
所以每个都遍历的话会就是\(O\left ( n^{2} \right )\) ,
肯定会TLE,
所以想到了尺取法。

如果只遍历一端的话,
那么时间复杂度大概在\(O\left ( n\log_{}{n} \right )\)左右,
不会TLE,
所以我们只需要遍历每个端点最短的的\(\ge s\)的子数组的长度就结束这个端点的遍历(因为后面即便有\(\ge s\)长度也比之前找到的长,没有找的必要),
然后把它和目前所有端点最短的比较

标签:map,right,日报,元素,first,left,20230724,指针
From: https://www.cnblogs.com/Eutopiax7/p/17577310.html

相关文章

  • 成语积累 20230724
    难兄难弟:nan4xiongnan4di:处于同样困境的人。(nan2:兄弟二人都非常好,难分高下。或讥讽两者同样低劣。出处:元方难为兄,季方难为弟。近义:难分伯仲)暴虎冯河:暴:通"虣",和老虎打斗;冯:通"淜",指无舟渡河。空手打虎,徒步过河。多用于比喻有勇无谋,冒险蛮干。也比喻勇猛果敢。例句:我原以为他......
  • 课程设计工作日报表6/18
    课程设计工作日报表时间:2023年  6月18日序号工作分类工作任务完成情况待解决问题解决方法备注1平衡二叉树的根将给定的一系列数字插入初始为空的AVL树,请你输出最后生成的AVL树的根结点的值。对于给定一系列数字,插入初始为空的AVL树,可......
  • 日报
    ActivityActivity 是与用户交互的入口点。它表示拥有界面的单个屏幕。例如,电子邮件应用可能有一个显示新电子邮件列表的Activity、一个用于撰写电子邮件的Activity以及一个用于阅读电子邮件的Activity。尽管这些Activity通过协作在电子邮件应用中形成一种紧密结合的用户体......
  • 人民日报:天翼云持续拓展云网基础设施覆盖广度和深度
    5月31日,由人民日报文化传媒有限公司主办的2023数字经济论坛在北京举行,本次论坛主题为“发展数字经济,共建数字中国”。人民日报社副总编辑徐立京、中国国际经济交流中心副理事长王一鸣、科学技术部高技术研究发展中心主任张洪刚、工业和信息化部信息技术发展司一级巡视员王建伟、中......
  • 日报
    python作业源代码import pygameWIDTH = 800HEIGHT = 600FPS = 30pygame.init()screen = pygame.display.set_mode((WIDTH, HEIGHT))clock = pygame.time.Clock()class Shape:    def __init__(self, x, y, width, height):        s......
  • 日报 python
    (一)、中国大学排名数据分析与可视化;(写到实验报告中)【源代码程序】importrequestsfrombs4importBeautifulSoupasbsimportpandasaspdfrommatplotlibimportpyplotasplt  defget_rank(url):   count=0   rank=[]   headers={     ......
  • 日报 数学
     工程数学实验 1.算法步骤   黄金分割法也叫0.618法,是一种基于区间收缩的极小值搜索算法。比如以[a,b][a,b][a,b]为区间,产生两个内点x1=a+0.382∗(b−a)x2=a+0.618∗(b−a)x_1=a+0.382*(b-a)\\x_2=a+0.618*(b-a)x1​ =a+......
  • 日报
    工程数学实验1.算法步骤   首先定义了目标函数f,然后设置了多个不同的初始点,和最大迭代次数和精度要求。接着进行循环,每次取出一个初始点x0,并把迭代点x初始化为它。同时设定步长a和梯度的范数grad_norm的初始值为正无穷。然后进入迭代循环:每次计算目标函数的梯度grad,并根......
  • 日报 事后诸葛亮
    我们的软件一开始的首要目的就是实现人像衣像的结合,从而达到虚拟试衣的目标。整体方向还算很清楚,但却是缺乏对典型用户和典型场景精确的描述。项目实施之前并没有制定太多的计划,这就直接导致后续遇到问题的时候比较手足无措。当遇到团队成员意见分歧时,我们一般通过商讨采用最直......
  • 人民日报推荐:2023年必读的100本经典好书
    中国篇 1.《论语·大学·中庸》  儒家学说经典合辑,阐述儒学哲学核心思想,汇集学习与传承的篇章。2.《干家诗·神童诗·名贤集·增广贤文》  行孝道、做善事,珍惜时间,勤学苦读体现了其独特的文化魅力和思想价值。3.《弟子规·三字经·百家姓·干字文》  被......