记录学习过程中的点点滴滴
2011年五月
【编程之美】单链表是否存在环以及环入口的位置【转载】
五 26th
原文地址:http://blog.csdn.net/ssfp8762/archive/2009/07/08/4331419.aspx
解答:
一、判断链表是否存在环,办法为:
设置两个指针(fast, slow),初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定相遇。
二、链表环入口的位置计算
当fast若与slow相遇时,slow肯定没有走遍历完链表,而fast已经在环内循环了n圈(1<=n)。假设slow走了s步,则fast走了2s步(fast步数还等于s 加上在环上多转的n圈),设环长为r,则:
2s = s + nr
s= nr
设整个链表长L,入口环与相遇点距离为x,起点到环入口点的距离为a。
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L – a
a = (n-1)r + (L – a – x)
(L – a – x)为相遇点到环入口点的距离,由此可知,从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点,于是我们从链表头、与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇第一点为环入口点。
扩展问题:
判断两个单链表是否相交,如果相交,给出相交的第一个点(两个链表都不存在环)。
比较好的方法有两个:
一、将其中一个链表首尾相连,检测另外一个链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个点。
二、如果两个链表相交,那个两个链表从相交点到链表结束都是相同的节点,我们可以先遍历一个链表,直到尾部,再遍历另外一个链表,如果也可以走到同样的结尾点,则两个链表相交。
这时我们记下两个链表length,再遍历一次,长链表节点先出发前进(lengthMax-lengthMin)步,之后两个链表同时前进,每次一步,相遇的第一点即为两个链表相交的第一个点。
socket编程中如何区分不同的网络连接
五 25th
在网络编程中,服务器程序的代码结构一般如下:
socket() -> bind() -> listen() -> accept()
当有一个新的客户端连接时,accept建立一个新的socket,然后将sockfd返回,接下来数据的发送和接收就都在这个sockfd中进行
但是一直有一个问题我比较困惑:在服务器端,当有数据到达时,协议栈是如何将数据传递到正确的sockfd的呢(服务器端存在多个已连接的客户端)?因为不同的网络连接是使用同一个监听端口,如80端口,不可能为每一个建立的连接分配一个端口(事实也不是这样);
上网搜寻一下,一个比较合理的解释:使用网络连接的源ip+源port来区分不同的数据连接,本身TCP协议中提供,而且可以唯一标识网络连接,因为不可能同一个客户端使用同一个端口进行来连接server的。
平面中两点的最近距离与最远距离
五 23rd
今天看编程之美,看到求平面中两点的最近距离,书中给出了O(nlogn)算法,主要是采用分治的方法来做的,首先将平面的点按x坐标分为两部分,分别求最近点对,然后是合并;合并过程中对于两个点分别在两个区域的分析非常巧妙,有效地减少了需要比较的点对的个数。
在poj中对应的题目3714
然后又看到了扩展问题:如何求平面中最远的两个点的距离
这个就不能继续套用“最近距离点对”的分治策略,上网查了下,原来是使用凸包算法+旋转卡壳算法,poj中对应的题目是2187和3608
这里简单记录下,明天做下这两个题目
关于凸包算法和旋转卡壳算法的介绍:
http://yishan.cc/blogs/gpww/archive/2011/02/16/graham-s-scan.aspx
http://www.cppblog.com/staryjy/archive/2010/09/25/101412.html
http://yishan.cc/blogs/gpww/archive/2011/02/15/1787.aspx
linux中有关用户与组的命令小结
五 6th
添加用户:
adduser username #添加用户 passwd username #为用户设置密码 adduser -g groupname username #添加用户时也添加组 gpasswd -a usename groupname #将用户添加到组中
添加组:
groupadd groupname # 这里不知为何与adduser的命名方式不一样
锁定用户:
passwd username -l #锁定用户 passwd username -u #解锁用户
永久删除用户:
deluser username groupdel groupname gpasswd -d username groupname #从组groupname中删除用户username
近期评论