搜狗2019秋招前端工程师部分编程题合集（第二场）

定义如下图所示的比赛地图：
 
S表示比赛起点，E表示比赛终点。实线表示陆路，虚线表示水路。兔子只能走陆路，乌龟既可以走陆路也可以走水路。每条路径的长度在图中给出。假定兔子和乌龟足够聪明，问谁先到达终点。
输入描述： 第1行输入v1，v2。v1是兔子的速度，v2是乌龟的速度（水路、陆路速度相同）。第2行输入n,m，点的编号是1~n,然后是m行，其中1是起点，n是终点（路径本身不限定方向）。下面m行4个数 a, b, d, c，表示a和b之间有一条边，且其长度为d，类型是c（0表示陆路，1表示水路）。最后一行是end，表示输入结束。输入保证1和n之间至少有一条路径联通。(1&ltn<=10000, 0&ltm<=1000000)。输入样例： 10 5 3 3 1 2 30 0 2 3 20 0 1 3 20 1 end 输出描述： 输出-1,0,1中的一个数。-1表示乌龟获胜，1表示兔子获胜，0表示同时到达终点。输出样例 -1

判断一个数字串是否匹配一个表达式，具体如下：
1）表达式m：一定不为空，只能由数字和“*”构成，其中的“*”表示匹配一个或多个“它前面所有非”*“的数字的和值除以10的余数”；“*”如果在最前面或其前面都是“*”，则只可以是任意一个数字。
2）数字串s：可能为空，只能由数字构成，不能包含其它字符。
3）是否匹配：匹配要求覆盖整个数字串s，而不是某一部分匹配。

解题要求：不能将m转写成标准正则表达式来解题，需要自己编程实现匹配算法。

注意，对应objc语言，系统里的@autoreleasepool {} 需要改写成如下形式

#import <Foundation/Foundation.h>
//strcmp
//NSString:
//- (NSArray<NSString *> *)componentsSeparatedByCharactersInSet:(NSCharacterSet *)separator
//- (unichar)characterAtIndex:(NSUInteger)index
//- (NSString *)substringWithRange:(NSRange)range

int main(int argc, const char * argv[]) {
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init]
    //...
    //add your code
    //...
    [pool drain]
    return 0
}

输入描述： 见输入样例，其中最后一行的0表示结束输入输入样例： 3 1* 11111 **1 121 **1 1221 0 输出描述： YES:匹配

NO:不匹配输出样例 YES YES NO