yc_cy1999-CSDN博客

原创优先队列 priority_queue

LeetCode上的模板为：/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val

2022-01-06 10:41:31 591

原创链表数据结构模板

通常在算法题中，使用结构体来描述一个链表：struct ListNode{ int val; ListNode* next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode* next) : val(x), next(next) {}};或者是下面这种写起来比较复杂的形式：struct ListNode{ int val;

2022-01-05 09:39:13 283

原创 LeetCode 第 224 场周赛 5655. Largest Submatrix With Rearrangements【动态规划】⭐⭐⭐⭐⭐

文章目录题目描述知识点我的实现码前思考代码实现时空复杂度分析码后反思参考文档题目描述知识点动态规划我的实现码前思考这道题目的motivation跟LeetCode 85非常像，是它的一个简化版。在LeetCode 85中，我们利用分解问题的方法，提出最大子矩阵一定是以某一行为底的思想对问题进行分解（这是代码的第一层循环）。在LeetCode 85中，我们需要使用到单调栈，但是在这道题目中，由于列是可以移动的，所以我们直接“贪心”地对高度进行排序，这样就能够保证充分利用列可移动的条件得到.

2021-01-19 09:16:58 272

原创 721. Accounts Merge【并查集】⭐

文章目录题目描述知识点我的实现码前思考代码实现时空复杂度分析码后反思参考文档题目描述知识点并查集我的实现码前思考对于这种集合合并的问题，并查集最适合了。代码实现//感觉可以先使用排序进行同名分组，再在组里面进行小范围的并查集合并。//但是我直接使用并查集算了class Djset{ public: vector<int> parent; //记录节点的根 vector<int> rank; //记录根节点的深度（用.

2021-01-19 09:15:15 172

原创剑指 Offer 09. 用两个栈实现队列【栈+队列】

文章目录题目描述知识点我的实现码前思考代码实现时空复杂度分析码后反思参考文档题目描述知识点栈，队列，设计我的实现码前思考数据结构模拟题代码实现//使用两个栈来实现队列//入队列就是入栈，出队列就是转移栈，然后弹出最上面那个class CQueue {public: stack<int> pushSt; stack<int> popSt; CQueue() { } void appendTail.

2021-01-15 22:33:12 116

原创剑指 Offer 07. 重建二叉树【树+递归】

文章目录题目描述知识点我的实现结果码前思考代码实现码后反思题目描述知识点树，递归我的实现结果码前思考模板题代码实现/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {.

2021-01-08 21:24:51 61

原创剑指 Offer 06. 从尾到头打印链表【链表】

文章目录题目描述知识点我的实现结果码前思考代码实现码后反思题目描述知识点链表我的实现结果码前思考不想使用stack，直接使用数组；代码实现/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; *///时间复杂度和空间复杂度.

2021-01-07 19:34:32 60

原创剑指 Offer 05. 替换空格【STL操作+原地操作】

文章目录题目描述知识点结果实现码前思考代码实现码后反思题目描述知识点字符串string STL操作结果实现码前思考本来是想暴力求解的，但是记得C++ STL里面有现成的函数，所以还是决定用现成的函数来解题；代码实现class Solution {public: string replaceSpace(string s) { int pos = 0; int srclen = 1; int dstlen = 3; .

2021-01-06 19:32:07 115

原创剑指 Offer 04. 二维数组中的查找【数组 / BST】

文章目录题目描述知识点解法一——二分结果码前思考代码实现解法二——思维⭐⭐⭐⭐⭐(重要！！！)结果码前思考代码实现码后反思参考文档题目描述矩阵的每行从左到右是升序，每列从上到下也是升序，在矩阵中查找某个数。知识点二分、分支、思维解法一——二分结果码前思考看到有序，第一反应就是二分查找。最直接的做法，一行一行的进行二分查找即可。此外，结合有序的性质，一些情况可以提前结束：比如某一行的第一个元素大于了 target ，当前行和后边的所有行都不用考虑了，直接返回 false。.

2021-01-04 19:53:09 131

原创剑指 Offer 03. 数组中重复的数字【哈希 / 原地交换】

文章目录题目描述知识点结果实现码前思考代码实现码后反思参考解析题目描述知识点数组，哈希表结果实现码前思考我的第一感觉就是 O(N)O(N)O(N)的遍历数组+hash table ，事实证明我还是想的太简单了，面试的时候不可能就这么简单地问，还要综合考虑时间复杂度和空间复杂度的！代码实现哈希表版本：//应该是考察hash table的使用//数组大小可以放下class Solution {public: int findRepeatNumber(vector.

2021-01-03 19:25:42 147

原创 LeetCode 25. Reverse Nodes in k-Group【经典面试题+k个一组反转链表】⭐⭐⭐⭐⭐

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述知识点链表题我的实现码前思考使用的递归的思想，里面有分治的概念。每次反转一组，接下来的其他组就交给递归函数了。代码实现/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * };.

2020-09-09 17:09:56 88

原创 LeetCode 121. Best Time to Buy and Sell Stock【股票问题最简单版本】

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述知识点数组遍历我的实现码前思考由于时间的问题，所以是记录之前最低价，然后以当前天作为售出天进行解题。代码实现//只需要记录前面的最低价就好了//时间复杂度为O(n)class Solution {public: int maxProfit(vector<int>& prices) { if(prices.size()==0){ return 0; .

2020-09-07 15:40:41 75

原创 LeetCode 84. Largest Rectangle in Histogram【单调栈模板题】⭐⭐⭐⭐⭐

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述84. Largest Rectangle in Histogram知识点单调栈我的实现码前思考由于不小心看见了提示，知道了得用单调栈来解题。。。罪过啊思想就是一个一组连续的矩形，它们能构成的长方形一定是取决于最低点的，所以只需要将每个矩形当作最低点，然后求它们向左向右最大能够延申多长即可。代码实现//使用单调栈进行解题class Solution {public: int largestRectangleAr.

2020-09-06 15:54:14 131

原创 LeetCode 3. Longest Substring Without Repeating Characters【双指针/滑动窗口/动态规划】

文章目录题目描述知识点我的实现码前思考代码实现码后反思二刷代码题目描述知识点哈希表、双指针、滑动窗口我的实现码前思考首先想到的还是使用动态规划来解题，没有想到滑动窗口，惭愧。代码实现//使用滑动窗口进行解题class Solution {public: int lengthOfLongestSubstring(string s) { int size = s.size(); //进行特判 if(size == 0){ .

2020-09-01 16:05:53 111

原创 LeetCode 2. Add Two Numbers

文章目录题目描述知识点我的实现码前思考代码实现码后反思二刷代码题目描述知识点链表、数学我的实现码前思考大整数加法的模拟题代码实现//类似于大整数加法，只不过将数组变成了单链表//注意特判一些特殊情况/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL.

2020-09-01 15:32:30 76

原创 PAT A1131 Subway Map (30分)【DFS求最短路径】⭐⭐⭐⭐⭐

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述1131 Subway Map (30分)给一张map，求map中某点到某点的最短距离。知识点图的DFS我的实现码前思考我第一次写的时候用的是Dijkstra，结果超时了，所以一直都没改正。这一次写的时候参考了柳神的代码，使用了DFS的方式来求解问题。很奇怪的是，DFS这么暴力的方法，居然也可以做到不超时，实在是令人匪夷所思！！！代码实现#include <iostream>#include <ve.

2020-08-23 14:54:19 115

原创 Jungle Roads【最小生成树模板题】

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述就是裸的最小生成树知识点最小生成树我的实现码前思考考虑到多条边的情况，使用邻接表；考虑顶点数固定，使用prim~代码实现//对于这种图的顶点比较少的图，我们使用prim#include <iostream>#include <vector>#include <algorithm>using namespace std;const int maxn = 30;const int.

2020-08-22 17:47:42 91

原创【图的DFS遍历】PAT A1013 Battle Over Cities (25分)

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述知识点图的遍历我的实现码前思考就是求图中的连通块的数量代码实现//建议使用邻接表进行访问 #include <iostream>#include <vector>#include <algorithm>using namespace std;const int maxn = 1010;//共享数据结构的初始化bool vis[maxn];vector<int>.

2020-08-21 15:43:43 108

原创 ⭐⭐⭐【树的遍历】PAT A1053 Path of Equal Weight (30分)

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述求满足【根节点】到【叶子节点】的权值为S的所有路径，路径需要降序输出。知识点树的遍历我的实现码前思考需要使用一个vector来保存路径，你依然可以不建树。代码实现#include <iostream>#include <cstdio>#include <vector>#include <algorithm>using namespace std;int N,M,S;.

2020-08-19 16:38:16 78

原创【后序+中序重构】PAT A1020 Tree Traversals (25分)

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述知识点二叉树的遍历我的实现码前思考我第一次用的是建树的方式，后来看了柳神的代码，原来可以之间得到层序遍历结果，妙啊。利用的是完全二叉树的性质。代码实现#include <iostream>#include <queue>#include <map>#include <algorithm>using namespace std;const int maxn = 40;.

2020-08-18 22:40:50 69

原创 ⭐【高精度取余】大整数的因子

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述知识点高精度运算我的实现码前思考这里我使用了在网上考到的高精度求余数的模板，我觉得很好用的~代码实现//采用新学会的模板进行书写 #include <iostream>#include <algorithm>#include <vector>#include <cstring>using namespace std; const int maxn = 100;c.

2020-08-18 20:59:58 181

原创 ⭐【斐波拉契数列思想】递推数列

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述知识点记忆化递归我的实现码前思考emmm，之前还想求递推公式，结果发现这就是一道需要记忆化的斐波拉契数列啊~代码实现//类似于斐波拉契数列的解题方法，需要设置一个备忘录~ #include <iostream>#include <algorithm>using namespace std;typedef long long ll;const int maxn = 1e4+10;ll me.

2020-08-18 15:30:21 93

原创 ⭐⭐⭐⭐⭐【快速幂】矩阵幂

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述知识点快速幂的巧用我的实现码前思考这道题目用的是快速幂相关地思想，而不是简单的快速幂模板代码实现#include <iostream>#include <algorithm>using namespace std;const int maxn = 20;int a[maxn][maxn],b[maxn][maxn];int n,k;//C++数组传的是引用，需要谨慎修改 void.

2020-08-18 14:52:10 101

原创 ⭐⭐⭐⭐⭐【快速幂】root(N,k)

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述知识点快速幂（好难证明啊）我的实现码前思考不会写代码实现//经过证明，这是一道快速幂的题目 #include <iostream>#include <algorithm>using namespace std;typedef long long ll;ll binaryPow(ll x,ll y,ll k){ //printf("%lld\n",k); if(y==0){ retu.

2020-08-17 23:07:47 82

原创 ⭐【质因子分解】约数的个数

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述知识点质因子分解我的实现码前思考这里需要用到《算法笔记》上一个比较偏的知识点：代码实现//仍然是打印素数表的方法 #include <iostream>#include <algorithm>using namespace std;const int maxn = (int) sqrt(1e9+10);int n; int input[1010];int num=0;int pri.

2020-08-17 16:23:58 152

原创 ⭐⭐⭐⭐⭐【进制转换+高精度四则运算】10进制vs2进制

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述知识点我的实现码前思考需要实现很多繁琐的步骤；高精度的加、乘、除都需要；逆转过来记得去处前导0；代码实现//需要使用高精度加法，乘法和除法 #include <iostream>#include <cstring>#include <algorithm>using namespace std;const int maxn = 1e4+10;struct bign{ i.

2020-08-16 21:25:19 342

原创【进制转换+高精度除法】进制转换

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述知识点我的实现码前思考代码实现//高精度除法运算 #include <iostream>#include <algorithm>#include <cstring>using namespace std;struct bign{ int d[50]; int len; bign(){ fill(d,d+50,0); len=0; }}; bign chang.

2020-08-16 20:11:45 224

原创【十进制转换成其他进制】PAT A1019 General Palindromic Number (20分)

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述十进制转换成其他进制知识点进制转换我的实现码前思考注意十进制为0的情况！！！代码实现//进制转换经典模板题 #include <iostream>#include <algorithm>using namespace std;const int maxn = 100;int n,b;int res[maxn];int num=0; int main(){ scanf("%d .

2020-08-16 17:19:55 89

原创【进制转换】PAT A1058 A+B in Hogwarts (20分)

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述知识点进制转换我的实现码前思考我二刷使用的就是比较暴力的加法代码实现//模拟题，从高位到低位进位即可 #include <iostream>#include <algorithm>using namespace std;int a[3];int b[3];int c[3]; int main(){ scanf("%d.%d.%d %d.%d.%d",&a[0],&a.

2020-08-16 17:03:02 88

原创 PAT A1071 Speech Patterns (25分)

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述知识点哈希我的实现码前思考按照题目的定义，并不是仅仅以空格为分隔符分割单词的，其他只要不是数字或者字母的字符都可以作为分割符！！！所以我们选择一个个字符的读取，只要读到一个非字母或者数字时，就代表生成了一个单词（前提是这个单词是非空的！）代码实现#include<stdio.h>#include<map>#include<string>#include<iostream&gt.

2020-08-12 21:50:17 117

原创【map】PAT A1054 The Dominant Color (20分)

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述知识点STL我的实现码前思考题目中说了一定存在，那么每次判断就好了，水题！代码实现#include <iostream>#include <map>using namespace std;int main() { int m, n; scanf("%d %d", &m, &n); map<int, int> arr; int half .

2020-08-12 20:43:42 93

原创 ⭐【哈希大模拟+输入输出技巧】PAT A1022 Digital Library (30分)

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述1022 Digital Library (30分)知识点哈希我的实现码前思考这道题目就是暴力哈希的玩法，就是在输入和输出上要多加注意代码实现#include<stdio.h>#include<map>#include<vector>#include<string>#include<algorithm>#include<iostream>us.

2020-08-12 20:32:13 95 1

原创【unordered_set】PAT A1063 Set Similarity (25分)

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述知识点STL中的无序集合unordered_set我的实现码前思考这里我使用的是暴力遍历两个set到一个set里面，然后比较前后值的个数的变化，得到公共的部分。需要注意的是，千万不能两层for循环遍历，那样绝对会超时！代码实现//交集除以并集再乘100% //数组下标从1开始 #include <iostream>#include <unordered_set> #include <a.

2020-08-12 16:09:16 74

原创【手工哈希】PAT A1047 Student List for Course (25分)

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述知识点手工哈希我的实现码前思考由于前面做了一道Course List for Student，所以这里做的还算顺利。只是关于如何将数字重新变成字符数组呢？我们可以想象，如果每次都是使用函数，那么很麻烦，也很耗时。因此我们使用一个id2name的数组来保存id到name的映射，这样就能节省不少空间和时间了。我们的courseList里面只要存储id就好，到时候输出name时，直接映射就可了。代码实现//使用一个数组存放数字到.

2020-08-12 15:39:28 102

原创 ⭐⭐⭐⭐⭐【手动哈希】PAT A1039 Course List for Student (25分)

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述知识点手动哈希我的实现码前思考前几次提交使用的是map+string，结果都超时了。后来选择了手动hash，将string转换成int，然后使用vector数组，就过题了。主要还是map的性能不太行，加上string的cin和cout开销太大了。代码实现//采用map+vetctor #include <iostream>#include <unordered_map>#include &lt.

2020-08-12 15:11:24 149

原创 PAT A1026 Table Tennis (30分)

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述1026 Table Tennis (30分)又臭又长知识点大模拟！我的实现码前思考直接跳过这道题，柳神说了：pat现在不考这种题了！代码实现#include <iostream>#include <vector>#include <algorithm>#include <cmath>using namespace std;struct person { i.

2020-08-11 17:29:25 474

原创 PAT A1009 Product of Polynomials (25分)

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述知识点模拟题我的实现码前思考就是模拟题了代码实现//使用后结构体来办事 #include <iostream>#include <vector>#include <algorithm>using namespace std;const int maxn = 2e3+10;struct node{ int exp; double coef; node(){} node(i.

2020-08-11 16:16:37 109

原创 ⭐⭐⭐⭐⭐【区间DP】LeetCode 730. Count Different Palindromic Subsequences

文章目录题目描述知识点思路解析代码实现码后反思参考源码配合视频题目描述知识点思路解析首先要理解下面这张PPT的含义（这种情况还是非常见的）：综上，首尾相同有三种情况，首位不同只有一种情况。这种overlapping的情况，跟我们在讲括号匹配时有点相似。代码实现class Solution {public: int countPalindromicSubsequences(string S) { long long mod = 1000000007; .

2020-08-10 22:32:27 99

原创【字符串函数】PAT A1077 Kuchiguse (20分)

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述找所有字符串的共同后缀知识点STL字符串string的使用我的实现码前思考就一直比对就好代码实现#include <iostream>#include <string>using namespace std;const int maxn = 1e2+10;string ins[maxn];int n;int main(){ scanf("%d\n",&n); int len.

2020-08-10 16:19:49 96

原创【字符串水题】PAT A1035 Password (20分)

文章目录题目描述知识点我的实现码前思考代码实现码后反思题目描述知识点字符串处理我的实现码前思考水题代码实现#include <iostream>#include <string>#include <algorithm>#include <vector>#include <unordered_map>using namespace std;struct node{ string account; string .

2020-08-09 21:38:24 88

空空如也

空空如也