The observed PIN（4Kyu） - 图1

题目

Alright, detective, one of our colleagues successfully observed our target person, Robby the robber. We followed him to a secret warehouse, where we assume to find all the stolen stuff. The door to this warehouse is secured by an electronic combination lock. Unfortunately our spy isn’t sure about the PIN he saw, when Robby entered it. The keypad has the following layout: ┌───┬───┬───┐ │ 1 │ 2 │ 3 │ ├───┼───┼───┤ │ 4 │ 5 │ 6 │ ├───┼───┼───┤ │ 7 │ 8 │ 9 │ └───┼───┼───┘ │ 0 │ └───┘ He noted the PIN 1357, but he also said, it is possible that each of the digits he saw could actually be another adjacent digit (horizontally or vertically, but not diagonally). E.g. instead of the 1 it could also be the 2 or 4. And instead of the 5 it could also be the 2, 4, 6 or 8.

He also mentioned, he knows this kind of locks. You can enter an unlimited amount of wrong PINs, they never finally lock the system or sound the alarm. That’s why we can try out all possible (*) variations.

  • possible in sense of: the observed PIN itself and all variations considering the adjacent digits

Can you help us to find all those variations? It would be nice to have a function, that returns an array (or a list in Java and C#) of all variations for an observed PIN with a length of 1 to 8 digits. We could name the function getPINs (get_pins in python, GetPINs in C#). But please note that all PINs, the observed one and also the results, must be strings, because of potentially leading ‘0’s. We already prepared some test cases for you.

Detective, we are counting on you!

For C# user: Do not use Mono. Mono is too slower when run your code.

好的，侦探，我们的一个同事成功地观察到了我们的目标，抢劫犯罗比。我们跟着他到了一个秘密仓库，在那里我们可以找到所有被盗的东西。这个仓库的门是用一把电子组合锁固定的。不幸的是，我们的间谍不确定罗比进去时看到的那个PIN。 小键盘具有以下布局： ┌───┬───┬───┐

│ 1 │ 2 │ 3 │ ├───┼───┼───┤ │ 4 │ 5 │ 6 │ ├───┼───┼───┤ │ 7 │ 8 │ 9 │ └───┼───┼───┘ │ 0 │ └───┘ 他注意到了1357号PIN，但他也说，他看到的每一个数字都有可能是另一个相邻的数字（水平或垂直，但不是对角线）。E g.也可以是2或4，而不是1。也可以是2、4、6或8，而不是5。 他还提到，他知道这种锁。你可以输入无限数量的错误PIN，它们永远不会锁定系统或发出警报。这就是为什么我们可以尝试所有可能的（）变化。可能的意义：观察到的引脚本身和所有变化考虑到相邻的数字你能帮我们找到所有这些变化吗？最好有一个函数，它可以返回一个数组（或者Java和C语言中的一个列表），其中包含一个长度为1到8位的观察管脚的所有变量。我们可以将函数命名为getPINs（python中的getu pins，C中的getPINs）。但请注意，所有管脚（观察到的管脚和结果）都必须是字符串，因为可能是前导“0”。我们已经为这些管脚准备了一些测试用例你。警探，我们全靠你了

原题链接

分析

这个问题其实就是如何求笛卡尔积，在这里比较简单，将前一个集合进行遍历与后一个集合中的元素进行连接就可以了，因为是字符串，加起来就好了

我的解法

  1. import java.util.*;
  2. import java.util.concurrent.CopyOnWriteArrayList;
  4. public class ObservedPin {
  6.     public static List<String> getPINs(String observed) {
  7.       String[][] arr = {{"0", "8"}, {"1", "2", "4"}, {"2", "1", "3", "5"}, {"3", "2", "6"}, {"4", "1", "5", "7"}, {"5", "2", "4", "6", "8"}, {"6", "3", "5", "9"}, {"7", "4", "8"}, {"8", "5", "7", "9", "0"}, {"9", "6", "8"}};
  8.       List<String> PINs = new CopyOnWriteArrayList();
  9.       //笛卡尔积
  10.       for (int i = 0; i < observed.length(); i++) {
  11.           if (i == 0) {
  12.               for (String pin : arr[Integer.valueOf(observed.charAt(i) + "")]) {
  13.                   PINs.add(pin);
  14.               }
  15.           } else {
  16.               List<String> temp = new CopyOnWriteArrayList();
  17.               for (String pin : PINs) {
  18.                   for (String s : arr[Integer.valueOf(observed.charAt(i) + "")]) {
  19.                       temp.add(pin + s);
  20.                   }
  21.               }
  22.               PINs = temp;
  23.           }
  24.       }
  25.        return PINs;
  26.     } // getPINs
  28. } // ObservedPin

参考解法

  1. import java.util.*;
  3. public class ObservedPin {
  5.     private static final Map<Character,String> ADJACENTS = new HashMap<Character,String>() {{
  6.         put('1', "124");
  7.         put('2', "2135");
  8.         put('3', "326");
  9.         put('4', "4157");
  10.         put('5', "54268");
  11.         put('6', "6953");
  12.         put('7', "748");
  13.         put('8', "87590");
  14.         put('9', "986");
  15.         put('0', "08");
  16.     }};
  18.     public static List<String> getPINs(String observed) {
  20.         List<String> ans = Arrays.asList("");
  22.         for (char c: observed.toCharArray()) {
  24.             List<String> tmp = new ArrayList<String>();
  25.             for (char cc: ADJACENTS.get(c).toCharArray()) {
  26.                 for (String s: ans) tmp.add(s+cc);
  27.             }
  28.             ans = tmp;
  29.         }
  30.         return ans;
  31.     }
  33. }

提升

  1. 将观察的数字与对应可能出现的数字建立map,利用char 值进行查找，很聪明。
  2. 初始化的时候不是new一个空的list,而是Arrays.asList(“”) 避免了第一次遍历时前一个集合为空的情况。