描述   这是一篇面对初级coder的题解。 知识点：数学 排序 快速幂 难度：二星    题解   题目： 一共n个人，已知之前站在他们左部分和站在他们右部分的人的人数差的绝对值，求有多少种不同的站法？（结果需要对1e9+7取模） 分析： 本题的关键在于判断队列是否存在，不难发现，站在他左部分和站在他右部分的人的人数差的绝对值是有一定规律的 如下图  之后只需要根据n是奇数和偶数，判断数组是否符合规范即可： 若数组符合规范，则最终结果为  但是由于数字较大，同时模的值也大需要用到   https://blog.nowcoder.net/n/c76abad6cf5d40bc902f3490c9...

描述   这是一篇面对初级coder的题解。 知识点： 数学 快速幂 大数乘法 逆元（费马小定理） 难度： 三星    题解   题目：  ，求f(x)%10000000033的值。        分析： 同上一题有相似之处 区别在于对数据长度的要求更高，输入已经变成了字符串  最近越来越多的协议会定义16字节长的整型，gcc 在 4.6 以上版本就可以使用 __int128_t & __uint128_t 了。   但需要注意的是，_uint128_t & __int128_t 仅对64位程序才有定义，因此如果编译选项中加入了 -m32，会出现找不到定义的编译错误。   另外...

描述   这是一篇面对初级coder的题解。 知识点：数学 快速幂 等比数列 费马小定理 难度：三星    题解   题目： 定义函数 ，然后在给定a和b的情况下，求f(x)%10000000033的值。 分析：   首先需要用等比数列的求和公式对   计算乘方可采用   https://blog.nowcoder.net/n/2e9d602a61804da2b971b16e8807341f   中的快速幂算法   方法一：直接计算   之前的乘方算法化简到最简单依旧需要计算两个大数乘法   long long 是8字节 两个long long相乘就到了是16字节，同时由于由于取模运算的模太大...

描述   这是一篇面对初级coder的题解。 知识点：动态规划 难度：三星    题解   题目： 定义一种新货币，有n(n<=50)种不同的币值，其中币值为 value(value<=50) 的有 w(w<=20) 个。现在你有 x(x<=100) 元，但是你想将 x 元换成若干零钱，请问有多少种换钱的方案？ 分析：   动态规划，但要注意和上楼梯的区别，这个是组合   采用动态规划的方法进行求解：    方法一：二维数组动态规划    记表示用前种货币凑出金额为的方案数量，   初始时，因为每种面值的货币的数量有限，我们要枚举每一个出现的可能数量。   则记第i种货...

描述   这是一篇面对初级coder的题解。 知识点：贪心 难度：二星    题解   题目： 有个项目需要锻炼，对于任意一个项目i分数不能超过目标分数。对于第i个项目已经获得了分。对于第i个项目，牛牛想多获得一分需要花费分钟。 要所有项目的平均分要超过d，达到目标最短还需要多少分钟？   分析： 本题可以用贪心的方式求解 因为必然是要优先练习提分快的科目 贪心算法简介： 贪心算法是指：在每一步求解的步骤中，它要求“贪婪”的选择最佳操作，并希望通过一系列的最优选择，能够产生一个问题的（全局的）最优解。 贪心算法每一步必须满足一下条件： 1、可行的：即它必须满足问题的约束。 2、局部最优：他是当...

描述   这是一篇面对初级coder的题解。 知识点：栈 难度：三星    题解   现在有n个人站成一列，第i个人的身高为 第i个人射击的水弹，就会击中在他前面第一个比他高的人。 对于第i个人，如果他击中了第j个人，则荒唐度加j，如果没有击中任何人，则荒唐度加0,求荒唐度   分析 本题最为简单想到的方式是暴力解法 双重遍历 但能否对结果做优化 避免重复遍历   方法一：暴力求解   双重遍历  class Solution { public: long long solve(int n, vector<int>& a) { long long ans=0;//...

描述   这是一篇面对初级coder的题解。 知识点：生成函数（母函数） 动态规划（背包问题） 难度：四星    题解   自助餐厅里有5个盘子，里面装的都是面包。   第1个盘子里有无限个面包；   第2个盘子里只有1个面包；   第3个盘子里只有4个面包；   第4个盘子里也有无限个面包，但必须两个两个地拿；   第5个盘子里也有无限个面包，但必须5个5个地拿；   给定正整数n，求有多少种正好拿出n个面包的方案。   方案a和方案b不同，当且仅当方案a存在从某个盘子里拿出面包的数量与方案b中对应盘子拿出的数量不同。   分析：这道题乍看和跳台阶的动态规划有些类似 但是那个是排列 这个是组...

描述   这是一篇面对初级coder的题解。 知识点：搜索（BFS、DFS） 二维vector使用 难度：二星    题解     给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。     分析：   由于寻找的岛屿形不规整，动态规划时容易造成岛屿的分离 所以采用搜索算法   对每一个等于“1”的点（岛屿）向其四个方向搜索 为节约空间 采用不保留原数组的形式，直接在原数组上置零：         方法一：深度优先搜索(DFS)   对于每一个等于‘1’的点：...

描述   这是一篇面对初级coder的题解。 知识点：动态规划 二维vector使用 难度：二星    题解   给定一个由'0'和'1'组成的2维矩阵，返回该矩阵中最大的由'1'组成的正方形的面积   分析：   与NC109相比，由于寻找的正方形较为规整 所以可以动态规划                        方法一：暴力求解   遍历数组 对于每一个可能是1的点 循环扩大正方形面积   扩大面积时可按如下方法遍历 保证只遍历一遍：      class Solution { public:     int findsquare(vector<vector...

描述   这是一篇面对初级coder的题解。 知识点：二分法 导数 难度：二星    题解   题目：    山峰元素是指其值大于或等于左右相邻值的元素。给定一个输入数组nums，任意两个相邻元素值不相等，数组可能包含多个山峰。找到索引最大的那个山峰元素并返回其索引。   假设 nums[-1] = nums[n] = -∞。       方法一：线性遍历      class Solution { public:     int solve(int* a, int aLen)&nbs...

描述   这是一篇面对初级coder的题解。 知识点：数组 STL中vector的使用 难度：一星    题解         分析：   正常情况下，需要新建数组，先加入后面k=n-m个元素，然后加入前面m个元素即可   本题的坑主要在于当m>n时 需要    m = m%n;    为了防止右移的长度大于数组的长度，所以才有取余   操作图解如下      方法一：逐个拼接   class Solution { public:     vector<int> solve(int n, int m, vector<int>...

描述   这是一篇面对初级coder的题解。 知识点：冒泡排序 数学知识 难度：二星    题解   给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)。   考察数学知识：乘法负负得正   同时也考察排序的基础知识   题目分析：        目前最大的问题就是找到最小两个数和最大三个数     需要比较：   1、前三大的数相乘 2、最大的数 和 最小的两个数 相乘     方法一：排序后输出   #include <limits.h>//引入最大最小值 class Solution...

描述   这是一篇面对初级coder的题解。 知识点：矩阵 难度：二星    题解      输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵：      [[1,2,3,4], [5,6,7,8], [9,10,11,12], [13,14,15,16]]  则依次打印出数字      [1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]         方法一：转圈打印   思路：记录边界，用循环转圈打印，边界碰撞后结束       class Solution { public:  &...

描述   这是一篇面对初级coder的题解。 知识点：栈 难度：二星    题解   题目：  定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数，并且调用 min函数、push函数 及 pop函数 的时间复杂度都是 O(1)   push(value):将value压入栈中   pop():弹出栈顶元素   top():获取栈顶元素   min():获取栈中最小元素       这道题考察栈的知识：   本题难点是如何维护最小元素，如果用一个单一值来记录最小值，   最小值出栈后就会用O(n)复杂度重新查找，最坏情况时间复杂度O(n)，不符合题目要求   双栈法   ...