Immature_7-CSDN博客

原创并查集模板--C语言

并查集模板–C语言#include <stdio.h>//初始化并查集void Initial(int S[],int size){ for(int i=0;i<size;i++){ S[i]=-1; }} //Find "查"操作，找x所在集合（路径压缩）int Find(int S[],int x){ int root=x; while(S[root]>=0) root=S[root];//循环找到根 while(x!=root){//压缩路径

2021-10-30 11:31:00 2734

原创 408计算机考研--数据结构--2020年统考真题（C语言）

2020年408统考真题（C语言）一、题目描述定义三元组(a,b,c)（a、b、c均为正数）的距离D=|a-b|+|b-c|+|c-a|。给定3个非空整数集合S1、S2、S3，按升序分别存储在3个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组(a,b,c)(a∈S1,b∈S2,c∈S3)中的最小距离。例如S1={-1,0,9}，S2={-25,-10,10,11}，S3={2,9,17,30,41},则最小距离为2，相应的三元组为(9,10,9)。二、算法的基本思想①使用Dmin记录

2021-08-24 19:06:04 3038

原创 408计算机考研--数据结构--排序模板（C语言）

数据结构–排序模板（C语言）1.插入排序–直接插入排序（稳定的排序算法）//折半插入排序--稳定排序。//时间复杂度：最好情况下：O(n)。最坏情况下：O(n^2);//空间复杂度：O(1)void InsertSort3(int* A,int numSize){ int i,j,low,high,mid,temp; for(int i=1;i<numSize;i++){ //找到前有序序列的当前数的插入位置 temp=A[i]; low=

2021-07-17 10:46:28 611

原创 408计算机考研--数据结构--2016年统考真题（C语言）

标题408数据结构–2016年统考真题（C语言）一、题目描述已知由n(n>=2)个正整数构成的集合A={ak|0<=k<n},将其划分为两个不相交的子集A1和A2,元素个数分别是n1和n2，A1和A2中的元素之和分别为S1和S2。设计一个尽可能高效的划分算法，满足|n1-n2|最小且|S1-S2|最大。要求：给出算法的基本设计思想。根据设计思想，采用C或C++语言描述算法，关键之处给出注释说明你所设计的算法的平均时间复杂度和空间复杂度。二、解决思路1. 暴力法–排序直接

2021-07-16 18:48:15 2328

原创算法练习贴--75--在排序数组中查找元素的第一个和最后一个位置（C语言）

标题在排序数组中查找元素的第一个和最后一个位置（C语言）一、题目描述给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。（题目来源：力扣（LeetCode））进阶：你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？示例 1：输入：nums = [5,7,7,8,8,10], target = 8输出：[3,4]示例 2：输入：nums = [

2021-07-16 12:15:37 385

原创算法练习帖--74--在排序数组中查找数字 I（C语言）

在排序数组中查找数字 I（C语言）一、题目描述统计一个数字在排序数组中出现的次数。（题目来源：力扣（LeetCode））示例 1输入: nums = [5,7,7,8,8,10], target = 8输出: 2示例 2:输入: nums = [5,7,7,8,8,10], target = 6输出: 0限制：0 <= 数组长度 <= 50000二、解决方法二分查找int search(int* nums, int numsSize, int target)

2021-07-16 11:57:48 130

原创 408计算机考研--数据结构--图的学习（C语言)

图的学习一、图的存储及BFS、DFS算法1.1、邻接矩阵法特点：无向图的邻接矩阵一定是一个对称矩阵（并且唯一）。因此，在实际存储邻接矩阵时只需存储上（或下）三角矩阵的元素。对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是顶点i的度TD(vi)。对于有向图，邻接矩阵的第i行非零元素（或非∞元素）的个数正好是顶点i的出度OD(vi)；第i列非零元素（或非∞元素）正好是顶点i的入度ID(vi)。用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中

2021-07-15 08:29:39 735

原创 408计算机考研--数据结构--二叉排序树学习（C语言）

二叉排序树一、二叉排序树(创建、增删改查)学习#include<stdio.h>#include<stdlib.h>typedef struct BSTNode{ int key; struct BSTNode *lchild,*rchild;}BSTNode,*BSTree;//在二叉排序树插入关键字为k的新结点（递归实现），时间复杂度：O(h)-O(n)之间 int BST_Insert(BSTree &T,int k){ if(T==NULL){/

2021-07-09 19:03:09 188

原创 408计算机考研--数据结构--线索化二叉树学习（C语言）

线索化二叉树学习（C语言）一、线索二叉树的基本概念传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。我们知道，在含n个结点的二叉树中，有n+1个空指针。利用这些空指针来存放其前驱或后继的指针，这样就可以使得我们在遍历二叉树时可以像遍历单链表那样方便。引入线索二叉树正是为了加快查找结点前驱和后继的速度。（有三种线索化二叉树，分别是先序线索化二叉树、中序线索化二叉树以及后序线索化二叉树）二、中序线索化二叉树创建、找前驱、找后继以及遍历#include<stdio.h

2021-07-08 18:01:23 557

原创 408计算机考研--数据结构--二叉树学习（C语言）

二叉树学习一、二叉树的前中后序递归遍历及应用（求树深度）#include<stdio.h>#inlcude<stdlib.h>typedef struct BiTNode{ int data; struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;//先序遍历void PreOrder(BiTree T){ if(T!=NULL){ visit(T);//访问根节点 PreOrder(T.lchild);//

2021-07-08 17:50:30 278

原创算法练习贴--73--错误的集合（C语言）

错误的集合（C语言）一、题目描述集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合丢失了一个数字并且有一个数字重复。给定一个数组 nums 代表了集合 S 发生错误后的结果。请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。（题目来源：力扣（LeetCode））示例 1：输入：nums = [1,2,2,4]输出：[2,3]示例 2：输入：nums = [1,1]输出：[1,2]

2021-07-05 18:49:24 218

原创 408计算机考研--数据结构--队列学习（C语言）

队列学习（C语言）一、队列的顺序存储方式#include<stdio.h>#include<stdlib.h>#define MaxSize 10typedef struct SqQueue{ int data[MaxSize];//存储队列数据 int front,rear;//队头，队尾指针 }SqQueue; //初始化队列 void Init_SqQueue(SqQueue &Q){ Q.front=Q.rear=0;}//判队空boo

2021-07-03 16:14:37 194

原创 408计算机考研--数据结构--栈学习（C语言）

栈学习（C语言）一、栈的基本概念栈（Stack）是只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。栈顶（top）:线性表允许进行插入和删除的那一端。栈底（Bottom）：固定的，不允许进行插入和删除的另一端。空栈：不含任何元素的空表。二、栈的顺序存储结构#include<stdio.h>#include<stdlib.h> #define MaxSize 10 //定义栈中元素的最大个数typed

2021-07-02 22:23:05 675 2

原创 408计算机考研--数据结构--快慢指针学习（C语言指针）

快慢指针学习（C语言指针）一、判断环形链表1.1、题目描述给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。如果链表中存在环，则返回 true 。否则，返回 false 。力扣（LeetCode）进阶：你能用 O(1)（

2021-07-02 18:04:15 699 2

原创算法练习帖--72--重排链表（C语言）

重排链表一、题目描述给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。（题目来源：力扣（LeetCode））示例 1:给定链表 1->2->3->4, 重新排列为 1->4->2->3.示例 2:给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3

2021-07-02 17:06:19 458

原创算法练习帖--71--反转链表(C语言)

反转链表一、题目描述定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。（题目来源：力扣官网）示例:输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL 限制：0 <= 节点个数 <= 5000二、解决方法1.头插法struct ListNode* reverseList(struct ListNode* head){ if(head==NULL|

2021-07-01 23:12:05 126 1

原创 408统考真题--线性表(2013年)

[2013统考真题]已知一个整数序列A=(a0,a1,···,an-1),其中0<=ai<n(0<=i<n)。若存在ap1=ap2=···=apm=x且m>n/2(0<=pk<n,1<=k<=m),则称x为A的主元素。例如A=(0,5,5,3,5,7,5,5)，则5为主元素；又如A=(0,5,5,3,5,1,5,7)，则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输

2021-07-01 21:35:13 894

原创算法练习贴--70--寻找两个正序数组的中位数(C语言)

寻找两个正序数组的中位数(C语言)一、题目描述给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。（题目来源：力扣（LeetCode））示例 1：输入：nums1 = [1,3], nums2 = [2]输出：2.00000解释：合并数组 = [1,2,3] ，中位数 2示例 2：输入：nums1 = [1,2], nums2 = [3,4]输出：2.50000解释：合并数组 = [1,2,3,4] ，中位数

2021-06-30 23:38:40 953 2

原创 408计算机考研--数据结构--线性表学习(C语言)

线性表的学习1.线性表的顺序表示–顺序表1.1、顺序表的定义–静态分配#include <stdio.h>#define MaxSize 10 //定义最大长度 typedef struct{ int data[MaxSize];//用数组存储数据元素 int length;//顺序表的当前长度 }SeqList;//顺序表的类型定义 //基本操作--初始化一个顺序表void InitList(SeqList &L){ for(int i=0;i<Ma

2021-06-29 21:13:04 586

原创算法练习帖--69--数据流中的第 K 大元素(java)

数据流中的第 K 大元素(java)一、题目简介设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。请实现 KthLargest 类：KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。(题目来源：力扣（LeetCode）)示例：输入：["KthLargest", "add"

2021-02-11 15:28:11 136 1

原创弗洛伊德算法学习(Java)

弗洛伊德算法学习(Java)学习视频：尚硅谷韩老师java讲解数据结构和算法一、弗洛伊德(Floyd)算法介绍和 Dijkstra 算法一样，弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978 年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名弗洛伊德算法(Floyd)计算图中各个顶点之间的最短路径迪杰斯特拉算法用于计算图中某一个顶点到其他顶点的最短路径。弗洛伊德算法 VS 迪杰斯特拉算法：迪杰斯特拉算法通过选定的被访

2021-02-08 20:40:43 381 1

原创算法练习帖--68--最长湍流子数组(Java)

最长湍流子数组一、题目简介当 A 的子数组 A[i], A[i+1], …, A[j] 满足下列条件时，我们称其为湍流子数组：若 i <= k < j，当 k 为奇数时， A[k] > A[k+1]，且当 k 为偶数时，A[k] < A[k+1]；或若 i <= k < j，当 k 为偶数时，A[k] > A[k+1] ，且当 k 为奇数时， A[k] < A[k+1]。也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数

2021-02-08 14:40:52 148

原创算法练习帖--67--可获得的最大点数(Java)

可获得的最大点数一、题目简介几张卡牌排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。你的点数就是你拿到手中的所有卡牌的点数之和。给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。(题目来源:力扣（LeetCode）)示例 1：输入：cardPoints = [1,2,3,4,5,6,1], k = 3输出：12解释：第一次行动，不管拿哪张牌，你的点

2021-02-06 15:34:51 137

原创算法练习帖--66--最小体力消耗路径(Java)

最小体力消耗路径(Java)一、题目简介你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往上，下，左，右四个方向之一移动，你想要找到耗费体力最小的一条路径。一条路径耗费的体力值是路径上相邻格子之间高度差绝对值的最

2021-02-05 17:17:40 535 2

原创迪杰斯特拉(Dijkstra)算法学习(Java)

迪杰斯特拉(Dijkstra)算法学习(Java)一、迪杰斯特拉(Dijkstra)算法介绍迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。它的主要特点是以起始点为中心向外层层扩展**(广度优先搜索思想)**，直到扩展到终点为止。二、迪杰斯特拉(Dijkstra)算法过程设置出发顶点为 v，顶点集合 V{v1,v2,vi…}，v 到 V 中各顶点的距离构成距离集合 Dis，Dis{d1,d2,di…}，Dis 集合记录着 v 到图中各顶点的距离(到自身

2021-02-05 15:01:46 321

原创算法练习帖--65--尽可能使字符串相等(Java)

尽可能使字符串相等一、题目简介给你两个长度相同的字符串，s 和 t。将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。如果 s 中没有子字符串可以转化成 t 中对应的子字符串，

2021-02-05 10:54:31 138

原创算法练习帖--64--交换字符串中的元素（Java）

交换字符串中的元素（Java）一、题目简介给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。你可以任意多次交换在 pairs 中任意一对索引处的字符。返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。(题目来源：力扣（LeetCode）)示例 1:输入：s = "dcab", pairs = [[0,3],[1,2]]输出："bacd"解释：交换 s[0] 和 s[3]

2021-02-04 14:58:52 183

原创克鲁斯卡尔算法学习（Java）

克鲁斯卡尔算法（Java）学习视频：尚硅谷韩老师java讲解数据结构和算法一、应用场景-公交站问题某城市新增 7 个站点(A, B, C, D, E, F, G) ，现在需要修路把 7 个站点连通各个站点的距离用边线表示(权) ，比如 A – B 距离 12 公里问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短?二、克鲁斯卡尔算法介绍2.1、以城市公交站问题来图解说明克鲁斯卡尔算法的原理和步骤：在含有 n 个顶点的连通图中选择 n-1 条边，构成一棵极小连通子图，并使该连

2021-02-03 20:31:40 411

原创算法练习帖--63--冗余连接（Java）

冗余连接一、题目简介在本问题中, 树指的是一个连通且无环的无向图。输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式

2021-02-02 22:02:09 138

原创算法练习帖--62--替换后的最长重复字符(Java)

替换后的最长重复字符一、题目简介给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。注意：字符串长度和 k 不会超过 104。(题目来源：力扣（LeetCode）)示例 1：输入：s = "ABAB", k = 2输出：4解释：用两个'A'替换为两个'B',反之亦然。示例 2：输入：s = "AABABBA", k = 1输出：4解释：将中间的一个'A'替换为'B',字符串变

2021-02-02 12:25:41 197 3

原创算法练习帖--61--省份数量(Java)

省份数量一、题目描述有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。返回矩阵中省份的数量。(题目来源：力扣（

2021-02-01 21:36:14 407

原创普里姆算法学习(Java)

普里姆算法学习(Java)学习视频：尚硅谷韩老师java讲解数据结构和算法一、应用场景-修路问题1.1、看一个应用场景和问题：有胜利乡有 7 个村庄(A, B, C, D, E, F, G) ，现在需要修路把 7 个村庄连通各个村庄的距离用边线表示(权) ，比如 A – B 距离 5 公里问：如何修路保证各个村庄都能连通，并且总的修建公路总里程最短?思路: 将 10 条边，连接即可，但是总的里程数不是最小.正确的思路：就是尽可能的选择少的路线，并且每条路线最小，保证总里程数最少二、最

2021-02-01 15:35:17 433 1

原创算法练习帖--60--公平的糖果棒交换(Java)

公平的糖果棒交换一、题目描述爱丽丝和鲍勃有不同大小的糖果棒：A[i] 是爱丽丝拥有的第 i 根糖果棒的大小，B[j] 是鲍勃拥有的第 j 根糖果棒的大小。因为他们是朋友，所以他们想交换一根糖果棒，这样交换后，他们都有相同的糖果总量。（一个人拥有的糖果总量是他们拥有的糖果棒大小的总和。）返回一个整数数组 ans，其中 ans[0] 是爱丽丝必须交换的糖果棒的大小，ans[1] 是 Bob 必须交换的糖果棒的大小。如果有多个答案，你可以返回其中任何一个。保证答案存在。（题目来源：力扣（LeetCod

2021-02-01 10:56:17 134

原创算法练习帖--59--相似字符串组(Java)

相似字符串组一、题目简介如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。例如，“tars” 和 “rats” 是相似的 (交换 0 与 2 的位置)； “rats” 和 “arts” 也是相似的，但是 “star” 不与 “tars”，“rats”，或 “arts” 相似。总之，它们通过相似性形成了两个关联组：{“tars”, “rats”, “arts”} 和 {“star”}。注意，“tar

2021-01-31 20:32:20 232

HuGongTrain123456_files.zip

空空如也