江南路漫-CSDN博客

两种算法都是基于贪心的方法。Prim算法：适用于稠密图。时间复杂度为O(V^2)。(V为顶点数）与Dijkstra算法相似，每次选择离离原点最近的点，加入到现有的生成树中。Kruskal算法：适用于稀疏图。时间复杂度为O(E*logE)。（E为边数）将边按照长度由小到大进行排序（边的结构体内要存入连接的两个顶点的信息），每次选择最短的一条边出来，在确认加入新边不会形成环后，将其加入生成树中。如何判断是否会形成环的方法是，建立一个关于边的并查集，加入新边时判断边连接的两个端点是否在同一个集合中。若

2022-05-01 00:24:04 362

原创最短路径SPFA和Bellman-Ford算法

参考模板：#include<bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3ftypedef long long ll;struct node { int v, dis; node(int v, int dis) { this->v = v, this->dis = dis; }};vector<node> adj[1005];int n, d[1005], num[1005];

2022-04-30 19:20:17 400

原创 PAT Family Property DFS+哈希

题目链接思路：本题将每个人作为一个单独的结点，若两个人之间是家人关系，则建立边关系。通过哈希法建立人名与编号，编号与人名之间的映射。最后统计每个家庭的人数时，用DFS遍历即可。对于本题我犯过两个错误，仅供读者参考：1.建立边关系的时候，应当建立双向边，而不是单向边。2.出现的人数比较大，数组开大一点。参考代码：#include<bits/stdc++.h>#include<unordered_map>using namespace std;#define INF

2022-04-27 09:14:42 190

原创 AcWing 构造数组区间合并

思路：这道题第一眼来看以为是动态规划类型的题目，然而尝试了用dp的方法做，然而超时了，过了差不多一半的测试店，显示的是超时。那么应该来说动态规划是可以做的，但数据卡的比较严。在看其他同学的评论后，使用KMP算法也会使得部分测试点超时。听完讲解后，发现大佬是通过区间合并的方法实现的。由题意可知，若a[i]等于a[j]，则b[i]和b[j]也必须是相同的，而数组b是非递减的，此时数组b中第i到j项的元素必须是相同的，才能符合题目要求。所以我们要统计这样的区间的个数。运用区间合并的方法，得出最后的区间数为.

2022-04-26 17:49:09 184

原创 AcWing 删减栈思想

思路：这道题要是不卡时间复杂度，是道大水题，然而字符串的长度到了6次方，若使用string中的erase函数，看似时间复杂度不高，其实，每次删除子字符串后，后边的字符串需要移动到前面来，最坏的情况下，时间复杂度能达到O（n*n)。那么我可以想办法让字符串不要发生移动。可以一个个地将字符串加入到新字符串中，加一个字符就判断一次，判断是否满足删除条件。参考代码：#include<bits/stdc++.h>using namespace std;#define INF 0x3f3f3f..

2022-04-22 23:24:14 245

原创 Is It a Complete AVL Tree AVL树

思路：考察的点是建立AVL树以及如何判断是否为满二叉树。建立AVL树需要搞清楚LL、LR、RR、RL四种情况如何左旋和右旋，如下：类型BF条件操作LLBF(root)=2,BF(root->lchild)=1root右旋LRBF(root)=2,BF(root->lchild)=-1先root->lchild左旋，再root右旋RRBF(root)=-2,BF(root->rchild)=-1root左旋RLBF(roo..

2022-04-22 20:28:10 310

原创蓝桥杯迷宫与陷阱 BFS

参考代码：#include<bits/stdc++.h> #define INF 0x3f3f3f3fusing namespace std;typedef long long ll;struct node{ int x, y, step, ticket; node(int a, int b, ll c, int d) { x=a, y=b, step=c, ticket=d; }};queue<node> q;bool vis[1005][1005];

2022-04-07 22:52:18 334

原创蓝桥杯人物相关性分析二分

思路：这道题是常规的模拟题，根据题意写出相关代码即可。模拟题一般容易在边界条件上出错，建议自己设计几个样例测试一下。这题纯暴力的方法不能通过所有的测试点，对于最后的查询，应该使用二分查找，这样算法的整体复杂度是O(nlogn)参考代码：#include<bits/stdc++.h> #define INF 0x3f3f3f3fusing namespace std;typedef long long ll;string s;int k, len;vector<int&gt

2022-04-07 14:55:25 403

原创蓝桥杯递增三元组二分

参考代码：#include<bits/stdc++.h> #define INF 0x3f3f3f3fusing namespace std;typedef long long ll;ll cnt = 0; int a[100005], b[100005], c[100005];int main(){ ios::sync_with_stdio(false); int n; cin >> n; for(int i = 0; i < n; i++)

2022-04-07 00:50:25 141

原创蓝桥杯子串分值递推

思路：本题有点难想，采用贡献和的思想。首先需要定义一个last数组，用于记录当前遍历的字母s[i]上一次出现在字符串s中的位置。接着遍历数组，计算每一个字母的贡献值。参考代码：#include<bits/stdc++.h> #define INF 0x3f3f3f3fusing namespace std;typedef long long ll;int main(){ ios::sync_with_stdio(false); string s; cin >&gt

2022-04-06 00:27:23 132

原创 Leetcode 35.搜索插入位置二分

题目链接思路：是常规的二分法，需要注意的是，当数字不存在的时候，需要返回插入该数进序列并保持有序的位置，即返回的是最后一个小于查找数target的位置。二分查找最后结束的位置，即退出循环时的左边界或者右边界+1。参考代码：class Solution {public: int searchInsert(vector<int>& nums, int target) { int left = 0, right = nums.size()-1, mid;

2022-04-04 00:22:14 307

原创 Leetcode 34.在排序数组中查找元素的第一个和最后一个位置二分

第一种方法，比较简单，左边界查找使用C++的upper_bound()函数，右边界从左边界开始往下查找。参考代码：class Solution {public: vector<int> searchRange(vector<int>& nums, int target) { vector<int> res; int len = nums.size(); int left = lower_bound(nu

2022-04-03 14:25:44 480

原创 Leetcode 1094.拼车差分

思路：这道题有很多种解法，刚好最近在学差分，就用差分做吧。首先是初始没有乘客，差分diff数组各项为0，不用求差构造差分数组了。接着是每一次乘车方案，起点站需要加上乘客数，终点站需要减去乘客数。注意：乘车区间是前闭后开的，因为终点站乘客下车了以后还可以继续拉客。（这里坑了我一会儿）参考代码：class Solution {public: bool carPooling(vector<vector<int>>& trips, int capacity) {

2022-04-03 00:32:31 694

原创 Leetcode 1109.航班预定统计差分

思路：这道题假如要用暴力的方法，是过不去的。要使用差分的思想，创建一个差数组。因为本道题初始的座位数是0，直接建立一个全0数组即可。参考代码：class Solution {public: vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) { vector<int> v; for(int i = 0;i <= n

2022-04-02 21:11:42 526

原创蓝桥杯作物杂交 DFS搜索

参考代码：#include<bits/stdc++.h> #define INF 0x3f3f3f3fusing namespace std;typedef long long ll;int cost[2005]; //记录每个作物杂交所需要的时间 int dis[2005]; //记录每个作物到t点的最短时间 struct node{ //结构体存储每种杂交方案 int a, b, time;};vector<node> solution[2005];

2022-04-01 20:02:11 374

原创蓝桥杯 k倍区间前缀和

参考代码：#include<bits/stdc++.h> using namespace std;typedef long long ll;int array[100005], t[100005]; //array记录每个元素值，t记录取余k，各余数对应前缀和的数量 int main(){ ios::sync_with_stdio(false); ll sum = 0, cnt = 0; int n, k; cin >> n >> k; fo.

2022-03-31 22:29:59 258 2

原创蓝桥杯 123 二分+打表

参考代码：#include<bits/stdc++.h> using namespace std;typedef long long ll;ll temp[1500000], sum[1500000]; //temp数组记录序号和，sum数组记录前缀和 ll cal(ll n) //计算自然数求和 { return (n+1)*n/2;}int main(){ ios::sync_with_stdio(false); ll index = 1; ll end.

2022-03-31 20:00:11 557

原创蓝桥杯子串分值

参考代码：#include<bits/stdc++.h> using namespace std;int main(){ ios::sync_with_stdio(false); string str; cin >> str; int sum = 0; int left, right; char s; int len = str.size(); for(int i = 0; i < len; i++) //依次循环每一个字符，将其贡献值相加 .

2022-03-30 00:44:07 432

原创蓝桥杯日志统计尺取

参考代码：#include<bits/stdc++.h> using namespace std;typedef long long ll;vector<int> v[100005]; //定义容器用于存放第i篇帖子被点赞的时间 int main(){ ios::sync_with_stdio(false); int n, d, k; cin >> n >> d >> k; int ts, id; for(int i =

2022-03-28 19:58:12 585

原创蓝桥杯迷宫

参考代码：#include<bits/stdc++.h>using namespace std;typedef long long ll;int e[55][55], vis[55][55]; //e矩阵表示障碍物信息，vis矩阵表示点是否被访问过 int m = 30, n = 50;struct node{ //定义结构体，用于存放点的信息 int x; int y; string path; //用来表示从起点到该点的最短路径 };queue<node&

2022-03-26 00:59:49 71

原创蓝桥杯分巧克力二分

#include<bits/stdc++.h>using namespace std;typedef long long ll;ll n, k;vector<ll> width, height;bool check(ll length) //判断边长为length的正方形都否满足需求 { ll sum = 0; //记录能切成的最大方块数 for(int i = 0; i < n; i++) { sum += (width[i] / length.

2022-03-25 20:43:05 426

原创蓝桥杯递增序列

思路：这道题一开始想复杂了，其实这么小的数据量直接暴力求解即可。参考代码：#include<bits/stdc++.h>using namespace std;typedef long long ll;int m = 30, n = 50; bool checkL(int x, int y) //判断坐标是否超出边界 { if(x >= 0 && y >= 0 && x < m && y < n) .

2022-03-23 22:27:24 970 2

原创蓝桥杯数字三角形贪心+动态规划

参考代码：#include<bits/stdc++.h>using namespace std;typedef long long ll;int data[105][105];int main(){ ios::sync_with_stdio(false); int n; cin >> n; for(int i = 1; i <= n; i++) { for(int j = 1; j <= i; j++) { cin >&gt..

2022-03-23 17:39:59 1422

原创蓝桥杯左baby右兄弟

试题：思路：“左孩子右兄弟”是常见的多叉树转化成二叉树的方法。具体的实现方式是，从第二层最右边的结点开始，将将自己的孩子结点放到左边，左边一位的兄弟放到左边的结点上。对于是多支的孩子先递归转成一支树。本题寻求最大深度，依次递归即可。参考代码：#include<bits/stdc++.h>using namespace std;typedef long long ll;vector<int> v[100005];vector<int> depth;i

2022-03-20 17:24:14 1290

原创蓝桥杯砝码称重

试题：思路：经典的0-1背包问题：动态转移方程：dp[i][j] = dp[i-1][j] + dp[i-1][j+weight[i]] + dp[i-1][abs(j-weight[i])]边界条件：这题坑的地方在于方案数会超过边界，当发现当前重量可行时，直接归为1，防止dp数组累加时溢出。或者最后统计的时候，将判断条件从if(dp[n][i])>0改为if(dp[n][i]) 。dp[0][0] = 1参考代码：#include<bits/stdc++.h>u

2022-03-19 23:32:39 95

原创蓝桥杯杨辉三角形

如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列： 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 给定一个正整数 NN，请你输出数列中第一次出现 NN 是在第几个数？

2022-03-19 21:12:12 278

原创蓝桥杯印章&拿金币

对于大数组的定义要放在main函数外，否则会报错认真思考动态规划的边界设置，不是机械地设置1或0参考代码#include<bits/stdc++.h>using namespace std;int main(){ int n, m; scanf("%d %d", &n, &m); if(n > m){ printf("0.0000"); } else{ double dp[21][21] = {0}; for(int i

2022-03-03 23:30:06 249

原创深度学习初步理解

梯度下降概念：我们用到一种名为梯度下降（gradient descent）的方法，这种方法几乎可以优化所有深度学习模型。它通过不断地在损失函数递减的方向上更新参数来降低误差。梯度下降最简单的用法是计算损失函数（数据集中所有样本的损失均值）关于模型参数的导数（在这里也可以称为梯度）。但实际中的执行可能会非常慢：因为在每一次更新参数之前，我们必须遍历整个数据集。因此，我们通常会在每次需要计算更新的时候随机抽取一小批样本，这种变体叫做小批量随机梯度下降（minibatch stochastic g

2022-02-06 23:41:55 1243

原创本地Jupyter连接远程linux服务器

连接的前提是本地装好了Jupyter，以及远程的服务器也配置好了。先连接远程的Linux服务器，输入脚本命令：jupyter notebook得到执行结果：[I 14:29:11.290 NotebookApp] Serving notebooks from local directory: /home/ubuntu[I 14:29:11.290 NotebookApp] Jupyter Notebook 6.4.8 is running at:[I 14:29:11.290 Notebook

2022-01-30 14:43:17 1575

原创交叉验证中n_jobs=-1并行运算

scikit_learn包中的cross_val_score（）是支持并行运算，但这并不是说只要让n_jobs=-1就能让CPU使用率接近100%。这要取决于交叉验证的折数cv，假如折数cv是n，这意味着最多只能使用n个物理CPU。score1 = cross_val_score(clf, x_train, y_train, cv=5, scoring='accuracy', n_jobs=-1).mean()...

2021-12-25 02:23:01 3395

原创使用Java查询Sql Server数据库

import java.sql.*;public class Connect{ static Connection con; static Statement stmt; public static void doConnect() throws SQLException { String JDriver = "com.microsoft.sqlserver.jdbc.SQLServerDriver";// SQL数据库引擎 String connectDB = "jd

2021-12-24 03:15:21 1251

原创机器学习读取特征矩阵

def getMatrix(dirname): pssmList = os.listdir(dirname) pssmList.sort(key=lambda x: eval(x[:])) m = len(pssmList) reMatrix = np.zeros((m, 20)) for i in range(m): matrix= readToMatrix(dirname + '/' + pssmList[i], 'pssm') m

2021-11-21 20:23:28 595

原创 GridSearchCV和RandomizedSearchCV（以SVM为例）

参考代码 CC = [] gammas = [] for i in range(-5, 16, 2): CC.append(2 ** i) for i in range(3, -16, -2): gammas.append(2 ** i) param_grid = {"C": CC, "gamma": gammas} gs = GridSearchCV(SVC(probability=True), param_grid, cv=

2021-11-21 18:55:30 1154

原创 PAT-A Maximum Subsequence Sum

是道常规的动态规划题，不过我有被卡住（丢脸需要考虑当序列整体求和为0的情况。#include<bits/stdc++.h>using namespace std;int main(){ int k; vector<int> v; scanf("%d", &k); int temp; bool all_negative = true; for(int i = 0; i < k; i++) {

2021-09-29 18:02:32 60

原创 PAT-A Sign In and Sign Out

这题挺水的，就是要注意char数组长度至少设置为16，设成15由于存在结尾结束符，会导致长度为15的ID无法存入数组中。#include<bits/stdc++.h>using namespace std;int main(){ int n; scanf("%d", &n); char be[16], ed[16]; int b = 0x3f3f3f3f, e = -1; char name[16]; int hh, mm, ss

2021-09-27 01:04:06 60

空空如也

空空如也