- 博客(54)
- 收藏
- 关注
RSS订阅原创 leetcode146. LRU Cache
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。// 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}// 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}// 缓存是 {1=1, 2=2}// 返回 -1 (未找到)lRUCache.get(1);// 返回 -1 (未找到)lRUCache.put(1, 1);// 缓存是 {1=1}lRUCache.get(1);
2023-05-03 17:33:13
657
原创 Redis In Action Chap01
我用golang重写了Redis In Action第一章中关于构建一个 article voting application的backend函数。书中使用python来调用redis database。
2023-02-27 17:42:58
43
原创 利用快排中的思想，不排序，求数组中的中位数、求第K小的数
int get_median(int* a, int n) { int low = 0, high = n - 1, mid,pivot,i,j; while (1) { i = low, j = high; pivot = a[i]; while (i < j) { while (i<j && a[j] >= pivot)j--; if (i< j)a[i] = a[j]; while (i< j && a[
2021-03-26 20:50:52
250
1
原创 连通图
题目描述给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。输入描述:每组数据的第一行是两个整数 n 和 m（0<=n<=1000）。n 表示图的顶点数目，m 表示图中边的数目。随后有 m 行数据，每行有两个值 x 和 y（0<x, y <=n），表示顶点 x 和 y 相连，顶点的编号从 1 开始计算。输入不保证这些边是否重复。输出描述:对于每组输入数据，如果所有顶点都是连通的，输出"YES"，否则输出"NO"。示例1输入复制4 31 22 3
2021-03-15 22:58:20
503
原创 浙大机试_二叉搜索树
题目描述判断两序列是否为同一二叉搜索树序列输入描述:开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。输出描述:如果序列相同则输出YES，否则输出NO示例1输入复制25674325432675763420输出复制YES
2021-03-14 18:02:26
156
原创 二叉排序树
题目描述输入一系列整数，建立二叉排序树，并进行前序，中序，后序遍历。输入描述:输入第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。输出描述:可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。每种遍历结果输出一行。每行最后一个数据之后有一个空格。输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。示例1输入复制51 6 5 9 8输出复制1 6 5 9 81 5 6 8
2021-03-14 17:25:30
101
原创 二叉排序树
题目描述二叉排序树，也称为二叉查找树。可以是一颗空树，也可以是一颗具有如下特性的非空二叉树： 1. 若左子树非空，则左子树上所有节点关键字值均不大于根节点的关键字值； 2. 若右子树非空，则右子树上所有节点关键字值均不小于根节点的关键字值； 3. 左、右子树本身也是一颗二叉排序树。 现在给你N个关键字值各不相同的节点，要求你按顺序插入一个初始为空树的二叉排序树中，每次插入后成功后，求相应的父亲节点的关键字值，如果没有父亲节点，则输出-1。输入描述:输入包含多组测试数据，每组测试数据两行。第一行，一个
2021-03-14 15:51:37
520
原创 二叉树遍历
题目描述二叉树的前序、中序、后序遍历的定义： 前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树； 中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树； 后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。 给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。输入描述:两个字符串，其长度n均小于等于26。第一行为前序遍历，第二行为中序遍历。二叉树中的结点名称以大写字母表示：A，B，C…最多26个结点。
2021-03-14 14:15:35
158
原创 约数的个数
题目描述输入n个整数,依次输出每个数的约数的个数输入描述:输入的第一行为N，即数组的个数(N<=1000)接下来的1行包括N个整数，其中每个数的范围为(1<=Num<=1000000000)输出描述:可能有多组输入数据，对于每组输入数据，输出N行，其中每一行对应上面的一个数的约数的个数。示例1输入复制51 3 4 6 12输出复制12346假设一个数x的约数为n,且x的质因子为pi,各个质因子对应的幂次为ei,则n=(e1+1)(e2+1)…所以先
2021-03-13 18:32:20
131
原创 质因数的个数
题目描述求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=22235，共有5个质因数。输入描述:可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。输出描述:对于每组数据，输出N的质因数的个数。示例1输入复制120输出复制5准确求出每个质因子和其对应的幂次#include<iostream>#include<vector>#include<cstring>#define m
2021-03-13 18:16:04
183
原创 最简真分数
真分数：分子小于分母，且分子和分母的最大公约数为1#include<iostream>#include<vector>#include<algorithm>using namespace std;int gcd(int a,int b);vector<int>nums;int main(){ int n,cur,res; while(cin>>n){ if(!n)break; res=0
2021-03-13 17:21:28
199
原创 数制转换
题目描述求任意两个不同进制非负整数的转换（2进制～16进制），所给整数在long所能表达的范围之内。 不同进制的表示符号为（0，1，…，9，a，b，…，f）或者（0，1，…，9，A，B，…，F）。输入描述:输入只有一行，包含三个整数a，n，b。a表示其后的n 是a进制整数，b表示欲将a进制整数n转换成b进制整数。a，b是十进制整数，2 =< a，b <= 16。数据可能存在包含前导零的情况。输出描述:可能有多组测试数据，对于每组数据，输出包含一行，该行有一个整数为转换后的b
2021-03-13 00:52:19
116
原创 字符串分割函数
当字符串的分隔符是单个字符时vector<string>str_split(string s, char delim) { typedef struct { int start_pos, len; }substring_info; substring_info cur_info,last_info; vector<substring_info>infos; bool first = true; for (int i = 0; i < s.size(); i++
2021-03-12 13:59:19
192
原创 机试中数组的读取
机试中的测试用例不含每次的数组长度时的处理方法。#include<iostream>#include<vector>#include<string>using namespace std;vector<int>get_str_vec();int read();vector<int>str_data;int index;string s;int main() { while (getline(cin, s)) { index
2021-03-12 11:37:49
74
原创 进制转换2
题目描述将M进制的数X转换为N进制的数输出。输入描述:输入的第一行包括两个整数：M和N(2<=M,N<=36)。下面的一行输入一个数X，X是M进制的数，现在要求你将M进制的数X转换成N进制的数输出。输出描述:输出X的N进制表示的数。示例1输入复制10 211输出复制1011备注:注意输入时如有字母，则字母为大写，输出时如有字母，则字母为小写。//#include<iostream>//#include<vector>//#includ
2021-03-12 00:35:53
145
原创 进制转换
题目描述将一个长度最多为30位数字的十进制非负整数转换为二进制数输出。输入描述:多组数据，每行为一个长度不超过30位的十进制非负整数。（注意是10进制数字的个数可能有30个，而非30bits的整数）输出描述:每行输出对应的二进制数。示例1输入复制0138输出复制01111000#include<iostream>#include<vector>#include<string>using namespace std;strin
2021-03-11 20:54:21
81
原创 The triangle
王道第246页DFS#include<iostream>using namespace std;int res=0,mat[101][101],n;void dfs(int row, int col, int cur_sum);int main() { cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < i + 1; j++) { cin >> mat[i][j];
2021-03-10 20:35:44
43
原创 放苹果
题目描述把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。输入描述:每行均包含二个整数M和N，以空格分开。1<=M，N<=10。输出描述:对输入的每组数据M和N，用一行输出相应的K。示例1输入复制17 3输出复制8首先是低效率的强行搜索,生成方案后再去重,时间效率击败百分之三…#include<vector>#include<iostream>#inclu
2021-03-10 20:07:34
51
原创 最小邮票数
题目描述有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。 如，有1分，3分，3分，3分，4分五张邮票，要求凑成10分，则使用3张邮票：3分、3分、4分即可。输入描述:有多组数据，对于每组数据，首先是要求凑成的邮票总值M，M<100。然后是一个数N，N〈20，表示有N张邮票。接下来是N个正整数，分别表示这N张邮票的面值，且以升序排列。输出描述: 对于每组数据，能够凑成总值M的最少邮票张数。若无解，输出0。示例1输入复制1051 3 3 3 4输出复制
2021-03-10 18:52:49
123
原创 Coincidence（longest common subsequence）
题目描述Find a longest common subsequence of two strings.输入描述:First and second line of each input case contain two strings of lowercase character a…z. There are no spaces before, inside or after the strings. Lengths of strings do not exceed 100.输出描述:For e
2021-03-08 14:21:27
52
原创 DFS求解某个字符串的所有子序列
一个字符串string s的某个子序列定义为：在s中按照原先的先后次序依次取出若干个字符组成一个新的字符串，所以一个字符串s对应着一组字符串子序列vector<string>getSubsequence(string s) { vector<string>res; dfs(s, "", 0, res); return res;}void dfs(string s,string cur,int pos, vector<string>& strs) {
2021-03-08 13:50:57
777
原创 合唱队形
题目描述N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学不交换位置就能排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …, TK， 则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。输入描
2021-03-07 21:08:49
167
原创 最大上升子序列和
题目描述一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …,aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中序列和最大为18，为子序列(1, 3, 5, 9)的和. 你的任
2021-03-07 20:42:56
95
原创 拦截导弹
题目描述某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。输入描述:每组输入有两行，第一行，输入雷达捕捉到的敌国导弹的数量k（k<=25），第二行，输入k个正整数，表示k枚导弹的高度，按来袭导弹的袭击
2021-03-07 18:20:54
164
原创 最大子矩阵
题目描述已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。 比如，如下4 * 4的矩阵 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 的最大子矩阵是 9 2 -4 1 -1 8 这个子矩阵的大小是15。输入描述:输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N2
2021-03-07 17:04:34
249
原创 计算表达式
题目描述对于一个不存在括号的表达式进行计算输入描述:存在多种数据，每组数据一行，表达式不存在空格输出描述:输出结果示例1输入复制6/2+3+3*4输出复制18#include<iostream>#include<vector>#include<string>#include<cctype>#define MaxStackSize 201using namespace std;int getPriority(char c);
2021-03-07 00:18:53
73
原创 简单计算器
题目描述读入一个只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。输入描述:测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。输出描述:对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。示例1输入复制1 + 24 + 2 * 5 - 7 / 110输出复制3.0013.36#include<iostream>#inc
2021-03-06 20:05:40
52
原创 括号匹配问题
王道机识指南 第75页#include<iostream>#define maxStackSize 101using namespace std;typedef struct { char c; int pos;}stack_elem;stack_elem my_stack[maxStackSize];int top = -1;//指向栈顶int main() { string s; while (cin >> s) { int stack_output_
2021-03-05 18:30:14
39
原创 猫狗收容所
王道机试指南 第69页#include <iostream>#include<queue>#include<vector>using namespace std;typedef struct { int num, kind;}animal;queue<animal>cats,dogs;vector<int>res;int main(){ animal tmp; int n,kind,_kind,cnt=0; cin &g
2021-03-05 16:12:16
161
原创 约瑟夫问题 No.2
王道机识指南 第67页//Joseph Problem#include <iostream>#include<queue>using namespace std;queue<int>children;int main(){ int n, p, m; while (cin >> n >> p >> m) { if (n == 0 && p == 0 && m == 0) break;
2021-03-05 15:37:30
57
原创 2018年暨南大学考研复试上级真题
考试时间 2 hours一、15 分斐波那契数列为：1，1，2，3，5…请输入一个 n，要求输出斐波那契数列的第 n 项（要求用递归）二、25 分蛇形矩阵，是由 1 开始的自然数一次排列成的 N*N 的正方形矩阵，请输入一个 n，要求输出宽度为 n 的蛇形矩阵 ，例如：【输入】3【输出】1 2 36 5 47 8 9【输入】6【输出】1 2 3 4 5 612 11 10 9 8 713 14 15 16 17 1824 23 22 21 20 1925 26 27
2021-03-04 23:42:59
195
2
原创 单词替换
题目描述输入一个字符串，以回车结束（字符串长度<=100）。该字符串由若干个单词组成，单词之间用一个空格隔开，所有单词区分大小写。现需要将其中的某个单词替换成另一个单词，并输出替换之后的字符串。输入描述:多组数据。每组数据输入包括3行， 第1行是包含多个单词的字符串 s， 第2行是待替换的单词a，(长度<=100) 第3行是a将被替换的单词b。(长度<=100) s, a, b 最前面和最后面都没有空格.输出描述:每个测试数据输出只有 1 行， 将s中所有单词a替换成b之后的字符
2021-02-24 22:15:10
84
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人