在Java中为一个数字生成多个组合列表

Question

以下是我正在解决的问题和我的代码片段。 有没有更好的方法来实现这个？我在下面使用了基本的控制结构。

将行和列存储在映射中并根据键/值对搜索映射是否更好？

建筑物入口处有一个安全键盘。它有 9 个数字 1 - 9，采用 3x3 矩阵格式。

1 2 3
4 5 6
7 8 9

安全部门已决定允许一个人出现一位数字错误，但该数字应该是水平或垂直的。示例：对于 5，允许用户输入 2、4、6、8；对于 4，允许用户输入 1、5、7。如果要输入的安全代码是 1478，并且如果用户输入 1178，则应允许用户输入。

以下是我正在处理的代码片段：

ArrayList<Integer> list = new ArrayList<Integer>();
int num = 9;
int[][] arr = {{1,2,3},{4,5,6},{7,8,9}};

for(int i =0;i< arr.length;i++){
  for(int j = 0; j <arr.length;j++){
    if(num == arr[i][j]){
      row = i;
      col = j;
      break;

    }
  }
}
for(int j1 = 0; j1< 3 ; j1++){
  if(arr[row][j1] != num){
    list.add(arr[row][j1]);
  }
}
for(int i1 = 0 ; i1 <3;i1++){
  if(arr[i1][col] != num){
    list.add(arr[i1][col]);
  }
}

Answer 1

有很多方法可以解决这个问题，但我认为使用 HashMap 和 HashSet 可以比多次迭代更有效地解决。

如果我是你，我会首先使用哈希图和哈希集构建数据模型。这是因为哈希图和哈希集具有快速查找（无迭代）

HashMap<Integer,HashSet<Integer>> values = new HashMap<Integer, HashSet<Integer>>();

//now put in the accepted values for one
HashSet<Integer> oneValues = new HashSet<Integer>();
oneValues.put(1);
oneValues.put(2);
oneValues.put(4);
values.put(1, oneValues);

//put in 2 values
......

然后当您解析输入时，如果您想查看代码是否接受输入的值，只需执行类似的操作

private boolean isAccepted(int input, int combinationValue)
{
  // check to see if the inputed value in the accepted values set
  return values.get(combinationValue).contains(input);
}

Answer 2

我倾向于想要一个类似于 isCloseTo(int a, int b) 的函数所以，比如说，如果我调用 isCloseTo(5, 5) 它将返回 true 。如果我调用 isCloseTo(2, 5) 它也应该返回 true。但如果我调用 isCloseTo(1, 3) 它将返回 false。

所以我会编写这样的测试：

assertTrue(isCloseTo(5, 5));

好的，这真的很容易通过：

public boolean isCloseTo(int a, int b) {return true;}

然后，也许

assertFalse(isCloseTo(1, 3) );

上面的实现失败了，所以我需要更改它

public boolean isCloseTo(int a, int b) {return a == b;}

这仍然是一个不完整的实现，所以我们需要另一个测试

assertTrue(isCloseTo(1, 2));

现在我们开始需要一些真正的实质内容。我想我会把剩下的作为练习留给读者。是的，我已经省略了棘手的部分，但这是一种策略（测试驱动设计），它可以让您更直接地找到解决方案，而不仅仅是尝试编写代码。只要您保持所有测试都通过，您就可以朝着完整的解决方案稳步前进。祝你好运！

Answer 3

这里有许多不同的可接受的解决方案。我想构造 10x10 整数矩阵来检查错误会更容易（例如 errorMatrix）。第一个索引表示原始数字，第二个索引表示用户输入的数字，arr[i][j] 的值是该数字对的错误数量。以这种方式初始化它：
errorMatrix[i][i] = 0 //没有错误
errorMatrix[i][j] = 1，其中 i 和 j 是水平或垂直相邻的数字
在其他情况下，errorMatrix[i][j] = 2。

那么对于每个数字对，您将得到 O(1) 的错误数量。您声明您只接受一个错误，因此对于不匹配的对，值 2 就足够了，您只需将错误数相加并将其与 1 进行比较即可。

那么，如何构建这个。迭代所有数字对并找出误差值。你应该更好地实现函数 CheckError 来计算数字对 a 和 b

1. 如果 a=b，则 errorMatrix 为 0;
2. 数字 a 和 b 是垂直的
   如果 abs(ab) = 3，则为邻居。所以，是
   abs(ab)==3 设置 errorMatrix[a][b] =
   1;

3. 数字a和b是水平的
   邻居如果

   a. (a-1)/3==(b-1)/3 - 在这里我们检查这些数字是否在同一行。
   b. abs(ab)==1 - 在这里我们检查数字是否在相邻单元格中。
   如果(a)和(b)则误差值为1；

4. 在其他情况下错误值为 2。

在我看来这个规范是正确的。不过使用前需要先测试一下

因此，如果您想处理键盘布局的更改，您只需重写 CheckError 方法即可。

希望它有所帮助。

Answer 4

或者这个...

boolean matchDigit(int p, int d) {
   return (p==d) 
       || (p==d-3) 
       || (p==d+3) 
       || (d%3!=1 && p==d-1) 
       || (d%3!=0 && p==d+1);
} 

假设我们已经确保 p 和 d 在 1 到 9 之间。

Answer 5

对于您问题中的特定键盘，我们可以使用基数 3 来解决此问题并计算数字/按键之间的距离。

1 { 1 / 3, 1 % 3 } = {0, 1}
2 { 2 / 3, 2 % 3 } = {0, 2}
...
5 { 5 / 3, 5 % 3 } = {1, 2}
...
8 { 8 / 3, 8 % 3 } = {2, 2}

public boolean isValidCode(int code, int expexted) {
    while(code > 0)
    {
        if (!isValidDigit(code % 10, expected % 10))
            return false ;
        code /= 10 ;
        expected /= 10 ;
    }

    return (code == expected) ;
}

public boolean isValidDigit(int a, int b) {
    int dx = (a - b) / 3 ;
    int dy = (a - b) % 3 ;
    return ((Math.abs(dx) + Math.abs(dy)) == 1)
}

一个更通用和更强大的解决方案是创建一个 Map，您可以在其中设置您接受的其他键。

示例：A 允许使用 A、Z、P、M、N：在映射中放置一个新条目 'A'="AZPMN"，检查字符是否相同或类型字符是否在例外字符串中。

private Map acceptedChars = new HashMap() ;

public void loadAcceptedCharacters() {
    acceptedChars.put('A', "AZPMN") ;
}

public boolean isValidKeyword(String word, String expected)
{
    if (word == null || word.matches("\\s*"))
        return false ;

    if (word.length() != expected.length())
        return false ;

    for(int idx = 0; idx < word.length(); idx++)
    {
        if (!isValidDigit(word.chatAt(idx), expected.charAt(idx)))
            return false ;
    }

    return true ;
}

public boolean isValidDigit(char chr, char expected) {
    String accepted ;
    if (chr != expected)
    {
        accepted = acceptedChars.get(chr) ;
        if (accepted == null)
            return false ;
        if (accepted.indexOf(chr) < 0) 
            return false ;
    }
    return true ;
}