算法面试题

原创
2014/05/21 09:28
阅读数 2K
1、 给出一个由小写字母组成的字符串,把所有连续出现的 2 a 替换成 bb 2 b ),但是对于超过两个连续的 a ,那么这些字符都不作替换。例如:

  bad -> bad (一个a,不替换)

  baad -> bbbd (替换成bb

  baaad -> baaad (连续三个a,不替换)

  apaapaaapaa -> apbbpaaapbb (这里连续的a出现了4次,只有第二段和最后一段被替换)

- (NSString *)replace:(NSString *)str {
    // CODE HERE
    NSMutableString *retString = [NSMutableString stringWithString:str];
    // 准备替换的字符串
    NSString *replaceString = @"bb";
    // 正则表达式 (^a{2}[^a]) 以aa(第三个字母不是a)开头,([^a]a{2}[^a]) 字符串中间的aa(前后都不是a),([^a]a{2}$) 以aa结尾(倒数第三个字母不是a)
    NSRegularExpression *regular = [[NSRegularExpression alloc] initWithPattern:@"(^a{2}[^a])|([^a]a{2}[^a])|([^a]a{2}$)" options:NSMatchingReportProgress error:nil];
    NSRange range;
    do {
        range = [regular rangeOfFirstMatchInString:retString options:NSMatchingReportProgress range:NSMakeRange(0, retString.length)];
        if (range.length == 4) {// 替换中间的aa
            [retString replaceCharactersInRange:NSMakeRange(range.location + 1, 2) withString:replaceString];
        } else if (range.length > 0) {
            if (range.location == 0) {// 替换开头的aa
                [retString replaceCharactersInRange:NSMakeRange(range.location, 2) withString:replaceString];
            } else {// 替换结尾的aa
                [retString replaceCharactersInRange:NSMakeRange(retString.length - 2, 2) withString:replaceString];
            }
        }
    } while (range.length > 0);
    return retString;
}



2、 给出一个字符串,其中只包含括号(大中小括号 “()[]{}” ),括号可以任意嵌套。如果同样的左右括号成对出现并且嵌套正确,那么认为它是匹配的。例如:

  ()  ->  TRUE  (匹配)

  [()]  ->  TRUE  (匹配,括号可以嵌套)

  ()()   ->  TRUE     (匹配,括号可以并列排列)

  ({}([]))  ->  TRUE   (匹配,括号可以任意嵌套,大括号不必在外)

  )   ->  FALSE    (不匹配,缺少左括号)

  (}   ->  FALSE     (不匹配,左右括号不一样)

  {)(}   ->  FALSE     (不匹配,左右括号相反)

- (BOOL)isMatch:(NSString *)str {
    // CODE HERE
    // 采用进站出站的思想,遍历完字符串时如果array为空则匹配成功,否则失败
    NSMutableArray *array = [NSMutableArray array];
    for (int i = 0; i < str.length; i++) {
        int tag = [self createTagWithString:[str substringWithRange:NSMakeRange(i, 1)]];
        if (tag != 0) {
            int lastTag = [[array lastObject] intValue];
            if ((lastTag + tag) == 0) {
                [array removeLastObject];
            } else {
                [array addObject:@(tag)];
            }
        }
    }
    return array.count == 0;
}

- (int)createTagWithString:(NSString *)str {
    if ([str isEqualToString:@"("]) {
        return -1;
    } else if ([str isEqualToString:@")"]) {
        return 1;
    } else if ([str isEqualToString:@"["]) {
        return -2;
    } else if ([str isEqualToString:@"]"]) {
        return 2;
    } else if ([str isEqualToString:@"{"]) {
        return -3;
    } else if ([str isEqualToString:@"}"]) {
        return 3;
    }
    return 0;
}



3、写一个函数,找出一个数组中出现次数超过一半的数字,如果数字不存在,则返回-1。例如:

    [0, 1, 2]             -->     -1   (每个数字只出现1次)

    [0, 1, 2, 1]         -->     -1   (1出现了2次,刚好一半)

    [0, 1, 2, 1, 1]     -->     1    (1出现了3次,超过一半)

(注:数组不是按从小到达排序的,也许排序之后更容易找到这个数,但是有没有更好、更快的方法在不重新调整顺序的情况得到结果?)

- (int)mode:(NSArray *)array {
    // CODE HERE
    // 将集合中得数字转存到字典中,数字做key,对应出现的次数做value
    NSMutableDictionary *modeMap = [NSMutableDictionary dictionary];
    [array enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
        NSString *key = obj;
        id count = modeMap[key];
        int i = [(NSNumber *)count intValue];
        [modeMap setObject:@(i + 1) forKey:key];
    }];
    __block int retInt = -1;
    // 遍历字典,找出其中value大于集合一半的key并返回
    [modeMap.allKeys enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
        NSString *key = obj;
        int mode = [modeMap[key] intValue];
        if (mode > array.count / 2) {
            retInt = key.intValue;
            *stop = YES;
        }
    }];
    return retInt;
}


展开阅读全文
加载中
点击加入讨论🔥(6) 发布并加入讨论🔥
6 评论
10 收藏
1
分享
返回顶部
顶部