题目链接|计算某字符出现次数 写出一个程序，接受一个由字母、数字和空格组成的字符串，和一个字符，然后输出输入字符串中该字符的出现次数。（不区分大小写字母） 方法一：直接计数所询问字符的出现次数 由于每个case询问唯一，可以直接判断所询问字符是否和字符串中的每个字符相同。字母不区分大小写，所以可以统一转换成小写后进行比较。 时间复杂度：O(N)O(N)O(N)，解释：需要对字符串的每个字符进行遍历，NNN为字符串的长度。 空间复杂度：O(N)O(N)O(N)，解释：需要O(N)O(N)O(N)大小的空间存储字符串的每个字符。 #include <cstdio> #inclu...

题目链接|明明的随机数 明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 NNN 个 111 到 100010001000 之间的随机整数（ N≤1000N\leq 1000N≤1000 ），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作(同一个测试用例里可能会有多组数据(用于不同的调查)，希望大家能正确处理)。 简化版题意：有NNN个111到100010001000的随机数，去掉重复的之后进行排序。 方法一：使用数组标记...

题目链接| 字符串分隔 连续输入字符串，请按长度为8拆分每个输入字符串并进行输出； 长度不是8整数倍的字符串请在后面补数字0，空字符串不处理。 （注：本题有多组输入） 方法一：正常输入，暴力模拟 对字符串进行循环，每八位输出一次，如果最后一次不足八位，就在后面补0。 时间复杂度：O(N)O(N)O(N)，解释：遍历一遍字符串时间复杂度为O(N)O(N)O(N)。 空间复杂度：O(N)O(N)O(N),解释：需要O(N)O(N)O(N)长度的数组存放字符串。 #include <cstdio> #include <cstring> #include <ios...

题目链接|进制转换 写出一个程序，接受一个十六进制的数，输出该数值的十进制表示。保证结果在1≤n≤231−11 \leq n \leq 2^{31}-11≤n≤231−1。 方法一：按照十六进制转十进制的方法直接进行转换 一般十六进制数用数字0到9和字母A到F表示，其中A~F相当于十进制的10~15，这些称作十六进制数字。十六进制转为十进制的方法是：∑v∗pos16\sum{v * pos ^{16}}∑v∗pos16，其中vvv是代表第pospospos位上的数字，最高位计为 pos=0pos=0pos=0。 时间复杂度：O(length(N))O(length(N))O(length(...

题目链接|取近似值 写出一个程序，接受一个正浮点数值，输出该数值的近似整数值。如果小数点后数值大于等于 0.50.50.5 ,向上取整；小于 0.50.50.5 ，则向下取整。数据范围：保证输入的数字在 323232 位浮点数范围内 方法一：利用语言特性求解，输入加上0.5后取整 如果小数点后的数值大于0.50.50.5，那么加上0.50.50.5后比原数字+1+1+1大，取整后为原数的整数部分+1+1+1，即上整数；如果小数点后的数值大于0.50.50.5，由于c/c++的取整操作是取下整，所以取整后为原数字的整数部分。 时间复杂度: O(1)O(1)O(1)，空间复杂度 O(1)O(1...

题目链接|合并表记录 数据表记录包含表索引和数值（int范围的正整数），请对表索引相同的记录进行合并，即将相同索引的数值进行求和运算，输出按照key值升序进行输出。 方法一：利用python中的字典进行模拟求解 （哈希表） 使用python下的dict（C++/C中可以使用map/unordered_map达到相似的效果）对相同索引下的记录数字进行相加后输出。 时间复杂度:O(Nlog(N))O(Nlog(N))O(Nlog(N))，解释：需要对所有输入的操作进行处理，时间复杂度O(N)O(N)O(N)，排序时间复杂度O(Nlog(N))O(Nlog(N))O(Nlog(N))。 空间复杂...

题目链接|提取不重复的整数 题意：输入一个 int 型整数，按照从右向左的阅读顺序，返回一个不含重复数字的新的整数。保证输入的整数最后一位不是 0 。 数据范围： 1≤n≤1081\leq n\leq 10^81≤n≤108 输入描述： 输入一个int型整数 输出描述： 按照从右向左的阅读顺序，返回一个不含重复数字的新的整数 方法一：使用数组记录每个数字是否已经出现 (哈希表思想) 因为字符串的范围在0～9，最多只有10种字符。可以从右向左取出数字的每一位，并维护一个数组记录，当前数字是否已经出现。如果当前字符已经出现，该数字不输出，如果当前字符没有出现过，将记录的数组设成1，并输出当前...

题目链接｜字符个数统计 题意：编写一个函数，计算字符串中含有的不同字符的个数。字符在 ASCII 码范围内( 0~127 ，包括 0 和 127 )，换行表示结束符，不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次 例如，对于字符串 abaca 而言，有 a、b、c 三种不同的字符，因此输出 3。 数据范围： 1≤n≤5001\leq n\leq5001≤n≤500 输入描述： 输入一行没有空格的字符串。 输出描述： 输出 输入字符串 中范围在(0~127，包括0和127)字符的种数。 方法一：使用数组记录每种字符是否已经出现 (哈希表思想) 因为字符串的范围在0～127，最...

链接字符串最后一个单词的长度 题意：计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。 （注：字符串末尾不以空格为结尾） 方法一：维护当前单词长度 在输入句子时，由于使用scanf("%s",str)会将空格分割的字符串自动划分，变量str会不断更新为最新的一个不包含空格的字符序列。所以可以维护一个变量len，利用EOF判断字符串输入结束，同时不断更新当前单词长度。这样当读到文件末尾，当前的len即为最后一个单词的长度。 时间复杂度：O(n)O(n)O(n)，空间复杂度：O(1)O(1)O(1) #include <stdio.h> #include &...

二叉树的个数 已知一棵节点个数为 的二叉树的中序遍历单调递增, 求该二叉树能有多少种树形, 输出答案对取模 解法1：动态规划 对于N个节点的树，将其分为三个部分看，根节点，左子树和右子树。我们考虑根节点的取值，可以取1到N，比如取2的时候，左子树即为一颗有一个节点的树，而右节点为节点个数为N-2的树。此时方案数为一个节点的树的方案数乘上N-2个节点的树的方案数（乘法原理）。而对于根节点的不同取值，则进行累加（加法原理）。这样得到递推式： 对于这个公式，我们可以采用递归的记忆化搜索，或者动态规划。这里详细讲述动态规划的解法：当我们需要求解时，都已经求得，这个时候只需要按上面的递推式，逐...

最大公约数 如果有一个自然数 能被自然数 整除，则称 为 的倍数， 为 的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。输入 和 , 请返回 和 的最大公约数。 解法一：暴力做法 设两个数中较大的数为 ，较小的数为 。循环暴力求解， 从 开始循环，到 停止，判断当前 是否能同时整除和，如果可以，退出循环。时间复杂度：，空间复杂度:。 解法二：辗转相除法 辗转相除法大致过程是这样的：用两个数中较大的数除以较小的数，如果能整除，那么较小的数就是所求的最大公约数。如果不能整除，使用余数来除刚才的除数；再用...

kmp算法 描述 给你一个文本串S，一个非空模板串T，问S在T中出现了多少次

几步可以从头跳到尾 描述 给你一个长度为 的数组 。 表示从 这个位置开始最多能往后跳多少格。求从 1 开始最少需要跳几次就能到达第 个格子。 复杂度要求： 解法1:时间复杂度： 空间复杂度： 解法2:时间复杂度： 空间复杂度：

主持人调度 描述有n个活动即将举办，每个活动都有活动的开始时间与活动的结束时间，第i个活动的开始时间是,第i个活动的结束时间是,举办某个活动就需要为该活动准备一个活动主持人。一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，活动主持人参与了第i个活动，那么该主持人在,这个时间段不能参与其他任何活动。求为了成功举办这n个活动，最少需要多少名主持人。 这道题的核心思路是在于考察同一时刻最多有多少场活动同时进行。 解法1: 遍历时刻先根据所有活动的起止时间，获得最先开始的时间和最后开始的时间。因为所有的起止时间都是整数，所以我们可以按整数进行遍历。并对每一时刻...