2018-04-11 算法 Objective-C作业

算法 Objective-C作业

如题：

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

给一个字符串，找出最长没有重复字符的子串。

解法一：
没有使用oc的字符串函数本版本

NSUInteger lengthOfLongestSubstring(NSString *str) {
    
    NSUInteger max = 0;
    int start = 0;
    int end   = 0;
    
    for (int i = 1; i < str.length; ++i) {
    
        char ci = [str characterAtIndex:i];
        for (int j = i - 1; j>0; --j) {
            char cj = [str characterAtIndex:j];
            if (ci == cj) {
                break;
            } else {
                if (i - j + 1 > max) {
                    max = i - j + 1;
                    start = j;
                    end   = i;
                }
            }
        }
    }
    
    NSLog(@"start : %@ end: %@",@(start),@(end));
    
    return max;
}

解法二：使用OC的字符串函数

NSUInteger lengthOfLongestSubstring1(NSString *str) {
    
    NSUInteger max = 0;
    
    NSString *result = @"";
    int start = 0;
    NSMutableString *recordStr = [[NSMutableString alloc] init];
    for (int i = 0; i < str.length; ++i)
    {
        if (![recordStr containsString:[str substringWithRange:NSMakeRange(i, 1)]])
        {
            [recordStr appendString:[str substringWithRange:NSMakeRange(i, 1)]];
        }
        else
        {
            if (i == str.length-1)
            {
                break;
            }
            NSRange range = [recordStr localizedStandardRangeOfString:[str substringWithRange:NSMakeRange(i, 1)]];
            i = (int)range.location + start;
            recordStr = [[NSMutableString alloc] init];
            
            start = i+1;
        }
        if (recordStr.length > result.length) {
            result = recordStr;
        }
    }
    
    NSLog(@"longestStris : %@",result);
    
    max = result.length;
    
    return max;
}

测试用例

NSString *s1 = @"111111";
    NSString *s2 = @"12342";
    NSString *s3 = @"abcabcda";
    NSString *s4 = @"ababc78tgtasdcfty";
    lengthOfLongestSubstring1(s1);
    
    lengthOfLongestSubstring1(s2);
    
    lengthOfLongestSubstring(s3);
    
    lengthOfLongestSubstring1(s4);