数组原理、实战应用
- C++: int a[100];
- Java: int[] a = new int[100];
- Python:a=[]
- 数组的基本特点:支持随机访问
- 数组的关键:索引与寻址
- C++: a[i], *(a+i)
- Java, Python: a[i]
- 数组在内存中是–段连续的存储空间
数组-插入元素
数组-删除元素
时间复杂度
实战
26.删除有序数组中的重复项
https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
class Solution { public: int removeDuplicates(vector<int>& nums) { int n = nums.size(); if (n == 0) { return 0; } int fast = 1, slow = 1; while (fast < n) { if (nums[fast] != nums[fast - 1]) { nums[slow] = nums[fast]; ++slow; } ++fast; } return slow; } };
283.移动零
https://leetcode.cn/problems/move-zeroes/
class Solution { public: void moveZeroes(vector<int>& nums) { int n = nums.size(), left = 0, right = 0; while (right < n) { if (nums[right]) { swap(nums[left], nums[right]); left++; } right++; } } };
88.并两个有序数组
https://leetcode.cn/problems/merge-sorted-array/
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { for(int i=0;i<n;i++) { nums1[m+i]=nums2[i]; } sort(nums1.begin(),nums1.end()); } };
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { // for(int i=0;i<n;i++) // { // nums1[m+i]=nums2[i]; // } // sort(nums1.begin(),nums1.end()); int pos=m-- + n-- -1; while(m>=0 && n>=0) { nums1[pos--]=nums1[m]>nums2[n]?nums1[m--]:nums2[n--]; } while(n>=0) { nums1[pos--]=nums2[n--]; } } };
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int p1 = m - 1, p2 = n - 1; int tail = m + n - 1; int cur; while (p1 >= 0 || p2 >= 0) { if (p1 == -1) { cur = nums2[p2--]; } else if (p2 == -1) { cur = nums1[p1--]; } else if (nums1[p1] > nums2[p2]) { cur = nums1[p1--]; } else { cur = nums2[p2--]; } nums1[tail--] = cur; } } };
设计变长数组
- C++: vector
- Java: ArrayList
- Python: list
如何实现一个变长数组?
- 支持索引与随机访问
- 分配多长的连续空间?
- 空间不够用了怎么办?
- 空间剩余很多如何回收?
一个简易的实现方法
- 初始:空数组，分配常数空间，记录实际长度(size) 和容量(capacity)
- Push back:若空间不够，重新申请2倍大小的连续空间，拷贝到新空间，释放旧空间
- Pop back:若空间利用率(size/capacity) 不到25%，释放一半的空间
- 均摊0(1)
- 在空数组中连续插入n个元素，总插入/拷贝次数为n+n/2+n/4+…< 2n
- 一次扩容到下一次释放，至少需要再删除n- 2n*0.25=0.5n次
思考:若释放空间的阈值设定为50%，会发生什么情况?
链表原理讲解、实战应用
单链表(linked list)
单链表-插入
单链表-删除
双链表(double linked list)
时间复杂度
保护节点
实战
206.反转链表
https://leetcode.cn/problems/reverse-linked-list/
class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* curr = head; while (curr) { ListNode* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } };
25. K个一组翻转链表
https://leetcode.cn/problems/reverse-nodes-in-k-group/
class Solution { public: // 翻转一个子链表，并且返回新的头与尾 pair<ListNode*, ListNode*> myReverse(ListNode* head, ListNode* tail) { ListNode* prev = tail->next; ListNode* p = head; while (prev != tail) { ListNode* nex = p->next; p->next = prev; prev = p; p = nex; } return {tail, head}; } ListNode* reverseKGroup(ListNode* head, int k) { ListNode* hair = new ListNode(0); hair->next = head; ListNode* pre = hair; while (head) { ListNode* tail = pre; // 查看剩余部分长度是否大于等于 k for (int i = 0; i < k; ++i) { tail = tail->next; if (!tail) { return hair->next; } } ListNode* nex = tail->next; // 这里是 C++17 的写法，也可以写成 // pair<ListNode*, ListNode*> result = myReverse(head, tail); // head = result.first; // tail = result.second; tie(head, tail) = myReverse(head, tail); // 把子链表重新接回原链表 pre->next = head; tail->next = nex; pre = tail; head = tail->next; } return hair->next; } };
141.环形链表
https://leetcode.cn/problems/linked-list-cycle/
- 快慢指针法, 0(length) 时间，0(1) 空间
- 有环必定发生套圈(快慢指针相遇)，无环不会发生套圈(快指针到达null)
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool hasCycle(ListNode *head) { ListNode* fast = head; while(fast != nullptr && fast->next != nullptr) { fast = fast->next->next; head = head->next; if(fast == head) return true; } return false; } };
142.环形链表II
- 相遇时,有2(l+p)=l+p+k*r,其中k为整数(套的圈数)
- 即l=kr-p=(k-1) r+(r-p)
- 含义:从head走到st,等于从meet走到st,然后再绕几圈
- 此时开始让慢指针与head同时移动，必定在环的起始点相遇
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode* fast = head; ListNode* slow = head; while(fast != nullptr && fast->next != nullptr) { fast = fast->next->next; slow = slow->next; if (fast == slow) { while (head != slow ) { head = head->next; slow = slow->next; } return head; } } return nullptr; } };
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
