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

发布于:2024-07-11 ⋅ 阅读:(23) ⋅ 点赞:(0)

(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;
}