题目难度：一星 考察点：字符串、模拟 方法：模拟 1.分析： 根据题意，是要对相邻的字符进行压缩，那么我们可以直接从头开始进行遍历，如果遇到相同的，直接计数，直到遇到相邻字符不相同的，直接输出前一个字符的个数和前一个字符，即用一个记录字符个数的变量ans，初始时ans=1，然后指针i从1开始遍历，如果s[i] == s[i-1]，那么ans++，否则的话输出ans和s[i-1]，同时将ans再次置为1，以方便下次计数。 举个例子： 拿字符串"aaabccccdd"来说，初始化ans = 1, 字符串长度len = 10， 从i = 1开始遍历： 当i = 1时，此时s[1...

题目难度：一星 考察点：回文字符串 方法1：暴力 1. 分析： 这个题我们首先看到的是字符串s的长度才不到50，所以可以使用最简单的暴力枚举就可以解决这个问题。这个问题可以拆分成如下两部分: (1). 如何枚举字符串s的全部子串; (2). 如何判断字符串是否为回文字符串。 对于第(1)部分来说，我们就直接利用两个指针i和j进行枚举，以i(0<=i<len(s))为子串起点，j(i<=j<len(s))为子串终点，对于第(2)部分来说，我们写一个函数判断是否为回文字符串，即第一个和最后一个字符比，第二个和倒数第二个比，即第i个和len(s)-i-1个比，如...

题目难度：二星 考察点：动态规划 方法1：暴力 1. 分析： 这道题类似于完全背包问题，每个货物都可以无限使用，但是要求背包必须装满，而且要求背包中的物品数目最少。由于货物是无限的，那么假设dp[n]表示背包容量为n的能够装满的最少货物个数，如果选择3, 5, 7任意的一种货物重量，那么dp[n-3]、dp[n-5]、dp[n-7]就会是背包容量为n的一种选择，所以问题就转化为了求dp[n-x]，其中x=3、5、7，那么这就是一个递归求解的问题。 举个例子：n=8,求dp[8] 那么dp[8] = min(dp[8-3], dp[8-5], dp[8-7]) + 1 = min(...

题目难度：一星 考察点：字符串 方法1：暴力 1. 分析： 这个题的意思就是给定两个字符串a和b，判断a是不是b的子串或者b是不是a的子串，我们先只考虑一种情况即a是不是b的子串，另外一种情况是一样的，那么对于这种情况来说，我们可以假设a的长度为lena,b的长度为lenb，那么我们可以枚举i从0到lenb-lena,然后j从0到lena，然后判断它们的每一位是不是相等即b[i+j]是不是等于a[j]，如果每一位都相等，那么显然a是b的子串，否则i继续遍历，知道遍历到lenb-lena之后都没有找到与a相等的子串，那么就判定a不是b的子串。 算法实现： (1). 首先输入两个...

题目难度：一星 考察点：合并两个有序数组 方法：合并两个有序数组 1. 分析： 题目的意思就是给定两个有序数组，然后将这两个有序数组进行排序，然后输出，但是不能使用c++内部自定义的sort函数等等。其实这个跟归并排序的想法是差不多的，首先我们假设两个有序数组a和b，长度分别为n和m，那么我们可以创建一个新的数组ans用来保存排序之后的数组，那么我们具体的想法就是定义两个指针i=0和j=0，i指针代表遍历的是a数组，j指针代表遍历的是b数组，然后我们比较a[j]和b[j]，然后把小的那个放在ans数组种。具体表现形式为: if(a[i] < b[j]) ans[k++] =...

题目难度：1星 考察点：组合数学 方法：组合数学 1. 分析 我们分析一下题意，其实这个题就是求给定一个只包含小写字母的字符串，然后在加入一个新的小写字母，看能够组成多少种不同的字符串？这个题我们可以借助高中时候学习的插空法，假设字符串的长度为n，那么就有n+1个空，每个空都有26种（小写字母有26个）选择，所以一共有(n+1)26种方法，但是这些字符串种可能有重复的，所以接下来就是计算重复的字符串个数。这个其实也很容易，对于插入的新字符如果有跟原有字符串s相同的字符，那么此时插入的字符放在前后都是一样的了，所以只需要在原有的计算结果上减掉字符串长度即可，即ans = (n+1)...

题目难度：二星 考察点：动态规划 方法1：暴力、二进制枚举 1. 分析 我们分析一下题意，对于每个输入的字符串s，它的子串(包括不连续的子串)有2^n个，其中n为字符串s的长度，那么我们就可以枚举这2^n个子串，判断当前枚举到子串是不是回文字符串，如果是回文字符串的话，就记录答案，并取得长度最大值进行比较，否则继续枚举。 算法实现： (1). 写一个判断字符串是不是回文字符串的函数； (2). 对这2^n个子串进行枚举； (3). 如果当前枚举的字符串是回文字符串的话，就更新长度最大值ans； (4). 输出答案ans。 2. 复杂度分析： 时间复杂度：O(2^n) ...

题目难度：一星 考察点：字符串、排序 方法：字符串、排序 1. 分析 我们分析一下题意，对于输入的若干个长度小于100的字符串，每个字符串样本的最后六位均是数字，所以首先需要将每一个字符串中的后六位字符（即数字）提取出来，但是需要注意的是提取的后六位数字仍然是一个字符串，此时将字符串转化为数字，然后对若干组数字的大小进行排序输出即可。 举个例子： 输入3组字符串 hygdhi458611 arfgy123478 acg452361 步骤1：将上述三个字符串中的后六位字符提取出来，得到字符串"458611"、"123478"和"452361"。 步骤2：将提取出来的字符串转换为数字...

题目难度：一星 考察点：计数 方法：计数 1. 分析： 根据题意，我们统计26个字母每个字母出现的次数，对于字符串中的每个字符统计个数，具体的统计方法就是用一个计数数组保存个数，即a[s[i]-'a']++,最后再输出的时候判断a[i]是否为0，如果不为0就输出对应的字母和字母统计的个数。 例如："dabcab" 定义i表示遍历的指针。 当i = 0时, a['d'-'a']++ 即a[3] = 1 当i = 1时, a['a'-'a']++ 即a[0] = 1 当i = 2时, a['b'-'a']++ 即a[1] = 1 当i = 3时, a['c'-'a']++ 即a[2]...

题目难度：三星 考察点：动态规划、滚动数组 方法1：动态规划 1. 分析： 这个题的本质就是就一个最大的m段字段和，本质还是动态规划。设一个dp[i][j] 表示以第j个数字结尾的前面j个数字取i段的最大和。那么对于第j个数字来说就有两种选择： (1). 第j个数字属于最后一段，即dp[i][j] = dp[i][j-1] + a[j] (2). 第j个数字不属于最后一段，自己是一个新段，即dp[i][j] = max{dp[i-1][k]} + a[j] 其中i-1<=k<j。 对于dp的状态转移方程就很好写了,就是(1)(2)两种选择的最大值而已，最后输出max{...

题目难度：二星 考察点：动态规划、预处理 方法1：暴力、动态规划 分析： 这个题很像之前的跳台阶：一共有n个台阶，青蛙只能跳1阶或者是2阶，问有多少种跳法？ 跳台阶思路如下: 假设青蛙跳n个台阶的跳法为f(n)那么： 如果第一次跳的是1阶，那么剩下的n-1个台阶，跳法是f(n-1) 如果第一次跳的是2阶，那么剩下的n-2个台阶，跳法是f(n-2) 由此可得：f(n) = f(n-1) + f(n-2) 当n=1时，f(1) = 1 当n=2时，f(2) = 2 至此，跳台阶问题已经解决。 对于这道题来说的话，我们可以借助之前的想法，假设月神有f(n)种方法...

题目难度：三星考察点：排序、最长不下降子序列（O(nlogn)） 方法1：排序、动态规划 分析：根据题意，我们可以首先按照长度（或者是宽度）其中之一进行排序，那么我们接下来就只需要想办法将宽度搭积木的层数变得最多就可以了，将其转化为了最长不下降子序列（因为序列中是可以有相等的情况）的问题，我们就可以运用动态规划的思想进行操作。令dp[i]表示以a[i]结尾的最长不下降子序列长度。那么对于第i个来说就有两种可能：(1). 如果存在a[i]之前的元素a[j]，使得a[i] >= a[j]，那么就把a[i]放在以a[j]结尾的序列后面，找到了一条更长的不下降子序列，此时dp[i] = max...

题目难度：二星考察点：双指针 方法1：暴力、前缀和 分析：我们按照题意进行计算，枚举第一刀下标i和第二刀的下标j即可，然后判断区间[1, i]和区间[j,n]的和是不是相等，如果相等记录答案，取最大值即可。在计算区间和的时候要注意的是需要提前预处理一下前缀和，要不然直接计算区间和的话会使得时间复杂度变高。 算法实现：(1). 首先用一个数组sum计算前缀和。(2). 枚举切两刀的两个下标i和j，计算区间[1,i]和[j,n]的值，那么区间[1,i]的和显然等于sum[i]，区间[j,n]的和则等于sum[n]-sum[j-1]，我们只需要判断这两个是否相等即可，相等则记录答案。(3). 输...

题目难度：二星考察点：贪心、模拟 方法：贪心、模拟 分析：我们分析一下题意，如果想尽可能的让塔的不稳定性小的话，那么就需要让最高塔高度与最低塔高度的差尽可能低，也就是让最高塔的高度尽可能低，最低塔的高度尽可能高。那么我们每次进行操作的时候就是首先将整个高度数组按照从小到大进行排序，然后高度最大值-1，高度最小值+1。一直循环k次， 在每次进行操作的时候分别记录最大值和最小值即可。还需要注意的一点是如果高度最大值-高度最小值<=1的时候，此时就不需要进行操作了，因为此时操作是完全多余的，而题目让我们求的是最少操作次数。举个例子：就拿样例来说，我们可以进行两次操作：第一次操作：我们首先将高...