当前位置：首页 > news >正文

华为OD机试(C卷,200分)- 字符串拼接、田忌赛马

news 2025/7/18 22:16:31

(C卷,200分)- 字符串拼接

题目描述
给定 M（0 < M ≤ 30）个字符（a-z），从中取出任意字符（每个字符只能用一次）拼接成长度为 N（0 < N ≤ 5）的字符串，
要求相同的字符不能相邻，计算出给定的字符列表能拼接出多少种满足条件的字符串，
输入非法或者无法拼接出满足条件的字符串则返回0。

输入描述
给定的字符列表和结果字符串长度，中间使用空格(" ")拼接

输出描述
满足条件的字符串个数

用例
输入 abc 1
输出 3
说明给定的字符为a,b,c，结果字符串长度为1，可以拼接成a,b,c，共3种
输入 dde 2
输出 2
说明给定的字符为dde，结果字符串长度为2，可以拼接成de,ed，共2种

题目解析
这道题目和46.全排列的区别在与给定一个可包含重复字母的序列，要返回所有不重复的全排列。
还要强调的是去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。
图中我们对同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重。
去重关键代码

if(i>0&&str[i]==str[i-1])continue;

#include <stdio.h>
#include <stdlib.h>
int pathTop=0;
int ansTop=0;
int len=0;
char str[100];
void backtracking(int level,int size,int* used){if(pathTop==size){ansTop++;return;}for(int i=0;i<len;i++){if(i>0&&str[i]==str[i-1])continue;if(used[i])continue;used[i]=1;pathTop++;backtracking(level+1,size,used);used[i]=0;pathTop--;}}
int cmp(const void *a, const void *b) {return *((char *) a) - *((char *) b);
}
int main()
{int size;scanf("%s",str);while(str[len]!='\0'){len++;}//printf("%d\n",len);scanf("%d",&size);qsort(str, len, sizeof(char), cmp);int used[len];for(int i=0;i<len;i++)used[i]=0;backtracking(0,size,used);printf("%d",ansTop);return 0;
}

(C卷,200分)- 田忌赛马

题目描述
给定两个只包含数字的数组a，b，调整数组 a 里面的数字的顺序，使得尽可能多的a[i] > b[i]。
数组a和b中的数字各不相同。
输出所有可以达到最优结果的a数组的结果。

输入描述
输入的第一行是数组 a 中的数字，其中只包含数字，每两个数字之间相隔一个空格，a数组大小不超过10。
输入的第二行是数组 b 中的数字，其中只包含数字，每两个数字之间相隔一个空格，b数组大小不超过10。

输出描述
输出所有可以达到最优结果的 a 数组的数量。

用例
输入 11 8 20
10 13 7
输出 1
说明最优结果只有一个，a = [11, 20, 8]，故输出1
输入 11 12 20
10 13 7
输出 2
说明有两个a数组的排列可以达到最优结果，[12, 20, 11] 和 [11, 20, 12]，故输出2
输入 1 2 3
4 5 6
输出 6
说明 a无论如何都会全输，故a任意排列都行，输出所有a数组的排列，6种排法。

题目解析
本题数量级不大，可以考虑暴力破解。即求解a数组的所有全排列，然后将a数组的每个全排列和b数组逐个元素进行比较，统计每个全排列中a[i] > b[i]的个数biggerCount。我们保留最大的Count 为 maxCount。
最终统计的是a[i] > b[i]的个数为maxCount的全排列的数量。
关于全排列的求解，可以参考：
添加链接描述

本题不需要我们输出具体排列，因此不用定义path记录全排列。

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
int a[MAX_SIZE];
int sizeA=0;
int b[MAX_SIZE];
int sizeB=0;
int maxcount=0;int ans=0;
void backtracking(int level,int* used,int count){if(level>=sizeA){if(count>maxcount){//找到最优结果maxcount=count;ans=1;}else if(maxcount==count){ans+=1;}return;}for(int i=0;i<sizeA;i++){if(used[i])continue;used[i]=1;backtracking(level+1,used,count+(a[i]>b[level]?1:0));used[i]=0;}}
int main()
{while(scanf("%d",&a[sizeA++])){if(getchar()!=' ')break;}while(scanf("%d",&b[sizeB++])){if(getchar()!=' ')break;}int used[MAX_SIZE]={0};backtracking(0,used,0);printf("%d",ans);return 0;
}