面试题35. 复杂链表的复制
题目在此面试题35.复杂的链表的复制
有三种方法可以做这一道题
迭代法
BFS
DFSunordered_map是无序的哈希函数unordered_map<Node\,Node*> copylist 其实是用来同步复制结点和原结点,例如,原结点到达了head.那么head的复制结点就是copylist[head],相当于把原结点和复制节点绑定了起来 *这样做的好处是:举个例子若不使用unordered_map函数,我们创建3个复制结点就需要创建3个指针(例如:p1,p2,p3)去指向它,以备后续建立结点相互链接关系时再次访问,但是如果我原节点有10000个,那么我就需要手动创建10000个指针,而用了unordered_map就可以将创建的复制结点与原结点绑定起来,结点间建立链接关系时只需要通过原节点就可以访问相应的复制结点(原结点head的复制节点copylist[head])
下面方法除了优化迭代法的时间复杂度为O(n),空间复杂度为O(1),其他的时间空间复杂度都为O(n)
迭代法class Solution {
public:
Node* c
对于指针的一些理解
在复习数据结构链表那一章时对创建头指针然后指向首元节点或者头节点(两者是不同的东西)的具体实现过程有些许疑问,它们在内存中是怎么工作的呢?于是我写了个小程序来验证了一下
#include<stdio.h>
#include<stdlib.h>
struct test
{
struct test* next;
int data;
};
int main ()
{
struct test* temp=NULL ;
struct test* address;
printf("未申请内存时的&address=%p\n",&address);
address=(struct test*)malloc(sizeof(struct test));
address->data=10;
address->next=NULL;
temp=address;
printf("&address=%p\n&quo
Chapter 3: Transport Layer
Most of content come from Computer-network-A-Top-Down-Approach.
3.4 Principles of Reliable Data Transferit may be corrupt bits , lose packets, packets out of order during the data transfer from client to servers . So . For avoid the data lose or other situation happened When we receive the data at the Application layer,we need to build a reliable data transfer protocol.In fact , the layer that below the reliable data transfer protocol is unreliable . For example , TCP protocol is reliable data t
Shell入门学习
#!/bin/bash
echo -e "hello, world\n"
# 1.变量的定义使用
my_name=lexssama
echo "1.$my_name"
# 2. 另一种定义方式
course="linux start"
echo 2. ${course}
# 3. 只读变量
readonly course
course="linux kernel" #readonly 不能写入(改变)
echo "3. ${course}" # 输出的还是linux start
# 4.删除变量
unset my_name
echo "4.${my_name}"
# 5.export 导出一个环境变量
export MY_NAME="lexssama"
# 6. 查找自定义的环境变量
env | grep MY_NAME
# 7. 特殊变量
echo "文件名称: $0&quo
Manjaro-System-configuran
Manjaro System finish picture
一下配置文件都在 https://github.com/LEXSSAMA/Configure-file-of-Manjaro-System
步骤1.首先下载镜像安装2.换源sudo pacman-mirrors -i -c China -m rank
选择一个好用的就可以,我选择的是https://mirrors.sjtug.sjtu.edu.cn/manjaro/
3.更新系统sudo pacman -Syy #更新缓存
sudo Pacman -Syyu #更新系统
4.配置VIMsudo pacman -S vim
然后编辑$HOME下的.vim/vimrc文件即可我的也是刚刚开始使用vim所以配置的内容并不丰富
syntax on
set number
set relativenumber
set hlsearch
set smartcase
set cursorline
set cursorcolumn
hi CursorColumn term=reverse ctermbg=white guibg=
chapter2 :Homework problems and Questions
下面提到的的文档都收藏在 https://github.com/LEXSSAMA/Valuable-document-collention-during-learning-process中
课本是:computer network a top-down approach
1.列出5个(非专有)的互联网应用,并说明他们使用的应用层协议查过一些资料,好像有一个技术叫做Deep packet inspection (DPI)可以查到软件使用的协议,github上也有一个开源软件nDPI,还有一个软件叫做wireshark,但是因为有点复杂,我现在暂且不深入研究,下面答案都来着互联网
1 . Chrome (谷歌浏览器貌似不是开源的...,不管了用的最多,下面答案来自stackoverflow) in term of what protocol you can use in the chrome browser bar you can use: HTTP,HTTPS,FILE and FTP.SSH is not implemented by chrome,but rather it im
Chapter 2: Application Layer
The questions is provided below,we can find the answer in the Computer Network A Top-down Approach
HTTP
HTTP is said to be a stateless protocolno-persistent-connections and persistent-connectionsno-persistent-connections:Client obtains the 10 JPEGs over 10 serial TCP connections or whether JEPGs are obtained over parallel TCP connections?
Advantage of persistent-connections(or disadvantage of no-persistent-connections):NO-persistent-connection has some shortcoming.First, a brand-new connection
VIM指令学习
vim 选中的行列递增例如想要替换下行中10行BL1,依次递增为BL1.BL2….BL10,可以用这种方法
BL1BL1
BL1BL1
BL1BL1
BL1BL1
BL1BL1
BL1BL1
BL1BL1
BL1BL1
BL1BL1
BL1BL1
先用可视块选中这10行,然后ESC退到命令模式再按:输入命令
:'<,'>s/BL\zs\d*\ze/\=line(".")-line("'<")+1/g
这些指令的意思如下:
'<,'> 我们所选中的区域 (:help '<,:help '> )
s 在选中的区域中进行替换 (:help :s )
\zs 指明匹配由此开始 (:help /\zs )
\d* 查找任意位数的数字 (:help /\d )
\ze 指明匹配到此为止 (:help /\ze )
\= 指明后面是一个表达式 (:he
KMP算法
感谢:KMP算法 Next数组详解(【洛谷3375】KMP字符串匹配 )从头到尾彻底理解 KMP字符串匹配的KMP算法
KMP算法即是用来解决在一个字符串S(例如ABCDEFG)中快速查找字符串P(ABCD)的一个算法.在介绍KMP算法之前我们先介绍暴力查找字符的算法
字符串的暴力查找法如下图用暴力查找法在字符串S(BB….DE)中寻找匹配项字符P(ABCDABD).
暴力查找法核心就是发现S[i]和P[j]不相等,S和P就开始回退,S回退到i=i-(j-1)处 ,j回退为0.具体看下图:
比较S[0]!=P[0]不相等则回退,i=i-(j-1)=0-0+1=1,j=0,相当于S向前进一步,而P回到j=0再开始比较还是不相等,与上面情况相同S[i]=p[i],i++,j++继续向下比较发现S[i]!=P[j]不相等开始回退置i=i-(j-1)=9-(6-1)=4,j=0,继续比较,即开始比较S[4]=B和P[0]=A,
可以发现暴力查找的缺点就在发现不相等,S和P都要回退,再重新比较,倘若S和P都特别长,假设S有10000个字符,P有1000个字符,S与P从第0个字符开始相等,而在第9