首页 > 编程语言 >代码随想录算法训练营第三天 |203、707、206

代码随想录算法训练营第三天 |203、707、206

时间:2024-05-26 23:46:58浏览次数:29  
标签:node index 203 curr val 206 self 随想录 next

链表基础理论:https://programmercarl.com/链表理论基础.html
203题目链接:https://leetcode.cn/problems/remove-linked-list-elements/
203代码随想录:https://programmercarl.com/0203.移除链表元素.html#算法公开课
707题目链接:
https://leetcode.cn/problems/design-linked-list/description/
707代码随想录:https://programmercarl.com/0707.设计链表.html#其他语言版本
206题目链接:https://leetcode.cn/problems/reverse-linked-list/submissions/535001438/
206代码随想录:
https://programmercarl.com/0206.翻转链表.html#其他语言版本

链表基础知识笔记

链表示意图
image

单链表(如上图)

class linknode:
    def __init__(self,val,next = None):
        self.val = val
        self.next = next

双链表

class blinknode:
    def __init__(self,val,next = None,front = None):
        self.val = val
        self.next = next
        self.front = front

链表操作

删除节点

image

加入节点

image

203.移除链表元素

重点内容

  • 设置虚拟头节点,在删除头节点时会更便利;
  • 考虑链表遍历的条件和范围
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
    node_1 = ListNode()
    node_1.next = head
    curr = node_1
    while curr.next:
        if curr.next:
            if curr.next.val == val:
                curr.next = curr.next.next
                continue
        curr = curr.next
    return node_1.next

707 设计链表

重点内容:

  • 基本可以自己复现
  • 问题1:可以设置self.size 遍历循环
  • 遍历到index前一个和index当前那一个的公式不同
  • get 和 delete的范围[0,size) add——index范围是[0,index]
curr = self.dummy_node
for i in range(curr):
    curr = curr.next
### 结束时 curr为index的前一个

最终解答:

class Node:
    def __init__(self,val=0 ,next = None):
        self.val = val
        self.next = next

class MyLinkedList:
    def __init__(self):
        self.headnode = Node()
        self.size = 0

    def get(self, index: int) -> int:
        if index<0 or index>=self.size:
            return -1
        curr = self.headnode.next
        for i in range(index):
            curr = curr.next
        return curr.val

    def addAtHead(self, val: int) -> None:
        node_1 = Node(val)
        node_1.next = self.headnode.next
        self.headnode.next = node_1
        self.size = self.size+1

    def addAtTail(self, val: int) -> None:
        node_1 = Node(val)
        curr = self.headnode
        while curr.next:
            curr = curr.next
        curr.next = node_1
        self.size = self.size+1

    def addAtIndex(self, index: int, val: int) -> None:
        if index<0 or index>self.size:
            return 
        node_1 = Node(val)
        curr = self.headnode
        for i in range(index):
            curr = curr.next
        node_1.next = curr.next
        curr.next = node_1
        self.size =self.size+1


    def deleteAtIndex(self, index: int) -> None:
        if index>=0 and index<self.size:
            curr = self.headnode
            for i in range(index):
                curr = curr.next
            curr.next = curr.next.next
            self.size = self.size-1
        else:
            return

206反转链表

重点:

  • 第一遍没做出来,但其实只要想起来双指针就会了;
  • python的迭代和递归区别不太大

最终解答:

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        curr = head
        pre = None
        while curr:
            tmp = curr.next
            curr.next = pre
            pre = curr
            curr = tmp
        return pre

标签:node,index,203,curr,val,206,self,随想录,next
From: https://www.cnblogs.com/P201821440041/p/18214549

相关文章

  • 代码随想录算法训练营第第18天 | 513.找树左下角的值 、112. 路径总和 、106.从中
    找树左下角的值本地递归偏难,反而迭代简单属于模板题,两种方法掌握一下题目链接/文章讲解/视频讲解:https://programmercarl.com/0513.找树左下角的值.html/***Definitionforabinarytreenode.*functionTreeNode(val,left,right){*this.val=(val===undef......
  • Day36 代码随想录打卡|二叉树篇---翻转二叉树
    题目(leecodeT226):给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。方法:迭代法翻转二叉树,即从根节点开始,一一交换每个节点的左右孩子节点,然后递归此过程,将根节点的左右孩子节点再分别作为参数传入交换节点的函数中。重复此过程,直到结束。就完成了二叉树的翻......
  • 代码随想录算法训练营第三十七天|435. 无重叠区间、763.划分字母区间、56. 合并区间、
    435.无重叠区间文档讲解:代码随想录题目链接:.-力扣(LeetCode)本道题与上个题目相似,都是求重叠区间统计重叠区间的个数,减去重叠区间的个数就是无重叠区间了主要就是为了让区间尽可能的重叠。(为什么)按照左边界排序①如果i的左边界大于等于上一个区间的右边界,就没有重叠......
  • 代码随想录算法训练营第十六天 | 104.二叉树的最大深度、559.n叉树的最大深度、111.二
    104.二叉树的最大深度题目链接:https://leetcode.cn/problems/maximum-depth-of-binary-tree/文档讲解:https://programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE......
  • 代码随想录算法训练营第36期DAY38
    DAY38435无重叠区间昨晚很快就想出来了,今天相当于二刷。class Solution {public:    static bool mycmp(vector<int>&a,vector<int>&b){        return a[1]<b[1];    }    int eraseOverlapIntervals(vector<vector<int>>& intervals) {   ......
  • 代码随想录算法训练营第36期DAY39
    道心破碎的一天,继续加油吧,坚持努力。DAY39738单调递增的数字暴力法:没有想到用inti=n;i>0;i--来遍历。class Solution {private:    bool checknum(int num){        if(num<10) return true;        while(num/10!=0){           ......
  • 代码随想录算法训练营第36期DAY37
    DAY37先二刷昨天的3道题目,每种方法都写:是否已完成:是。报告:134加油站的朴素法没写对。原因是:在if中缺少了store>=0的判断,只给出了index==i的判断。前进法没写出来。因为忘记了总油量的判断。Sum。注意变量的初始化。分配糖果注意if里面放的是ratings;860柠檬水找零网上摘得思......
  • 代码随想录——二叉树的所有路径(Leetcode257)需要回顾
    题目链接BFS+队列维护一个队列,存储节点以及根到该节点的路径。一开始这个队列里只有根节点。在每一步迭代中,我们取出队列中的首节点,如果它是叶子节点,则将它对应的路径加入到答案中。如果它不是叶子节点,则将它的所有孩子节点加入到队列的末尾。当队列为空时广度优先搜......
  • 代码随想录算法训练营第一天 | 977.有序数组的平方;
    代码随想录算法训练营第一天|977.有序数组的平方;977题链接:https://leetcode.cn/problems/squares-of-a-sorted-array/代码随想录链接:https://programmercarl.com/0977.有序数组的平方.html#思路209题链接:https://leetcode.cn/problems/minimum-size-subarray-sum/submission......
  • 代码随想录算法训练营第第17天 | 110.平衡二叉树、257. 二叉树的所有路径、404.左叶子
    三道题都没想出来,还是要加强递归的练习110.平衡二叉树(优先掌握递归)再一次涉及到,什么是高度,什么是深度,可以巩固一下。题目链接/文章讲解/视频讲解:https://programmercarl.com/0110.平衡二叉树.htmlfunctiongetHeight(node){if(node===null)return0;letleftH......