(A卷,100分)- 猜字谜（Java & JS & Python）

题目描述

小王设计了一个简单的猜字谜游戏，游戏的谜面是一个错误的单词，比如nesw，玩家需要猜出谜底库中正确的单词。猜中的要求如下：
对于某个谜面和谜底单词，满足下面任一条件都表示猜中：

变换顺序以后一样的，比如通过变换w和e的顺序，“nwes”跟“news”是可以完全对应的；
字母去重以后是一样的，比如“woood”和“wood”是一样的，它们去重后都是“wod”

请你写一个程序帮忙在谜底库中找到正确的谜底。谜面是多个单词，都需要找到对应的谜底，如果找不到的话，返回”not found”

输入描述

谜面单词列表，以“,”分隔
谜底库单词列表，以","分隔

输出描述

匹配到的正确单词列表，以","分隔
如果找不到，返回"not found"

备注

单词的数量N的范围：0 < N < 1000
词汇表的数量M的范围：0 < M < 1000
单词的长度P的范围：0 < P < 20
输入的字符只有小写英文字母，没有其他字符

用例

输入	conection connection,today
输出	connection
说明	无

输入	bdni,wooood bind,wrong,wood
输出	bind,wood
说明	无

题目解析

本题有点歧义，那就是：

对于某个谜面和谜底单词，满足下面任一条件都表示猜中：

变换顺序以后一样的，比如通过变换w和e的顺序，“nwes”跟“news”是可以完全对应的；

字母去重以后是一样的，比如“woood”和“wood”是一样的，它们去重后都是“wod”

那么如果两个条件都满足的话，算不算猜中呢？

如果两个条件都满足也算猜中的话，那我们直接对谜底和谜面单词进行去重+字典序排序，然后对比即可。

~~如果两个条件都满足不算猜中，只有一个条件满足才算猜中的话，则需要对单词分别进行去重和字典序排序，然后对比两次。~~

~~这里我给出两个情况的实现。~~

2023.02.21 根据机考网友反馈，本题使用“两个条件都满足”的解法可以获得100%通过率

JavaScript算法源码

两个条件都满足也算猜中

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 2) {
    const issues = lines[0].split(",");
    const answers = lines[1].split(",");
    console.log(getResult(issues, answers));
    lines.length = 0;
  }
});

function getResult(issues, answers) {
  const ans = [];

  for (let issue of issues) {
    const str1 = [...new Set(issue)].sort().join("");
    let find = false;

    for (let answer of answers) {
      const str2 = [...new Set(answer)].sort().join("");
      if (str1 === str2) {
        ans.push(answer);
        find = true;
        // break; // 如果一个谜面对应多个谜底，这里就不能break，如果一个谜面只对应一个谜底，那这里就要break，考试的时候都试下
      }
    }

    if (!find) {
      ans.push("not found");
    }
  }

  return ans.join(",");
}

唯一条件满足才算猜中

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 2) {
    const issues = lines[0].split(",");
    const answers = lines[1].split(",");
    console.log(getResult(issues, answers));
    lines.length = 0;
  }
});

function getResult(issues, answers) {
  const ans = [];

  for (let issue of issues) {
    const sorted_issue = [...issue].sort().join(""); // 排序后字符串
    const distinct_issue = [...new Set(issue)].join(""); // 去重后字符串
    let find = false;

    for (let answer of answers) {
      const sorted_answer = [...answer].sort().join(""); // 排序后字符串
      const distinct_answer = [...new Set(answer)].join(""); // 去重后字符串

      if (
        sorted_issue === sorted_answer ||
        distinct_issue === distinct_answer
      ) {
        ans.push(answer);
        find = true;
        // break; // 如果一个谜面对应多个谜底，这里就不能break，如果一个谜面只对应一个谜底，那这里就要break，考试的时候都试下
      }
    }

    if (!find) {
      ans.push("not found");
    }
  }

  return ans.join(",");
}

Java算法源码

两个条件都满足也算猜中

import java.util.ArrayList;
import java.util.Scanner;
import java.util.StringJoiner;
import java.util.TreeSet;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    String[] issues = sc.nextLine().split(",");
    String[] answers = sc.nextLine().split(",");

    System.out.println(getResult(issues, answers));
  }

  public static String getResult(String[] issues, String[] answers) {
    ArrayList<String> ans = new ArrayList<>();

    for (String issue : issues) {
      String str1 = getSortedAndDistinctStr(issue);
      boolean find = false;

      for (String answer : answers) {
        String str2 = getSortedAndDistinctStr(answer);
        if (str1.equals(str2)) {
          ans.add(answer);
          find = true;
          // break; // 如果一个谜面对应多个谜底，这里就不能break，如果一个谜面只对应一个谜底，那这里就要break，考试的时候都试下
        }
      }

      if (!find) {
        ans.add("not found");
      }
    }

    StringJoiner sj = new StringJoiner(",", "", "");
    for (String an : ans) {
      sj.add(an);
    }
    return sj.toString();
  }

  public static String getSortedAndDistinctStr(String str) {
    TreeSet<Character> set = new TreeSet<>();
    for (char c : str.toCharArray()) set.add(c);
    return set.toString();
  }
}

唯一条件满足才算猜中

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String[] issues = sc.nextLine().split(",");
        String[] answers = sc.nextLine().split(",");

        System.out.println(getResult(issues, answers));
    }

    public static String getResult(String[] issues, String[] answers) {
        ArrayList<String> ans = new ArrayList<>();

        for (String issue : issues) {
            String[] issueDeal = getSortedAndDistinctStr(issue);
            boolean find = false;

            for (String answer : answers) {
                String[] answerDeal = getSortedAndDistinctStr(answer);

                if(issueDeal[0].equals(answerDeal[0]) || issueDeal[1].equals(answerDeal[1])) {
                    ans.add(answer);
                    find = true;
                    // break; // 如果一个谜面对应多个谜底，这里就不能break，如果一个谜面只对应一个谜底，那这里就要break，考试的时候都试下
                }
            }

            if(!find) {
                ans.add("not found");
            }
        }

        StringJoiner sj = new StringJoiner(",","","");
        for (String an : ans) {
            sj.add(an);
        }
        return sj.toString();
    }

    public static String[] getSortedAndDistinctStr(String str) {
        char[] arr = str.toCharArray();
        Arrays.sort(arr);
        String sorted_str = new String(arr); // 字典序排序后的字符串

        LinkedHashSet<Character> set = new LinkedHashSet<>();
        for (char c : str.toCharArray()) set.add(c);
        String distinct_str = set.toString(); // 去重后的字符串

        return new String[]{sorted_str, distinct_str};
    }
}

Python算法源码

两个条件都满足也算猜中

# 输入获取
issues = input().split(",")
answers = input().split(",")


# 算法入口
def getResult(issues, answers):
    ans = []

    for issue in issues:
        str1 = "".join(sorted(set(issue)))
        find = False

        for answer in answers:
            str2 = "".join(sorted(set(answer)))

            if str1 == str2:
                ans.append(answer)
                find = True
                # break # 如果一个谜面对应多个谜底，这里就不能break，如果一个谜面只对应一个谜底，那这里就要break，考试的时候都试下

        if not find:
            ans.append("not found")

    return ",".join(ans)


# 算法调用
print(getResult(issues, answers))

唯一条件满足才算猜中

# 输入获取
issues = input().split(",")
answers = input().split(",")


# 算法入口
def getResult(issues, answers):
    ans = []

    for issue in issues:
        sorted_issue = "".join(sorted(issue))
        distinct_issue = "".join(set(issue))
        find = False

        for answer in answers:
            sorted_answer = "".join(sorted(answer))
            distinct_answer = "".join(set(answer))

            if sorted_issue == sorted_answer or distinct_issue == distinct_answer:
                ans.append(answer)
                find = True
                # break # 如果一个谜面对应多个谜底，这里就不能break，如果一个谜面只对应一个谜底，那这里就要break，考试的时候都试下

        if not find:
            ans.append("not found")

    return ",".join(ans)


# 算法调用
print(getResult(issues, answers))

免责声明：

1、IT资源小站为非营利性网站，全站所有资料仅供网友个人学习使用，禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享，本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题，请立即告知本站，本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员，一律视为同意网站规定，本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文

3、原文链接：https://moreit.club/?blog=a%e5%8d%b7100%e5%88%86-%e7%8c%9c%e5%ad%97%e8%b0%9c%ef%bc%88java-js-python%ef%bc%89，转载请注明出处。

2024华为OD机试题库