iOS算法篇-leetcode题目记录

1.两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

###方法一
- (NSArray *)twoSum:(NSArray *)nums target:(int)target {
    for (int i = 0; i < nums.count; i++) {
        for (int j = i + 1; j < nums.count; j++) {
            if ( [nums[i] intValue] + [nums[j] intValue] == target) {
                return @[@(i),@(j)];
            }
        }
    }
    return nil;
}

###方法二
- (NSArray *)twoSum:(NSArray *)nums target:(int)target {
    NSMutableDictionary *dic = [[NSMutableDictionary alloc] init];
    for (int i = 0; i < nums.count; i++) {
        [dic setObject:nums[i] forKey:@(i)];
    }
    for (int i = 0; i < nums.count; i++) {
        int value = target - [nums[i] intValue];
        if ([[dic allValues] containsObject:@(value)]) {
            return @[@(i),@([nums indexOfObject:@(value)])];
        }
    }
    return nil;
}

###方法三
- (NSArray *)twoSum:(NSArray *)nums target:(int)target {
    NSMutableDictionary *dic = [[NSMutableDictionary alloc] init];
    for (int i = 0; i < nums.count; i++) {
        [dic setObject:nums[i] forKey:@(i)];
        int value = target - [nums[i] intValue];
        if ([nums containsObject:@(value)] && ([nums indexOfObject:@(value)] != i)) {
            return @[@(i),@([nums indexOfObject:@(value)])];
        }
    }
    return nil;
}

//算法测试
NSArray *array = [[ NSArray alloc]initWithObjects:@(2),@(17),@(7),@(8),@(5), nil];
NSArray *newArray = [self twoSum:array target:9];
NSLog(@"newArray是%@",newArray);

2.两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

###方法一
- (NSArray *)addTwoNumbers:(NSArray *)array1 withArray:(NSArray *)array2 {
    int arraycount = (array1.count > array2.count ? array1.count : array2.count);
    int numA = 0;
    int numB = 0;
    int tes = 0;
    NSMutableArray *newArray = [[NSMutableArray alloc] init];
    for(int i = 0; i < arraycount; i++) {
        numA = (i < array1.count ? [array1[i] intValue] : 0);
        numB = (i < array2.count ? [array2[i] intValue] : 0);
        if (numA + numB < 10) {
            if (tes == 0) {
                [newArray addObject:@(numA + numB)];
            }else{
                [newArray addObject:@(numA + numB + 1)];
            }
            tes = 0;
        }else{
            if (tes == 0) {
                [newArray addObject:@(numA + numB - 10)];
            }else{
                [newArray addObject:@(numA + numB - 10 + 1)];
            }
            tes = 1;
        }
    }
    return newArray;
}

//算法测试
NSArray *array1 = [[ NSArray alloc]initWithObjects:@(2),@(4),@(3),@(3),nil];
NSArray *array2 = [[ NSArray alloc]initWithObjects:@(9),@(8),@(5), nil];
NSArray *newArray = [self addTwoNumbers:array1 withArray:array2];
NSLog(@"newArray是%@",newArray);

3.无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

方法一
将数据依次放入新数组,放入前先遍历新数组中是否有重复数据,若没有则添加,若有,则清空新数组,记录长度,将数据放入新数组中,每次发现重复数据时均比较长度,取最大值.

###方法一
- (int)lengthOfLongestSubstring:(NSString *)string {
//字符串转换为数组
    NSMutableArray *array = [NSMutableArray array];
    for (NSInteger i = 0; i < string.length; i++) {
        NSRange   range =  NSMakeRange(i, 1);
        NSString *subStr = [string substringWithRange:range];
        [array addObject:subStr];
    }
    
    NSMutableArray *newArray = [[NSMutableArray alloc] init];
    int num = 0;
    int max = 0;
    for (int i = 0; i < array.count; i++) {
        for (int j = 0; j < newArray.count; j++) {
            if (array[i] == newArray[j]) {
                [newArray removeAllObjects];
                max = max < num ? num : max;
                num = 0;
            }
        }
        [newArray addObject:array[I]];
        num++;
    }
    max = max < num ? num : max;
    return max;
}

//算法测试
int a = [self lengthOfLongestSubstring:@"abcdaabcded"];