最 简单 详细 易懂的反转链

思想:

把原始链表节点一个个切下来,粘到左边的新链表上(左链表初始为空)

时间复杂度O(n),空间复杂度O(1)

链表变化过程:
node1->node2->node3-node4

一个个切下粘到左边

node1 … node2->node3->node4

node1<-node2 …. node3->node4

node1<-node2<-node3 …. node4

node1<-node2<-node3<-node4

代码思路: 循环切下每个节点,依次粘到左侧链表中

​ 1. 保存当前被切节点的next, 即切后原始链表的头结点,(4)里迭代下一个节点要用

2. 切下的节点粘贴到左边

3. 左边链表增加节点后更新头结点

4. 迭代下一个被切的节点, 即原始链表的头结点

(1)中保存next目的是为了(4)中用,如果不保存,经过二操作后cur->next节点就不是原来cur->next节点了)

递归版中3和4步和在一起了,

链表定义

 

循环版本代码

 

递归版
采用尾递归,翻转完成时候直接返回左边链表即可

 

高精度加法和乘法

高精度加法和乘法

加法(只支持自然数的大整数相加)

1.通过模拟加法算式,从右往左依次累加,如果两个不一样长,要在短的前面用0补上。
2.取余保留,除10进位,注意最后一位如果有进位要把进位加上去。

乘法(只支持自然数的大整数相乘)

1. 通过模拟乘法算式,从右往左数的话,s1[i] * s2[j] 贡献给了ans[i+j]。
2.所以为了方便从右往左数, 先把s1,s2翻转,且乘法后的结果最多有 len1+len2位。
3.因为s1[i] * s2[j] 和s1[j] * s2[i]都会贡献给ans[i+j],所以要写两层for循环。
4.贡献值 = 第一次贡献值 + 第二次贡献值,然后取余保留,除10进位。
5.最后得到结果,要找到非0的首位,并且要反过来,也要判断结果为0的时候,返回”0″。

Bellman-Ford负权值 最短路 模版

1.n个点,m条边,含有负边。
2.外层循环n-1次,内层循环m次,进行松弛
3.添加check变量判断本轮是否进行松弛了,如果未进行松弛则可以提前退出循环
4.处理有向边时,注意u[i]和v[i]的顺序不要颠倒

 

优先队列使用

优先队列详解和使用

1.优先队列和普通队列相似,但是出队按照优先级高的先出队,进队和出队时间复杂度都为O(log2n)。

2.因为内部原理是用堆实现,插入时候把堆调整(花费o(log2n)),删除时直接删除堆顶(O(1)),然后把剩下元素调整(O(long2 n))。把一个原始无序集合,通过完全二叉树够造成堆花费O(nlog2n)。

3.(1).适用于动态添加和删除时,实时维护最值。(2).也可用于n个元素取前k个(比如10G的数据,取前100个最值,在内存不够情况下,只需要开辟100个数据的堆空间,把这10G数据依次读取进/出优先队列(堆),即可解决内存的问题,而且时间复杂度在nlong2k)。

 

c++为例
初始化 priority_queue<T> q;
入队 q.push();
出队 q.pop();
队头( 优先队列队头是top,普通的是front ) q.top()
元素个数 q.size();
判断队是否空 q.empty();

根据日期计算周几星期几

根据日期计算周几星期

1.根据基姆拉尔森计算公式枚举即可
2.W = (d+2m+3(m+1)/5+y+y/4-y/100+y/400) % 7
3.注意:在公式中有个与其他公式不同的地方:把一月和二月看成是上一年的十三月和十四月例:如果是2018-1-1则换算成:2017-13-1来代入公式计算。

 

排列组合

排列组合

从n种情况选m个选择,有多少中可能:

C n m

边乘边除法

 

计算质因子个数

计算质因子个数

计算数字 n 中有因子 a 的个数普通计算

 

进阶:计算数字 !n 中有因子 a 的个数快速计算

有一个公式:利用这个公式可以把时间复杂度降到O(nlogn)

 

其中除法向下取整

 

递归版:!n 中有因子 a 的个数快速计算

 

素数筛子

素数筛子

打印出1-100000内所有的素数

假定所有数都是素数,然后从头遍历把素数的所有倍数(2,3,4…n倍)筛掉,则剩下的为真素数。维护一个bool类型数组,false表示没被筛掉,true表示被筛掉了。

快速幂

快速幂

基于二分思想,时间复杂度为O(logb);当b奇数,ans = ans * (a ^ (b – 1) % m);当b偶数,ans = (a ^ (b / 2) % m) * (a ^ (b / 2) % m);当b为零,退出。

 

递归版:

 

全排列 公式&手动实现

全排列