Finding if input has exactly one pair and zero or more triplets java

huangapple go评论72阅读模式
英文:

Finding if input has exactly one pair and zero or more triplets java

问题

I am a Java Developer and I was on a interview with an algorithm problem which I cannot seem to solve nor find a solution already for it, but I'm really curious how it can be solved.

Here is the problem.

>You’re working on making some mini-games, and you’ve decided to make a simpler variant of the game Mahjong. In this variant, players have a number of tiles, each marked 0-9. The tiles can be grouped into pairs or triples of the same tile. A “complete hand” is defined as a collection of tiles where all the tiles can be grouped into any number of triples (zero or more) and exactly one pair, and each tile is used in exactly one triple or pair. Write a function that takes a string representing a player’s tiles in no particular order, and returns the string “COMPLETE” if the hand is complete, and “NOT COMPLETE” if it is not. Each tile may only be used in a single group (either a pair or a triple). All tiles must be used to complete a hand. There may be a pair and triples of the same tile. A single pair with no triples (ex: 99) is a valid hand. The input will only consist of characters 0-9.
>
>Examples
>
>These three hands would all return “COMPLETE”:
>
>33344466 -> 333 444 66
This hand can be grouped into a triple of 3s and 4s, and a pair of 6s
>
>55555555 -> 555 555 55
This hand can be grouped into two triples of 5s and a pair of 5s
>
>22 -> 22
This hand is a single pair of 2s (no triples are required)
>
>These three hands would all return “NOT COMPLETE”:
>
>1357
This hand has tiles which cannot be formed into pairs or triples.
>
>335577
This hand has three pairs, a complete hand must have exactly one pair.
>
>666888
This hand has two triples, but no pairs.

英文:

I am a Java Developer and I was on a interview with an algorithm problem which I cannot seem to solve nor find a solution already for it, but I'm really curious how it can be solved.

Here is the problem.

>You’re working on making some mini-games, and you’ve decided to make a simpler variant of the game Mahjong. In this variant, players have a number of tiles, each marked 0-9. The tiles can be grouped into pairs or triples of the same tile. A “complete hand” is defined as a collection of tiles where all the tiles can be grouped into any number of triples (zero or more) and exactly one pair, and each tile is used in exactly one triple or pair. Write a function that takes a string representing a player’s tiles in no particular order, and returns the string “COMPLETE” if the hand is complete, and “NOT COMPLETE” if it is not. Each tile may only be used in a single group (either a pair or a triple). All tiles must be used to complete a hand. There may be a pair and triples of the same tile. A single pair with no triples (ex: 99) is a valid hand. The input will only consist of characters 0-9.
>
>Examples
>
>These three hands would all return “COMPLETE”:
>
>33344466 -> 333 444 66
This hand can be grouped into a triple of 3s and 4s, and a pair of 6s
>
>55555555 -> 555 555 55
This hand can be grouped into two triples of 5s and a pair of 5s
>
>22 -> 22
This hand is a single pair of 2s (no triples are required)
>
>These three hands would all return “NOT COMPLETE”:
>
>1357
This hand has tiles which cannot be formed into pairs or triples.
>
>335577
This hand has three pairs, a complete hand must have exactly one pair.
>
>666888
This hand has two triples, but no pairs.

答案1

得分: 0

这是我的解决方案。
这并不是唯一的解决方案。请参考@Bohemian的评论
(在代码之后是解释。)

import java.util.Arrays;

public class Mahjongs {
    private static final String COMPLETE = "COMPLETE";
    private static final String NOT_COMPLETE = "NOT COMPLETE";

    private static String isComplete(String hand) {
        String msg = "Tile %d is not valid: '%c'";
        String result = COMPLETE;
        if (hand == null) {
            result = NOT_COMPLETE;
        } else {
            hand = hand.strip();
            if (hand.length() < 2) {
                result = NOT_COMPLETE;
            } else {
                char[] tiles = hand.toCharArray();
                Arrays.sort(tiles);
                char last = tiles[0];
                if (!Character.isDigit(last)) {
                    throw new IllegalArgumentException(String.format(msg, 0, last));
                }
                int count = 1;
                int doubles = 0;
                for (int i = 1; i < tiles.length; i++) {
                    if (!Character.isDigit(tiles[i])) {
                        throw new IllegalArgumentException(String.format(msg, i, tiles[i]));
                    }
                    if (tiles[i] == last) {
                        count++;
                        if (count == 3) {
                            count = 0;
                        }
                    } else {
                        if (count == 1) {
                            result = NOT_COMPLETE;
                            break;
                        }
                        if (count == 2) {
                            doubles++;
                            if (doubles != 1) {
                                result = NOT_COMPLETE;
                                break;
                            }
                        }
                        count = 1;
                        last = tiles[i];
                    }
                }
                if (count == 1) {
                    result = NOT_COMPLETE;
                } else if (count == 2) {
                    doubles++;
                }
                if (result.equals(COMPLETE) && doubles != 1) {
                    result = NOT_COMPLETE;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(isComplete("33344466"));
        System.out.println(isComplete("55555555"));
        System.out.println(isComplete("22"));
        System.out.println(isComplete("1357"));
        System.out.println(isComplete("335577"));
        System.out.println(isComplete("666888"));
        System.out.println();
    }
}
  • 方法isComplete是您被要求编写的方法。它接受一个String参数并返回一个String,可以是_COMPLETE_或_NOT_COMPLETE_。
  • 首先,该方法检查其参数的有效性。虽然在问题陈述中没有明确提到,但我认为这是一个很好的做法。
    • 如果方法参数为null,则方法返回_NOT_COMPLETE_,否则...
    • 从参数中删除前导和尾随空格。
    • 如果hand包含至少一个对子,则hand是完整的,因此参数的长度必须至少为2,所以如果长度小于2,则方法返回_NOT_COMPLETE_。
  • 将参数转换为字符数组。
  • 对数组进行排序(因为问题陈述没有明确说明hand已排序)。
  • 将数组的第一个元素保存在变量last中。
    (必须有一个第一个元素,因为此时数组包含至少两个元素。)
  • 从第二个字符开始,迭代数组中的字符。
  • 如果字符不是数字,则方法参数非法,并引发异常。
  • 变量count保存给定字符的连续出现次数。如果count达到3,那么我们有一个三张牌,然后我们重新开始计数。
  • 当“当前”字符与last不同时,如果count等于1,则意味着只有一个数字的连续出现,这意味着hand不完整,因此方法返回_NOT_COMPLETE_。
  • 变量doubles保存“对子”的数量。必须只有一个对子,所以如果我们计数多于一个对子,方法将返回_NOT_COMPLETE_。
  • 当“当前”字符与last不同时,重置last并重置count
  • for循环结束时,检查count的值并根据需要更新doubles
  • 同样,在for循环结束时,检查doubles的值。如果不恰好为1(一个),则方法返回_NOT_COMPLETE_。
  • 最后,返回result的值,它可以是_COMPLETE_或_NOT_COMPLETE_。

运行上述代码将产生以下输出:

COMPLETE
COMPLETE
COMPLETE
NOT COMPLETE
NOT COMPLETE
NOT COMPLETE
英文:

Here's my solution.
It is not the only solution. Refer to the comment from @Bohemian.
(Explanations after the code.)

import java.util.Arrays;

public class Mahjongs {
    private static final String  COMPLETE = &quot;COMPLETE&quot;;
    private static final String  NOT_COMPLETE = &quot;NOT COMPLETE&quot;;

    private static String isComplete(String hand) {
        String msg = &quot;Tile %d is not valid: &#39;%c&#39;&quot;;
        String result = COMPLETE;
        if (hand == null) {
            result = NOT_COMPLETE;
        }
        else {
            hand = hand.strip();
            if (hand.length() &lt; 2) {
                result = NOT_COMPLETE;
            }
            else {
                char[] tiles = hand.toCharArray();
                Arrays.sort(tiles);
                char last = tiles[0];
                if (!Character.isDigit(last)) {
                    throw new IllegalArgumentException(String.format(msg, 0, last));
                }
                int count = 1;
                int doubles = 0;
                for (int i = 1; i &lt; tiles.length; i++) {
                    if (!Character.isDigit(tiles[i])) {
                        throw new IllegalArgumentException(String.format(msg, i, tiles[i]));
                    }
                    if (tiles[i] == last) {
                        count++;
                        if (count == 3) {
                            count = 0;
                        }
                    }
                    else {
                        if (count == 1) {
                            result = NOT_COMPLETE;
                            break;
                        }
                        if (count == 2) {
                            doubles++;
                            if (doubles != 1) {
                                result = NOT_COMPLETE;
                                break;
                            }
                        }
                        count = 1;
                        last = tiles[i];
                    }
                }
                if (count == 1) {
                    result = NOT_COMPLETE;
                }
                else if (count == 2) {
                    doubles++;
                }
                if (result.equals(COMPLETE)  &amp;&amp;  doubles != 1) {
                    result = NOT_COMPLETE;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(isComplete(&quot;33344466&quot;));
        System.out.println(isComplete(&quot;55555555&quot;));
        System.out.println(isComplete(&quot;22&quot;));
        System.out.println(isComplete(&quot;1357&quot;));
        System.out.println(isComplete(&quot;335577&quot;));
        System.out.println(isComplete(&quot;666888&quot;));
        System.out.println();
    }
}
  • Method isComplete is the method you were asked to write. It takes a single, String parameter and returns a String which is either COMPLETE or NOT_COMPLETE.
  • Firstly, the method checks the validity of its parameter. While not explicitly mentioned in the problem statement, I think it's always a good idea to do so.
    • If the method parameter is null, the method returns NOT_COMPLETE, otherwise...
    • Remove leading and trailing spaces from the parameter.
    • hand is complete if it contains at least a single pair, hence the length of the parameter must be at least 2, so if the length is less than 2, the method returns NOT_COMPLETE.
  • Convert the parameter to an array of char.
  • Sort the array (since the question does not explicitly state that hand is sorted).
  • Save the first element of the array in variable last.
    (There must be a first element because, at this point, the array contains at least two elements.)
  • Iterate through the characters in the array, starting from the second character.
  • If a character is not a digit then the method parameter is illegal and the method throws an exception.
  • Variable count holds the number of consecutive appearances of a given character. If count reaches 3, we have a triple and we start counting again.
  • When the "current" character is different to last, then if count equals one, that means there is only a single, consecutive appearance of a digit and that means that the hand is incomplete and therefore the method returns NOT_COMPLETE.
  • Variable doubles holds the number of "pairs". There must only be precisely one double so if we count more than one double, the method returns NOT_COMPLETE.
  • When the "current" character differs from last reset last and also reset count.
  • At the end of the for loop, check the value of count and update doubles if required.
  • Also at the end of the for loop, check the value of doubles. If it is not exactly 1 (one), then the method returns NOT COMPLETE.
  • Finally, return the value of result &ndash; which is either COMPLETE or NOT COMPLETE.

Running the above code produces the following output:

COMPLETE
COMPLETE
COMPLETE
NOT COMPLETE
NOT COMPLETE
NOT COMPLETE

答案2

得分: 0

这个方法实现了重要的部分。根据注释,应该很容易理解。

public static boolean isComplete(String s) {
    // 将字符映射到计数;如果只有数字,可以直接存储在计数数组中
    HashMap<Integer, Integer> map = new HashMap<>();
    s.chars().forEach(c -> map.put(c, map.getOrDefault(c, 0) + 1));
    // 检查是否恰好有1对,以及任意数量的三元组,没有剩余字符
    boolean foundPair = false;
    for (int v : map.values()) {
        v %= 3; // 只保留除以三的余数,因为三元组可以自由忽略
        if (v == 2 && !foundPair) {
            foundPair = true;                
        } else if (v != 0) {
            return false; // 只允许三元组(或1对)!
        } 
    }
    return foundPair;
}
英文:

This method implements the important part. It should be easy to understand given the comments.

public static boolean isComplete(String s) {
// map characters to counts; if only digits, could have just stored in array-of-counts
HashMap&lt;Integer, Integer&gt; map = new HashMap&lt;&gt;();
s.chars().forEach(c -&gt; map.put(c, map.getOrDefault(c, 0)+1));
// check that there is exactly 1 pair, and any number of triples, and no left-overs
boolean foundPair = false;
for (int v : map.values()) {
v %= 3; // keep only remainder modulo-three, as triples can be freely ignored
if (v == 2 &amp;&amp; !foundPair) {
foundPair = true;                
} else if (v != 0) {
return false; // only triples (or 1 pair) allowed!
} 
}
return foundPair;
}

huangapple
  • 本文由 发表于 2023年5月13日 17:23:45
  • 转载请务必保留本文链接:https://go.coder-hub.com/76241980.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定