9.18 字节笔试编程题题解
// 先占个坑，笔试结束发题解。
总的来说，4题都不难，甚至第4题30分还是力扣中等题。
1.
给你一些盘子，每个盘子有一个编号，你需要将这些盘子按顺序收拾起来。
盘子叠放后被分成多个堆，每个堆可能由一个或多个盘子组成。
叠放在同一堆的盘子的序号都是不间断递增的，并且盘子数量至少是3个
输入：一个固定长度的递增整数数组
输出：一个字符串，每个堆被逗号分隔开，如果堆中只有一个盘子，就用序号表示。
如果堆中有多个盘子，用 [起始编号]-[终止编号] 表示
示例：
输入：[-3,-2,-1,2,10,15,16,18,19,20] （这里不是直接输入整数，可能有些同学不会处理IO...，可以学一下，华为笔试题IO就是这种风格）
输出: -3--1,2,10,15,16,18-20
给你一些盘子，每个盘子有一个编号，你需要将这些盘子按顺序收拾起来。
盘子叠放后被分成多个堆，每个堆可能由一个或多个盘子组成。
叠放在同一堆的盘子的序号都是不间断递增的，并且盘子数量至少是3个
输入：一个固定长度的递增整数数组
输出：一个字符串，每个堆被逗号分隔开，如果堆中只有一个盘子，就用序号表示。
如果堆中有多个盘子，用 [起始编号]-[终止编号] 表示
示例：
输入：[-3,-2,-1,2,10,15,16,18,19,20] （这里不是直接输入整数，可能有些同学不会处理IO...，可以学一下，华为笔试题IO就是这种风格）
输出: -3--1,2,10,15,16,18-20
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v;
char c;
int x;
while (~scanf("%c", &c) && c != ']') {
scanf("%d", &x);
v.push_back(x);
}
const int n = v.size();
for (int i = 0; i < n; i++) {
int j = i;
while (j+1 < n && v[j+1] == v[j]+1) j++;
if (j-i+1 >= 3) {
printf("%d-%d", v[i], v[j]);
} else {
if (i == j) {
printf("%d", v[i]);
} else {
printf("%d,%d", v[i], v[j]);
}
}
i = j;
if (i < n-1) putchar(',');
}
return 0;
} 2. 题目太长了，我不想写。思路就是：自底向上模拟一遍就完事了，动态更新下面一层能够存在的砖头。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
if (n == 0) {
cout << 0 << endl;
return 0;
}
int p, m;
cin >> m;
int ans = m;
vector<int> lstLevel;
for (int i = 0; i < m; i++) {
cin >> p;
lstLevel.push_back(p);
}
for (int i = 1; i < n; i++) {
cin >> m;
vector<int> t;
for (int j = 0; j < m; j++) {
cin >> p;
int pr = p+100, pm = p+50;
auto idx = lower_bound(lstLevel.begin(), lstLevel.end(), p) - lstLevel.begin();
bool ok = false;
if (idx < lstLevel.size() && lstLevel[idx] < pm) ok = true;
else if (idx && pm < lstLevel[idx-1]+100) ok = true;
else if (idx < lstLevel.size() && pr > lstLevel[idx] && idx && lstLevel[idx-1]+100 > p) ok = true;
if (ok) {
ans ++;
t.push_back(p);
}
}
lstLevel = std::move(t);
}
cout << ans << endl;
return 0;
} 3. 给定一个只包含0和1的正整数序列，求最长神奇数列的长度。
神奇数列是指没有相邻两个数相同且长度至少是3的数列。如10101,010
输入：一行连续的数，只有0和1
输出：神奇数列的长度
神奇数列是指没有相邻两个数相同且长度至少是3的数列。如10101,010
输入：一行连续的数，只有0和1
输出：神奇数列的长度
// 思路没啥好讲的，扫一遍就行了，很简单
#include <bits/stdc++.h>
using namespace std;
int main() {
string s; cin >> s;
const int n = s.length();
int ans = 0;
for (int i = 0; i < n; i++) {
int j = i;
while (j+1 < n && s[j+1] != s[j]) j++;
if (j-i+1 >= 3)
ans = max(ans, j-i+1);
i = j;
}
cout << ans << endl;
return 0;
} 4. 经典二分+前缀和，考过很多了。 给定一个长度为4倍数的字符串，只由ASDF四个字母构成，要求替换一个子串使整个串中4个字母的个数一同。
求满足要求的最小子串长度
输入：一个字符串
输出：满足条件的最小字串长度
示例1：
输入： ADDF
输出： 1
示例2：
输入：ASAFASAFADDD
输出：3 (替换AFA)
求满足要求的最小子串长度
输入：一个字符串
输出：满足条件的最小字串长度
示例1：
输入： ADDF
输出： 1
示例2：
输入：ASAFASAFADDD
输出：3 (替换AFA)
// C++ 版本
#include <bits/stdc++.h>
using namespace std;
int main() {
string s; cin >> s;
const int n = s.length();
int target = n/4;
vector<int> cnt(4);
vector<vector<int>> ps(n+1, vector<int>(4));
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 4; j++) ps[i][j] = ps[i-1][j];
if (s[i-1] == 'A') ps[i][0] ++;
if (s[i-1] == 'S') ps[i][1] ++;
if (s[i-1] == 'D') ps[i][2] ++;
if (s[i-1] == 'F') ps[i][3] ++;
}
auto ck = [&] (int m) -> bool {
for (int i = 1; i <= n-m+1; i++) {
// 除了i开始长度为m的连续子串，设其为s，整个串中剩下的字符个数。因为s中的字母可以替换成任意字符，所以只需要剩下的字符个数不超过目标个数就行。
vector<int> t(4);
for (int k = 0; k < 4; k++) t[k] = ps[n][k] - ps[i+m-1][k] + ps[i-1][k];
if (*max_element(t.begin(), t.end()) <= target) return true;
}
return false;
};
int ans = n;
int l = 1, r = n;
while (l <= r) {
int m = (l+r)/2;
if (ck(m)) {
ans = m;
r = m-1;
} else {
l = m+1;
}
}
cout << ans << endl;
return 0;
} // Go 语言版本 package main
import "fmt"
func balancedString(s string) int {
n := len(s)
ps := make([][]int, n+1)
for i := range ps {
ps[i] = make([]int, 4)
}
for i, c := range s {
for j := range ps[i] {
ps[i+1][j] = ps[i][j]
}
if c == 'A' {
ps[i+1][0] += 1
}
if c == 'S' {
ps[i+1][1] += 1
}
if c == 'D' {
ps[i+1][2] += 1
}
if c == 'F' {
ps[i+1][3] += 1
}
}
if ps[n][0] == ps[n][1] && ps[n][0] == ps[n][2] && ps[n][0] == ps[n][3] {
return 0
}
ck := func(m int) bool {
for i := 1; i <= n-m+1; i++ {
t := make([]int, 4)
for j := range t {
t[j] = ps[n][j] - ps[i+m-1][j] + ps[i-1][j]
}
if max(max(t[0], t[1]), max(t[2], t[3])) <= n/4 {
return true
}
}
return false
}
l, r, ans := 1, n, n
for l <= r {
m := (l + r) / 2
if ck(m) {
ans = m
r = m - 1
} else {
l = m + 1
}
}
return ans
}
func max(a, b int) int {
if a >= b {
return a
}
return b
}
func main() {
var s string
fmt.Scan(&s)
fmt.Println(s)
fmt.Println(balancedString(s))
} 
查看7道真题和解析