《数据结构与算法》章节试读

《数据结构与算法》的笔记-第286页

我们只注意失配左边的文本字符此处没有把算法描述的很清楚。
假设：
主串：s: s[1] s[2]...s[n] 模式：p: p[1] p[2]...p[m]
若：主串第i个字符与模式串的第j(j<=m)个字符"失配"后，主串第i个字符与模式串的第k(k<j)个字符继续比较(跳跃j-k)，则有：
p[1]...p[j-1] = s[i-j+1]...s[i-1];
p[1]...p[k-1] = s[i-k+1]...s[i-1]
可以推出：
p[1]...p[k-1] = p[j-k+1]...p[j-1]
此即可以右移以匹配结束于i处的模式部分的模式最长前缀有多长的理论基础

《数据结构与算法》的笔记-第219页

X的最佳移动是遍历所有可占据的点，得分最大的点。需要注意的是，在内部节点上，从将要执行移动的玩家观点看，其得分是最佳子节点的得分。因此，当X遍历所以可移动的节点时，应用minimaxForO()来计算得分，minimaxForO()值最大的点即为最佳移动点。(若取minimaxForO()最小的点，那玩家就输定了，对方够智能的话 :) )

《数据结构与算法》的笔记-第262页

我们应该把>>用于除以2的幂的数字除法，但把>>>用于右移位向量
>>>右移，从左边移入0；>>右移，复制最左边的符号位
>>之所以可以用于除以2的幂的数字除法，是因为CPU的基本运算采用补码表示法(补码表示法可使减法运算转换为加法运算，且符号位能与有效值部分一起参加运算)。
有关原码，反码，补码，详见http://blog.csdn.net/macky0668/archive/2009/02/21/3917878.aspx

《数据结构与算法》的笔记-第143页

6.29 判断链表是否有环
提示：当两位选手以不同的速度沿着跑道赛跑时，如果跑道是环形的，那么速度较快的选手最终会领先较慢的选手一圈吗？
判断是否有环是比较简单的：
ListNode fast = front, slow = front;
遍历的时候，
fast = fast.getNext().getNext();slow = slow.getNext();
如果链表存在环，则fast必定先进入环，而slow后进入环，且必定相遇。如果fast遍历尾部为null，则为无环链表。代码如下：
public boolean isCyclic() {
ListNode<E> fast = front, slow = front;
while (fast != null && fast.getNext() != null) {
fast = fast.getNext().getNext();
slow = slow.getNext();
if (slow == fast)
return true;
}
return false;
}
但是如何获得入环点呢？
因为slow, fast每走一步(1,2)，他们之间的距离(fast追上slow的距离)减少一步，当slow到达入环点，fast在必定在它前面，他们之间的距离少于环长，所以slow走完一圈之内他们就能相遇。
假设相遇时，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)为相遇点到入环点(终点的next)的距离，由此可知，从链表头到入环点等于(n -1)循环 + 相遇点到入环点，于是我们从链表头、相遇点分别设置一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为入环点。代码如下:
public ListNode findLoopPortNode() {
ListNode<E> fast = front, slow = front;
while (fast != null && fast.getNext() != null) {
fast = fast.getNext().getNext();
slow = slow.getNext();
if (slow == fast) {
break;
}
}
if (fast == null)
reurn null;
slow = front;
while (slow != fast) {
slow = slow.getNext();
fast = fast.getNext();
}
return slow;
}