笔试强训week2

本文主要是介绍笔试强训week2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

day1

Q1   难度⭐⭐

字符串中找出连续最长的数字串_牛客题霸_牛客网 (nowcoder.com)

题目：
读入一个字符串str，输出字符串str中的连续最长的数字串

输入描述：个测试输入包含1个测试用例，一个字符串str，长度不超过255。

输出描述：在一行内输出str中里连续最长的数字串。

思路：

快慢指针记录更新最长区间

#include <iostream>
#include <string>
using namespace std;string find(string s)
{string ans;int slow = 0;while(slow < s.size()){while(slow < s.size() && s[slow] < '0' || s[slow] > '9')slow ++;int fast = slow + 1;int n = 1;while(s[fast] >= '0' && s[fast] <= '9'){n ++;fast ++;}if(ans.size() < n)ans = s.substr(slow, n);slow = fast;}return ans;
}int main() 
{string s;cin >> s;if(s.empty()){cout << "" << endl;return 0;}cout << find(s) << endl;return 0;
}

 Q2   难度⭐⭐⭐

岛屿数量_牛客题霸_牛客网 (nowcoder.com)

题目：
给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。

岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。

思路：

从左上角开始遍历，碰见“岛屿”将结果+1并多源DFS将“岛屿”变“海洋”

#include <vector>
class Solution 
{
public:int ans = 0;vector<vector<int> > d = {{-1,0},{1,0},{0,-1},{0,1}};vector<int> find = {0,0,0,0};void dfs(int i, int j, vector<vector<char> >& grid){if(i >= grid.size() || i < 0 || j >= grid[0].size() || j < 0 || grid[i][j] == '0'){return;}grid[i][j] = '0';for(int k = 0; k < d.size(); k++){dfs(i + d[k][0], j + d[k][1], grid);}}int solve(vector<vector<char> >& grid) {for(int i = 0; i < grid.size(); i ++)for(int j = 0; j <grid[0].size(); j ++){if(grid[i][j] == '1'){ans ++;dfs(i, j, grid);}}return ans;}
};

Q3   难度⭐⭐⭐

A-拼三角_牛客小白月赛32 (nowcoder.com)

题目：
给出6根棍子，能否在选出3根拼成一个三角形的同时剩下的3根也能组成一个三角形？

输入描述：首先在一行中给出一个 t,，代表测试数据的组数，接下来t行，每行给出6个数字代表棍子长度，棍子长度为正且小于

输出描述：在一行中输出 "Yes" or "No"

思路：

每6个数判断一遍是否能33围成三角形（两边之和大于第三边）

全排列
先sort
再next_permutation

#include <iostream>
#include <algorithm>
using namespace std;bool YES(int a, int b, int c)
{if(a + b > c && a + c > b && b + c > a)  return 1;else return 0;
}int main() 
{int n;cin >> n;while(n--){int s[6];for(int i = 0; i < 6; i++)cin >> s[i];sort(s, s + 6);bool find = 0;do{if(YES(s[0], s[1], s[2]) && YES(s[3], s[4], s[5])){find = 1;break;}} while(next_permutation(s, s + 6));if(find != 0)  cout << "Yes" << endl;else  cout << "No" << endl;}return 0;
}

day2

Q1   难度⭐

求最小公倍数_牛客题霸_牛客网 (nowcoder.com)

题目：
正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。

数据范围：1≤𝑎,𝑏≤100000

思路：

while(c * a % b != 0)  c ++;
最小公倍数为 a * c;

#include <iostream>
using namespace std;int main() 
{int a, b;long long c = 1;cin >> a >> b;while(c * a % b != 0)c ++;cout << a * c;return 0;
}

Q2   难度⭐

数组中的最长连续子序列_牛客题霸_牛客网 (nowcoder.com)

题目：
给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 3,4,5,6为连续的自然数）

数据范围：，

思路：

先排序，再判断前后差值是否为1，并更新记录最长长度

#include <vector>
class Solution 
{
public:int MLS(vector<int>& arr) {if(arr.size() == 1)  return 1;sort(arr.begin(),arr.end());int ans = 1;int tmp = 1;for(int i = 1; i < arr.size(); i++){if(arr[i]-arr[i-1] == 1)tmp += 1;else if(arr[i] == arr[i-1])continue;else  tmp = 1;ans = max(ans, tmp);}return ans;}
};

Q3   难度⭐⭐

字母收集_牛客题霸_牛客网 (nowcoder.com)

题目：
有一个 𝑛∗𝑚 的矩形方阵，每个格子上面写了一个小写字母。
小红站在矩形的左上角，她每次可以向右或者向下走，走到某个格子上就可以收集这个格子的字母。小红非常喜欢 "love" 这四个字母。她拿到一个 l 字母可以得 4 分，拿到一个 o 字母可以得 3 分，拿到一个 v 字母可以得 2 分，拿到一个 e 字母可以得 1 分。
她想知道，在最优的选择一条路径的情况下，她最多能获取多少分？

输入描述：1≤n,m≤500，接下来的 𝑛 行 每行一个长度为 𝑚 的、仅有小写字母构成的字符串，代表矩形方阵。

输出描述：小红最大可能的得分。

思路：

dp（记录从右下角往左或上走，使其结果最大）

#include <iostream>
using namespace std;char s[510][510];
int dp[510][510];int main() 
{int n, m;cin >> n >> m;for(int i = 1; i <= n; i++)cin >> s[i] + 1;for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++){if(s[i][j] == 'l') dp[i][j] = 4;if(s[i][j] == 'o') dp[i][j] = 3;if(s[i][j] == 'v') dp[i][j] = 2;if(s[i][j] == 'e') dp[i][j] = 1;}for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)dp[i][j] = max(dp[i - 1][j] + dp[i][j], dp[i][j - 1] + dp[i][j]);cout << dp[n][m] <<endl;return 0;
}

day3

Q1   难度⭐

添加逗号_牛客题霸_牛客网 (nowcoder.com)

题目：
对于一个较大的整数 N(1<=N<=2,000,000,000)比如 980364535，我们常常需要一位一位数这个数字是几位数，但是如果在这 个数字每三位加一个逗号，它会变得更加易于朗读。因此，这个数字加上逗号成如下的模样：980,364,535请写一个程序帮她完成这件事情

思路：

翻转，再倒序输出（每3位数输出一次","）

#include <bits/stdc++.h>
using namespace std;int main() 
{string n;cin >> n;reverse(n.begin(), n.end());for(int i = n.size() - 1; i >= 0; i --){if((i + 1) % 3 == 0 && i + 1 < n.size())cout << ",";cout << n[i];}return 0;
}

Q2   难度⭐

跳台阶_牛客题霸_牛客网 (nowcoder.com)

题目：
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围：0≤𝑛≤40

要求：时间复杂度：𝑂(𝑛) ，空间复杂度： 𝑂(1)

输入描述：本题输入仅一行，即一个整数 n

输出描述：输出跳上 n 级台阶有多少种跳法

思路：

最简单的dp

#include <iostream>
using namespace std;int main() 
{int n;cin >> n;if(n < 3){cout << n;return 0;}int a[41];a[1] = 1;a[2] = 2;for(int i=3;i<=n;i++)a[i]=a[i-1]+a[i-2];cout<<a[n];return 0; 
}

Q3   难度⭐⭐

扑克牌顺子_牛客题霸_牛客网 (nowcoder.com)

题目：
现在有2副扑克牌，从扑克牌中随机五张扑克牌，我们需要来判断一下是不是顺子。
有如下规则：
1. A为1，J为11，Q为12，K为13，A不能视为14
2. 大、小王为 0，0可以看作任意牌
3. 如果给出的五张牌能组成顺子（即这五张牌是连续的）就输出true，否则就输出false。
4.数据保证每组5个数字，每组最多含有4个零，数组的数取值为 [0, 13]

输入描述：输入五张扑克牌的值

返回值描述：五张扑克牌能否组成顺子。

思路：

记录0的个数，判断是否有重复的牌（非0），计算最大牌与最小牌的差值（非0）是否小于5

class Solution 
{
public:bool IsContinuous(vector<int>& numbers) {sort(numbers.begin(), numbers.end());int king_nums = 0;int i = 0;while(numbers[i] == 0){king_nums ++;i ++;}if(king_nums == 4) return true;int j = i;while(j < numbers.size()){if(numbers[j] == numbers[j - 1])return false;j ++;}return numbers.back() - numbers[i] < 5;}
};

day4

Q1   难度⭐⭐

最长回文子串_牛客题霸_牛客网 (nowcoder.com)

题目：
对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。

数据范围： 1≤𝑛≤10001≤n≤1000

思路：

快慢指针

class Solution 
{
public:int getLongestPalindrome(string A) {int LongestPalindrome = 0;for(int i = 0; i < A.size(); i++){int l = i;int r = i;while(r < A.size() - 1 && A[r] == A[r + 1])  r++;while (l <= r && r < A.size() && A[l] == A[r]) {l --;r ++;}LongestPalindrome = max(LongestPalindrome, r - l - 1);}return LongestPalindrome;}
};

Q2   难度⭐⭐

买卖股票的最好时机(一)_牛客题霸_牛客网 (nowcoder.com)

题目：
假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

1. 你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
2. 如果不能获取到任何利润，请返回0
3. 假设买入卖出均无手续费

输入描述：第一行输入一个正整数 n 表示数组的长度
                  第二行输入 n 个正整数，表示股票在第 i 天的价格

输出描述：输出只买卖一次的最高收益

思路：

每次输入记录当前最小值和与最小值的最大差值

#include <iostream>
#include <algorithm>
using namespace std;int main() 
{int n;cin >> n;int ans = 0, min_price = 0x3f3f3f;int day_prices;for(int i = 0; i < n; i ++){cin >> day_prices;ans = max(ans, day_prices - min_price);min_price = min(min_price, day_prices);}cout << ans << endl;return 0;
}

Q3   难度⭐⭐⭐⭐

[NOIP2002]过河卒 (nowcoder.com)

题目：
如图，𝐴 点有一个过河卒，需要走到目标 𝐵 点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的 C𝐶 点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如图中 𝐶 点上的马可以控制 9 个点（图中的 𝑃1,𝑃2…𝑃8 和 𝐶）。

卒不能通过对方马的控制点

棋盘用坐标表示，𝐴 点的坐标为 (0,0)、𝐵 点的坐标为 (𝑛,𝑚) ，马的位置 𝐶 点的坐标为 (𝑋,𝑌)（约定: 𝐶≠𝐴，同时 𝐶≠𝐵）。

现在要求你计算出卒从 𝐴 点能够到达 𝐵 点的路径的条数。

输入格式：共一行，包含 n,m,X,Y𝑛,𝑚,𝑋,𝑌。

输出格式：一个整数，表示路径条数。

数据范围：1≤𝑛,𝑚≤20，0≤𝑋≤𝑛，0≤Y≤m

思路：

先bfs标记障碍物，再dp从原点到B

#include <iostream>
#include <algorithm>
using namespace std;const int N = 400, M = 400;
typedef long long LL;bool map[N][M];
LL dp[N][M];
bool st[N][M];
pair<int, int> q[M];int dx[] = {0, -2, -2, -1, -1,  1,  1,  2,  2};
int dy[] = {0, -1,  1, -2,  2, -2,  2, -1,  1};
int ddx[] = {0, 1, 0}, ddy[] = {0, 0, 1};int main() 
{int n, m, x, y;cin >> n >> m >> x >> y;n++, m++, x++, y++;map[x][y] = true;for(int i = 1; i <= 8; i ++){int a = x + dx[i], b = y + dy[i];if(a >= 1 && a <= n && b >= 1 && b <= m)map[a][b] = true;}q[0] = {1, 1};dp[1][1] = 1;int hh = 0, tt = 0;while (hh <= tt) {auto t = q[hh++];for(int i = 1; i <= 2; i++){int a = t.first + ddx[i], b = t.second +ddy[i];if(a >= 1 && a <= n && b >= 1 && b <= m && !map[a][b]){dp[a][b] = dp[a - 1][b] + dp[a][b - 1];if(!st[a][b])q[++ tt] = {a, b}, st[a][b] = true;}}}cout << dp[n][m] << endl;return 0;
}

day5

Q1

Q2

Q3

day6

Q1

Q2

Q3

这篇关于笔试强训week2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---