SandMonth - 个人主页动态 - 牛客网

发布(36) 刷题

2021-10-14 17:02

题解 | #牛牛算数#

NC637 牛牛算数 给你一个含有n个元素的数组arr[i]，问这个数组的中位数大还是平均数大，如果中位数更大输出1，如果平均数更大输出-1，如果中位数和平均数相等输出0 案例 输入：[6,6,6,6,5,8] 返回值：-1 说明：中位数6，平均数约等于6.17，所以输出-1 方法一: 模拟 对原先的序列进行排序,如果n为偶数取正中间的两位做中位数也就是(n/2和n/2−1)(n / 2 和 n / 2 - 1)(n/2和n/2−1)位，如果n位奇数则中位数为(n/2)(n / 2)(n/2).然后在遍历一遍求平均数做对比即可 class Solution { public: ...

0 点赞评论收藏

转发

2021-10-18 14:12

已编辑

题解 | #简单的变换#

NC638 简单的变换 给你一个正整数n，重复进行以下操作： 1.如果n是奇数，令n=n−3 2.如果n是偶数，令n=n/2 重复上述直至n=0停止，请输出进行操作的次数，如果n永远无法变成零，输出-1 案例 输入：9 返回值：3 说明： 1.9->6(9-3=6) 2.6->3(6/2=3) 3.3->0(3-3=0) 三步操作后n变为0，所以返回3。 方法一 数学 如果n是3的倍数则说明不可能减到0否则暴力计算,题目中规定每次可以选n-3 和 n/2，很明显一个数n到0的最后一步一定是-3，以此往前推,假设n不是为的倍数那么最后一步一定小于3且大于0，例如8不是3...

0 点赞评论收藏

转发

2021-10-13 01:32

题解 | #走网格#

NC641 走网格 一个nxm的网格中，起点在(1,1)，终点在(n,m)，网格中有一块不能走的矩形区域，左下坐标为(x0,y0)，右上坐标为(x1,y1)，求从起点到终点的路径条数。 案例 输入：4,4,2,2,3,3 返回值：2 说明：只有两条可达路径 方法一:记忆搜索 走到(i,j)的方法有两种一种是从上到下一种是从左到右,所以能得出第(i,j)的数量 = (i - 1,j)的数量 + (i, j - 1)的数量，然后开个二维数组dp记录每一位的方案数，考虑递归返回的情况有:\ (i,j)出界了 返回0 (i,j)在非法范围内 返回0 (i,j)走过了 返回dp[i][j]dp...

0 点赞评论收藏

转发

2021-10-13 01:01

已编辑

题解 | #石头、剪刀、布I#

NC642 石头、剪刀、布I Alice和Bob打牌，每人都有n张牌 Alice的牌里有p1张石头牌，q1张剪刀牌，m1张布牌。 Bob的牌里有p2张石头牌，q2张剪刀牌，m2张布牌。 Alice知道Bob每次要出什么牌，请你安排策略，使Alice获胜次数最多。 输出获胜次数。 案例 输入：6,2,2,2,2,2,2 返回值：6 说明： Alice可以在Bob出石头的时候出布，在Bob出布的时候出剪刀，在Bob出剪刀的时候出石头，按照这个策略Alice最多能赢下所有的比赛，所以最多能赢6局 方法一: 暴力 对于Alice的石头牌 和Bob的剪刀牌互减 直到有一方没有牌为止 对于Alic...

0 点赞评论收藏

转发

2021-10-14 17:06

已编辑

题解 | #构建乘积数组#

构建乘积数组 给定一个数组A[0,1,...,n−1]A[0,1,...,n-1]A[0,1,...,n−1],请构建一个数组B[0,1,...,n−1]B[0,1,...,n-1]B[0,1,...,n−1],其中B中的元素B[i]=A[0]∗A[1]∗...∗A[i−1]∗A[i+1]∗...∗A[n−1]B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]B[i]=A[0]∗A[1]∗...∗A[i−1]∗A[i+1]∗...∗A[n−1]。不能使用除法。（注意：规定B[0]=A[1]∗A[2]∗...∗A[n−1]，B[n−1]=A[0]∗A[1]∗...

0 点赞评论收藏

转发

2021-10-14 17:06

已编辑

题解 | #二维数组中的查找#

二维数组中的查找 在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 [ [1,2,8,9], [2,4,9,12], [4,7,10,13], [6,8,11,15] ] 给定 target = 7，返回 true。 给定 target = 3，返回 false。 进阶：空间复杂度 O(1)O(1) ，时间复杂度 O(n+m)O(n+m) 案例 输入：7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11...

0 点赞评论收藏

转发

2021-10-18 14:02

已编辑

题解 | #牛牛爱奇数#

牛牛爱奇数 在牛牛面前放着nnn个数，这些数字既有奇数也有偶数，只不过牛牛对奇数情有独钟，他特别想让这些数都变成奇数。 现在牛牛获得了一种能力，他可以执行一种操作：每次选中一个偶数，然后把这些数中与该数相等的数都除以222，例如现在有一个数组为[2,2,3][2,2,3][2,2,3]，那么牛牛可以执行一次操作，使得这个数组变为[1,1,3][1,1,3][1,1,3]。 牛牛现在想知道，对于任意的nnn个数，他最少需要操作多少次，使得这些数都变成奇数？ 输入：3,[2,2,3] 返回值：1 说明：只需做一次操作，会将其中的偶数2都变成1，满足了所有的数都是奇数的要求。 方法一:set...

0 点赞评论收藏

转发

2021-10-18 14:01

已编辑

题解 | #牛牛的分配#

牛牛的分配 长度为nnn的数组，每次可以选这若干元素使元素的值变味这些元素的和的平均值，给出数组的数字xxx，求经过操作数组中最多有多少个数字不小于xxx 案例： 输入: 3,7,[9,4,9] 输出: 3 一开始有3个数字，分别为9，4，9，x为7操作这3个数字后每个数字都不小于x 方法一： 排序 元素从大到小排序，每次选取最大的值加到总和中如果加入当前值后平均数小于x则说明添加后面的数也无法大于x class Solution { public: int arrange(int n, int x, vector<int>& a) { /...

0 点赞评论收藏

转发

2021-09-19 22:52

已编辑

题解 | #简单变向#

简单变向 牛牛准备在一个3行n列的跑道上跑步。一开始牛牛位于(1,1)。当牛牛位于第i行第j列时，他可以的下一步最多可能有三种选择： 跑到第i行第j+1列 跑到第i-1行第j+1列（如果i=1则不可以这么跑）。 跑到第i+1行第j+1列（如果i=3则不可以这么跑）。跑道上有一些格子设置了路障(一个格子可能有多个路障)，牛牛不能跑到路障上。现在牛牛想知道，从(1,1)到(3,n)有多少条不同的路径？为了防止答案过大，答案对1e9+7取模。 案例说明输入：4,1,[1],[2]返回值：2说明：在第一行第二列的位置有一个障碍牛牛有两种跑法： (1,1)->(2,2)->(2,...

0 点赞评论收藏

转发

2021-09-19 22:51

已编辑

题解 | #好多牛牛#

好多牛牛 给出一个字符串S，牛牛想知道这个字符串有多少个子序列等于"niuniu"子序列可以通过在原串上删除任意个字符(包括0个字符和全部字符)得到。为了防止答案过大，答案对1e9+7取模 案例输入："niuniniu"返回值：3说明：删除第4，5个字符可以得到"niuniu"删除第5，6个字符可以得到"niuniu"删除第6，7个字符可以得到"niuniu" 方法一 动态规划 定义一个二维dp数组表示当到达s数组第i位时取到niuniu字符串第j位的所有子序列，然后考虑两种情况 &#...

0 点赞评论收藏

转发

2021-09-19 22:50

已编辑

题解 | #又见台阶#

又见台阶 一共又n层台阶有些台阶上有积水，牛牛一开始在第0层，它每次可以跳奇数层台阶，他想跳到第n曾，但他不想在跳跃的过程中跳到有积水的台阶，现在已知有m个台阶上有积水，问牛牛在不跳到积水台阶的情况下跳到第n层有多少种跳法， 答案对取模 案例输入：9,3,[1,3,5]返回值：2说明：因为1，3，5都不能走，所以第一步可以跳到第7层或者第9层所以一共两种方案： 第一步跳7，第二步跳1，第三步跳1 第一步跳9 方法一 模拟 遍历所有台阶对于第i个有3种情况 如果台阶上有积水，则跳过当前台阶不统计当前台阶的次数 如果台阶上没有积水，且当前的台阶是奇数，则当前台阶的次数最少为1因为可以...

0 点赞评论收藏

转发

2021-09-19 22:50

已编辑

题解 | #牛妹的项链#

牛妹的项链 有一个项链共有n个珠子,每个珠子都有一个颜色,这n珠子构建成一个环,牛妹想要一段最长的珠子其中同一个颜色不出现两次。 案例输入：4,[3,1,1,2]返回值：3说明：牛妹可以选择在第3个珠子的左边和右边各切一刀，截取第4个，第1个和第2个珠子连起来的连续珠子。 方法一 暴力 遍历a中的每一个珠子i，每次从第i个珠子开始往后遍历记录最长不重复颜色的珠子长度。 class Solution { public: int solve(int n, vector<int>& a) { // write code here int...

0 点赞评论收藏

转发

2021-09-19 22:50

已编辑

题解 | #相似和#

相似和 给出n个字符串串,定义两个字符串的相似度为他们的最长公共前缀长度求 案例输入：3,["niuniu","niumei","niuneng"]返回值：10说明："niuniu"与"niumei"的相似度为3"niuniu"与"niuneng"的相似度为4"niumei"与"niuneng"的相似度为3所以相似度的总和为10 方法一 暴力 遍历字符串数组对于第i个字符串需要再遍历i之后的所有字符串与第i字...

0 点赞评论收藏

转发

2021-09-19 22:49

已编辑

题解 | #原根#

原根 题目:给出n个只包含小写字母'a'~'z'的字符串，我们称一个字符串为原根，当且仅当给出的其他任何字符串都不是它的前缀。 案例输入：3,["a","ab","ba"]返回值：2说明："a"是原根因为"a"是"ab"的前缀，所以"ab"不是原根"ba"是原根 方法一 暴力 暴力的遍历每一个字符串与其他字符串是否为该字符串的前缀即可，如果存在有一个字符串为该字符串的前缀则该字符串不是原根 class Solution { pu...

0 点赞评论收藏

转发

2021-09-19 22:49

已编辑

题解 | #打字#

打字 按照时间顺序给出牛妹按下的键（以字符串形式给出,'<'代表回退backspace，其余字符均是牛妹打的字符，字符只包含小写字母与'<'），牛妹想知道最后在屏幕上显示的文本内容是什么。若为空则返回一个空串。 案例输入："acv<"返回值："ac"说明： 前面三个字符串输入完后最后一个字符为回退所以答案为ac 方法一 STL队列 使用deque队列存储字符,遍历给定字符串如果当前遍历到字符则将字符存入队列中,如果遇到'<'时将队列中最后一个元素弹出最后将元素转为字符串输出即可 class Solution { publi...

0 点赞评论收藏

转发

工具箱

TA的圈子

TA的笔记

牛客网
牛客企业服务