文档章节

一道笔试题

芝麻糖葫芦
 芝麻糖葫芦
发布于 2017/05/18 21:23
字数 428
阅读 25
收藏 0
点赞 0
评论 0

下午面试遇到一道笔试题,题目是编写一个支持部分正则表达式的解析器,获取目标字符串在原字符串中第一次出现的索引,例如 查找“ava”在“Lear Java.”中第一次出现的索引为6

其中“.”代表任意单个字符,“^”代表从字符串的开头开始匹配,“$”匹配字符串的结尾,“*”匹配任意个字符

因为在其他笔试题中浪费了太多时间,没有写出这部分代码,回家路上有了思路,现在记录下来。

/**
 * 主要的工具类
 * Created by Morven on 2017/5/18.
 */
public class RegularMacher {
    private RegularMacher() {}

    private static class RegularMacherHolder {
        private static RegularMacher instance = new RegularMacher();
    }

    public static RegularMacher getInstance() {
        return RegularMacherHolder.instance;
    }

    public int matchIndex(String source, String regular) {
        char[] chars = regular.toCharArray();
        for (int i = 0; i < source.length(); i++) {
            int index = indexOf(source, i, chars, 0);
            if (index > -1) return index;
        }
        return -1;
    }

    private int indexOf(String source, int beginIndex, char[] chars, int charIndex) {
        char c = chars[charIndex];
        if (c == '^') {
            if (beginIndex > 0) {
                return -1;
            }
            int index = indexOf(source, beginIndex, chars, charIndex + 1);
            if (index > -1) {
                return beginIndex;
            }
            return -1;
        } else if (c == '$') {
            if (beginIndex < source.length()) {
                return -1;
            }
            return beginIndex;
        } else if (c == '.') {
        } else if (c == '*') {
            if (charIndex + 1 == chars.length) {
                return beginIndex;
            }
            if (charIndex + 2 == chars.length && chars[charIndex + 1] == '$') {
                return beginIndex;
            }
            for (int i = beginIndex; i < source.length(); i++) {
                int index = indexOf(source, i, chars, charIndex + 1);
                if (index > -1) return index;
            }
            return -1;
        } else {
            if (c != source.charAt(beginIndex)) {
                return -1;
            }
        }
        if (charIndex + 1 == chars.length) return beginIndex;
        if (beginIndex + 1 == source.length()) {
            if (charIndex + 2 < chars.length) return -1;
        }
        int index = indexOf(source, beginIndex + 1, chars, charIndex + 1);
        if (index > -1) {
            return beginIndex;
        }
        return -1;
    }
}

/**
 * 测试
 * Created by Morven on 2017/5/18.
 */
public class RegularMacherTest {
    public static void main(String[] args) {
        System.out.println(RegularMacher.getInstance().matchIndex("Test java in Action.", ".est"));//0
        System.out.println(RegularMacher.getInstance().matchIndex("Test java in Action.", ".ssdfa"));//-1
        System.out.println(RegularMacher.getInstance().matchIndex("Test java in Action.", "^.aa"));//-1
        System.out.println(RegularMacher.getInstance().matchIndex("Test java in Action.", "*"));//0
        System.out.println(RegularMacher.getInstance().matchIndex("Test java in Action.", "*$"));//0
        System.out.println(RegularMacher.getInstance().matchIndex("Test java in Action.", "j*i"));//5
        System.out.println(RegularMacher.getInstance().matchIndex("Test java in Action.", "j*ava"));//5
    }
}

© 著作权归作者所有

共有 人打赏支持
芝麻糖葫芦
粉丝 3
博文 19
码字总数 4908
作品 0
济南
高级程序员

暂无文章

NNS域名系统之域名竞拍

0x00 前言 其实在官方文档中已经对域名竞拍的过程有详细的描述,感兴趣的可以移步http://doc.neons.name/zh_CN/latest/nns_protocol.html#id30 此处查阅。 我这里主要对轻钱包开发中会用到的...

暖冰
今天
0
0
32.filter表案例 nat表应用 (iptables)

10.15 iptables filter表案例 10.16/10.17/10.18 iptables nat表应用 10.15 iptables filter表案例: ~1. 写一个具体的iptables小案例,需求是把80端口、22端口、21 端口放行。但是,22端口我...

王鑫linux
今天
0
0
shell中的函数&shell中的数组&告警系统需求分析

20.16/20.17 shell中的函数 20.18 shell中的数组 20.19 告警系统需求分析

影夜Linux
今天
0
0
Linux网络基础、Linux防火墙

Linux网络基础 ip addr 命令 :查看网口信息 ifconfig命令:查看网口信息,要比ip addr更明了一些 centos 7默认没安装ifconfig命令,可以使用yum install -y net-tools命令来安装。 ifconfig...

李超小牛子
今天
1
0
[机器学习]回归--Decision Tree Regression

CART决策树又称分类回归树,当数据集的因变量为连续性数值时,该树算法就是一个回归树,可以用叶节点观察的均值作为预测值;当数据集的因变量为离散型数值时,该树算法就是一个分类树,可以很...

wangxuwei
昨天
1
0
Redis做分布式无锁CAS的问题

因为Redis本身是单线程的,具备原子性,所以可以用来做分布式无锁的操作,但会有一点小问题。 public interface OrderService { public String getOrderNo();} public class OrderRe...

算法之名
昨天
10
0
143. Reorder List - LeetCode

Question 143. Reorder List Solution 题目大意:给一个链表,将这个列表分成前后两部分,后半部分反转,再将这两分链表的节点交替连接成一个新的链表 思路 :先将链表分成前后两部分,将后部...

yysue
昨天
1
0
数据结构与算法1

第一个代码,描述一个被称为BankAccount的类,该类模拟了银行中的账户操作。程序建立了一个开户金额,显示金额,存款,取款并显示余额。 主要的知识点联系为类的含义,构造函数,公有和私有。...

沉迷于编程的小菜菜
昨天
1
0
从为什么别的队伍总比你的快说起

在机场候检排队的时候,大多数情况下,别的队伍都要比自己所在的队伍快,并常常懊悔当初怎么没去那个队。 其实,最快的队伍只能有一个,而排队之前并不知道那个队快。所以,如果有六个队伍你...

我是菜鸟我骄傲
昨天
1
0
分布式事务常见的解决方案

随着互联网的发展,越来越多的多服务相互之间的调用,这时候就产生了一个问题,在单项目情况下很容易实现的事务控制(通过数据库的acid控制),变得不那么容易。 这时候就产生了多种方案: ...

小海bug
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部