程序员进阶之算法练习（六十四）
题目1
题目链接 题目大意： 给出一个字符串（由26个大写字母组成），询问这个字符串中，是否相同的字母都连在一起。
输入： 第一行整数t，表示有t个样例（1≤𝑡≤1000） 每个样例两行，第一行是整数n，表示字符串长度 (1≤𝑛≤50) 第二行是字符串 输出： 如果满足要求，则输出YES； 如果不满足要求，则输出NO；
Examples input 5 3 ABA 11 DDBBCCCBBEZ 7 FFGZZZY 1 Z 2 AB
output NO NO YES YES YES
题目解析： 用一个数组记录已经出现的字符串，从左到右枚举字符串； 对于第i个字符，如果和第i-1个字符不相同，则判断是否出现过： 已出现过则不满足要求； 未出现则标识该字符已出现。
class Solution {
static const int N = 100010;
public:
int n, m;
string str;
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> n;
cin >> str;
int a[256] = {0}, ok = 1;
a[str[0]] = 1;
for (int i = 1; i < n; ++i) {
if (str[i] == str[i-1]) {
continue;;
}
else {
if (a[str[i]]) {
ok = 0;
}
else {
a[str[i]] = 1;
}
}
}
if (ok) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
}
}
ac;题目2
题目链接 题目大意： 给出一个数字n，求出[1,n]的区间中，有多少整数是可以满足，所有数字都是相同的。
输入： 第一行是整数t，表示有t个样例(1≤𝑡≤1e4). 每个样例一行，第一行是整数n(1≤𝑛≤1e9). 输出： 每个样例一行，输出1到n的整数中，有多少个由相同数字组成的数。
Examples input 6 1 2 3 4 5 100
output 1 2 3 4 5 18
题目解析： 如果直接遍历数字1到n，可以算出来有多少个整数满足要求。 因为n比较比较大，这种做法会超时。 注意到满足要求的数字应该不多，我们可以直接满足要求的数字： 先看一位数的有多少个数字； 再看二位数的有多少个数字； ... 直到枚举出来的数字，比n还要大。
class Solution {
static const int N = 100010;
public:
int n, m;
string str;
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> n;
int ans = 0;
int current = 1, cnt = 1;
while (current * cnt <= n) {
++ans;
++cnt;
if (cnt > 9) {
current = current * 10 + 1;
cnt = 1;
}
}
cout << ans << endl;
}
}
}
ac;题目3
题目链接 题目大意： 给出一个数字n，构造n * n的矩阵，要求： 相邻的数字，绝对值之差要大于1； 每个数字可以和上下左右，四个方向的数字相邻； 矩阵中的数字是1~n * n，没有重复；
输入： 第一行是整数t，表示有t个样例 (1≤𝑡≤100). 每个样例第一行是整数𝑛 (1≤𝑛≤100). 输出： 如果有解，则输出n行，每行n个整数； 如果无解则输出-1；
Examples input 3 1 2 3
output 1 -1 2 9 7 4 6 3 1 8 5
题目解析： 1只有一个解，2无解； 从3开始，可以采用间隔的方式先填充数字； 1 0 2 0 3 0 4 0 5 如上，先从上到下，从左到右填充； 最后补齐 1 5 2 6 3 7 4 8 5 因为我们都是间隔着填充，相邻的数字只差，肯定大于1，满足要求。
class Solution {
static const int N = 100010;
public:
int n, m;
int a[101][101];
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> n;
if (n == 1) {
cout << 1 << endl;
}
else if (n == 2) {
cout << -1 << endl;
}
else {
int cnt = 1, x = 0, y = 0;
while (cnt <= n*n) {
a[x][y] = cnt;
++cnt;
y += 2;
if (y >= n) {
x += 1;
y -= n;
}
if (x >= n) {
x = 0;
y = 1;
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << a[i][j] << " ";
}
cout << endl;
}
}
}
}
}
ac;题目4
题目链接 题目大意： 给出n个数字的数组，问数组中存在多少个(i, j)的组合，满足i<j 且 a[j]-a[i]=j-i；
输入： 第一行是整数t，表示t个样例(1≤𝑡≤1e4). 每个样例有2行，第一行是整数n (1≤𝑛≤2⋅1e5) 第二行是n个整数𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤𝑛)
输出： 输出满足要求的组合数量。
Examples input 4 6 3 5 1 4 6 6 3 1 2 3 4 1 3 3 4 6 1 6 3 4 5 6
output 1 3 3 10
题目解析： 将题目要求的 a[j]-a[i]=j-i 换一下位置，得到 (a[j] - j)= (a[i] - i)； 那么将所有的数字，减去当前的位置，然后排序，即可知道每一组数字的数量； 每一组数字假设有k个，那么就有k*(k-1)/2的可能。
class Solution {
static const int N = 200010;
public:
int n, m;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
a[i] -= i;
}
a[n] = 0;
sort(a, a + n);
lld ans = 0, cnt = 1;
for (int i = 1; i<= n; ++i) {
if (a[i] != a[i - 1]) {
ans += cnt * (cnt - 1) / 2;
cnt = 1;
}
else {
++cnt;
}
}
cout << ans << endl;
}
}
}
ac;题目5
题目链接 题目大意： 给出长度为n的字符串，'*'表示绵羊， '.'表示空地； 每次可以把绵羊移动到相邻的空地，问需要移动多少次，才能将所有的绵羊赶在一起。
输入： 第一行是整数t，表示t个样例(1≤𝑡≤1e4). 每个样例有2行，第一行是整数n (1≤𝑛≤2⋅1e5) 第二行是字符串
输出： 最小的移动次数。
Examples input
5
6
**.*..
5
*****
3
.*.
3
...
10
*.*...*.**output 1 0 0 0 9
题目解析： 方法1： 暴力，假设羊最终集中在区间[left, right]上面，枚举left的位置，再用贪心从左到右匹配羊的位置。
方法2： 动态规划 dpLeft[i]表示，前i个位置中的所有羊，都集中在位置i左边； dpRight[i]表示，[i, n]的位置中所有羊，都集中在位置i的右边； 这样只要得到结果之后，只要枚举每一个位置即可。
数据范围较大，没用long long 错了2次。
class Solution {
static const int N = 1000010;
public:
int n, m;
string str;
pair<lld, lld> dpLeft[N], dpRight[N]; // first 是最小代价，second的当前绵羊数量
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> n;
cin >> str;
dpLeft[0] = make_pair(0, 0);
for (int i = 1; i <= n; ++i) {
char c = str[i - 1];
if (c == '*') {
dpLeft[i].first = dpLeft[i-1].first;
dpLeft[i].second = dpLeft[i-1].second + 1;
}
else {
dpLeft[i].first = dpLeft[i-1].first + dpLeft[i-1].second;
dpLeft[i].second = dpLeft[i-1].second;
}
}
dpRight[n+1] = make_pair(0, 0);
for (int i = n; i > 0; --i) {
char c = str[i - 1];
if (c == '*') {
dpRight[i].first = dpRight[i+1].first;
dpRight[i].second = dpRight[i+1].second + 1;
}
else {
dpRight[i].first = dpRight[i+1].first+dpRight[i+1].second;
dpRight[i].second = dpRight[i+1].second;
}
}
lld ans = dpRight[1].first;
for (int i = 0; i <= n; ++i) {
ans = min(ans, dpLeft[i].first + dpRight[i + 1].first);
}
cout << ans << endl;
}
}
}
ac;腾讯云开发者
