文档章节

递归处理 编程实战讲解

coffee377
 coffee377
发布于 2017/03/30 09:49
字数 784
阅读 37
收藏 0

昨晚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));
    }
}

最终测试结果

© 著作权归作者所有

coffee377
粉丝 0
博文 2
码字总数 877
作品 0
合肥
程序员
私信 提问
Python为什么这么火?

人生苦短,我用Python!对于学习Python的人来说肯定特别熟悉,当然这要归功于python强大的功能:它能把复杂的语言简单化,满足企业运维日常的数据分析和运维系统的管理,编写自动化运维平台,...

让往事随风
2016/05/03
509
2
强力推荐,非常全的 Python 学习资料(今日免费)

各位想高效学习和掌握Python的朋友,请看过来。好了在给大家分享之前呢,我介绍一下我弄的一个学习交流群,有什么不懂的问题,都可以在群里踊跃发言,需要啥资料随时在群文件里面获取自己想要...

python达人
2017/11/17
0
0
阿里云大学云学院 “人工智能” 专业重磅预售

阿里云认证专家带你探索人工智能,掌握人工智能核心技术 学习链接:点击这里 (阿里云认证资深专家,手把手带你6个月入门人工智能) 阿里云云学院人工智能专业,由阿里云认证专家亲自辅导,并...

mcy0425
2018/06/27
0
0
精通Python网络爬虫-书籍介绍

 内容简介 本书从技术、工具与实战3个维度讲解了Python网络爬虫: 技术维度:详细讲解了Python网络爬虫实现的核心技术,包括网络爬虫的工作原理、如何用urllib库编写网络爬虫、爬虫的异常...

weiwei_pig
2017/04/09
0
0
一年走向【Java架构师】之葵花宝典

大多数时候,不是我们不努力,而是不知从何下手,我深知一份好的学习资料是多么的重要,我们通常会把大量的时间都浪费在找资源上,本人搜集学习java架构师的经典学习路线如下可供参考!!! 一...

我一路狂奔
2017/05/20
395
1

没有更多内容

加载失败,请刷新页面

加载更多

跟我来见证:《Kafka如何实现每秒上百万的高并发写入?》

本文来聊一下Kafka的一些架构设计原理,这也是互联网公司面试时非常高频的技术考点。 Kafka是高吞吐低延迟的高并发、高性能的消息中间件,在大数据领域有极为广泛的运用。配置良好的Kafka集群...

Java干货分享
26分钟前
3
0
Storm+Hbase广告实时统计

本文主要讲述使用Kafka+Strom+Hbase搭建的一套广告实时计算系统。其中服务器显示使用的是SpringBoot+Vue+ElementUI+EChats. 主要内容: 1.需求 2.日志格式 3.Hbase表格设计 4.编写Storm程序 ...

飓风2000
49分钟前
4
0
android,ContentProvider+ContentObserver+ContentResolver,用法。

这个是传智播客老师讲android开发时的一个图。 一、 PersonProvider继承ContentProvider,实现ContentProvider中的数据操作类。 ContentObserver——内容观察者,目的是观察(捕捉)特定Uri引起...

天王盖地虎626
55分钟前
3
0
解决markdown中的不换行问题

没有解决我的格式显示问题 https://blog.csdn.net/qq_23483671/article/details/79017609

南桥北木
今天
2
0
产品上新|ZStack3.5.0正式发布啦!

海量产品资料传送门~ 一、ZStack全线产品下载通道汇总 社区版(免费): https://www.zstack.io/product/zstack_open_source/ 企业版下载: https://www.zstack.io/product/zstack_enterpris...

ZStack社区版
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部