JavaInterview JavaInterview
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)

『Java面试+Java学习』
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)
  • 指南
  • 简历

  • Java

  • 面试

  • 算法

  • algorithm
  • leetcode
JavaInterview.cn
2024-03-24
目录

猜猜这个单词Java

文章发布较早,内容可能过时,阅读注意甄别。

# 题目

给你一个由 不同 字符串组成的单词列表 words ,其中 words[i] 长度均为 6 。words 中的一个单词将被选作秘密单词 secret 。

另给你一个辅助对象 Master ,你可以调用 Master.guess(word) 来猜单词,其中参数 word 长度为 6 且必须是 words 中的字符串。

Master.guess(word) 将会返回如下结果:

  • 如果 word 不是 words 中的字符串,返回 -1 ,或者
  • 一个整数,表示你所猜测的单词 word 与 秘密单词 secret 的准确匹配(值和位置同时匹配)的数目。 每组测试用例都会包含一个参数 allowedGuesses ,其中 allowedGuesses 是你可以调用 Master.guess(word) 的最大次数。

对于每组测试用例,在不超过允许猜测的次数的前提下,你应该调用 Master.guess 来猜出秘密单词。最终,你将会得到以下结果:

  • 如果你调用 Master.guess 的次数大于 allowedGuesses 所限定的次数或者你没有用 Master.guess 猜到秘密单词,则得到 "Either you took too many guesses, or you did not find the secret word." 。
  • 如果你调用 Master.guess 猜到秘密单词,且调用 Master.guess 的次数小于或等于 allowedGuesses ,则得到 "You guessed the secret word correctly." 。 生成的测试用例保证你可以利用某种合理的策略(而不是暴力)猜到秘密单词。

示例 1:

输入:secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"], allowedGuesses = 10
输出:You guessed the secret word correctly.
解释:
master.guess("aaaaaa") 返回 -1 ,因为 "aaaaaa" 不在 words 中。
master.guess("acckzz") 返回 6 ,因为 "acckzz" 是秘密单词 secret ,共有 6 个字母匹配。
master.guess("ccbazz") 返回 3 ,因为 "ccbazz" 共有 3 个字母匹配。
master.guess("eiowzz") 返回 2 ,因为 "eiowzz" 共有 2 个字母匹配。
master.guess("abcczz") 返回 4 ,因为 "abcczz" 共有 4 个字母匹配。
一共调用 5 次 master.guess ,其中一个为秘密单词,所以通过测试用例。

示例 2:

输入:secret = "hamada", words = ["hamada","khaled"], allowedGuesses = 10
输出:You guessed the secret word correctly.
解释:共有 2 个单词,且其中一个为秘密单词,可以通过测试用例。

提示:

  • 1 <= words.length <= 100
  • words[i].length == 6
  • words[i] 仅由小写英文字母组成
  • words 中所有字符串 互不相同
  • secret 存在于 words 中
  • 10 <= allowedGuesses <= 30

# 思路

根据每个字符串,构建一个字典树,如果树的深度小于等于10,就可以通过10次查询出来

# 解法


class Solution {
    public void findSecretWord(String[] wordlist, Master master) {
        Node node = null;
        for (int i = 0; i < wordlist.length; i++) {
            node = new Node(wordlist[i], 0);
            for (int j = 0; j < wordlist.length; j++) {
                node.add(wordlist[j]);
            }
            if (node.h < 10) {
                break;
            }
        }
        while (node != null) {
            int t = master.guess(node.s);
            node = node.ns[t];
        }
    }
    public int check(String s, String e) {
        char[] ss = s.toCharArray();
        char[] es = e.toCharArray();
        int num = 0;
        for (int i = 0; i < ss.length; i++) {
            if (ss[i] == es[i]) {
                num++;
            }
        }
        return num;
    }
    class Node {
        String s;
        Node[] ns;
        int h;

        public Node(String s, int h) {
            this.s = s;
            ns = new Node[7];
            this.h = h;
        }

        public int add(String e) {
            int t = check(s, e);
            if (ns[t] == null) {
                ns[t] = new Node(e, h + 1);
                return this.h = ns[t].h;
            } else {
                return this.h = ns[t].add(e);
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

# 总结

  • 分析出几种情况,然后分别对各个情况实现
微信 支付宝
最近更新
01
1686. 石子游戏VI Java
09-07
02
1687. 从仓库到码头运输箱子 Java
09-07
03
1688. 比赛中的配对次数 Java
09-07
更多文章>
Theme by Vdoing | Copyright © 2019-2025 JavaInterview.cn
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式