「手撕算法」锁定大厂看这就可

这个题的难点不是判断数是不是快乐数，而是如何判断一个数不是快乐数，如果不是快乐数，说明没有办法通过有限的次数到达数字1，那么到底是 经过多少次呢?1k次，10w次?很难确定上限。在说这个问题之前我们先看几个高频链表练习题

例题1 用数组判断链表中是否有环

在上面我们介绍了最后一个节点指向空，可是你有没有想过如果链表的最后一个节点不是空地址而是指向链表中的一个节点，这不就是环了?

链表环

如上图所示，节点8指向了3，这样形成了3,4,5,6,7,8的环状结构，此时使用指针遍历链表将永无止境。那通过什么办法判断是否有环呢?

使用数组标记的方法。记录出现过的节点信息，每次遍历新节点就去数组查看记录，这样的时间复杂度不给力。经过第一个节点，需要在数组查找0次，第2个节点，数组查找1次，第i个节点，在数组查找i-1次，直到遍历第n+1个节点，查找的总次数为(n + 1) * n / 2，这样时间复杂度为O(n^2)。太慢了，给我优化 快慢指针法

AB两位同学跑步，A同学速度快，B同学速度慢，他们并不知道跑道是环形的，如果是环形，跑得快的，在足够的时间终究会从速度慢的B同学经过，形成相遇的情况。如果不是环形，速度快的先到重点，不会相遇---快慢指针法。

快慢指针

在这里，我们将链表当做跑道，跑道上两个指针，指针A每次走两步，指针B每次走两步，如果快的指针先跑到终点注定没有环，如果两指针相遇则有环。

int hasCycle(struct Node *head) {     if (head == NULL) return 0;     // p 是慢指针，q 是快指针     struct Node *p = head, *q = head;     // 每次循环，p 走1步，q 走2步     do {             p = p->next;             q = q->next;             if (q == NULL) return 0;             q = q->next;         } while (p != q && q);     return p == q; } 

3 二分查找初探

说到二分查找，这里就有个笑话了。

小孙同学去图书馆借书，一次性了借了40本书，出图书馆的时候报警了，不知道哪一本书没有消磁，然后把书放在地上，准备一本本尝试。

4 二分查找基础

最简单的二分算法即在一个有序数组中，查找一个数字X是否存在。注意有序性。那么如何在数组中查找一个数

从头到尾一个一个查找，找到即有数字x

二分算法即通过确定一个区间，然后查找区间的一半和x比较，如果比x大则在x前半段查找。如果比x小则在后半段查找，只需要log2n的比较即可确定结果。

二分初探

图中呢，我们以查找 17 这个数字为例，L 和 R 所圈定的，就是当前的查找区间，一开始 L= 0，R = 6，mid 所指向的就是数组的中间位置，根据 L 和 R 计算得到 mid 的值是 3。查看数组第 3 位的值是 12，比待查找值 17 要小，说明如果 17 在这个有序数组中，那它一定在 mid 所指向位置的后面，而 mid 本身所指向的数字已经确定不是 17 了，所以下一次我们可以将查找区间，定位到 mid + 1 到 R，也就是将 L 调整到 mid + 1 (即数组第 4

位)的位置。

1 第一种小白写法

int BinarySerach(vector& nums,int n, int target) {     int left = 0, right = n-1;     while (left <= right) {         int mid = (left+right)/2;         if (nums[mid] == target) return mid;         else if (nums[mid] < target) left = mid + 1;         else right = mid-1;     }     return -1; } 

面试官发话了

方法二优化版

如果right和left比较的时候，两者之和可能溢出。那么改进的方法是mid=left+(right-left)/2.还可以继续优化，我们将除以2这种操作转换为位运算mid=left+((right-left)>>1).

哪有这么简单的事儿，大多数的笔试面试中可能会出现下面的几种情况。

四 、二分的各种变种

（编辑：应用网_阳江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!