devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

力扣刷题学习（跟随视频学着刷）

作者：知新_RL | 2024-04-30 03:44:55

赞

踩

力扣刷题学习（跟随视频学着刷）

使用入门

视频链接

【手把手带你刷Leetcode力扣｜各个击破数据结构和算法｜大厂面试必备技能【已完结】-哔哩哔哩】 https://b23.tv/vIcRT61

时空复杂度

时间：

空间：主要有O(1)和O(n)两种，只用计算开辟的内存，若数组当做参数传进来了，不用计算数组的空间

数组

特点：适合读多写少

操作

  1. 创建数组
  2. 添加元素（追加元素在列表末端，时：O(1),否则为O(n)）
  3. 访问元素（时：O(1)）
  4. 修改元素（时：O(1)）
  5. 删除元素
  6. 遍历数组
  7. 查找元素
  8. 数组长度
  9. 数组排序

相关习题

补充

在Python中，self参数是一个约定俗成的参数名，用于表示对象自身。它通常作为方法的第一个参数，用于引用当前正在调用该方法的对象。

  1. class Person:
  2.     def _init_(self, name):
  3.         self.name = name
  4.     def introduce(self):
  5.         print("My name is {self.name}.")
  6.  
  7. person = Person("Tom")
  8. person.introduce()
My name is Tom.

485. 最大连续 1 的个数

. - 力扣（LeetCode）

测试部分用例对了，还未找到错因

  1. def findMaxConsecutiveOnes(nums):
  2.         """
  3.         :type nums: List[int]
  4.         :rtype: int
  5.         """
  6.         # 遍历列表，遍历到列表中的元素为1时：当前计数+1；碰到0时：将当前计数与最大计数对比，若当前计数大，则将当前计数覆盖最大计数，然后将当前计数归0，如此往复，最后返回当前计数和最大计数中的最大值（当列表最后一个元素为1时，也需要对比当前计数和最大计数）
  7.         now_count = 0	# 当前计数
  8.         final_count = 0 # 最大计数
  9.         for i in range(len(nums)):
  10.             if nums[i] == 1 :
  11.                 now_count += 1
  12.             else:
  13.                 final_count = max(final_count, now_count)
  14.                 now_count = 0
  15.         return max(final_count, now_count)
  16. nums = [1,0,1,1,0,1]
  17. print(findMaxConsecutiveOnes(nums))
2

时：O(n)

空：O(1)

283. 移动零

. - 力扣（LeetCode）

  1. def moveZeroes(nums):
  2.         """
  3.         :type nums: List[int]
  4.         :rtype: None Do not return anything, modify nums in-place instead.
  5.         """
  6.         # 特殊指针法，当前指针遍历列表，若当前指针遍历到非零元素，则将非零元素向前覆盖，然后继续往后遍历；若遍历到0元素，则计数加1。
  7.         count = 0 # 计数，记录0元素个数，用于计算覆盖元素的位置
  8.         for i in range(0,len(nums)):
  9.             if nums[i] != 0:
  10.                 # 元素向前覆盖
  11.                 nums[i - count] = nums[i]
  12.             else:
  13.                 count += 1
  14.         # 后面元素覆0值
  15.         for i in range(0, count):
  16.             nums[len(nums) - 1 - i] = 0
  17.         return nums
  18. nums = [0,1,0,3,12]
  19. print(moveZeroes(nums))
[1, 3, 12, 0, 0]

易错点：（这个-1一定别忘了，假如此时count=1,代表只有一个0被覆盖了，此时应当是nums[len(nums) - 1] = 0）

时：O(n)

空：O(1)

27. 移除元素

. - 力扣（LeetCode）

  1. def removeElement(nums, val):
  2.         """
  3.         :type nums: List[int]
  4.         :type val: int
  5.         :rtype: int
  6.         """
  7.         # 特殊指针法，当前指针遍历列表，若当前指针遍历到非val元素，则将非零元素向前覆盖，然后继续往后遍历；若遍历到val元素，则计数加1。
  8.         count = 0 # 计数，记录val元素个数，用于计算覆盖元素的位置
  9.         for i in range(0,len(nums)):
  10.             if nums[i] != val:
  11.                 # 元素向前覆盖
  12.                 nums[i - count] = nums[i]
  13.             else:
  14.                 count += 1
  15.         # 后面元素删除
  16.         for i in range(0, count):
  17.             nums.pop()
  18.         return nums
  19. nums = [3,2,2,3]
  20. print(removeElement(nums, 3))
  21. print(len(nums))
  1. [2, 2]
  2. 2

时：O(n)

空：O(1)

链表

相关习题

203.移除链表元素

. - 力扣（LeetCode）

  1. struct ListNode* removeElements(struct ListNode* head, int val) {
  2.     // 头结点单独处理
  3.     while(head != NULL && head->val == val){
  4.         head = head->next;
  5.     }
  6.     if (NULL == head){
  7.         return head;
  8.     }
  9.     struct ListNode *pre = head, *temp;
  10.     while(pre->next != NULL){
  11.         if(pre->next->val == val){   //该元素需要删除
  12.             temp = pre->next;
  13.             pre->next = temp->next;
  14.             free(temp);
  15.         }else{
  16.             pre = pre->next;
  17.         }
  18.     }
  19.     if(pre->val == val){
  20.         free(pre);
  21.     }
  22.     return head;
  23. }

时：O(n)

空：O(1)

206.反转链表

. - 力扣（LeetCode）

  1. struct ListNode* reverseList(struct ListNode* head) {
  2.     if(head == NULL){
  3.         return head;
  4.     }
  5.     // p用来遍历单链表，r是为了防止断链
  6.     struct ListNode *p = head->next, *r;
  7.     head->next = NULL;
  8.     while( p != NULL){
  9.         r = p->next;
  10.         // 头插法将元素插入
  11.         p->next = head;
  12.         head = p;
  13.         p = r;
  14.     }
  15.     return head;
  16. }

时：O(n)

空：O(1)

2

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     struct ListNode *next;
  6.  * };
  7.  */
  8. int power(int x, int n) {    //该函数用于实现计算x次幂，那么之后求n-1、n-2...次幂都可以用了
  9.     while (n != 1) {
  10.         return x*power(x, n - 1);
  11.     }
  12.     if (n == 1) {
  13.         return x;
  14.     }
  15. }
  16. struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
  17.     /*
  18.     算法思想：
  19.     （1）用两个指针p、q分别遍历两个单链表，将p所指结点的数据一一加和到countl1中。
  20.     （2）遍历第二个单链表，将q所指结点数据加和countl1到count中，
  21.     （3）q在遍历期间，首先判断是否会进位，然后将count%10，count/10得到的数据覆盖链表l1的数据，为防止l1链表长度不够，还需要票判断链表是否为空（最后返回l1的数据）
  22.     */
  23.  
  24.     struct ListNode *p = l1, *q = l2;   //p、q分别用来遍历l1、l2
  25.     int countl1 = 0, count = 0;
  26.     int i = 0;
  27.     while(p != NULL){                   //遍历第一个单链表
  28.         countl1 += (p->val * power(10, i));
  29.         p = p->next;
  30.         i++;
  31.     }
  32.     i = 0;
  33.     int insertdata = 0,prepose = 0;     //insertdata是将要插入链表的数据,prepose控制进位
  34.     p = l1;
  35.     while(q != NULL){
  36.         insertdata = countl1%10 + q->val;
  37.         if(insertdata >= 10){    //需要进位
  38.             insertdata /= 10;
  39.             p->val = insertdata + prepose;
  40.             prepose = 1;
  41.         }else{                  //不需要进位
  42.             p->val = insertdata + prepose;
  43.             prepose = 0;
  44.         }
  45.  
  46.         p = p->next;
  47.         q = q->next;
  48.         countl1 /= 10;
  49.     }
  50.     return l1;
  51.  
  52.  
  53.  
  54. }
  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstddef>
  4. using namespace std;
  5. struct ListNode {
  6.     int val;
  7.     ListNode* next;
  8.     
  9.     ListNode(int value) : val(value), next(nullptr) {}
  10. };
  11.  
  12. ListNode* createSList(int* nums, int sz) {
  13.     ListNode* head = nullptr;
  14.     ListNode* tail = nullptr;
  15.  
  16.     for (int i = 0; i < sz; ++i) {
  17.         ListNode* newNode = new ListNode(nums[i]);
  18.  
  19.         if (tail == nullptr) {
  20.             head = tail = newNode;
  21.         } else {
  22.             tail->next = newNode;
  23.             tail = newNode;
  24.         }
  25.     }
  26.  
  27.     return head;
  28. }
  29.  
  30. void destroySList(ListNode* head) {
  31.     while (head != nullptr) {
  32.         ListNode* temp = head;
  33.         head = head->next;
  34.         delete temp;
  35.     }
  36. }
  37.  
  38. int main() {
  39.     int arr[] = {1, 2, 3, 4, 5, 6};
  40.     int sz = sizeof(arr) / sizeof(arr[0]);
  41.  
  42.     ListNode* plist = createSList(arr, sz);
  43.  
  44.     // 在程序结束前释放链表占用的内存
  45.     destroySList(plist);
  46.  
  47.     return 0;
  48. }
  49. ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
  50.         /*
  51.         算法思想：
  52.         （1）用两个指针p、q分别遍历两个单链表，将p所指结点的数据一一加和到countl1中。
  53.         （2）遍历第二个单链表，将q所指结点数据加和countl1到count中，
  54.         （3）q在遍历期间，首先判断是否会进位，然后将count%10，count/10得到的数据覆盖链表l1的数据，为防止l1链表长度不够，还需要票判断链表是否为空（最后返回l1的数据）
  55.         */
  56.         struct ListNode *p = l1, *q = l2;   //p、q分别用来遍历l1、l2
  57.         int countl1 = 0, count = 0;
  58.         int i = 0;
  59.         while(p != NULL){                   //遍历第一个单链表
  60.             countl1 += (p->val * pow(10, i));
  61.             p = p->next;
  62.             i++;
  63.         }
  64.         i = 0;
  65.         int insertdata = 0,prepose = 0;     //insertdata是将要插入链表的数据,prepose控制进位
  66.         p = l1;
  67.         while(q != NULL){
  68.             insertdata = countl1%10 + q->val;
  69.             if(insertdata >= 10){    //需要进位
  70.                 insertdata /= 10;
  71.                 p->val = insertdata + prepose;
  72.                 prepose = 1;
  73.             }else{                  //不需要进位
  74.                 p->val = insertdata + prepose;
  75.                 prepose = 0;
  76.             }
  77.             p = p->next;
  78.             q = q->next;
  79.             countl1 /= 10;
  80.         }
  81.         return l1;
  82. }
  83.

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/511278
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号