超多注释助你手撕LeetCode（一）

2023-10-27 14:48
文章标签 leetcode 注释 超多

本文主要是介绍超多注释助你手撕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（一）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/286369。

相关文章

Rust中的注释使用解读

Rust中的注释使用解读

《Rust中的注释使用解读》本文介绍了Rust中的行注释、块注释和文档注释的使用方法,通过示例展示了如何在实际代码中应用这些注释,以提高代码的可读性和可维护性... 目录Rust 中的注释使用指南1. 行注释示例：行注释2. 块注释示例：块注释3. 文档注释示例：文档注释4. 综合示例总结Rust 中的注释
阅读更多...
哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
leetcode-24Swap Nodes in Pairs

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L
阅读更多...
leetcode-23Merge k Sorted Lists

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...
vscode中文乱码问题，注释，终端，调试乱码一劳永逸版

vscode中文乱码问题，注释，终端，调试乱码一劳永逸版

忘记咋回事突然出现了乱码问题，很多方法都试了，注释乱码解决了，终端又乱码，调试窗口也乱码，最后经过本人不懈努力，终于全部解决了，现在分享给大家我的方法。 乱码的原因是各个地方用的编码格式不统一，所以把他们设成统一的utf8. 1.电脑的编码格式 开始-设置-时间和语言-语言和区域 管理语言设置-更改系统区域设置-勾选Bata版：使用utf8-确定-然后按指示重启 2.vscode
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
C语言 | Leetcode C语言题解之第393题UTF-8编码验证

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目： 题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
阅读更多...
【JavaScript】LeetCode：16-20

【JavaScript】LeetCode：16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i，右指针j，从头遍历数组，若j指针指向的元素不在set中，则加入该元素，否则更新结果res，删除集合中i指针指向的元素，进入下一轮循环。 /*** @param
阅读更多...
LeetCode：64. 最大正方形 动态规划 时间复杂度O(nm)

LeetCode：64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵，找出只包含 1 的最大正方形，并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2