数据结构

数据结构

复习的方法应该是：审题->思考->表达->码字。

首先，审题很重要无需废话，拿到题目，我们需要认真思考一番。然后就需要组织语言，把自己所想表达清楚。别小看这一个步骤，组织语言表达清楚很重要。一些公司都是先让说思路，再让写代码的，甚至是只说思路。所以，在复习的时候，把每道题的思路想清楚，说明白很重要。最后，我们再将自己的想法写成代码。

链表：

1、找出单链表的倒数第K个元素（仅允许遍历一遍链表）

答：使用指针追赶的方法，定义一个fast指针和一个slow指针，fast指针先走K步，然后fast和slow同时继续走。当fast指针走到链表尾部时，slow指向的位置就是倒数第K个元素。注意：要考虑链表长度应该大于K。

2、找出单链表的中间元素（仅允许遍历一遍链表）

答：使用指针追赶的方法，定义一个fast指针和一个slow指针，两个指针同时走，fast指针每次走两步，slow指针每次走一步。当fast指针到链表尾部时，slow指针指向的就是链表的中间元素。

3、判断单链表是否有环？

答：使用指针追赶的方法，定义一个fast指针和一个slow指针，两个指针同时走，fast指针每次走两步，slow指针每次走一步。如果有环，则两者会相遇；如果没有环，fast指针会遇到NULL退出。

4、已知单链表有环，如何知道环的长度？

答：使用指针追赶的方法，定义一个fast指针和一个slow指针，两个指针同时走，fast指针每次走两步，slow指针每次走一步，找到碰撞点。然后使用slow指针，从该碰撞点开始遍历，绕着走一起圈，再次回到该点，所走过的结点数就是环的长度。

5、如何找到环的入口结点？

答：先使用题4的方法，计算出环的长度。然后重新从头结点开始遍历，定义定义一个fast指针和一个slow指针，fast指针先走l（环的长度）步，然后两个指针以相同的速度在链表上向前移动，直到它们再次相遇，那么这个相遇点即为环的入口结点。

6、判断两个无环单链表是否相交？

答：一旦两个链表相交，那么两个链表从相交节点开始到尾节点一定都是相同的节点。所以，如果他们相交的话，那么他们最后的一个节点一定是相同的，因此分别遍历到两个链表的尾部，然后判断他们是否相同。

7、如何知道两个单链表（可能有环）是否相交？

答：根据两个链表是否有环来分别处理，若相交这个环属于两个链表共有

（1）如果两个链表都没有环，如题6所示方法。

（2）一个有环，一个没环，肯定不相交。

（3）两个都有环。在A链表上，使用指针追赶的方法，找到两个指针碰撞点，之后判断碰撞点是否在B链表上。如果在，则相交。

8、寻找两个相交链表的第一个公共结点。

答：我们也可以先让把长的链表的头砍掉，让两个链表长度相同，这样，同时遍历也能找到公共结点。此时，时间复杂度O(m+n)，空间复杂度为O(MAX(m,n))。参考：剑指Offer（三十六）：两个链表的第一个公共结点

9、反转链表。

答：我们使用三个指针，分别指向当前遍历到的结点、它的前一个结点以及后一个结点。在遍历的时候，交换当前结点的尾结点和前一个结点的。参考：剑指Offer（十五）：反转链表指

数组：

1、给定一个数组（非递减排序），同时给定一个目标数字，找出这个数字在该数组中第一次出现的位置，如果不存在，返回-1。例如[1,3,5,5,5,5,8,9,13,15]，输入5，返回2，输入8，返回6，输入18，返回-1。

答：使用二分查找法即可。

# -*-coding:utf-8 -*-
def BinarySearch(input_list, end, value):
    if end == 0 or value < input_list[0] or value > input_list[-1]:
        return -1
    left = 0
    right = end - 1
    while left <= right:
        middle = left + (right - left) // 2
        if input_list[middle] >= value:
            right = middle - 1
        else:
            left = middle + 1

    return left if left < end else -1

if __name__ == '__main__':
    input_list = [1,3,5,5,5,5,8,9,13,15]
    target = 5
    print(BinarySearch(input_list, len(input_list), target))

运行结果如下图所示：

2、给定一个数组，里面有很多数字（乱序），找出其中最大的4个数字。

答：最简单的办法就是先排序再找出最大的四数，这种方法时间复杂度过高。一个更好的方法是使用堆排序，即维护一个存储最大的4个数的最大堆。

解析：这的思想和代码可以参考《剑指Offer（二十九）：最小的K个数》，这里仅仅做了一个变形。

3、给定一个整数的数组nums，返回相加为target的两个数字的索引值。假设每次输入都只有一个答案，并且不会使用同一个元素两次。

答：如果这个数组是已经排序的，可以使用头指针和为指针。如果是已经排序的，那么我们可以定义一个头指针left，一个为指针right。left指针指向元素值+right指针指向元素值的和为sum，用sum和target比较。如果sum大于target，说明和大了，那么right右指针左移一位，然后重新判断。反之，如果sum 小于target，说明和小了，那么left左指针右移以为，然后会从新判断。直到找到sum=target的情况。如果没有排序，可以使用使用哈希表，也就是散列表。

解析：如果没有排序，这道题就是Leetcode中的一道题。代码可以参考《Two Sum》。

4、给定一个字符串，找到最长无重复子字符串。

答：定义两个变量longest和left，longest用于存储最长子字符串的长度，left存储无重复子串左边的起始位置。然后创建一个哈希表，遍历整个字符串，如果字符串没有在哈希表中出现，说明没有遇到过该字符，则此时计算最长无重复子串，当哈希表中的值小于left，说明left位置更新了，需要重新计算最长无重复子串。每次在哈希表中将当前字符串对应的赋值加1。

解析：Leetcode中的一道题。代码可以参考《Longest Substring Without Repeating Characters》。

其他：

1、不使用现成的开根号库函数，如何实现开平方根的操作？

答：可以使用二分查找法或者牛顿法。

# -*-coding:utf-8 -*-
def sqrt_binary_search(target):
    left = 0
    right = target
    mid = (left + right) / 2

    while abs(mid*mid-target) > 0.000001:
        if mid*mid == target:
            return mid
        elif mid*mid > target:
            right = mid
        else:
            left = mid
        mid = (left + right) / 2
    return mid

def sqrt_newton(target):
    k = target
    while abs(k*k-target) > 0.000001:
        k = 0.5*(k+target/k)
    return k

if __name__ == '__main__':
    print("二分查找法:",sqrt_binary_search(64))
    print("牛顿法:",sqrt_newton(64))

运行结果如下图所示：