- 博客(135)
- 收藏
- 关注
RSS订阅
原创 面试常见知识点思维导图
目录标题Linux基础命令进程间通信C语言和C++内存分配数据结构排序测试方面软件测试测试性能指标数据库三大范式事务锁数据库三个删除表命令计算机网络http和httpshttp状态码Linux基础命令进程间通信C语言和C++内存分配数据结构排序测试方面软件测试我把软件工程书上的第13章梳理好的内容，看完肯定有新收获测试性能指标数据库三大范式事务锁数据库三个删除表命令计算机网络http和httpshttp状态码...
2021-12-13 19:23:07
2562
原创 经典贪心-最小延迟调度问题（问题描述坑死我了）
Description假定有一单个的资源在一个时刻只能处理一个任务。现给定一组任务，其中的每个任务 i 包含一个持续时间 ti 和截止时间 di 。设计与实现一个算法，从 0 时刻开始任务，对这组任务给出一个最优调度方案，使其所有任务中的最大延迟最小化。任务 i 的延迟指实际完成时间fi减去截止时间diInput第一行输入一个t，代表有t组样例。（t≤10）每个样例第一行输入一个n（n≤100），代表工作数，接下来n行，每行输入两个数ti（1≤ti≤100）和di（1≤di≤1000），代表任务持续
2021-12-02 17:53:30
1522
原创 经典贪心-找零钱
Description现有100，50，20，10，5，2，1元的纸币，现在一个物品价值n元，问至少需要多少张钱，才可以支付该物品。Input输入多组数据，每组第一行输入整数n（1≤n≤9999）。Output输出至少需要的钱的张数，并输出方案（输出格式：币值张数+币值张数+….=n,币值从大到小输出，其中张数为1则无需乘以张数）Sample Input611000Sample Output2 5+1=61 1=110 100*10=1000思路：创建两个不同的数组存放num存
2021-12-02 16:42:26
876
原创 经典贪心-多设备区间调度
Description多个调度任务，给出调度任务的起始时间和结束时间，问至少需要多少个设备能完成调度任务，在保证最小设备的情况，要求所有设备运行总时长最短。每个设备的运行时长：从给这个设备的第一个任务开始计算到这个设备的最后一个任务结束，中间哪怕没有任务也要计算运行时长。Input输入的第一行包含一个正整数t(t ≤ 100)，代表共有t组输入实例。每组输入实例中，第一行包含一个正整数n(n ≤ 100)，接下来输入n行，每一行包含两个正整数l和r(0 ≤ l < r ≤ 109)
2021-11-21 19:31:32
1419
原创 贪心入门-最少拦截系统（思路解析）
Description某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于成本所在，我们要用尽可能少的拦截系统，请帮忙算一下最少需要多少套拦截系统方可抵御一次进攻。Input输入若干组数据.每组数据包括:导弹总个数,导弹依次飞来的高度。第一个数输入n(1≤n≤100)，代表有n个导弹，接下来在同一行中，输入n个数，代表导弹依次飞来的高度。Output
2021-11-11 17:40:31
404
原创 经典动态规划-饭卡
Description如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。 某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。Input多组数据。对于每组数据： 第一行为正整数n，表示菜的数量。n<=1000。 第二行包括n个正整数，表示每种菜的价格。价格不超过50。 第三行包括一个正整数m，表示卡上的余额。m<=1000。
2021-11-11 17:23:16
90
原创 经典动态规划-连续数组最大和问题
Description求最大连续子段和，并输出此子段的起始位置和终止位置的值。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{ 11, -4, 13 }，最大和为20。Input测试输入包含若干测试用例，每个测试用例占2行，第1行给出正整数K( < 10000 )，第2行给出K个整数，中间用空格分隔。当K为0时，输入结束，该用例不被处理。Output对每个测试用例，在1行里输出最大和、最大连续子序列的第一个和最后一个元 素，中间用空格分隔。如果最大连续
2021-11-04 17:38:50
829
原创 动态规划入门-大学线代的矩阵链相相乘
Description设A1,A2,…,An为矩阵序列，Ai是阶为Pi−1∗Pi的矩阵(1≤i≤n)。试确定矩阵的乘法顺序，使得计算A1 A2 … An 过程中元素相乘的总次数最少。Input多组数据第一行一个整数n(n <= 300)，表示一共有n个矩阵。第二行n个整数B1, B2, B3… Bn(Bi <= 100)，第i个数Bi表示第i个矩阵的行数和第i-1个矩阵的列数。等价地，可以认为第j个矩阵Aj(1 <= j <= n)的行数为Bj，列数为Bj+1。
2021-10-25 22:07:17
202
原创 动态规划入门-打家劫舍
Description你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。Input每组测试案例有两行，第一行只有一个整数N，代表着有N间房屋(2 <= N <= 10000)第二行有N个整数，代表着每间房屋里的金额，金额范围[0, 1000]。O
2021-10-14 16:42:08
107
原创 基础分治-幂运算
Description给你三个整数a,b,q，求ab mod p的值Input第一行是一个整数t，表示t组数据。接下来的n行，每行有 3 个整数，分别表示a, b, pt ≤ 2 * 105，a > 0, b > 0, p ≥ 2,Output每组数据，输出一个整数表示答案。Sample Input22 10 92 3 3Sample Output72#include<iostream>int main(){ int t; scanf(".
2021-10-09 22:04:30
315
原创 基础分治-逆序对
逆序对Description对于一个序列a,如果有ai > aj且i < j，则称ai, aj为一逆序对。现给定一个序列，求出序列中逆序对的数量（序列中可能存在重复数字）Input第一行是一个整数，表示序列的长度 n。第二行有 n 个整数，第 i 个整数表示序列的第 i 个数字ai 。Output输出一个整数表示答案。Sample Input65 4 2 6 3 1Sample Output11利用归并排序即可如图所示，当a[j]<a[i]时，即 前面所有的
2021-10-09 21:57:59
1237
原创 冒泡排序 （DS排序）
题目描述给定一个包含从0到n-1各一次的数组，若使用冒泡排序将其排为升序，问其中需要进行多少次交换输入测试数据有多组，每组由两行组成：第一行包含正整数n（n <= 5000）; 下一行包含从0到n-1的n个整数的序列。输出对于每组测试数据，输出交换次数样例输入101 3 6 9 0 8 5 7 4 2样例输出22#include<iostream>using namespace std;int main() { int n; int *arr; w.
2021-01-07 19:54:24
753
原创 DS内排—直插排序
题目描述给定一组数据，使用直插排序完成数据的升序排序。–程序要求-- 若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio 程序中若include多过一个头文件，不看代码，作0分处理 不允许使用第三方对象或函数实现本题的要求输入数据个数n，n个数据输出直插排序的每一趟排序结果样例输入7 34 23 677 2 1 453 3样例输出23 34 677 2 1 453 323 34 677 2 1 453 32 23 34 67.
2021-01-05 22:22:01
272
原创 DS内排—堆排序
题目描述给定一组数据，使用堆排序完成数据的降序排序。（建小顶堆)。输入数据个数n，n个整数数据输出初始创建的小顶堆序列每趟交换、筛选后的数据序列，输出格式见样例样例输入8 34 23 677 2 1 453 3 7样例输出8 1 2 3 7 23 453 677 348 2 7 3 34 23 453 677 18 3 7 453 34 23 677 2 18 7 23 453 34 677 3 2 18 23 34 453 677 7 3 2 18 34 677 453 2.
2020-12-30 10:32:38
347
原创 DS排序--快速排序
题目描述给出一个数据序列，使用快速排序算法进行从小到大的排序–程序要求-- 若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio 程序中若include多过一个头文件，不看代码，作0分处理 不允许使用第三方对象或函数实现本题的要求输入第一行输入t，表示有t个测试示例 第二行输入n，表示第一个示例有n个数据 第三行输入n个数据，都是正整数，数据之间用空格隔开 以此类推输出每组测试数据，输出每趟快排的结果，即每次排好一个数字结果（长度为1的子.
2020-12-29 20:46:09
477
原创 DS排序--希尔排序
题目描述给出一个数据序列，使用希尔排序算法进行降序排序。间隔gap使用序列长度循环除2直到1输入第一行输入t，表示有t个测试示例 第二行输入n，表示第一个示例有n个数据(n>1) 第三行输入n个数据，都是正整数，数据之间用空格隔开以此类推输出对每组测试数据，输出每趟排序结果。不同组测试数据间用空行分隔。样例输入26111 22 6 444 333 55877 555 33 1 444 77 666 2222样例输出444 333 55 111 22 6444 333 .
2020-12-29 16:41:05
583
原创 DS哈希查找—二次探测再散列（附图解）
题目描述定义哈希函数为H(key) = key%11。输入表长（大于、等于11），输入关键字集合，用二次探测再散列构建哈希表，并查找给定关键字。输入测试次数t每组测试数据格式如下：哈希表长m、关键字个数nn个关键字查找次数kk个待查关键字输出对每组测试数据，输出以下信息：构造的哈希表信息，数组中没有关键字的位置输出NULL对k个待查关键字，分别输出：0或1（0—不成功，1—成功）、比较次数、查找成功的位置（从1开始）样例输入112 1022 19 21 8 9 30 33.
2020-12-23 20:22:20
15367
6
原创 DS哈希查找—线性探测再散列（附图文解析）
题目描述定义哈希函数为H(key) = key%11。输入表长（大于、等于11），输入关键字集合，用线性探测再散列构建哈希表，并查找给定关键字。–程序要求–若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio 程序中若include多过一个头文件，不看代码，作0分处理 不允许使用第三方对象或函数实现本题的要求输入测试次数t每组测试数据为：哈希表长m、关键字个数nn个关键字查找次数kk个待查关键字输出对每组测试数据，输出以下信息.
2020-12-23 17:33:58
3710
原创 DS哈希查找--链地址法
题目描述给出一个数据序列，建立哈希表，采用求余法作为哈希函数，模数为11，哈希冲突用链地址法和表头插入如果首次查找失败，就把数据插入到相应的位置中实现哈希查找功能输入第一行输入n，表示有n个数据 第二行输入n个数据，都是自然数且互不相同，数据之间用空格隔开 第三行输入t，表示要查找t个数据从第四行起，每行输入一个要查找的数据，都是正整数输出每行输出对应数据的查找结果,每个结果表示为数据所在的位置[0-11)和查找次数,中间用空格分开。样例输入611 23 39 48 75 626.
2020-12-23 16:11:16
2114
1
原创 C语言实现平衡二叉树的插入、查找、删除
#include <stdio.h>#include <stdlib.h>#define KEY(n) (n ? n->key : 0)typedef struct Node { int key; struct Node *lchild, *rchild;} Node;Node *getNewNode(int key) { Node *p = (Node *)malloc(sizeof(Node)); p->key = key
2020-12-19 10:24:10
585
1
原创 DS查找—二叉树平衡因子（代码三十行 思路超级简单！！）
题目描述二叉树用数组存储，将二叉树的结点数据依次自上而下,自左至右存储到数组中，一般二叉树与完全二叉树对比，比完全二叉树缺少的结点在数组中用0来表示。计算二叉树每个结点的平衡因子，并按后序遍历的顺序输出结点的平衡因子。–程序要求-- 若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio 程序中若include多过一个头文件，不看代码，作0分处理 不允许使用第三方对象或函数实现本题的要求 输入 测试次数t每组测试数据一行，数组元素个数n，后跟.
2020-12-16 22:47:41
2094
原创 二叉排序树之删除（思路详解）
我参考了“z-k”博主 点击->原文链接和“半途行走”博主 点击->原文链接发现都没有考虑到排序二叉树 11 22 33 44 55 66 删除11根结点时只有一边结点的情况改进了代码删除结点一共有三种情况1.删除结点是叶子结点，没有子树；2.删除结点只有左子树或右子树；3删除结点既有左子树也有右子树第一种情况很简单直接删除即可 让父结点指向NULLif(!find->left && !find->right){ //该结点为叶子结点，直接删
2020-12-16 22:38:58
2983
3
原创 DS二叉排序树之查找
题目描述给出一个数据序列，建立二叉排序树，并实现查找功能对二叉排序树进行中序遍历，可以得到有序的数据序列输入第一行输入t，表示有t个数据序列第二行输入n，表示首个序列包含n个数据第三行输入n个数据，都是自然数且互不相同，数据之间用空格隔开第四行输入m，表示要查找m个数据从第五行起，输入m行，每行一个要查找的数据，都是自然数以此类推输入下一个示例输出第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到从第二行起，输出查找结果，如果查找成功输出查找次数，如果查找失败输出-1以此.
2020-12-15 20:41:25
147
原创 DS二叉排序树之创建和插入
题目描述给出一个数据序列，建立二叉排序树，并实现插入功能对二叉排序树进行中序遍历，可以得到有序的数据序列输入第一行输入t，表示有t个数据序列第二行输入n，表示首个序列包含n个数据第三行输入n个数据，都是自然数且互不相同，数据之间用空格隔开第四行输入m，表示要插入m个数据从第五行起，输入m行，每行一个要插入的数据，都是自然数且和前面的数据不等以此类推输入下一个示例输出第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到从第二行起，输出插入第m个数据后的有序序列，输出m行以此类.
2020-12-15 20:12:12
510
原创 C语言实现并查集
#include <stdio.h>#include <stdlib.h>#define swap(a, b) { \ __typeof(a) __temp =a;\ a = b; b = __temp;\}typedef struct UnionSet{ int *father,*size; int n;}UnionSet;UnionSet *init(int n){ UnionSet *u = (UnionSet *) malloc(sizeof(Un
2020-12-13 20:00:40
267
原创 C语言实现栈
#include<stdio.h>#include<stdlib.h>#include<time.h>typedef struct Stack { int *data; int size, top;} Stack;Stack *init(int);void clear(Stack *);int top(Stack *);int empty(Stack *);int push(Stack *,int);int pop(Stack *);void
2020-12-12 14:21:29
98
原创 C语言-队列
#include<stdio.h>#include<stdlib.h>#include<time.h>typedef struct Queue { int *data; int head, tail, length, cnt;} Queue;Queue *init(int n) { Queue *q = (Queue *)malloc(sizeof(Queue)); q->data = (int *)malloc(sizeof(int));
2020-12-11 23:00:31
135
1
原创 C语言实现链表
#include<stdio.h>#include<stdlib.h>#include<time.h>typedef struct ListNode { int data; struct ListNode *next;} ListNode;typedef struct List { ListNode head; int length;} List;ListNode *getNewNode(int);List *getLinkList();v
2020-12-11 16:34:44
171
原创 DS静态查找之顺序索引查找(无哨兵)
题目描述给出一个数组和要查找的数值，找出数值在数组中的位置，数组位置从1开始要求使用顺序索引查找算法，其中索引表查找和块内查找都采用不带哨兵、从头开始的顺序查找方法。输入第一行输入n，表示主表有n个数据第二行输入n个数据，都是正整数，用空格隔开 第三行输入k，表示主表划分为k个块，k也是索引表的长度第四行输入k个数据，表示索引表中每个块的最大值 第五行输入t，表示有t个要查找的数值 第六行起，输入t个数值，输入t行输出每行输出一个要查找的数值在数组的位置和查找次数，数据之间用短划线隔开，如.
2020-12-09 20:09:59
1026
原创 拓扑排序-STL版
输入第一行输入一个整数t，表示有t个有向图第二行输入n，表示图有n个顶点第三行起，输入n行整数，表示图对应的邻接矩阵以此类推输入下一个图的顶点数和邻接矩阵输出每行输出一个图的拓扑有序序列样例输入250 1 0 1 10 0 1 0 00 0 0 0 10 0 1 0 00 0 0 0 070 0 0 0 0 0 01 0 1 1 0 0 01 0 0 0 0 0 01 0 1 0 0 0 00 0 0 0 0 1 10 1 0 0 0 0 00 0 0 1 0 .
2020-12-02 20:04:46
629
原创 图的最短路径-STL版
输入第一行输入t，表示有t个测试实例第二行输入顶点数n和n个顶点信息第三行起，每行输入邻接矩阵的一行，以此类推输入n行第i个结点与其它结点如果相连则为距离，无连接则为0，数据之间用空格隔开。第四行输入v0，表示求v0到其他顶点的最短路径距离以此类推输入下一个示例输出对每组测试数据，输出：每行输出v0到某个顶点的最短距离和最短路径每行格式：v0编号-其他顶点编号-最短路径值----[最短路径]。没有路径输出：v0编号-其他顶点编号–1。具体请参考示范数据样例输入25 0 1 2 3.
2020-12-02 19:21:08
739
原创 c语言实现顺序表
#include<stdio.h>#include<stdlib.h>#include<time.h>typedef struct Vector { int *data; int size; //总大小 int length; //现大小 } Vector;Vector *init(int n) { Vector *vec = (Vector *)malloc(sizeof(Vector)); vec->data = (int *)mall
2020-11-30 22:07:15
106
原创 DS图应用--最短路径（附思路解析）
题目描述给出一个图的邻接矩阵，再给出指定顶点v0，求顶点v0到其他顶点的最短路径代码框架如下：输入第一行输入t，表示有t个测试实例第二行输入n，表示第1个图有n个结点第三行起，每行输入邻接矩阵的一行，以此类推输入n行第i个结点与其他结点如果相连则为1，无连接则为0，数据之间用空格隔开第四行输入v0，表示求v0到其他顶点的最短路径距离以此类推输入下一个示例输出每行输出v0到某个顶点的最短距离和最短路径每行格式：v0编号-其他顶点编号----[最短路径]，具体请参考示范数据样例输入.
2020-11-26 10:23:32
1073
原创 DS图—最小生成树（附思路解析）
题目描述根据输入创建无向网。分别用Prim算法和Kruskal算法构建最小生成树。（假设：输入数据的最小生成树唯一。）输入顶点数nn个顶点边数mm条边信息,格式为：顶点1 顶点2 权值Prim算法的起点v输出输出最小生成树的权值之和对两种算法，按树的生长顺序，输出边信息(Kruskal中边顶点按数组序号升序输出)样例输入6v1 v2 v3 v4 v5 v610v1 v2 6v1 v3 1v1 v4 5v2 v3 5v2 v5 3v3 v4 5v3 v5 6v3 .
2020-11-25 23:45:51
1195
原创 图综合练习--拓扑排序（有向拓扑图序列，及解析）
题目描述已知有向图，顶点从0开始编号，求它的求拓扑有序序列。拓扑排序算法：给出有向图邻接矩阵1.逐列扫描矩阵，找出入度为0且编号最小的顶点v2.输出v，并标识v已访问3.把矩阵第v行全清0重复上述步骤，直到所有顶点输出为止–程序要求-- 若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio 程序中若include多过一个头文件，不看代码，作0分处理 不允许使用第三方对象或函数实现本题的要求输入第一行输入一个整数t，表示有t个有向图.
2020-11-25 16:13:26
2616
原创 DS图—图的连通分量（附思路解析）
题目描述输入无向图顶点信息和边信息，创建图的邻接矩阵存储结构，计算图的连通分量个数。输入测试次数t每组测试数据格式如下：第一行：顶点数 顶点信息第二行：边数第三行开始，每行一条边信息输出每组测试数据输出，顶点信息和邻接矩阵信息输出图的连通分量个数，具体输出格式见样例。每组输出直接用空行分隔。样例输入34A B C D2A BA C6V1 V2 V3 V4 V5 V65V1 V2V1 V3V2 V4V5 V6V3 V581 2 3 4 5 6 7 8.
2020-11-24 21:11:44
1734
原创 图的应用之——图的连通（附思路解析）
题目描述给定一个图的邻接矩阵，请判断该图是否是连通图。连通图：任意两个顶点之间都有路径。–程序要求-- 若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio 程序中若include多过一个头文件，不看代码，作0分处理 不允许使用第三方对象或函数实现本题的要求输入第1行输入一个整数k，表示有k个测试数据 第2行输入一个整数n，表示有n个结点从第3行起到第n+2行输入一个邻接矩阵，其中Matrix[i,j]=1表示第i，j个结点之间有边，否则不.
2020-11-24 20:08:25
1526
原创 走地图问题：DS图—图非0面积（递归思路详解）
题目描述编程计算由"1"围成的下列图形的面积。面积计算方法是统计"1"所围成的闭合曲线中"0"点的数目。如图所示，在10*10的二维数组中，"1"围住了15个点，因此面积为15。输入测试次数t每组测试数据格式为：数组大小m,n一个由0和1组成的m*n的二维数组输出 对每个二维数组，输出符号"1"围住的"0"的个数，即围成的面积。假设一定有1组成的闭合曲线，但不唯一。样例输入 210 100 0 0 0 0 0 0 0 0 0 00 0 0 1 1 1 0 0 0 0 00 0 1.
2020-11-18 20:38:34
1704
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人