资讯专栏INFORMATION COLUMN

利用PHP实现《剑指 offer》之链表(数据结构与算法实战 )

hiYoHoo / 2046人阅读

摘要:一定要认真看分析注释题目要求题目描述输入一个链表,从尾到头打印链表每个节点的值。分析因为链表只有知道当前结点才能知道下一结点,所以不可能直接从后往前打印。

</>复制代码

  1. 一定要认真看 分析 | 注释 | 题目要求
Question 1

题目描述:
输入一个链表,从尾到头打印链表每个节点的值。

分析:
因为链表只有知道当前结点才能知道下一结点,所以不可能直接从后往前打印。这种逆序的算法(策略)我们常用这种数据结构来解决,所以我们的基本思路为,先将链表压入栈,再弹出,但是这样做我们需要遍历两次才能得出答案,更奇妙的解决方案为一次将结点值插入数组头部,一次便可以满足题目要求,代码如下:

</>复制代码

  1. val = $x;
  2. }
  3. }*/
  4. function printListFromTailToHead($head)
  5. {
  6. $stack = [];
  7. if(!$head){
  8. return $stack;
  9. }
  10. while($head){
  11. array_unshift($stack,$head->val); #array_unshift返回头插后的数组单元数目
  12. $head = $head->next;
  13. }
  14. return $stack;
  15. }

测试地址:https://www.nowcoder.com/prac...

Question 2

题目描述
输入一个链表,输出该链表中倒数第k个结点。

分析:
前提:链表是动态分配的,事先不能知道链表的总长度
一般思路:遍历链表,得出长度,输出结点
面试思路:准备两个指针,假如第一个指针走到n-1(即链表末尾),第二个指针走到倒数k的位置,两者之间相差(n-1)-(n-k) = k-1,先让一个指针走到k-1,第二个指针原地等待,然后让第二个指针和第一个指针同时走,走到末尾,找到k,代码如下:

</>复制代码

  1. next != null){
  2. $head = $head->next;
  3. }else{
  4. /* 注意:这里有一个隐藏的条件,就是链表的长度有可能小于k,当我们走到k-1时链表就已经遍历结束,这种情况同样非法 */
  5. return null;
  6. }
  7. }
  8. /* 当第一个指针走到k-1且还不为空,这时让第二个指针开始走,当第一个指针走到n-1的时候,第二个指针也走到了倒数第k的位置,即所求 */
  9. while($head->next != null){
  10. $head = $head->next;
  11. $behind = $behind->next;
  12. }
  13. return $behind;
  14. }

测试地址:https://www.nowcoder.com/prac...

Question 3

题目描述
输入一个链表,反转链表后,输出链表的所有元素。

分析:
画图最佳 主要就是运用临时节点 看注释

</>复制代码

  1. next; #首先将链上第二个位置的值放在临时容器中
  2. $pHead->next = $cur; #将第二个位置赋一个空值 保持链的关系
  3. $cur = $pHead; #将第一个位置的值赋给第二个位置
  4. $pHead = $tmp; #将原第二个位置的值赋给头结点
  5. }
  6. return $cur;
  7. }

测试地址:https://www.nowcoder.com/prac...

Question 4

题目描述
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

分析:
画图最佳 先用头结点比较大小,小的压入数组,大的和小的的后一位继续比较

</>复制代码

  1. val = $x;
  2. }
  3. }*/
  4. function MergeList($pHead1, $pHead2)
  5. {
  6. // write code here
  7. /*
  8. 先用头结点比较大小,小的压入数组,大的和小的的后一位继续比较
  9. */
  10. if($pHead1 == null && $pHead2 == null){
  11. return null;
  12. }
  13. if($pHead1 == null){
  14. return $pHead2;
  15. }
  16. if($pHead2 == null){
  17. return $pHead1;
  18. }
  19. $target = array();
  20. if($pHead1 != null && $pHead2 != null){ #这里作判断的目的主要是在递归过程中可能会有一方先遍历结束
  21. if($pHead1->val >= $pHead2->val){
  22. $target = $pHead2;
  23. $target->next = MergeList($pHead1,$pHead2->next);
  24. }else{
  25. $target = $pHead1;
  26. $target->next = MergeList($pHead1->next,$pHead2);
  27. }
  28. }
  29. return $target;
  30. }

测试地址:https://www.nowcoder.com/prac...

Question 5

题目描述
给定一个链表

</>复制代码

  1. 1.判断链表是否有环
  2. 2.链表起始结点(入口结点)

分析:
最近segment插图好像出了点问题,我给个链接吧环形链表

</>复制代码

  1. function EntryNodeOfLoop($pHead)
  2. {
  3. // write code here
  4. if($pHead == null){
  5. return null;
  6. }
  7. $fast = $pHead;
  8. $slow = $pHead;
  9. while($fast != null && $fast->next != null){
  10. $fast = $fast->next->next;
  11. $slow = $slow->next;
  12. if($fast == $slow){ #存在环
  13. $slow = $pHead;
  14. while($fast != $slow){ #此时slow为头结点
  15. $fast = $fast->next;
  16. $slow = $slow->next;
  17. }
  18. if($fast == $slow){
  19. return $fast;
  20. }
  21. }
  22. }
  23. return null;
  24. }
Question 6

题目描述
“约瑟夫环”是一个数学的应用问题:一群猴子排成一圈,按1,2,…,n依次编号。然后从第1只开始数,数到第m只,把它踢出圈,从它后面再开始数, 再数到第m只,在把它踢出去…,如此不停的进行下去, 直到最后只剩下一只猴子为止,那只猴子就叫做大王。要求编程模拟此过程,输入m、n, 输出最后那个大王的编号。

分析:
第一个出列的猴子肯定是a[1]=m(mod)n,设此时某个猴子的新编号是i,他原来的编号就是(i+a[1])%n

</>复制代码

  1. /**
  2. * @param $monkeys Array 预设数组
  3. * @param $m. Int。 预设剔除序号
  4. * @param $cur. Int。 标记
  5. */
  6. function JosephCircle($monkeys , $m , $current = 0){
  7. $number = count($monkeys);
  8. $num = 1;
  9. if(count($monkeys) == 1){
  10. echo $monkeys[0];
  11. return;
  12. }
  13. else{
  14. while($num++ < $m){
  15. $current++ ;
  16. $current = $current%$number;
  17. }
  18. echo $monkeys[$current];
  19. array_splice($monkeys , $current , 1); #剔除
  20. JosephCircle($monkeys , $m , $current);
  21. }
  22. }

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/28665.html

相关文章

  • PHPer也刷《剑指Offer链表

    摘要:剑指中链表相关题目俗话说光说不练假把式,既然学习了链表的基础概念和基本操作那我们一定要找些题目巩固下,下面来看剑指中的相关题目。题目分析合并两个排序的链表,需要分别比较两个链表的每个值,然后改变指针。 温故知新 链表由一个一个的作为节点的对象构成的,每一个节点都有指向下一个节点的指针,最后一个节点的指针域指向空。每个节点可以存储任何数据类型。 根据类型可以分为单链表、双链表、环形链表、...

    daydream 评论0 收藏0
  • 剑指offer系列——剑指 Offer 24. 反转链表(C语言)

    摘要:假设反转对象节点为,反转指向的结点为,反转后指向的结点为首结点。当然也可以根据栈先进后出的特点,使用栈反转链表。 ⭐️前面的话⭐️ 大家好!博主开辟了一个新的专栏—...

    weakish 评论0 收藏0
  • 从简历被拒到收割今日头条 offer,我用一年时间破茧成蝶!

    摘要:正如我标题所说,简历被拒。看了我简历之后说头条竞争激烈,我背景不够,点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收,也不过个月的时间,但这都是建立在我过去一年的积累啊。 本文是 无精疯 同学投稿的面试经历 关注微信公众号:进击的java程序员K,即可获取最新BAT面试资料一份 在此感谢 无精疯 同学的分享 目录: 印象中的头条 面试背景 准备面试 ...

    tracymac7 评论0 收藏0
  • 从简历被拒到收割今日头条 offer,我用一年时间破茧成蝶!

    摘要:正如我标题所说,简历被拒。看了我简历之后说头条竞争激烈,我背景不够,点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收,也不过个月的时间,但这都是建立在我过去一年的积累啊。 本文是 无精疯 同学投稿的面试经历 关注微信公众号:进击的java程序员K,即可获取最新BAT面试资料一份 在此感谢 无精疯 同学的分享目录:印象中的头条面试背景准备面试头条一面(Java+项目)头条...

    wdzgege 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<