递归处理 编程实战讲解

原创
2017/03/30 09:49
阅读数 37

昨晚XMH和我聊天,说她复试的时候面试官出了一道机试题,题目如下:

给定一个带通配符文问号的数W,问号可以代表任意一个一位数字。 再给定一个整数X,长度不超过W。 问有多少个整数符合W的形式并且比X大?

countBigger(“??”,90)应该等于9

ountBigger(“?9”,90)应该等于1

countBigger(“??”,9)应该等于90

countBigger(“8?3”,910)应该等于0

她和我讲述了她的解题思路,思路没有问题,但是最后功能没实现,所以与此份工作无缘

其实我的思路也是这样的,只不过在处理的使用用到了递归的思想,这就是关键所在,下面我就贴出源码

这是面试官定义的接口

public interface NumberGame {

    /**
     * @param pattern 通配符文数字字符串,? 代表任意一个一位数字
     * @param target  位数小于等于 pattern 的长度
     * @return 符合 pattern 形式且比 target 大的数的数目
     */
    int countBigger(String pattern, int target);

}

接口实现类

/**
 * Created with IntelliJ IDEA.
 * Email:  coffee377@dingtalk.com
 * Time:  2017/03/29 20:37
 */
public class NumberGameImpl implements NumberGame {
    private final static char QUESTION_MARK = '?';

    @Override
    public int countBigger(String pattern, int target) {
        if (!bitLess(pattern, target)) {
            throw new RuntimeException("目标数字位数必须小于等于通配符数字的长度");
        }
        List<String> recursive = recursive(pattern, new ArrayList<String>());
        List<Integer> bigger = new ArrayList<>();
        for (String s : recursive) {
            int temp = Integer.parseInt(s);
            if (temp > target) {
                bigger.add(temp);
            }
        }
        return bigger.size();
    }

    /**
     * 递归处理通配符文数字字符串
     *
     * @param pattern 通配符文数字字符串,? 代表任意一个一位数字
     * @param result  递归集合参数
     * @return 符合条件的数字字符串集合
     */
    private List<String> recursive(String pattern, List<String> result) {
        if (hasOneMark(pattern)) {
            for (int i = 0; i < 10; i++) {
                result.add(pattern.replaceFirst(String.valueOf("\\" + QUESTION_MARK), String.valueOf(i)));
            }
        } else if (hasMoreMark(pattern)) {
            for (int i = 0; i < 10; i++) {
                recursive(pattern.replaceFirst(String.valueOf("\\" + QUESTION_MARK), String.valueOf(i)), result);
            }
        } else {
            result.add(pattern);
        }
        return result;
    }

    /**
     * 目标数字位数必须是否小于等于通配符数字的长度
     *
     * @param pattern 通配符文数字字符串,? 代表任意一个一位数字
     * @param target  位数小于等于pattern的长度
     * @return boolean
     */
    private boolean bitLess(String pattern, int target) {
        return null != pattern && !"".equals(pattern) && String.valueOf(target).length() <= pattern.length();
    }

    /**
     * 是否含有一个通配符
     *
     * @param pattern 通配符文数字字符串
     * @return 含有一个返回 true ,否则返回 false
     */
    private boolean hasOneMark(String pattern) {
        return countMark(pattern) == 1;
    }

    /**
     * 至少含有两个通配符(>1)
     *
     * @param pattern 通配符文数字字符串
     * @return 大于 1 返回 true ,否则返回 false
     */
    private boolean hasMoreMark(String pattern) {
        return countMark(pattern) > 1;
    }

    /**
     * 计算占位符个数
     *
     * @param pattern 通配符文数字字符串,? 代表任意一个一位数字
     * @return 占位符数目
     */
    private int countMark(String pattern) {
        int num = 0;
        for (int i = 0; i < pattern.length(); i++) {
            if (pattern.charAt(i) == QUESTION_MARK) {
                num++;
            }
        }
        return num;
    }
}

Junit测试单元

import org.junit.BeforeClass;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

/**
 * Created with IntelliJ IDEA.
 * Email:  coffee377@dingtalk.com
 * Time:  2017/03/29 20:37
 */
public class NumberGameTest {

    private static NumberGame numberGame;

    @BeforeClass
    public static void beforeClass() {
        numberGame = new NumberGameImpl();
    }

    @Test
    public void countBigger() throws Exception {
        // countBigger(“??”,90)应该等于9
        // countBigger(“?9”,90)应该等于1
        // countBigger(“??”,9)应该等于90
        // countBigger(“8?3”,910)应该等于0

        assertEquals(9,numberGame.countBigger("??", 90));
        assertEquals(1,numberGame.countBigger("?9", 90));
        assertEquals(90,numberGame.countBigger("??", 9));
        assertEquals(0,numberGame.countBigger("8?3", 910));
    }
}

最终测试结果

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部