- 博客(477)
- 收藏
- 关注
RSS订阅
原创 要是我再犯这种憨憨错误就.../(ㄒoㄒ)/~~
1. 乘法取模的时候，记得先取模再相乘，不然很可能炸。eg: HDU6961数据范围达到 1e18，而答案为
2021-07-26 11:45:46
110
原创 华为杯数学建模（准备）＜2018 - 2022＞
数据拟合、参数估计、插值等数据处理算法；线性规划、整数规划、多元规划、二次规划等规划类算法；动态规划、回溯搜索、分治算法、分支定界等计算机算法；最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法；（线性回归、逻辑回归、决策树、支持向量机、聚类、神经网络、遗传算法、粒子群算法、蚁群算法、模拟退火算法）1. 时间序列算法、拟合插值算法、基础的图论算法。3. 整数规划、线性规划、多元规划、二次规划等。6. 聚类算法、分类算法、预测算法等。5. 灰色预测、灰色综合评价。（评价类、预测类、优化类）
2023-09-02 21:26:04
347
原创 PAT甲级 - 1019 General Palindromic Number(b进制的回文数判断 | 测试点2、4)
十进制的n转换成b进制的数时，每次取余时得到的数可能大于9，因此用string存结果时会无法通过2、4两个测试点。：给出十进制的数字n，判断其在b进制下是否依旧是一个回文数字。
2022-08-24 15:11:31
250
1
原创 LeetCode 566. 重塑矩阵 (m*n数组变成r*c数组&展开填充)
思路： 一维展开：理解题意即将原数组一维展开后依次填充进r*c的数组，时间复杂度O(m*n)。
2022-07-12 16:12:35
133
原创 LeetCode 121. 买卖股票的最佳时机(单调栈 / 遍历+最低价格买进)
思路： 1.暴力枚举：两重循环枚举两点，得到前后最大差值，但是时间复杂度，此题的数据范围显然会超时。 2. 单调栈：本题目的即求后面与当前值的最大差值，可以考虑单调队列方法得到以当前i位置往后的单调栈，在以当前prices[i]和队投元素取差得到临时差值再不断取max即可，由于此题在不断的取单调栈，因此最坏的情况下是最后只剩下最后一个数，那么其最坏复杂度为O(2n)，忽略其常数情况下便是O(n)。...
2022-07-12 12:01:27
179
原创 LeetCode 350. 两个数组的交集 II (哈希计数 / 排序+双指针)
思路： 1. 哈希表：利用哈希表对每个数组中的元素进行统计，并取最小个数即可。2. 哈希表优化：上面的做法是进行了两次数量统计最后还要挨个push_back入答案，最坏的情况下的时间复杂度可能达到O(n+2m)或者O(2n+m)。而实际上我们可以只进行一次数量统计，在对第二个数组进行遍历时即可边遍历边push_back，时间复杂度为O(n+m)， 空间复杂度O(min(n, m))。3. 排序+双指针：如若两个数组都为有序的，那么就可以直接利用双指针进行交集的获取。因此我们可以先对数组进行排序，
2022-07-12 10:41:35
156
原创 LeetCode 88. 合并两个有序数组 (类似归并 / 填充sort)
思路：1. 归并：由于给出的两个数组都是有序的，而需要的结果也是有序的，那么每次从两个数组取最后的一个元素对比先填充大数即可，时间复杂度O(n+m)。2. sort：nums1后面n个空间以及存在了，那么我们可以直接将nums2中的数填充进后n个位置，然后再对nums1进行sort排序一下即可，sort的时间复杂度为，故此时间复杂度为。...
2022-07-12 09:53:46
125
原创 LeetCode 1. 两数之和（target，暴力/哈希表）
思路： 1. 直接暴力两重循环，O()枚举查询即可。2. 利用哈希表，O(1)直接查询 target-num[i]即可，整体时间复杂度O(n)。
2022-07-11 11:27:57
100
原创 LeetCode53. 最大子数组和(暴力、dp、贪心、分治)
思路： 比较经典的一个题，求最大连续区间的和。1. 暴力：直接利用两重循环枚举区间的左右边界点并不断取max即可，时间复杂度O().2. dp：状态转移表达式——dp[i] = max(dp[i-1]+num[1], num[i])，dp[i]表示以num[i]为结尾的最大区间和，每次的当前节点结尾最大值肯定是上一节点最大值加上当前节点与否，时间复杂度O(n)。3. 贪心：从开头就一直选择节点，知道当前的sum...
2022-07-11 10:47:50
383
原创 PAT甲级 1016 Phone Bills(时间差)
Link题意：远程电话的收费是按照每分钟来计费的，现在告诉你一天24小时中每分钟的收费标准，以及n条通话记录，试求出每个人该月的消费账单。只有开始记录没有结束记录的通话不计费，反之亦然。保证所有消费记录在同一个月，且至少含有一条满足计费的账单记录。输出是需要输出用户姓名，月份，每一条记录的开始结束时间于计费，总计费。按照用户名升序输出账单。思路：常规的一个时间差计算题，但是该题细节较多，也有许多坑点。先按照用户名升序，再按照时间升序来排序。再依次处理每次完整的通话。刚开始是考虑前缀和直接获取时间段对应的计费
2022-06-03 22:27:29
182
原创 PAT甲级 - 1015 Reversible Primes (进制转换&素数判断)
Link题意：判断一个数N是否是D进制内的翻转素数，即其在D进制内翻转后依旧是素数。思路：思路很简单，但是题意有点容易被误解，即当前N为十进制数，首先N必须是质数；再者其转换成D进制数后翻转，再变成十进制数后依旧得是素数才满足。代码实现：...
2022-06-03 16:26:36
237
原创 PAT甲级 - 1014 Waiting in Line (银行排队问题 | queue+模拟)
Link题意：银行里由N个窗口，每个窗口前可容纳M个人等待；N*M之后的人需要在黄线以外等待寻找最短且序号最小的窗口进入等待；现告诉你K个人办理业务需要的时间time_cost，试问其中Q个人的离开时间为多少。已知银行8：00开始接待客户，17：00停止接待。思路：显而可见，前N*M个人分别按照1~N，1~N……的顺序进入窗口，之后就是黄线内的N*M个人离开一个，黄线外的客户进入该窗口。设置N个queue模拟N个窗口，定义统一是时间线timeLine，每次寻找N个窗口头部耗时最短的用时minn_cost，将
2022-06-03 14:08:56
207
原创 PAT甲级 - 1013 Battle Over Cities(删点判连通块数量)
Link题意：给你一张地图，n个城市、m条路，现在问你毁掉某个城市相连的所有路后，最少还需要修建多少条路才能使得剩下的所有城市联通。一个k组测试询问。思路：相当于删除联通块中某个点剩下联通块个数-1的问题。思路1：并查集，思路二：bfs遍历。需要注意的是上限1e3个点，那么最多有1e6个边，容量不够大最后一个测试点无法通过。并查集代码：#include<bits/stdc++.h>#define int long long#define endl '\n'using na
2022-06-03 13:54:26
300
原创 PAT甲级 - 1012 The Best Rank(坑点)
Link题意：大概题意就是每个学生都有自己的序号id，以及C语言场景c，数学成绩m，英语成绩e，以及平均成绩a。题目会输出n个学生的id以及三门主科的成绩，气候跟寻m次询问，问某id的学生最佳成绩排名及科目名称。思路：思路其实很简单，分四个数组存放每科所有学生的成绩再排个序即可。但需要注意两个坑点：1.在选取学生最高排名时必须按照a，c，m，e的优先级取最高排名科目(即每个成绩都排名第三，但必须输出 3 A)。2. 相同分数排名相同，但下一分数不会递补(即现在有 90、90、89的三个成绩，则气排名
2022-05-24 17:07:51
304
原创 PAT甲级 - 1010 Radix(思维+二分)
Link题意：大概意思就是，tag==1，则N1为radix进制的数；tag==2，则N2为radix进制的数。试问另一个数为多少进制的数才能使得N1==N2，无解输出"Impossible"。思路：基本思路很简单，直接枚举另外一个数的进制即可，期间在进行进制的转换时需要注意许多细节。但如果直接枚举的话将有个测试点(1分)无法通过，不难看出其实进制的取值我们就可以通过二分来查询，其二分的下限即是另一个数的最大位数值maxx+1，上限即位radix进制数的十进制数值+1。（如果误将Impossible
2022-05-24 17:06:32
322
原创 PAT甲级 - 1007 Maximum Subsequence Sum
Link题意：没什么毛病，就是求一个最大子序列和的问题。思路： 两种种思路吧——暴力、dp。暴力就直接利用前缀和求个最大差值，不过还是很意外1e4的这个复杂度按理说是会超时的，但这个题可能数据比较水竟然400ms的限制也能过。暴力代码：#include<bits/stdc++.h>#define int long long#define endl '\n'using namespace std;const int N = 1e5+10;int n, a[N], pr
2022-05-23 21:40:18
155
原创 PAT甲级 - 1002 A+B for Polynomials
Link题意： 多项式加法，分别输入两行多项式，每一行 k 对<系数 指数>的格式，要求输出相加后的多项式（不好含指数为0的）。思路：将同系数的指数相加筛选非零项再对系数进行降序输出即可。AC代码：#include<bits/stdc++.h>#define int long long#define endl '\n'using namespace std;const int N = 1e5+10;int k, a;double b;vec.
2022-05-21 17:05:09
136
原创 PAT甲级 - 1001 A+B Format
Link题意：输出A+B的固定格式结果（每三位数含一共逗号）。思路：直接利用整型变量相加得到的结果再to_string()一下，再每三个位置插入一个逗号即可。AC代码：#include<bits/stdc++.h>using namespace std;const int N = 1e5+10;int a, b;signed main(){ cin >> a >> b; int c = a+b, cnt = 0;.
2022-05-21 16:54:57
113
原创 LeetCode - 9 - (整数反转、字符串转整数atoi、二进制距离、整数转罗马数字、最接近的三数之和)
class Solution {public: int reverse(int x) { if(x>INT_MAX||x<-INT_MAX) return 0; // 可能输入的数就超出范围 if(x>-10&&x<10) return x; // 个位数不用反转直接输出 string s; int flag = 0; if(x<0){ // 负数标记一下...
2022-04-24 13:45:37
235
原创 L2-006 树的遍历(中后序确定二叉树&层序遍历)
代码实现：#include<bits/stdc++.h>#define int long long#define endl '\n'using namespace std;const int N = 1e5+10;int n, cnt;int bk[N], md[N];map<int, int> pos;struct node{ int lson, rson, val;}tree[N];int build(int la, int lb, ...
2022-04-22 23:25:18
412
原创 L2-005 集合相似度(set判重)
思路：比较水的一个题，但是想通过所有测试点还需要考虑下最大复杂度的情况。代码实现：#include<bits/stdc++.h>#define int long long#define endl '\n'using namespace std;const int N = 100;int n, m, x, k;set<int> s[N], tmp;signed main(){ cin >> n; for(int i =...
2022-04-21 17:27:06
203
原创 L2-004 这是二叉搜索树吗？(先序输入&判断搜索二叉树&后序输出)
思路：由于时具有单调性的先序遍历，当出现单调性的结束位置便是左子树 -> 右子树(或右子树 -> 左子树)的转换。参考博客代码实现：#include<bits/stdc++.h>#define int long long#define endl '\n'using namespace std;const int N = 1e5+10;int n, a[N], mirror;vector<int> ans;void dfs(int l...
2022-04-21 17:01:25
948
原创 L2-001 紧急救援 (最短路Dijkstra的扩展 - 最短路径数&路径最大权值)
思路： 菜蒟只会求最短路，不会扩展/(ㄒoㄒ)/~~。参考博客代码实现：#include<bits/stdc++.h>#define int long long#define endl '\n'using namespace std;const int N = 510;int n, m, s, d;int ans, u, v, w;int g[N][N], c[N]; //邻接矩阵存边, c[i]表示第i个城市的救援队数量int dis[N], path[...
2022-04-21 12:14:07
176
原创 L2-002 链表去重(测试点1的坑)
思路： 通过map映射先将原链表处理出来，再通过判重将其分成两部分存储输出。注意测试点1有个坑点（原链表不是一条完成的链表，数据如下：）(测试点1)输入：00001 300001 1 0000200002 2 -100003 3 00004（测试点1）输出：00001 1 0000200002 2 -1代码实现：#include<bits/stdc++.h>#define int long long#define endl '...
2022-04-21 12:13:16
1464
1
原创 LeetCode - 8 - (三数之和、Z字形变换、两数之和＜链表＞、盛最多水的容器、电话号码的字母组合)
class Solution {public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); set<vector<int>> res; //去重 int n = nums.size(); for(int i = 0; i < n; i +...
2022-04-08 14:13:40
132
原创 LeetCode - 7 - (二叉树的最近公共祖先、轮转数组、二叉树的直径、下一个排列、组合总和)
class Solution {public: TreeNode* ans; bool dfs(TreeNode* root, TreeNode* p, TreeNode* q){ if(root==NULL) return 0; bool lson = dfs(root->left, p, q); bool rson = dfs(root->right, p, q); if((lson&&am...
2022-04-08 13:24:41
113
原创 LeetCode - 6 - (字符串相乘、下一个更大元素＜ⅠⅡⅢ＞、k个一组翻转链表)
class Solution {public: string multiply(string num1, string num2) { if(num1=="0"||num2=="0") return "0"; int n = num1.size(), m = num2.size(); vector<int> tmp(n+m); for(int i = n-1; ~i; i--){ //相乘计算 ...
2022-04-08 10:32:16
1185
原创 LeetCode - 5 - (重复的子字符串＜kmp＞、最长回文子串、转置矩阵、二叉树的(左右)视图)
朴素做法：O()class Solution {public: bool repeatedSubstringPattern(string s) { int n = s.size(); for(int i = 1; i <= n/2; i ++){ if(n%i==0){ bool flag = 1; for(int j = i; j < n; j ++){...
2022-04-04 13:19:03
158
原创 LeetCode - 4 - (接雨水、无重复字符的最长子串、分发糖果、二叉树的＜前中后层＞序遍历)
class Solution {public: int trap(vector<int>& height) { int len = height.size(); if(!len) return 0; vector<int> lmax(len); lmax[0] = height[0]; //记录当前位置左侧最高值 for(int i = 1; i < len; i ++)...
2022-03-29 17:11:35
600
原创 LeetCode -3 - (字符串相加、最大连续1的个数＜ⅠⅢ＞、考试的最大困扰度、删除链表的倒数第N个结点)
class Solution {public: string addStrings(string num1, string num2) { string ans; if(num1.size()>num2.size()) swap(num1, num2); reverse(num1.begin(), num1.end()); reverse(num2.begin(), num2.end()); int tmp...
2022-03-29 15:17:29
344
原创 LeetCode - 2 - (括号生成、最长回文串、环形链表、反转链表、两两交换链表中的节点)
class Solution {public: ListNode* swapPairs(ListNode* head) { ListNode* dummy = new ListNode(0); //开一个动态的链表 dummy->next = head; //表头指向head ListNode* tmp = dummy; while(tmp->next&&tmp->next->next){...
2022-03-29 03:22:36
1007
2
原创 LeetCode - 1 - (树的子结构、组合、螺旋矩阵、全排列＜ⅠⅢ＞)
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: bool check(TreeNode*...
2022-03-28 21:24:05
960
原创 L1-071 前世档案 (20 分) (类似二分)
传送门题目描述：思路：照我以前可能就会傻傻的去想怎么实现二叉树…也许是现在思维成熟了点，便能看出其实这就是类似于二分原理的水题。首先能够知道结论的总数，每次"y"和"n"的选择就像二分一样对半砍的操作，所以简单模拟下就行啦！AC代码：#include<bits/stdc++.h>#define int long long#define endl '\n'using namespace std;const int N = 1e5+10;int n, m,...
2022-03-23 09:11:29
1647
3
原创 L1-064 估值一亿的AI核心代码 (20 分) 格式错误
传送门题意： 思路：· 个人思路是先处理原文串a所有空格和大小写变成串b· 再处理串b中的各种替换问题，由于在处理单词替换时虽然先考虑的“I”的替换，但是之后再不会变量到该单词，所以并未出现大家所说的测试点2(can you)的卡顿。·但是特别注意这个题的另外一个坑点，本人就是一直测试点1和测试点4格式错误，后面通过这篇博客的详细讲解才通过了本题。·测试点1：结尾没有标点符号而有多个空格·测试点4：三个空格，要求输出"AI: "即可。AC代码：#inc...
2022-03-19 16:50:46
460
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人