题目难度：简单难度 知识点：字符串、数组 题解 首先考虑：将输入的字符串进行拆分转化为数组（该过程见代码）。其次：怎样判断是否越界，两种方法： 方法（一） 构造一个辅助数组，初始值为0，已经访问过的下标将其值设置为1。跳转到某个下标处是，判断辅助数组其下标处的值是否为1，若为1，则不能跳出，输出flase。对于ture的情况，判断条件为，得到的下标值小于0或者大于等于数组长度。 #include <iostream> #define Maxn 1000 using namespace std; int a[Maxn] ; int b[Maxn] ;//辅助数组 int main(...

字符串旋转 解析问题：对于输入字符串通过“；”拆分为字符串A和B。首先判断字符串A和B的长度是否相同，若不同直接输出flase，若相同进一步判断A是否可以通过旋转得到B： 暴力求解（一）： 根据字符串A的长度L，通过循环从字符串下标1到L-2处拆分为两个字符串str1和str2,再将两者按照str2 str1的顺序组成新字符串A1与B进行比较，若A1与B相同，跳出循环输出true,若循环结束没有相同情况输出flase（通过一个标志变量判断是否提前退出循环）。 #include <bits/stdc++.h> using namespace std; int main(){ ...

题目难度：四星 考察点：线段树、区间覆盖、离散化 方法：线段树、区间覆盖 1.分析： 这道题是一个线段树区间覆盖类型的题目，通过题目我们知道，在贴海报的过程中，后面贴的海报会影响前面的海报，即前面的海报会被覆盖。所以这其实就是一个区间的更新，即来一个区间[l,r]，我们对其进行update。所需要的知识就是线段数的区间更新。这一类题目也可以理解为是线段的互相覆盖，在更新过程中，动态的获取线段的并或者是区间的个数等等信息。那么在这里说一下怎么进行的区间覆盖，对于第i个区间[l,r]来说，相当于是利用i来表示覆盖的海报，所以就是相当于对[l,r]进行覆盖，即...

题目难度：三星 考察点：dfs 方法：dfs 1.题意： 由于给的题面是英文的，所以在这里先简单介绍一下题意，给定一个字符串S和一个包含单词（也是字符串）的字典dic，现在要求 在字符串S中添加若干个空格来组成一个句子，要求构造的单词必须全部在字典dic中出现，输出所有可能的情况。 2.分析： (1). 首先我们要处理的就是输入问题，无疑这个题目的输入是非常恶心的，我们要做的就是得到字符串S和字典dic，怎么得到呢？在这里我们不要采用直接cin的方式，因为读入的字符串中包含空格，所以如果是cin的话遇到空格就停止读入了，所以这里介...

题目难度：三星 考察点：二分 方法1：暴力、排序 1.分析： 其实这个题目我们完全可以以一种特别暴力的做法来做，就是直接输入n^2个数，然后将这n^2个数排序，输出第k个数就可以了，虽然也能过题，但是这样就不能理解这个题真正的做法了，所以这个方法仅仅适合笔试的时候。 2.复杂度分析： 时间复杂度：O(n^2log(n))  空间复杂度：O(n^2) 3.代码：  #include <bits/stdc++.h> using namespace std; int&...

题目难度：二星 考察点：字符串、高精度 方法：高精度 1.分析： 这个题就是一个二进制的加法，其实在转换一下就是一个高精度的加法，我们就按照实际做加法的方法来进行模拟就可以了，具体如下图：       首先将两个字符串a,b倒序，然后保证字符串a是长度比较小的，即如果a的长度大的话，就跟b进行交换。然后我们就模拟现实中的加法，即每一位相加，如果有进位的话，就用一个变量记录下，等下一位进行相加的时候加上进位，然后保留的显然是相加结果之后对2取余，即保留各位，然后等到遍历完a字符串后，剩下...

题目难度：二星 考察点：栈 方法：字符串 1.分析： 这是一个经典的括号匹配问题，只不过需要入栈的元素由一个变成了两个，而且这个题的题意不是很明确，如果包含除了括号之外的字符也是可以的。我们可以采用如下的步骤进行判断： 0. 首先定义一个栈st，栈所包含的元素为字符。 1. 遍历输入的括号序列，如果是'('或者是'['，那么就进栈，即st.push(s[i]); 2. 如果当前遍历到')'，那么首先判断栈是否为空，如果栈为空，那么匹配失败，否则判断栈顶元素是否为'('，如果当前栈顶元素不为'('，则匹配失败 3.&nbsp...

题目难度：一星 考察点：字符串 方法：字符串 1.分析： 这个题的本质其实就是将一个字符串逆序输出，如果是负数的话，就将除了第0位的字符之后的剩余字符串逆序输出就可以了。那么就考虑首位是否为'-'： (1). 如果首位为'-'，那么我们将i从[1, s.size()/2]， 然后交换s[i], s[s.size()-i]，此时就能达到除了第0位之外的剩余字符串逆序了，举个例子: s = "-12345" 当i=1时，交换s[1]和s[5]即交换1和5，此时s="-52341" 当i=2时，交换s[2]和s[4]...

题目难度：二星 考察点：链表合并 方法：链表 1.分析： 其实这个题就是合并两个有序链表，如果按照作弊的方法呢，就可以不把这个东西当作链表，直接把这个东西当作数组，即直接把两个有序数组进行排序，就跟之前说过的归并排序差不多，类似代码如下： int a[15],b[15],c[15]; void Merge_Sort(int n, int m)///n是数组a的长度，m是数组b的长度 {     int i, j, k;  ...

题目难度：一星 考察点：模拟、字符串 方法：模拟 1.分析： 这个题其实很简单了就是直接输出长度为n的子串就可以了，首先判断这个字符串的长度是否小于n，如果小于n，那么直接输出-1。否则就遍历区间，然后输出s.substr(i,n)，这里需要介绍一下substr函数，这个函数是用来求子串的。 用法：s.substr(i,j) 表示获得字符串s中，从第i位开始的长度为j的字符串。 例如字符串s = "abc" 那么s.substr(0,2) 就等于"ab"。 利用substr可以很方便的求子串。 算法实现： ...

题目难度：一星 考察点：动态规划 方法：动态规划 1.分析： 这个题我们采用动态规划的算法，设dp[i][j]表示位于坐标(i,j)时所有的走法数目，那么我们可以想坐标(i,j)可以由什么地方走到，那么显然由于小团只能向右或向下走，所以(i,j)只能由(i, j-1)和(i-1,j)坐标走到，所以就有如下状态转移方程： 初始化所有的dp[0][i] = dp[i][0] = 1。 拿样例来说： 算法实现： (1). 输入一个n, m。 (2). 初始化所有的dp[0][i] = dp[i][0] =...

题目难度：三星 考察点：模拟、双指针 方法：模拟、双指针 1.分析： 这个题我们可以完全采用双指针的做法来解决，因为双指针可以将问题给分隔开，其实这个字符串一共就分为四种情况： (1). L...L ，在这种情况下，将里面‘.’全部换成'L'； (2). R...L，在这种情况下，将里面左半部分替换为'L'，右半部分替换为'R'，需要注意的是区间长度的奇偶问题 (3). R...R，在这种情况下，将里面‘.’全部换成'R'； (4). L...R，在这种情况下，我们不做任何处理； 那么我们可以采用双指着的...

题目难度：三星 考察点：贪心 方法：贪心 1.分析： 这个题我们再来明确一下题意，有n个闭区间[a,b]，现在需要在每个闭区间中选择两个数，要求的是选出来的数的个数最少，拿样例来说： 4 4 7 2 4 0 2 3 6 可以从第一个区间中选择：4,5,6,7 可以从第二个区间中选择：2,3,4 可以从第三个区间中选择：0,1,2 可以从第四个区间中选择：3,4,5,6 那么显然我们可以选出四个数字1,2,4,5，这样能够保证每个区间能够选择两个数且选择出来的个数是最少...

题目难度：三星 考察点：动态规划、前缀和 方法1：动态规划 1.分析： 这个题其实可以采用动态规划的思想来做，我们设 dp[n] 表示的是当前点数为 n 的概率，如果不考虑 K 的话,那么就有dp[n]的公式如下 这里解释一下这个公式，其实就是看dp[n]是怎么来的，假设我们在[1,w]中随机抽取一个整数x，那么dp[n]就可以通过dp[n-x]+x来，即dp[n]=dp[n-x]/w，那么x的可以取值范围为[1,w]，所以dp[n]的公式就如上式。 举个例子：...