本文主要是介绍超多注释助你手撕LeetCode(一),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
超多注释助你手撕LeetCode(一)
链表复习:
Leetcode-86-分隔链表
- 使用两个链表,一个用于插入小于x的元素,一个用于插入大于等于x的元素,最后合并两个链表即可。
// 把链表分成大小两条单链表,之后再连接起来就可以了
// 用两个头,一个小,一个大
class Solution {
public:ListNode* partition(ListNode* head, int x) {// 分别用来存储大数和小数// r1和r2是为了让指针不要乱跑,这个算是虚拟头结点 ListNode r1, r2, *p1 = &r1, *p2 = &r2, *p = head, *q;while (p) {// 这句话应该是至关重要的部分吧,如果不先存储的话,p->next的值会变q = p->next;if (p->val < x) {// 小于的话直接接入小的链表的最后一位// 如果要把一个元素搞进来,那个元素不能在另一个链表里,不然// 另一个指针也会断掉,原来的链表可以全部拆掉p->next = p1->next;// 把这个节点接进来p1->next = p;// p1来到最后一个节点,方便下一次的插入p1 = p;} else {// p2->next其实就是nullptr,它把原来的链表拆掉了p->next = p2->next;p2->next = p;// 之后p2->next 就是nullptr了p2 = p;}// p指向下一个节点,开始下一轮判断p = q;}// 把p1的节点接回去p1->next = r2.next;// 这个是结果return r1.next;}
};
LeetCode #138 复制带随机指针的链表
- 题目很重要的思想是深copy,还有把随机指针复制下来
- 可以将 A − > B − > C A->B->C A−>B−>C 复制成 A − > A ′ − > B − > B ′ − > C − > C ′ A->A'->B->B'->C->C' A−>A′−>B−>B′−>C−>C′
- 之后把复刻出来的节点的random指针指向的节点向前挪动一位。
- 最后用两个指针把链表拆下来
// 最难的地方就是需要复刻random指针! 如何复制随机指针
class Solution {
public:Node* copyRandomList(Node* head) {if (head == nullptr) return nullptr;Node *p = head, *q, *new_head;while (p) {// 复制出来的节点和原来节点的指针域指向同一个节点q = new Node(p->val);// 赋值出来的随机指针域和源节点一样q->random = p->random;// 插入节点,将每个元素复制// q插入到p后面q->next = p->next;p->next = q;// 注意下面这句话,等下直接看看// p应该走到q的下一位p = q->next;}// 修正随机指针域// 指向被复制的那个节点p = head->next;while (p) {// 修正每个节点的random指针域// 如果不为空才可以进行这种操作if (p->random) p->random = p->random->next;// 向后走两步,骚操作,太骚了。先试探性走一步,然后走两个// p = p->next;// if(p) p = p->next;(p = p->next) && (p = p->next);}// 设置两个虚拟头结点new_head = head->next;// 指向原链表的第一个节点p = head;while (p) {// 实现方式有很多,难度:极其简单,代码实现是很随意的// 我好想哭啊// 将相邻的节点拆开q = p->next;// 注意拆分的时候节点的标志!!p->next = q->next;// 如果p->next 有值,就继续向下走// 还是需要画图解决这个问题。思路还需要更清晰一些if (p->next) q->next = p->next->next;// 只让p走就可以了,q在下一段代码开始的时候就自动走了p = p->next;}// 返回新链表的头结点,贪心很少面试,一般面试动态规划,因为它上限可能没有贪心这么高return new_head;}
};
队列封装->封装到疯
队列是什么:
- 一般来说,尾指针是指向最后一个元素的下一位(至少考研是这样的)。出队,头指针向后移动一位,入队,尾指针向后移动一位,并加入元素。允许插队的队列叫做优先队列。
- 队列是FIFO。
- 当尾指针没有位置的时候,这是队列满了的情况,或者说是队列溢出。但是如果存储的元素个数小于队列的空间的话,就可以叫做队列的假溢出(只是尾指针走到了最后一位)。
- 循环队列能够避免假溢出,指针走到队末,直接指向头。循环队列满了就真满了。
队列的应用:CPU的超线程技术:
-
真双核,这个管子是一个指令的队列。有两个核心,每个核心有一个指定队列。因为用户只能看到2个管子,就是双核CPU。真双核意思是一共有两个cpu核心。
-
虚拟四核,用户队列有4个,cpu核心有两个。因为核心的计算速度非常快,而普通的队列跟不上cpu的处理速度。所以一个cpu可以带两个任务管道。
-
线程是进程中执行的基本单位。
-
多路cpu:就是多个cpu。企业中会用32或者64核,这是多个cpu拼起来的。一般的电脑都是一个cpu。
-
进程和线程是什么?自己就是一个进程,在做的事情就是线程。如果同一时间做多件事情就是多线程,一个进程可以有多线程。C程序员必备这个知识。
-
以后要补充计网和计组。
-
我们需要频繁地进行线程的申请和销毁,这样会使得程序的效率变低。这时候出现了线程池。当任务多余线程的时候,多余的就存储在任务队列里面,任务队列相当于任务的缓冲区。相当于医院的凳子。C++有一个线程池的代码,可以自己去看看。队列能够用作缓冲区。
线程池需要的思想:函数式编程,泛型编程。
LeetCode #622 设计循环队列
- 队列封装,真没有什么好说的。最终要的就是要有一种模块化还有面向对象思维。
- 只能说是当局者迷,写完尿急。特别繁琐的题目,但是对编程能力的提高大有裨益
- 对了,需要补充的是循环队列的指针,指针可以通过取%来免去复杂的条件判断,具体取模在代码的注释中体现。
class MyCircularQueue {
public:// 连续的存储区,一个动态数组vector<int> arr;// 头指针,尾指针还有cnt,用数组下表来代替int head, tail, cnt;// 相当于函数里面有这个对象,初始化这些值,有了这句话都不需要其他初始化了MyCircularQueue(int k) : arr(k), head(0), tail(0), cnt(0) {}bool enQueue(int value) {if (isFull()) return false;// tail之后插入数据,让tail循环起来arr[tail] = value;// 对arr.size()取余tail = (tail + 1) % arr.size();cnt += 1;return true;}bool deQueue() {// 出队就是head+1if (isEmpty()) return false;head = (head + 1) % arr.size();cnt -= 1;return true;}// 查看队首元素int Front() {if (isEmpty()) return -1;return arr[head];}// 返回尾部元素,判断队列是不是空int Rear() {if (isEmpty()) return -1;// tail指向的位置不是尾部元素,要指向tail-1是整个数组的最后位置// int ind = tail -1;// if(ind == -1) ind = arr.size()-1;// return arr[ind];// 下面是为了防止出现负数,当下表是0的时候可以直接向前定位到n-1return arr[(tail - 1 + arr.size()) % arr.size()];}bool isEmpty() {return cnt == 0;}bool isFull() {return cnt == arr.size();}
};
LeetCode #641 设计双端循环队列
- 双端循环队列的意思是可以在头部进行入队和出队操作
- 单端循环队列意思是在头部进行出队,尾部入队。主要还是封装技巧
class MyCircularDeque {
public:
/** Initialize your data structure here. Set the size of the deque to bek. */vector<int> arr;int cnt, head, tail;// 这种初始化方法可以多记住一下MyCircularDeque(int k) : arr(k), head(0), tail(0), cnt(0) {}/** Adds an item at the front of Deque. Return true if the operation issuccessful. */// 不能满才能插入bool insertFront(int value) {if (isFull()) return false;head = head - 1;if (head == -1) head = arr.size() - 1;arr[head] = value;// 插入完元素必须cnt++cnt += 1;return true;}/** Adds an item at the rear of Deque. Return true if the operation issuccessful. */bool insertLast(int value) {// 和原来的一样if (isFull()) return false;arr[tail] = value;tail += 1;if (tail == arr.size()) tail = 0;cnt += 1;return true;}/** Deletes an item from the front of Deque. Return true if theoperation is successful. */bool deleteFront() {// 头部出队if (isEmpty()) return false;head = (head + 1) % arr.size();// 元素少了一个cnt -= 1;return true;}/** Deletes an item from the rear of Deque. Return true if the operationis successful. */bool deleteLast() {if (isEmpty()) return false;tail = (tail - 1 + arr.size()) % arr.size();cnt -= 1;return true;}/** Get the front item from the deque. */int getFront() {if (isEmpty()) return -1;return arr[head];}/** Get the last item from the deque. */int getRear() {// 不太想说了if (isEmpty()) return -1;return arr[(tail - 1 + arr.size()) % arr.size()];}/** Checks whether the circular deque is empty or not. */bool isEmpty() {return cnt == 0;}/** Checks whether the circular deque is full or not. */bool isFull() {return cnt == arr.size();}
};
LeetCode #1670 设计前中后队列
- 真没到写完就尿急,尿完回来还得写。非常繁琐
- 重难点是实现在中间的入队和出队操作
- 中间入队操作我们可以用两个双端队列实现。之后在最后把两个双端队列进行拼接就可以了
- 在每个双端队列之中,我们需要定义链表形式的节点,通过链表来进行动态的扩容。可以实现在this节点前插后插,前删后删。
// 用两个双端队列实现前中后队列
// 高级数据结构都是一些低级数据结构拼起来的
// 用链表实现双端队列
class Node {
public :int val;// 头结点和尾巴节点// 这个代码超级长!!!!!// 估计要花两个小时。。。。。。Node *next, *pre;Node(int val = 0, Node *next = nullptr, Node *pre = nullptr):val(val), next(next), pre(pre) {}// 用链表实现双端队列,主要学习一种思想的不同实现// 算法思想和编码能力是两码事,两种都要学// 在当前节点的前面插入新的节点,需要画图// 意思是从中间插入,最好花图// 要有正常的封装代码的思维// vim配置:ma6174// 除了烦人还是烦人// 当局者迷,写完尿急。真的晕void insert_pre(Node *p) {p->pre = pre;// this意思是当前节点p->next = this;// 当前节点向后指向pif (this->pre) this->pre->next = p;this->pre = p;return ;}void insert_next(Node *p) {// 一样看在哪里插入p->pre = this;p->next = this->next;if (this->next) this->next->pre = p;this->next = p;return ;}// 删除当前节点的前一个节点void delete_pre() {// 有前一个节点就可以插入,if (this->pre == nullptr) return ;Node *p = this->pre;this->pre = p->pre;if (p->pre) p->pre->next = this;// 为了防止内存泄露// 手动释放空间delete p;return ;}// 删除当前节点的后一个节点void delete_next() {// 有下一个节点才能删除if (this->next == nullptr) return ;Node *p = this->next;this->next = p->next;if (p->next) p->next->pre = this;delete p;return ;}
};class Queue {
public :Node head, tail;// 记录节点数量int cnt;// 初始化方法Queue() : cnt(0) {// 哪个节点在哪里head.next = &tail;head.pre = nullptr;tail.next = nullptr;tail.pre = &head;}// 从尾部入队void push_back(int val) {// 在当前节点的前面插入节点tail.insert_pre(new Node(val));cnt += 1;return ;}// 头部入队void push_front(int val) {head.insert_next(new Node(val));cnt += 1;return ;}// 尾部出队int pop_back() {if (isEmpty()) return -1;int ret = tail.pre->val;tail.delete_pre();cnt -= 1;return ret;}// 头部出队int pop_front() {if (isEmpty()) return -1;int ret = head.next->val;head.delete_next();cnt -= 1;return ret;}// 前面的值int front() {return head.next->val;}// 后面的元素int back() {return tail.pre->val;}// 是不是空bool isEmpty() {return head.next == &tail;}// size大小int size() {return cnt;}
};// 重头戏来了
class FrontMiddleBackQueue {
public:
// 需要两个双端队列。Queue q1, q2;FrontMiddleBackQueue() {}// 直接在q1头部进行删除void pushFront(int val) {q1.push_front(val);// 更新两个元素的元素数量// q1>=q2的元素数量update();return ;}void pushMiddle(int val) {// 如果q1比较大,就向后挪一个,之后再插进来if (q1.size() > q2.size()) {q2.push_front(q1.back());q1.pop_back();}// 不用update也是一样的q1.push_back(val);return ;}void pushBack(int val) {q2.push_back(val);update();return ;}int popFront() {if (isEmpty()) return -1;int ret = q1.pop_front();update();return ret;}// pop的是q1的元素int popMiddle() {if (isEmpty()) return -1;int ret = q1.pop_back();update();return ret;}int popBack() {// 先判断q2是不是空的if (isEmpty()) return -1;int ret;if (q2.isEmpty()) {ret = q1.pop_back();} else {ret = q2.pop_back();}update();return ret;}bool isEmpty() {// q1元素不少于q2的话,q1空了就空了return q1.size() == 0;}//更新队列元素,并实现匀一匀操作void update() {if (q1.size() < q2.size()) {q1.push_back(q2.front());q2.pop_front();}// 末尾拿一个元素出来if (q1.size() == q2.size() + 2) {q2.push_front(q1.back());q1.pop_back();}return ;}
};
LeetCode #933 最近请求次数
- 只要有大于3000的就让它出队。C++里面有已经实现好的queue方法
class RecentCounter {
public:queue<int> q;RecentCounter() {}int ping(int t) {// 队列裸题q.push(t);// 把所有t-3000之前的请出去,这个就是请出去的过程// t是从小到大的while(t-q.front() > 3000) q.pop();return q.size();}
};
LeetCode #面试题 17.09 第K个数
- 这道题目其实也叫做丑数
- 其实和线性筛的道理差不多,就是要注意一点,如果得到有两个数都是相同的最小值,指针都向后移动一位
- 因为时间不太够,没有办法完全整理下来思路。
class Solution {
public:int getKthMagicNumber(int k) {vector<int> arr;//先压入1arr.push_back(1);int p3 = 0, p5 = 0, p7 = 0;while (arr.size() < k) {int ans = 3 * arr[p3];// 有min就是舒服,p5指针指向的是arr的位数ans = min(ans, 5 * arr[p5]);ans = min(ans, 7 * arr[p7]);// 去重的过程if (3 * arr[p3] == ans) p3++;if (5 * arr[p5] == ans) p5++;if (7 * arr[p7] == ans) p7++;// 把最小的数压到栈里面arr.push_back(ans);}// 从0开始的,所以要返回k-1return arr[k - 1];}
};
比特位计数
- 通过循环写递归:具体实现如图
class Solution {
public:vector<int> countBits(int num) {// 因为从0开始,至少开的位数要比原来的大1vector<int> ans(num+1);ans[0] = 0;for (int i = 1;i<= num;i++){//就比ans[i & (i-1)]的1的个数多一个1ans[i] = ans[i & (i-1)] + 1;}return ans;}
};
// O(n)
Leetcode-860-柠檬水找零
- 一种简单的贪心算法。就是顾客给你20块的时候要保证先找10块回去
- 尽量给自己保留最多的5块就可以了
- 题目平淡无奇,我都会写
class Solution {
public:bool lemonadeChange(vector<int>& bills) {// 因为最大就20,20是没有办法找零的int cnt5 = 0, cnt10 = 0;for(int i = 0; i < bills.size(); i++) {switch(bills[i]) {case 5: cnt5++;break;case 10: {if(cnt5== 0) return false;cnt10++;cnt5--;// 不能忘记break,否则就会一直执行下去,把下面所有case里面的// 代码都执行完break;}case 20:{if(cnt10 && cnt5){cnt10--;cnt5--;}// 啥时候用else if一定要记住!!!!!!!!!!!else if(cnt5>=3 && (cnt10 == 0)){cnt5-=3;}else{return false;}break;}}}return true;}
};
Leetcode-859-亲密字符串
- 三段论:
- 首先判断size(),小size的不要
- 先找到不相同的第一个位置,再找到不相同的第二个位置
- 如果这两个位置的数是可以交换的,判断第二个不同之后的字母是不是一样的,一样就返回true
class Solution {
public:
// 注意abc和abc不是亲密字符串,aabc和aabc可以这么做
// 先找到不相同的第一个位置,再找到不相同的第二个位置
// 剩余的部分是相等的。注意这个复杂的条件判断bool has_repeate(string a) {// 开一个26位,然后去统计每一个出现了几次// 只有小写字母就任性int cnt[26] = {0};for (int i = 0; a[i]; i++) {cnt[a[i] - 'a'] += 1;if (cnt[a[i] - 'a'] == 2) return true;}return false;}bool buddyStrings(string a, string b) {// 不一样大就不是亲密字符串if (a.size() != b.size()) return false;// 相等的话,如果有相同的字符就可以if (a == b) return has_repeate(a);int i = 0, j;while (a[i] == b[i]) ++i;j = i + 1;// 判断两次while (j < a.size() && a[j] == b[j]) ++j;if (j == a.size()) return false;if (a[i] != b[j] || a[j] != b[i]) return false;j += 1;// 剩余部分while (j < a.size()) {if (a[j] != b[j]) return false;j += 1;}return true;}
};
Leetcode-621-任务调度器
- 这道题最终还是需要自己画个图好好理解一下。
class Solution {public:int leastInterval(vector<char>& tasks, int n) {// 先储存所有种类的任务int cnt[26] = {0};for (int i = 0; i < tasks.size(); i++) cnt[tasks[i] - 'A'] += 1;// (1)第一个是要排序的数组的起始地址。// (2)第二个是结束的地址(最后一位要排序的地址的下一位)// (3)第三个参数是排序的方法,可以是从大到小也可是从小到大,还可以不写第三个参数,此时默认的排序方法是从小到大排序。// 如果整个数组要排序,需要传入的是+整个数组的长度sort(cnt, cnt + 26);int m = 0;for (int i = 25; i >= 0 && cnt[i] == cnt[25]; i--, m++) ;// 如果能够填满所有的冷却时间的时候,没有冷却时间段的安排// 时间等于任务总数量// 如果没有填满就相当于当前矩形面积return max((int)tasks.size(), (cnt[25] - 1) * (n + 1) + m);}
};
Leetcode-969-煎饼排序
- 已经有点晕了,一定哟注意看题目。
- 每次将第N大的元素先翻转到第1位,再翻转到第N位,这样第N位就无需在后续进程中再进行处理,只需要考虑前N-1位即可。由于每个元素只需要2次翻转即可归位,因此所需的次数最多只需2N次,符合题目需求。
- 对于这种做法,可行的优化主要有两个。
一是可以去除值为“1”的翻转(值为“1”的翻转相当于未操作); - 二是可以跳过已经在正确位置上的元素。
class Solution {
public:
// 翻转之后还是记录在index中
// 从大到小排序把void reverse(vector<int> &arr, int n, vector<int> &ind) {// 前n位翻转for (int i = 0, j = n - 1; i < j; i++, j--) {swap(arr[i], arr[j]);ind[arr[i]] = i;ind[arr[j]] = j;}return ;}vector<int> pancakeSort(vector<int>& arr) {// +1可能是为了防止超出数组吧vector<int> ind(arr.size() + 1);vector<int> ret;// 记录当前元素的位置,相当于已经把元素从大到小排序好了for (int i = 0; i < arr.size(); i++) ind[arr[i]] = i;// 整理翻转方案for (int i = arr.size(); i >= 1; i--) {// 如果位置已经正确就不用排序了if(ind[i] == i-1) continue;// 得到彩蛋视频if (ind[i] + 1 != 1) {ret.push_back(ind[i] + 1);// 翻转,最终存储在ind中reverse(arr, ind[i] + 1, ind);}// 需要翻转梁侧if (i != 1) {ret.push_back(i);// 前i位置进行翻转,之后记录在ind中reverse(arr, i, ind);}}return ret;}
};
这篇关于超多注释助你手撕LeetCode(一)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!