使用入门

视频链接

【手把手带你刷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参数是一个约定俗成的参数名，用于表示对象自身。它通常作为方法的第一个参数，用于引用当前正在调用该方法的对象。

class Person:def _init_(self, name):self.name = namedef introduce(self):print("My name is {self.name}.")person = Person("Tom")
person.introduce()

My name is Tom.

485. 最大连续 1 的个数

. - 力扣（LeetCode）

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

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

2

时：O(n)

空：O(1)

283. 移动零

. - 力扣（LeetCode）

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

[1, 3, 12, 0, 0]

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

时：O(n)

空：O(1)

27. 移除元素

. - 力扣（LeetCode）

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

[2, 2]
2

时：O(n)

空：O(1)

链表

相关习题

203.移除链表元素

. - 力扣（LeetCode）

struct ListNode* removeElements(struct ListNode* head, int val) {// 头结点单独处理while(head != NULL && head->val == val){head = head->next;}if (NULL == head){return head;}struct ListNode *pre = head, *temp;while(pre->next != NULL){if(pre->next->val == val){   //该元素需要删除temp = pre->next;pre->next = temp->next;free(temp);}else{pre = pre->next;}}if(pre->val == val){free(pre);}return head;
}

时：O(n)

空：O(1)

206.反转链表

. - 力扣（LeetCode）

struct ListNode* reverseList(struct ListNode* head) {if(head == NULL){return head;}// p用来遍历单链表，r是为了防止断链struct ListNode *p = head->next, *r;head->next = NULL;while( p != NULL){r = p->next;// 头插法将元素插入p->next = head;head = p;p = r;}return head;
}

时：O(n)

空：O(1)

2

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
int power(int x, int n) {    //该函数用于实现计算x次幂，那么之后求n-1、n-2...次幂都可以用了while (n != 1) {return x*power(x, n - 1);}if (n == 1) {return x;}
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {/*算法思想：（1）用两个指针p、q分别遍历两个单链表，将p所指结点的数据一一加和到countl1中。（2）遍历第二个单链表，将q所指结点数据加和countl1到count中，（3）q在遍历期间，首先判断是否会进位，然后将count%10，count/10得到的数据覆盖链表l1的数据，为防止l1链表长度不够，还需要票判断链表是否为空（最后返回l1的数据）*/struct ListNode *p = l1, *q = l2;   //p、q分别用来遍历l1、l2int countl1 = 0, count = 0;int i = 0;while(p != NULL){                   //遍历第一个单链表countl1 += (p->val * power(10, i));p = p->next;i++;}i = 0;int insertdata = 0,prepose = 0;     //insertdata是将要插入链表的数据,prepose控制进位p = l1;while(q != NULL){insertdata = countl1%10 + q->val;if(insertdata >= 10){    //需要进位insertdata /= 10;p->val = insertdata + prepose;prepose = 1;}else{                  //不需要进位p->val = insertdata + prepose;prepose = 0;}p = p->next;q = q->next;countl1 /= 10;}return l1;}

#include<iostream>
#include<cmath>
#include<cstddef>
using namespace std;
struct ListNode {int val;ListNode* next;ListNode(int value) : val(value), next(nullptr) {}
};ListNode* createSList(int* nums, int sz) {ListNode* head = nullptr;ListNode* tail = nullptr;for (int i = 0; i < sz; ++i) {ListNode* newNode = new ListNode(nums[i]);if (tail == nullptr) {head = tail = newNode;} else {tail->next = newNode;tail = newNode;}}return head;
}void destroySList(ListNode* head) {while (head != nullptr) {ListNode* temp = head;head = head->next;delete temp;}
}int main() {int arr[] = {1, 2, 3, 4, 5, 6};int sz = sizeof(arr) / sizeof(arr[0]);ListNode* plist = createSList(arr, sz);// 在程序结束前释放链表占用的内存destroySList(plist);return 0;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {/*算法思想：（1）用两个指针p、q分别遍历两个单链表，将p所指结点的数据一一加和到countl1中。（2）遍历第二个单链表，将q所指结点数据加和countl1到count中，（3）q在遍历期间，首先判断是否会进位，然后将count%10，count/10得到的数据覆盖链表l1的数据，为防止l1链表长度不够，还需要票判断链表是否为空（最后返回l1的数据）*/struct ListNode *p = l1, *q = l2;   //p、q分别用来遍历l1、l2int countl1 = 0, count = 0;int i = 0;while(p != NULL){                   //遍历第一个单链表countl1 += (p->val * pow(10, i));p = p->next;i++;}i = 0;int insertdata = 0,prepose = 0;     //insertdata是将要插入链表的数据,prepose控制进位p = l1;while(q != NULL){insertdata = countl1%10 + q->val;if(insertdata >= 10){    //需要进位insertdata /= 10;p->val = insertdata + prepose;prepose = 1;}else{                  //不需要进位p->val = insertdata + prepose;prepose = 0;}p = p->next;q = q->next;countl1 /= 10;}return l1;
}