题目描述 有108个村庄排在一条公路上，依次编号为0~108-1，相邻村庄距离为1，其中有n个村庄居住着牛牛，居住着牛牛的村庄从小到大依次为a0~an-1，其中保证a0=0. 现在需要建设车站，有两个要求必须被满足： 1、每个有牛牛居住的村庄必须修建车站。 2、相邻车站的距离必须为1或为某个质数。 现给出n和a数组，求需要建设车站的最小数量。 题解： 纪念我第一次做这种题，以前都是做竞赛题 题目看似杂乱无序，但其实冥冥中都遵循着规律 没错就是哥德巴赫猜想 哥德巴赫猜想: 任一大于2的偶数都可写成两个素数之和 所以我们可以将题目总结为： 1.当两站之间距离为素数，那两站之间就不用修站了，就光算上...

题目描述 众所周知，牛妹非常喜欢吃蛋糕。 第一天牛妹吃掉蛋糕总数三分之一（向下取整）多一个，第二天又将剩下的蛋糕吃掉三分之一（向下取整）多一个，以后每天吃掉前一天剩下的三分之一（向下取整）多一个，到第n天准备吃的时候只剩下一个蛋糕。 牛妹想知道第一天开始吃的时候蛋糕一共有多少呢？ 题解： 题目问的是第一天吃的什么，给的是吃的天数 如果是正着推： dp[i]表示第i天还没吃蛋糕前，蛋糕的数量 dp[i+1]=dp[i]*(2/3)-1 dp[i]=(dp[i*3]+1)*2/3 模拟上面这个递推式即可 代码： class Solution {  public: /** * * @param n ...

牛客题霸 最少素数拆分 C++题解/答案 题目描述 牛牛刚刚学习了素数的定义，现在给定一个正整数N，牛牛希望知道N最少表示成多少个素数的和。 素数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。 提示 哥德巴赫猜想：任意大于2的偶数都可以拆分成两个质数之和。该猜想尚未严格证明，但暂时没有找到反例。 题解： 结合哥德巴赫猜想， 如果N==2，它就是被自身素数构造的，答案是1 如果N>3&&N是偶合数（也就是大于2的偶数）时，根据猜想可以拆分成两个质数之和，所以答案是2 如果N>3&&N是奇合数时，奇合数=奇数+偶数 如果这个偶数是2&...

[[蓝桥杯][2018年第九届真题]搭积木](https://www.dotcpp.com/oj/problem2292.html)  题目： 小明对搭积木非常感兴趣。他的积木都是同样大小的正立方体。 在搭积木时，小明选取 m 块积木作为地基，将他们在桌子上一字排开，中间不留空隙，并称其为第0层。 随后，小明可以在上面摆放第1层，第2层，……，最多摆放至第n层。摆放积木必须遵循三条规则： 规则1：每块积木必须紧挨着放置在某一块积木的正上方，与其下一层的积木对齐； 规则2：同一层中的积木必须连续摆放，中间不能留有空隙； 规则3：小明不喜欢的位置不能放置积木。 其中，小明不喜欢的位置都被标在了图纸...

牛客题霸 单链表的选择排序 C++题解/答案 题目描述 给定一个无序单链表，实现单链表的选择排序(按升序排序)。 题解： 不可能手写排序，这辈子不可能手写排序。。 基础的链表操作，将链表内的数据存到vector内，然后用sort排序，再将vector内的数据存会数组即可 代码： /** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution {  public: /** * * @param head ListNode类 the head node * @return ListNode类 */...

牛客题霸 转圈打印矩阵 C++题解/答案 题目描述 给定一个整型矩阵matrix，请按照顺时针转圈的方式打印它。 示例1 输入 复制 [[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] 题解： 题意很明确，就是让顺时针走矩阵 直接模拟就行  如图一样，设 int end=n-1; int beg=0; int l=0; int r=m-1;  四个变量，分别表示矩形的上下和左右，然后按照图中红色箭头的顺序一样存入vectorsum内即可 当(end = ...

牛客题霸 单链表的选择排序 C++题解/答案 题目描述 给出一个整数数组，请在数组中找出两个加起来等于目标值的数， 你给出的函数twoSum 需要返回这两个数字的下标（index1，index2），需要满足 index1 小于index2.。注意：下标是从1开始的 假设给出的数组中只存在唯一解 例如： 给出的数组为 {20, 70, 110, 150},目标值为90 输出 index1=1, index2=2 示例1 输入 复制 [3,2,4],6 返回值 复制 [2,3] 题目： 水题。。 直接两个for循环暴力走起 两个for循环看哪两个数之和等于目标值 然后用num俩记录坐标 题解： c...

题目描述 输入一个链表，反转链表后，输出新链表的表头。 示例1 输入 复制 {1,2,3} 返回值 复制 {3,2,1} 题解： 如果用偷懒的方法，可以用vector来存链表内容，然后来个翻转（vector自带）即可 但是，我们不可能光靠这种方法，来讲一下正解  通过图我们可以看出，其实翻转链表，也就是将指向翻转 所以我们需要一个链表s作为存新数据（也就是翻转后的数据） 还需要一个q作为中间变量 链表p为题目所给的pHead 步骤： 先用q存p的下一个节点的地址，这样是因为后续p有其他操作，如果不提前保存会丢失 然后将p->next=s,将当前节点与链表中断，并指向s 然后将s=p， 这...

牛客题霸 二分查找 C++题解/答案 题目描述 请实现有重复数字的有序数组的二分查找。 输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。 示例1 输入 复制 5,4,[1,2,4,4,5] 返回值 复制 3 题解： 二分模板题 如果是学竞赛的应该很懂 二分的本质就像是翻字典，一开始l=0，r=n，先翻到最中间（mid=(r+l)/2），然后看目标单词是在左侧还是右测，如果是在左侧，我们就继续翻左侧的中间页，重复上述操作，l=0,r=mid-1，mid=(l+r)>>1 代码： class Solution {  public: /** * 二分...

牛客题霸 判断链表中是否有环 C++题解/答案 题目描述 判断给定的链表中是否有环 扩展： 你能给出空间复杂度的解法么？ 题解： 在这介绍一个简便的方法：快慢指针 就是：一个指针走两步，一个指针走一步 快慢指针中，因为每一次移动后，快指针都会比慢指针多走一个节点，所以他们之间在进入环状链表后，不论相隔多少个节点，慢指针总会被快指针赶上并且重合，此时就可以判断必定有环。 如果快指针到达NULL，说明链表以NULL为结尾，没有环 为什么要这样？ 如果两个指针只走一步，那就有可能完美错开，无法相遇，所以要造成速度差，使得能相遇 除了能找环，还可以用来找环入口，这里就不细讲了 代码： /** * De...

文章目录    跳台阶   题目描述 题解： 代码：  合并有序链表   题目描述 题解： 代码：  用两个栈实现队列   题目描述 题解： 代码：  括号序列   题目描述 题解： 代码：  两个链表的第一个公共结点   题目描述 题解： 代码：     跳台阶 题目描述 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 题解： 递归的入门题 如果只剩一个台阶，只有一种跳法（一步） 如果还剩两个台阶，有两种跳法（两个一步或者一个两步） 当有n个台阶，可以转化成n-1和n-2两种情况的和 依次递归下去，边界就是n = = 1...

@[toc] 合并两个有序的数组 题目描述 给出两个有序的整数数组A 和B ，请将数组B 合并到数组A 中，变成一个有序的数组注意：可以假设 A数组有足够的空间存放B 数组的元素， A和B 中初始的元素数目分别为 m和n 题解： 将A和B从最后一位开始比，然后存入A中（下标从第m+n-1倒着开始）。当有一个用完后，将另一个数组内的元素全部按顺序存入A中 代码： class Solution { public: void merge(int A[], int m, int B[], int n) { int i = m - 1; int j = n - 1; int k = m + n - 1;...

@[toc] 跳台阶 题目描述 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 题解： 递归的入门题如果只剩一个台阶，只有一种跳法（一步）如果还剩两个台阶，有两种跳法（两个一步或者一个两步）当有n个台阶，可以转化成n-1和n-2两种情况的和依次递归下去，边界就是n = = 1和n = = 2 代码： class Solution { public: int jumpFloor(int number) { if(number==1)return 1; else if(number==2)return 2; else retu...

牛客题霸 判断链表中是否有环 C++题解/答案 题目描述 判断给定的链表中是否有环扩展：你能给出空间复杂度的解法么？ 题解： 在这介绍一个简便的方法：快慢指针就是：一个指针走两步，一个指针走一步快慢指针中，因为每一次移动后，快指针都会比慢指针多走一个节点，所以他们之间在进入环状链表后，不论相隔多少个节点，慢指针总会被快指针赶上并且重合，此时就可以判断必定有环。如果快指针到达NULL，说明链表以NULL为结尾，没有环为什么要这样？如果两个指针只走一步，那就有可能完美错开，无法相遇，所以要造成速度差，使得能相遇除了能找环，还可以用来找环入口，这里就不细讲了 代码： /** * Definition...