Datawhale面试刷题打卡-第1天(20210508)

Datawhale面试刷题打卡-第1天(20210508),第1张

概述20210508打卡每日一题题目解题思路相关算法链表双指针致谢每日一题题目地址:https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/解题思路首先回顾链表的特点。链表只能顺序地从前往后遍历,无法直接取到最后几个节点,并且如果想知道

20210508打卡每日一题题目解题思路相关算法链表双指针致谢

每日一题题目


地址: https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

解题思路

首先回顾链表的特点。链表只能顺序地从前往后遍历,无法直接取到最后几个节点,并且如果想知道链表的长度,也需要从头节点到尾节点遍历一遍。

在这里放弃了我一开始的思路,既先获取链表长度,然后根据总长度-k,遍历对应次数,获取链表最后几个节点。(时间复杂度稍高,有点麻烦)

最终,我在这道题上使用了双指针解法,第一个指针与第二个指针间隔K个步长。随后一起移动,当第一个指针到达尾节点的时候,返回第二个指针的链表,即为题目所求。

python代码如下:

class Solution:    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:        pointer1,pointer2=head,head        while pointer1:            while k>0:                    pointer1=pointer1.next                    k-=1            if pointer1:                pointer1=pointer1.next                    pointer2=pointer2.next            else:                break        return pointer2
相关算法链表

python数据结构之链表(linked list)
介绍了链表的基本结构,及在python中链表的一些基本 *** 作

双指针

【91算法-基础篇】05.双指针
介绍了双指针的常见题型,如快慢指针,首尾指针,固定间距指针等。 在本题中,我使用了固定间距指针。

致谢

感谢Datawhale的开源项目,及模拟面试项目的所有贡献者

附上Datawhale的开源面经库 Daily-intervIEw
https://github.com/datawhalechina/Daily-interview

总结

以上是内存溢出为你收集整理的Datawhale面试刷题打卡-第1天(20210508)全部内容,希望文章能够帮你解决Datawhale面试刷题打卡-第1天(20210508)所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/1186614.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-03
下一篇 2022-06-03

发表评论

登录后才能评论

评论列表(0条)

保存