序言

学习随笔是本人对自己一天的自学回顾，由于本人是非科班出身，不懂很多cs的专业术语，所以难免会有些错误，望各位批评指正，本人定当悉心接受并立即改正。希望自己能够慢慢坚持下去，坚持转行的道路，坚持每天学习的输出。

刷题篇

LeetCode

1.题目

给定两个（单向）链表，判定它们是否相交并返回交点。

2.大致思路

两人在长度不同的赛道跑步（匀速且两人速度相同），当跑完自己的赛道时，再从另一人赛道起点继续跑，如果两人能够相遇，则相遇点就是赛道的交点。

双指针分别指向两个链表，即p指向链表A，q指向链表B。同时开始遍历链表，p到表尾时，next指向链表B，q到表尾时，next指向A。直到p=q。

这里我产生了一个误区，第一次写出这个代码的时候我以为如果两链表没有交点的话，会无限循环，但我错了，具体看代码。

3.代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *p=headA,*q=headB;
    while(p!=q){      //这里，我本以为无交点会无限循环，但不会的。
                     //因为，两个指针走的距离是相同的。
                    //若没有交点，也就是说两指针会同时到达表尾，即为NULL，p=q跳出循环。
        if(p) p=p->next;
        else p=headB;
        if(q) q=q->next;
        else q=headA;
    }
    return p;
}

4.其他解法

1.暴力解法

一个一个比较结点是否相同，若有相同的结点，即返回此结点，否则返回NULL

2.通过长度求解

若两链表长度不同，两链表有交点且在交点前的部分链表长度不同，即从起点到交点，两指针走的距离不同，只要让两指针离交点距离相同即可。即让离交点远的指针先走一段距离，这段距离即为两链表长度之差。

这里说明一下：从交点开始往后，两链表的结点都是相同的，所以长度不同是由于交点前长度不同引起的。

数据结构

1.顺序表的查找

直接上代码（来自于《大话数据结构》，有几个问题）

int Sequential_Search(int *a,int n,int key){
    //在长度为n的数组a中，查找key，找到返回其位置，否则返回0
    int i;
    for(i=1;i<=n;i++){
        /*
            这里可以看到，i是从1开始，也就是说，是从a[1]到a[n]查找
            为什么呢，那第一个a[0]不就漏了，还有，数组长度不是只有n吗，不会越界吗？
            在我看来，这里的a相当于一个线性表，线性表长度在任何时候都是小于数组的，所以不会越界
            从a[1]开始找，若key在a[0]，找不到即返回0，相当于找到了，会不会引起歧义？
        */    
        if(a[i]==key)
        return i;
    }
    return 0;
}

由于每次都要判断i是否小于等于n，即判断是否越界，比较麻烦，故加入哨兵。

改进代码如下（加哨兵）

int Sequential_Search(int *a,int n,int key){
    int i;
    a[0]=key;
    i=n;
    while(a[i]!=key){
        i--;
    }
    return i;
}

2.有序表的查找

1.二分（折半）查找

关键代码   mid = (low+high)/2

思考：为什么判断条件是low<=high而不是low!=high呢？？？

2.插值查找

关键代码   mid=low + ((key-a[low])/(a[high]-a[low]))*(high-low)

3.斐波那契查找（这个需要多思考一下）

关键在于确定数组长度n位于斐波那契数列数列的位置k

int Fibonacci_Search(int *a,int n,int key){
    int low,high,mid,i,k;
    low=1;
    high=n;
    k=0;
    while(n>F[k]-1) {k++;}   //这里F即为斐波那契数列
    for(i=n;i<F[k-1]-1;i++) {a[i]=a[n];}   //这里还要补全数值，防止越界
    while(low<=high){
         mid=low+F[k-1]-1;
        if(key<a[mid]){
            high=mid-1;
            k=k-1;
        }
        else if(key>a[mid]){
            low=mid+1;
            k=k-2;
        }
        else{
            if(mid<n) return mid;
            else return n;
        }
    }
    return 0;
}

3.线性索引

1.稠密索引：有多少数据就要多少索引项，空间代价大

2.分块索引：

三个关键要素：最大关键码，块长，块首元素指针

两个性质：块内元素无序，块与块之间有序

查找方式：先查块（有序，则可用二分或插值查找），再查找块中元素（无序，顺序查找）

最大关键码的用处：

比如有分别以27,57,96为最大关键码的三个块，我要找77可能在哪个块，即57<77<96，所以在第三个块中找。

3.倒排索引（没有过多了解）