最 简单 详细 易懂的反转链

看不懂你来找我 嘿嘿

思想:

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

时间复杂度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步和在一起了,

链表定义

 

循环版本代码

 

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

 

macOS 升级 Mojave 导致 CLion 不能编译 出错

1.需要在mac上安装 Xcode Command Line Tools 

可用通过命令安装

会弹出一个这样的安装窗口,安装即可,大概有好几百M大小,耐心等待

安装完后会在 /Library/Developer 下看到安装成功

2.然后重新加载CLion即可 大概几十秒钟

如果电脑来不及刷新,不妨操作完,重启一下电脑

彻底删除JetBrains系列软件

删除这些目录下的与软件相关目录

例如删除CLion2018.1

 

删除IDEA或者 PyCharm同理,删除对应目录下的文件就行了

 

linux下的tar和zip压缩命令

tar 打包参数

c 创建新文件 (重名覆盖不提示)

f 指定原文件

x 提取文档

t 列出文档包含的文件

v 详细信息

tar 压缩参数

z gzip : .tar.gz 压缩速度最快 历史最悠久,应用最广泛

j bzip2 : .tar.bz2 压缩存档文件小,可用性不如gzip

J xz : .tar.zx 最新的方式 最佳的压缩效率

 

例如 把 aaa 这个文件或文件 打包成aaa.tar 压缩成aaa.tar.gz 并解压

zip压缩和解压缩

压缩aaa文件 和bbb目录 并解压

高精度加法和乘法

高精度加法和乘法

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

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″。

双向队列 deque 和 list

双向队列 deque 和 list

效率l介于ist和vector之间,支持随机访问(比vector效率低,比list高),支持两端插入删除(效率比list低,比vctor高)内部分块存储,结构比较复杂,不做深究

1、需要高效的随即存取,不关心插入和删除的效率,用vector 2、大量的插入和删除,不关心随即存取,用list 3、既需要随即存取,又要两端数据的插入和删除,用deque。

双向队列
deque<T> q 初始化
q.size() 当前队列长度
q.front() 返回队头元素
q.back() 返回队尾元素
q.push_back() 队尾入队
q.pop_back() 队尾出队
q.push_front() 队头队
q.pop_front() 队头出队
q.begin() 返回正向队头迭代器
q.end() 返回正向队尾迭代器
q.rbegin() 返回正向队尾迭代器
q.rend() 返回反向队尾迭代器
[] 存在操作,但效率低

双向队列
deque<T> a 初始化
a.size() 当前list长度
a.front() 返回头部元素
a.back() 返回尾部元素
a.push_back() 尾部添加元素
a.pop_back() 尾部删除元素
a.push_front() 头部添加元素
a.pop_front() 头部删除元素
a.begin() 返回正向list迭代器
a.end() 返回正向list迭代器
a.rbegin() 返回正向list迭代器
a.rend() 返回反向list迭代器
a.resize() 重新分配大小
a.reverse() 翻转链表
a.insert(*it,value) 插入
a.erase(*it) 删除
a.unique() 去重
a.merge(list2) 合并
a.sort() 排序

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来代入公式计算。

 

CLion 一个工程 运行多个 main cpp 文件

  1. 新建.cpp文件。例如 ,在工程所在文件夹上右键新建 main2.cpp 和main3.cpp。

  2. 修改 CMakeLists.txt 文件。添加红色框框中的内容,code2、code3为编译生成的文件名(自定义即可),然后点击右上角,重新加载或自动加载。
  3. 在右上角在即选择要编译运行的文件即可。

如果出现运行和代码不匹配情况,需要在这里设置一下,使 Target和Executable一致即可

Xcode 一个工程下添加多个 main cpp 文件