Java语言实现Google方程式

Dear 丶 2022-05-16 06:09 90阅读 0赞

有一个字符组成的等式：WWWDOT - GOOGLE = DOTCOM，每个字符代表一个0－9之间的数字，WWWDOT、GOOGLE和DOTCOM都是合法的数字，不能以0开头。请找出一组字符和数字的对应关系，使它们互相替换，并且替换后的数字能够满足等式。这个字符等式是Google公司能力倾向测试实验室的一道题目，这种题目主要考察人的逻辑推导能力和短期记忆能力。此类型的题目有很多变种，各种编程比赛中常常能见到它们的身影。比如2005年的GOOGLE中国编程挑战赛第二轮淘汰赛有一道名为“SecretSum”的500分的竞赛题，与本题如出一辙，只不过字母都是三个，而且用的是加法计算。现在言归正传，先看看如何分析这个问题。

### 备注： ###

关于上述题目，通常采用”穷举“算法求解，网上和一些书籍中都给出了C/C++的解法，Java解法比较少，本篇博客将基于Java实现Google方程式的解法

### 解法： ###

从穷举法的角度看，这是一个典型的排列组合问题，题目中一共出现了9个字母，每个字母都可能是0～9之间的数字，穷举的方法就是对每个字母用0～9的数字尝试10次，如果某一次得到的字母和数字的对应关系能够满足减法等式，则输出这一组对应关系。根据题目意思，每个字母代表一个数字，也就是说，如果 W 代表1，则其他8个字母就不可能是1。很显然，这是个组合问题，如果不考虑0开头数字的情况，这样的组合应该有10×9×8×7×6×5×4×3×2=3628800种组合，在这样的数量级上使用穷举法，计算机处理起来应该没有压力。

根据题目要求，W、G 和 D 这3个字符位于数字的头部，不能是0，因此枚举过程中对这3个字符是0的情况进行剪枝，通过剪枝操作，搜索次数由理论上的3628800次减少为2540160，减少了约30%的计算判断。

从数据结构定义上，由于字符与数字存在对应关系，这就需要定义一个可变化的字符元素列表，每个字符元素包含3个属性，分别是字母本身、字母代表的数字以及是否是数字的最高位（根据题意，最高位不能是0，所以要特别对待）：

public static class CharItem
        {
            char c;
            int value;
            boolean isLeading;
    
            CharItem(char c, int value, boolean isLeading)
            {
                this.c = c;
                this.value = value;
                this.isLeading = isLeading;
            }
        }

对于本题，这个列表可以初始化为：

List<CharItem> charList = new ArrayList<>();
            charList.add(new CharItem('W', -1, true));
            charList.add(new CharItem('D', -1, true));
            charList.add(new CharItem('O', -1, false));
            charList.add(new CharItem('T', -1, false));
            charList.add(new CharItem('G', -1, true));
            charList.add(new CharItem('L', -1, false));
            charList.add(new CharItem('E', -1, false));
            charList.add(new CharItem('C', -1, false));
            charList.add(new CharItem('M', -1, false));

因为这是一个组合问题，两个字母不能被指定为相同的数字，这就需要对每个数字做一个标识，当这个数字已经被某个字符“占用”时，其他字符不能再使用这个数字。我们对可参与穷举的数字也定义一个列表，对于这个问题来说，0～9都可以参与穷举，但是有的问题可能有特殊的约束，比如字符只能代表偶数，或只能代表奇数等，每个数字元素有一个额外的占用标识：

public static class NumStatus
        {
            boolean isUsed;
            int value;
    
            NumStatus(boolean isUsed, int value)
            {
                this.value = value;
                this.isUsed = isUsed;
            }
        }

穷举的搜索算法采用递归的方式进行组合枚举，按照`charList`列表中的顺序，逐个对每个字符进行数字遍历，算法实现如下：

/**
         * @param charList: 表示输入的字符元素列表，
         * @param numList: 0-9备选数字列表
         * @param index: 当前已经被赋值的字符元素的个数
         */
        public static void searchResult(List<CharItem> charList, List<NumStatus> numList, int index)
        {
            // 所有字符均已赋值，则检验当前的字符-数字对应方式是否满足等式要求
            if (index == charList.size())
            {
                // 等式中的字符
                String target = "WDOTGLECM";
                // 检验当前的字符-数字对应方式是否满足等式要求
                checkMode(charList, target);
                return;
            }
            
            // 将0-9数字与等式中的字符进行匹配尝试
            for (int i = 0; i<numList.size(); i++)
            {
                // 剪枝条件：等式中的各个字符串首字母不能为0，同一个匹配模式中数字不能重复
                if ((charList.get(index).isLeading && numList.get(i).value == 0) || numList.get(i).isUsed)
                {
                    continue;
                }
                // 使用过的数字进行标记
                numList.get(i).isUsed = true;
                // 字符与数字匹配
                charList.get(index).value=numList.get(i).value;
                // 递归，匹配下一个字符
                searchResult(charList, numList, index+1);
                // 回溯，实现穷举
                numList.get(i).isUsed = false;
            }
            
    
        }

完整代码如下：

package com.yingshulan.etcd.client.etcd_learning;
    
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    
    public class Solution
    {
    
        public static void main(String[] args)
        {
            List<CharItem> charList = new ArrayList<>();
            charList.add(new CharItem('W', -1, true));
            charList.add(new CharItem('D', -1, true));
            charList.add(new CharItem('O', -1, false));
            charList.add(new CharItem('T', -1, false));
            charList.add(new CharItem('G', -1, true));
            charList.add(new CharItem('L', -1, false));
            charList.add(new CharItem('E', -1, false));
            charList.add(new CharItem('C', -1, false));
            charList.add(new CharItem('M', -1, false));
            
            
            List<NumStatus> numList = new ArrayList<>();
            numList.add(new NumStatus(false, 0));
            numList.add(new NumStatus(false, 1));
            numList.add(new NumStatus(false, 2));
            numList.add(new NumStatus(false, 3));
            numList.add(new NumStatus(false, 4));
            numList.add(new NumStatus(false, 5));
            numList.add(new NumStatus(false, 6));
            numList.add(new NumStatus(false, 7));
            numList.add(new NumStatus(false, 8));
            numList.add(new NumStatus(false, 9));
    
            searchResult(charList, numList, 0);
    
        }
        
        /**
         * @param charList: 表示输入的字符元素列表，
         * @param numList: 0-9备选数字列表
         * @param index: 当前已经被赋值的字符元素的个数
         */
        public static void searchResult(List<CharItem> charList, List<NumStatus> numList, int index)
        {
            // 所有字符均已赋值，则检验当前的字符-数字对应方式是否满足等式要求
            if (index == charList.size())
            {
                // 等式中的字符
                String target = "WDOTGLECM";
                // 检验当前的字符-数字对应方式是否满足等式要求
                checkMode(charList, target);
                return;
            }
            
            // 将0-9数字与等式中的字符进行匹配尝试
            for (int i = 0; i<numList.size(); i++)
            {
                // 剪枝条件：等式中的各个字符串首字母不能为0，同一个匹配模式中数字不能重复
                if ((charList.get(index).isLeading && numList.get(i).value == 0) || numList.get(i).isUsed)
                {
                    continue;
                }
                // 使用过的数字进行标记
                numList.get(i).isUsed = true;
                // 字符与数字匹配
                charList.get(index).value=numList.get(i).value;
                // 递归，匹配下一个字符
                searchResult(charList, numList, index+1);
                // 回溯，实现穷举
                numList.get(i).isUsed = false;
            }
            
    
        }
    
        public static void checkMode(List<CharItem> charList, String target)
        {
            // 存储字符与数字的匹配结果 ：key-value：字符-数字    
            Map<Character, Integer> map = new HashMap<Character, Integer>();
    
            for (int i = 0; i < target.length(); i++)
            {
                for (CharItem en : charList)
                {
                    if ((en.c) == target.charAt(i))
                    {
                        map.put(en.c, en.value);
                    }
                    else
                    {
                        continue;
                    }
                }
            }
            // 根据字符与数字的匹配结果，将字符串等式转化为数字
            String str1 = "WWWDOT";
            String str2 = "GOOGLE";
            String str3 = "DOTCOM";
            
            String numStr1 = "";
            String numStr2 = "";
            String numStr3 = "";
            
            for (int i = 0; i < str1.length(); i++)
            {
                numStr1 += (char)(map.get(str1.charAt(i))+'0');
                numStr2 += (char)(map.get(str2.charAt(i))+'0');
                numStr3 += (char)(map.get(str3.charAt(i))+'0');           
            }
            
            int[] result = new int[3];
            result[0] = Integer.parseInt(numStr1);
            result[1] = Integer.parseInt(numStr2);
            result[2] = Integer.parseInt(numStr3);
              
            // 打印符合条件的结果
            if (result[0]-result[1] == result[2])
            {
                System.out.println(+result[0] +"-" + result[1] + "=" + result[2]);
            }
    
        }
    
        public static class CharItem
        {
            char c;
            int value;
            boolean isLeading;
    
            CharItem(char c, int value, boolean isLeading)
            {
                this.c = c;
                this.value = value;
                this.isLeading = isLeading;
            }
        }
    
        public static class NumStatus
        {
            boolean isUsed;
            int value;
    
            NumStatus(boolean isUsed, int value)
            {
                this.value = value;
                this.isUsed = isUsed;
            }
        }
    
    }

输出结果：

777589-188103=589486
    777589-188106=589483