//时间复杂度:可以理解为变化率,即随着变量的增加或减少,执行次数的变化率如何
1、两数之和类型
所用函数:unordered_map(哈希)
思路:让两个指针依次遍历一维数组中的两个数,每次遍历都计算二者之和,直到算出等于目标值的和;
解决问题代码:见第1题
时间复杂度:o(n*n)
2、整数翻转类型(爆int类型)
所用方法:从个位开始取出,每取出一个就存在vector类型的nums里,但是让返回一个int型的数,然后一旦 用到pow函数马上就会爆int
解决方法:pow函数会返回int类型,所以不用pow,直接每次sum*10+temp即可,至于结果爆int,可以先定义一个longlong类型的数,如果longlong大于INT_MAX,则返回0,否则把值赋给int类型的sum,最后返回sum;
问题:7题
时间复杂度:o(longx)
3、合并两个有序链表
所用方法:每次找出两个链表的较小的数插入新链表,最后比较一下剩下哪个链表就把剩下的链表插入,需要注意新链表必须有个head,即固定头结点才可以返回;
时间复杂度:o(n)
心得:通过做这个题给了我很大的信心,因为这个题是我最开始学数据结构就不懂得题,最开始学数据结构了解链表觉得链表就像c语言一样抽象,后来刷了几道链表的增删改查,只是一味的死记住了,一直搞不明白该怎么有顺序的插入,链表的工作原理到底是什么,它有什么好处,什么时候用,记得当时因为这个看了起码5遍的图解,刷完上百道题再回来做这个题瞬间觉得好简单,很快就ac了,这道题让我明白了算法坚持刷下去总会开花结果的!
4、计数质数(线形筛)
算法:线形筛,题目模板:筛质数(868)
时间复杂度:o(n)
大体思路:根据每个非质数的最小质因子来把不是质数的给踢走,把是质数的存到vector里,if(i%primes[j]==0) break;这句话大概意思是如果当前的不是最小质因子则跳过它,为了能使这个循环满足每次都是根据最小质因子来找非质数;
具体思路我实在理不清,智商有限,为了保头发,能背的模板,尽量不弄懂咋回事了
加油hh
这个hh注入灵魂 hh
谢谢大佬