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

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

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

题目难度：一星 考察点：字符串    方法：字符串   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]即交换2和4，此时s="-54321"   当i=3时...

题目难度：二星 考察点：链表合并    方法：链表   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). 输入一个字符串s。   (2). 判断字符串长...

题目难度：一星 考察点：动态规划    方法：动态规划   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。   (3). 按照上状态转移方程进行求解dp...

题目难度：三星 考察点：模拟、双指针    方法：模拟、双指针   1.分析：   这个题我们可以完全采用双指针的做法来解决，因为双指针可以将问题给分隔开，其实这个字符串一共就分为四种情况：   (1). L...L ，在这种情况下，将里面‘.’全部换成'L'； (2). R...L，在这种情况下，将里面左半部分替换为'L'，右半部分替换为'R'，需要注意的是区间长度的奇偶问题 (3). R...R，在这种情况下，将里面‘.’全部换成'R'； (4). L...R，在这种情况下，我们不做任何处理；   那么我们可以采用双指着的做法，首先建立两个指针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，这样能够保证每个区间能够选择两个数且选择出来的个数是最少的是4个。即:   第一个区间选择的是4和5   第二个区间选择的是2和4   第三个区间选...

题目难度：三星 考察点：动态规划、前缀和    方法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]的公式就如上式。   举个例子：假设n=10， w=5， 那么dp[10]可以...

题目难度：三星 考察点：归并排序    方法：归并排序   1.分析：   这个题的本质其实就是求一个逆序数，那么如何求逆序数呢，我们可以采用归并排序的方法。   归并排序：归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 具体操作： 比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[...

题目难度：二星 考察点：贪心    方法：贪心   1.分析：   因为这个题一定要注意的是每艘船最多可同时载两人这个条件，那么其实我们首先需要要将读入进来的体重数组进行排序，然后我们在采用贪心的算法，将最重的人和最轻的人尽可能的放在一条船上，这样保证得到的船只数是最小的，那么我们就要判断最重的人和最轻的人是否能够在一条船上，即判断最重的人和最轻的人是否大于limit的值就可以了，如果最重的人和最轻的人是否大于limit，那么最重的人就可以和最轻的人在一条船上，否则最重的人就只能一个人一条船。在对体重数组排序完成后，我们可以采用双指针的方法来求解答案，即设置l=0， r=n-1，其中l表示较轻...

题目难度：二星 考察点：动态规划    方法：动态规划   1.分析：   这是一道比较典型的动态规划问题，我们设dp[n]表示字符串前n个数字所有的解码方案，那么其实一共有26个英文字母，即对应着1-26这么多数字，而1-9是一位的，10-26是两位的，那么就存在如下两种情况：   a. 第n-2个数字和第n-1个数字组合起来的十进制数不超过26，那么此时dp[n] = dp[n-1] + dp[n-2]   b. 其它情况，dp[n] = dp[n-1]   所以有如下状态转移方程：        算法实现：  (1). 输入一个字符串s，初始化dp[0]=1。 (2). 遍历字符串，然后...

题目难度：一星 考察点：组合数学    方法：组合数学   1.分析：   对于这个题来说，一个员工可以缺勤不超过两天，那么就有如下三种情况：   a. 缺勤0天   b. 缺勤1天   c. 缺勤2天   那么我们只需要将上述三种情况的方法数加起来就可以了，即ans = f(a)+f(b)+(c)。   假设员工缺勤了x天，根据组合数学，那么缺勤x天的方法数就有C(n,x)，即从n天中选x天进行缺勤。所以我们根据上述三种情况，就是相当于求当x=0,1,2的情况下C(n,x)的和，即ans=C(n,0)+C(n,1)+C(n,2)。其中C(n,0)=1, C(n,1)=n, C(n,...