美文网首页
算法问题

算法问题

作者: Felix的笔头 | 来源:发表于2018-03-26 17:57 被阅读0次

1、我们的程序运行过程中每分钟会采集一个整数的数据指标。
持续采集n分钟就得到一个有n个元素的整数数组a[n]。
现在我们需要一个简单的算法,检测采集到的数据指标中,是否有异常。
异常的检测标准是:如果在连续m分钟内的指标的平均值大于w,则说明有异常。
输入:数组a[n], 正整数m, 整数w
返回:有异常返回 1,没有异常返回 0
例如:对于a={1, 5, 1, 3, 2}, m=2, w=2, 返回:1
附加说明:不同的实现方式执行效率不一样,如果能找到一个很高效的算法就更好了。

示例1:

    NSArray *firstArray = @[@"1",@"5",@"1",@"3",@"2"];
    NSInteger m = 2;
    NSInteger w = 2;
    [self judgeWithArray:firstArray withTimes:m withValue:w];
- (BOOL)judgeWithArray:(NSArray *)array withTimes:(NSInteger)times withValue:(NSInteger)value
{
    __block BOOL isTrue = NO;
    NSMutableArray *allTotalNumArray = [[NSMutableArray alloc] initWithCapacity:0];
    for (int i = 0; i<array.count; i++) {
        if (i>(array.count - times)) {
            break;
        }
        NSInteger totalNum = 0;
        [allTotalNumArray addObject:[NSString stringWithFormat:@"%zd",totalNum]];
                NSInteger num0 = [array[i] integerValue];
        for (int j = 0; j<allTotalNumArray.count; j++) {
            NSInteger num1 = [allTotalNumArray[j] integerValue];
            if ((i - j)<times) {
                num1 += num0;
                [allTotalNumArray replaceObjectAtIndex:j withObject:[NSString stringWithFormat:@"%zd",num1]];
            }
        }
    }
    [allTotalNumArray enumerateObjectsUsingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        CGFloat num2 = [obj floatValue] ;
        CGFloat average =ceil(num2/times);
        if (average>value) {
            isTrue = YES;
            *stop = YES;
        }
    }];
    return isTrue;
}

示例2:

[self judgeIsException:@[@1,@2,@2,@3,@1,@5,@3,@2] time:3 standard:3]
- (BOOL)judgeIsException:(NSArray *)arr time:(int)time standard:(int)standard{
    int max = time * standard;
    int count = (int)arr.count;
    int sum = 0;
    for (int i = 0; i < count; i++) {
        int currentValue = [arr[i] intValue];
        if (currentValue <= standard) {
            continue;
        }else{
            int start = i - time + 1;
            if (start < 0) {
                start = 0;
            }
            int loop = count - i;
            if (loop > time) {
                loop = time;
            }
            while (loop>0) {
                sum = 0;
                for (int j = start; j < time+start; j++) {
                    sum += [arr[j] intValue];
                }
                if (sum>max) {
                    return YES;
                }
                start++;
                loop--;
            }
            i = start;
        }
    }
    return NO;
}

2、我们的程序运行过程中用到了一个数组a,数组元素是一个Map/Dictionary。
数组元素的“键”和“值”都是字符串类型。在不同的语言中,对应的类型是:
PHP的array, Java的HashMap, C++的std::map, Objective-C的NSDictionary, Swift的Dictionary, Python的dict, JavaScript的object, 等等
示例:
a[0]["key1"]="value1"
a[0]["key2"]="value2"
a[1]["keyA"]="valueA"
...
为了方便保存和加载,我们使用了一个基于文本的存储结构,数组元素每行一个:
text="key1=value1;key2=value2\nkeyA=valueA\n..."

要求:请实现一个“保存”函数、一个“加载”函数。
text=store(a);
a=load(text);
这两个函数分别用于把数组保存到一个文本字符串中、把文本字符串中的内容读取为数组。
必须自己手写代码实现保存/加载逻辑,严格按照上述的“每行一个、key=value”的格式保存。

附加说明:基于上述格式,如果value中有特殊字符,比如有换行符/分号等怎么办?

如果有思路,请基于上述的格式设计并实现一个完美的方案。
示例:

   NSArray *array = @[@{@"key01":@"value\n01",@"key;02":@"value02"},@{@"key11":@"value11",@"key12":@"value12"},@{@"key21":@"value21",@"key22":@"value22"}];
    NSLog(@"originArray:%@",array);
    NSString *text = [self store:array];
    NSLog(@"text:%@",text);
    NSArray *loadArray = [self load:text];
    NSLog(@"loadArray:%@",[[loadArray description] stringByRemovingPercentEncoding]);
- (NSString *)store:(NSArray <NSDictionary *> *)array
{
    NSMutableString *string = [NSMutableString new];
    __block BOOL keyBegin = YES;
    BOOL nextElement = NO;
    for (NSDictionary *dic in array) {
        if (nextElement) {
            [string appendFormat:@"\n"];
        }
        keyBegin = YES;
        [dic enumerateKeysAndObjectsUsingBlock:^(id  _Nonnull key, id  _Nonnull obj, BOOL * _Nonnull stop) {
            [string appendFormat:@"%@%@=%@",keyBegin?@"":@";",[key stringByAddingPercentEncodingWithAllowedCharacters:[NSCharacterSet URLPathAllowedCharacterSet]],[obj stringByAddingPercentEncodingWithAllowedCharacters:[NSCharacterSet URLPathAllowedCharacterSet]]];
            if (keyBegin) {
                keyBegin = NO;
            }
        }];
        nextElement = YES;
    }
    return string;
}
- (NSArray *)load:(NSString *)text
{
    NSMutableArray *array = [NSMutableArray new];
    NSArray *tempArray = [text componentsSeparatedByString:@"\n"];
    for (NSString *dicString in tempArray) {
        NSArray *dicArray = [dicString componentsSeparatedByString:@";"];
        NSMutableDictionary *tempDic = [NSMutableDictionary new];
        for (NSString *keyValues in dicArray) {
            NSArray *dicInfo = [keyValues componentsSeparatedByString:@"="];
            [tempDic setObject:dicInfo.lastObject forKey:dicInfo.firstObject];
        }
        [array addObject:tempDic];
    }
    return array;
}

相关文章

  • 数据结构与算法——基础篇(一)

    前置问题 经典问题与算法 8皇后问题(92种摆法)——回溯算法 字符串匹配问题——KMP算法(取代暴力匹配) 汉诺...

  • 可判定性

    研究算法在求解问题上的能力。有些问题算法上可解,有些问题算法上不可解。 5.1 可判定语言 算法上可判定的语言。 ...

  • 垃圾回收算法

    标记-清除算法 是最基础的GC算法,其他算法都是基于此算法,并且改进其缺点。 缺点: 效率问题 空间问题:标记清除...

  • 区块链共识机制

    非拜占庭问题,采用帕克斯算法和RUFT算法;拜占庭问题,采用拜占庭容错算法,进一步发展了优化PBFT算法。PBFT...

  • 算法问题

    1、我们的程序运行过程中每分钟会采集一个整数的数据指标。持续采集n分钟就得到一个有n个元素的整数数组a[n]。现在...

  • 「数据分类」14决策树分类之CART算法

    1.CART算法与ID3算法对比 (1)CART算法解决了ID3算法的不足,既能用于分类问题,又能用于回归问题。 ...

  • Paxos算法介绍—Basic Paxos

    1算法背景和问题分析 1.1 Paxos算法解决的问题 Paxos算法解决的问题是一个分布式系统如何就某个值(决议...

  • 7.8图的应用:最短路径问题

    最短路径问题:Dijkstra算法 ❖解决带权最短路径问题的经典算法是以发明者命名的“Dijkstra算法”❖这是...

  • 算法与数据结构(十) 总结

    课程总结 过程: 线性问题: 树形问题: 图论问题: 更多算法问题 算法设计相关: 贪心:从最小到最大,或从最大到...

  • 算法(2)KMP算法

    1.0 问题描述 实现KMP算法查找字符串。 2.0 问题分析 “KMP算法”是对字符串查找“简单算法”的优化。 ...

网友评论

      本文标题:算法问题

      本文链接:https://www.haomeiwen.com/subject/amdvqftx.html