超多注释助你手撕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

相关文章

哈希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

带头结点。 /*** 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

带头结点。 /*** 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编码验证

题目: 题解: 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中文乱码问题,注释,终端,调试乱码一劳永逸版

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

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

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

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

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

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 解题思路 这道题的思路是使用动态规划

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析