小黑屋

0%

面试题-算法-经典问题解决

发表于 更新于 分类于

扑克洗牌算法

打乱一个已有顺序有多种实现方式，但是要高效地实现，还需要斟酌，以下是目前能想到的最有的解决方案：

1
2
3
4
5
6
7
8
9
10
11
//生成一副牌
Card[52] oneCard = generateOneCard;

//顺序与 随机位置交换
Random r = new Random();
for (int i = 0; i < oneCard.size(); i ++){
    int j = r.nextInt(52);
    Card tempCard = oneCard[i];
    oneCard[i] = onCard[j];
    onCard[j] = tempCard;
}

判断链表中是否有环

快慢指针法：创建两个指针1和2同时指向这个链表的头节点，然后两个指针分别向后移动，其中指针1每次向后移动一个节点，指针2每次向后移动两个节点，每移动一次就比较两个指针指向的节点是否相同，如果相同说明出链表有环；如果不同，则继续循环，直到有环结束或者到达尾部结束。

原理：两个人在环形跑道上同一位置开始跑，一人速度快，一人速度慢，如此持续跑一段时间，速度快的那个肯定会从速度慢的身后再次追上以及超越，这中间必然有个交汇点。如果是跑直线的话，到终点就结束了，不会再碰面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//判断是否有环
public static <T> boolean isLoopList(ListNode<T> head){
    ListNode<T> slowPointer, fastPointer;

    //使用快慢指针，慢指针每次向前一步，快指针每次两步
    slowPointer = fastPointer = head;
    while(fastPointer != null && fastPointer.next != null){
        slowPointer = slowPointer.next;
        fastPointer = fastPointer.next.next;

        //两指针相遇则有环
        if(slowPointer == fastPointer){
            return true;
        }
    }
    return false;
}

引申：如何判断环的入口

我们假定链表头到环入口的距离是len，环入口到slow和fast交汇点的距离为x，环的长度为R。slow和fast第一次交汇时，设slow走的长度为：d = len + x，而fast走的长度为：2d = len + nR + x，(n >= 1)，从而我们可以得知：2len + 2x = len + nR + x，即len = nR - x，(n >= 1)。所以，要找出环入口，也要两个指针，一个指针A指向相遇时候的节点，一个指针B指向链表头，两个指针每次都走一步，A指针在遍历过程中可能多次(n >= 1)经过环入口节点，但当B指针第一次达到入口节点时，A指针此时必然也指向入口节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//判断是否有环，有环就返回入口
public static <T> ListNode<T> findEntranceInLoopList(ListNode<T> head){
    ListNode<T> slowPointer, fastPointer;

    //使用快慢指针，慢指针每次向前一步，快指针每次两步
    boolean isLoop = false;
    slowPointer = fastPointer = head;
    while(fastPointer != null && fastPointer.next != null){
        slowPointer = slowPointer.next;
        fastPointer = fastPointer.next.next;

        //两指针相遇则有环
        if(slowPointer == fastPointer){
            isLoop = true;
            break;
        }
    }

    //一个指针从链表头开始，一个从相遇点开始，每次一步，再次相遇的点即是入口节点
    if(isLoop){
        slowPointer = head;
        while(fastPointer != null && fastPointer.next != null){
            //两指针相遇的点即是入口节点
            if(slowPointer == fastPointer){
                return slowPointer;
            }

            slowPointer = slowPointer.next;
            fastPointer = fastPointer.next;
        }
    }
    return null;
}

再引申，两个单链表是否相交

两个没有环的链表在某一节点相交，那么在这个节点之后的所有结点都是两个链表所共有的。如果它们相交，则最后一个结点一定是共有的，因此问题转化为：两个链表最后一个结点是否相同（时间复杂度为O(len1+len2)）。要找出相交的第一个结点，可以首先获得两个链表的长度，然后获得两个链表长度差值 K，之后长的链表指向第K个结点，短的链表从头开始，每次向后移动一个结点，再比较当前结点是否相等，第一次相等的那个结点点就是相交节点。

代码略

谢谢你的鼓励