美文网首页数据结构与算法算法
iOS-算法集锦-剑指offer-百题详解之一

iOS-算法集锦-剑指offer-百题详解之一

作者: 路飞_Luck | 来源:发表于2018-10-27 10:38 被阅读16次
目录

阅前需知

1.本文部分内容参考剑指 offer 题解，如有侵权，请告知。其他内容均属原创，转载请告知。
2.本文示例代码中给一些类增加了一些类扩展，因篇幅原因，未在文中写出，详情见项目源码，地址文末有提供。
3.阅读本文之前需要先了解节点,链表,栈,二叉树的实现。详情见如下文章连接。
4.因为 OC 中没有栈，链表节点，链表的概念，所以本项目自定义了栈，链表节点，链表类。
5.因技术水平有限，如有错误，欢迎指正。

以下是通过 OC 语法实现

3.数组中重复的数字

题目描述

在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

Input: {2, 3, 1, 0, 2, 5}
Output:2
解题思路

要求复杂度为 O(N) + O(1)，也就是时间复杂度 O(N)，空间复杂度 O(1)。因此不能使用排序的方法，也不能使用额外的标记数组。牛客网讨论区这一题的首票答案使用 nums[i] + length 来将元素标记，这么做会有加法溢出问题。

这种数组元素在 [0, n-1] 范围内的问题，可以将值为 i 的元素调整到第 i 个位置上。

以 (2, 3, 1, 0, 2, 5) 为例：

position-0 : (2,3,1,0,2,5) // 2 <-> 1
             (1,3,2,0,2,5) // 1 <-> 3
             (3,1,2,0,2,5) // 3 <-> 0
             (0,1,2,3,2,5) // already in position
position-1 : (0,1,2,3,2,5) // already in position
position-2 : (0,1,2,3,2,5) // already in position
position-3 : (0,1,2,3,2,5) // already in position
position-4 : (0,1,2,3,2,5) // nums[i] == nums[nums[i]], exit

遍历到位置 4 时，该位置上的数为 2，但是第 2 个位置上已经有一个 2 的值了，因此可以知道 2 重复。

具体代码如下:
+ (NSArray *)duplicate:(NSArray *)nums {
    if (nums == nil || nums.count == 0) {
        return nil;
    }
    
    NSMutableArray *numbers = [NSMutableArray arrayWithArray:nums];
    NSMutableArray *temp = [NSMutableArray array];
    
    for (int i = 0; i < numbers.count; i++) {
        while ([numbers[i] intValue] != i) {
            int number = [numbers[i] intValue];
            // 检查 number 与第 number 位置上的值是否相等,如果相等,说明该 number 重复了,否则索引 i 和 number 两者的值
            if (number == [numbers[number] intValue]) {
                [temp addObject:numbers[i]];
                return temp.copy;
            }
            [self cs_swap:numbers i:i j:number];
        }
    }
    
    return nil;
}

// 交换数组中i 和 j 位置上的数字
+ (void)cs_swap:(NSMutableArray *)numbers i:(int)i j:(int)j {
    if (i >= numbers.count || j >= numbers.count) {
        return;
    }
    NSNumber *number = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = number;
}
测试案例代码
// 3.数组中重复的数字
- (void)repeatNumber {
    NSMutableArray *arrM = [NSMutableArray array];
    for (int i = 0; i < 10; i++) {
        NSMutableArray *numbers = [NSMutableArray array];
        for (int j = 0; j < 10; j++) {
            [numbers addObject:[NSNumber numberWithInt:arc4random_uniform(10)]];
        }
        [arrM addObject:numbers];
    }
    
    for (int i = 0; i < arrM.count; i++) {
        NSArray *numbers = [arrM objectAtIndex:i];
        NSArray *repeatNumbers = [_3_repeatNumber duplicate:numbers];
        NSLog(@"i = %d, 原始数组:%@, 重复数字:%@",i,[numbers getAllObjectsDescription],[repeatNumbers getAllObjectsDescription]);
    }
}
运行结果
3.数组中重复的数字.png

4.二维数组中的查找

题目描述

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

Consider the following matrix:
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.
Given target = 20, return false.
解题思路

从右上角开始查找。矩阵中的一个数，它左边的数都比它小，下边的数都比它大。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来缩小查找区间。

复杂度：O(M + N) + O(1)

当前元素的查找区间为左下角的所有元素，例如元素 12 的查找区间如下：

image.png
详细代码如下
// 初始化一个二维数组
+ (bool)findNumber:(int)number numbers:(NSArray *)numbers {
    if (numbers == nil) {
        NSArray *number1 = @[@1,@4,@7,@11,@15];
        NSArray *number2 = @[@2,@5,@8,@12,@19];
        NSArray *number3 = @[@3,@6,@9,@16,@22];
        NSArray *number4 = @[@10,@13,@14,@17,@24];
        NSArray *number5 = @[@18,@21,@23,@26,@30];
        numbers = @[number1,number2,number3,number4,number5];
    }
    return [self find:number matrix:numbers];
}

// 在二维数组 matrix 中查找目标数 target
+ (bool)find:(int)target matrix:(NSArray *)matrix {
    if (matrix == nil || matrix.count == 0) {
        return false;
    }
    NSUInteger rows = matrix.count;    // 行数
    NSArray *colArray = matrix[0];
    NSUInteger cols = colArray.count;  // 列数
    int r = 0;  // 第 r 行
    int c = (int)cols - 1; // 第 c 列 从右上角开始
    
    while (r <= rows - 1 && c >= 0) {
        if (target == [matrix[r][c] integerValue]) {
            NSLog(@"target = %d, row = %d, col = %d",target,r,c);
            return true;
        } else if (target > [matrix[r][c] integerValue]) {
            r++; // 行数+1
        } else {
            c--;    // 列数减1
        }
    }
    return false;
}
测试案例代码
// 4.二维数组中的查找
- (void)twoDimensionArrayFind {
    NSArray *targets = @[@16,@6,@30,@20,@15];
    for (int i = 0; i < targets.count; i++) {
        bool isFind = [TwoDimensionalArrayFind_04 findNumber: [targets vFI:i] numbers:nil];
        if (!isFind) {
            NSLog(@"target = %d, noFind",[targets vFI:i]);
        }
    }
}
运行结果
4.二维数组中的查找.png

5.替换空格

题目描述

将一个字符串中的空格替换成 "%20"。

Input:
"We Are Happy"

Output:
"We%20Are%20Happy"
解题思路

在字符串尾部填充任意字符，使得字符串的长度等于替换之后的长度。因为一个空格要替换成三个字符（%20），因此当遍历到一个空格时，需要在尾部填充两个任意字符。

令 P1 指向字符串原来的末尾位置，P2 指向字符串现在的末尾位置。P1 和 P2 从后向前遍历，当 P1 遍历到一个空格时，就需要令 P2 指向的位置依次填充 02%（注意是逆序的），否则就填充上 P1 指向字符的值。

从后向前遍是为了在改变 P2 所指向的内容时，不会影响到 P1 遍历原来字符串的内容。

详细代码如下
+ (NSString *)replaceSpace:(NSString *)str {
    int p1 = (int)str.length - 1;
    NSMutableString *strM = [NSMutableString stringWithString:str];
    
    // 1.将在原来的空格后面再加上2个空格
    for (int i = 0; i < p1 + 1; i++) {
        NSString *temp = [str substringWithRange:NSMakeRange(i, 1)];
        if ([temp isEqualToString:@" "]) {
            [strM appendString:@"  "];
        }
    }
    
    // p1 p2依次从后往前遍历
    int p2 = (int)strM.length - 1;
    while (p1 >= 0 && p2 >= 0) {
        NSString *temp = [strM substringWithRange:NSMakeRange(p1--, 1)];
        if ([temp isEqualToString:@" "]) {  // 发现空格 - 逆序填充02%
            [strM replaceCharactersInRange:NSMakeRange(p2--, 1) withString:@"0"];
            [strM replaceCharactersInRange:NSMakeRange(p2--, 1) withString:@"2"];
            [strM replaceCharactersInRange:NSMakeRange(p2--, 1) withString:@"%"];
        } else {
            [strM replaceCharactersInRange:NSMakeRange(p2--, 1) withString:temp];
        }
    }
    
    return strM.copy;
}
测试案例代码
// 5.替换空格
- (void)replaceSpace {
    NSString *str = @"We Are Happy";
    NSLog(@"oldStr = %@",str);
    NSString *newStr = [ReplaceBlank_05 replaceSpace:str];
    NSLog(@"newStr = %@",newStr);
}
运行结果
5.替换空格.png

6.从尾到头打印链表

本题使用到栈，链表节点，链表。项目中已经实现了这些类的定义，详情请看原项目，这里不再过多的阐述。

题目描述

输入链表的第一个节点，从尾到头反过来打印出每个结点的值。


image.png
解题思路
6.1 使用栈
详细代码如下
/** 使用栈 */
+ (NSArray *)printListFromTailToHeadByShed:(NSArray *)numbers {
    LinkedArray *linkedArray = [[LinkedArray alloc] initLiknedArrayWithNunbers:numbers];
    // 第一个节点
    ListNode *listNode = [linkedArray getFirstListNode];
    
    return [self getListFromTailToHead:listNode];
}

// 使用栈
+ (NSArray *)getListFromTailToHead:(ListNode *)listNode {
    // 创建一个栈
    Stack *stack = [[Stack alloc] init];
    
    // 开始从第一个节点依次往后遍历,将数据全部入栈
    while (listNode != nil) {
        [stack push:listNode.content];
        listNode = listNode.next;
    }
    
    NSMutableArray *values = [NSMutableArray array];
    // 依次将栈出列并存储
    while (!stack.isEmpty) {
        [values addObject:stack.popObj];
    }
    
    return values.copy;
}
测试案例代码
// 1.使用栈
NSArray *arr = [PrintListFromTailToHead_06 printListFromTailToHeadByShed:@[@1,@2,@3]];
NSLog(@"arr = %@",arr);
运行结果
6.1使用栈.png
6.2 使用递归
详细代码如下
/** 使用递归 */
+ (NSArray *)printListFromTailToHeadByRecursion:(NSArray *)numbers {
    LinkedArray *linkedArray = [[LinkedArray alloc] initLiknedArrayWithNunbers:numbers];
    // 第一个节点
    ListNode *listNode = [linkedArray getFirstListNode];
    
    NSMutableArray *values = [NSMutableArray array];
    if (listNode != nil) {
        [values addObjectsFromArray:[self getListFromTailToHead:listNode.next]];
        [values addObject:listNode.content];
    }
    
    return values;
}

// 使用栈
+ (NSArray *)getListFromTailToHead:(ListNode *)listNode {
    // 创建一个栈
    Stack *stack = [[Stack alloc] init];
    
    // 开始从第一个节点依次往后遍历,将数据全部入栈
    while (listNode != nil) {
        [stack push:listNode.content];
        listNode = listNode.next;
    }
    
    NSMutableArray *values = [NSMutableArray array];
    // 依次将栈出列并存储
    while (!stack.isEmpty) {
        [values addObject:stack.popObj];
    }
    
    return values.copy;
}
测试案例代码
// 2.使用递归
NSArray *arr = [PrintListFromTailToHead_06 printListFromTailToHeadByRecursion:@[@1,@2,@3]];
NSLog(@"arr = %@",arr);
运行结果
6.2使用递归.png
6.3 使用头插法
解题思路

利用链表头插法为逆序的特点。

头结点和第一个节点的区别：

  • 头结点是在头插法中使用的一个额外节点，这个节点不存储值；
  • 第一个节点就是链表的第一个真正存储值的节点。
详细代码如下
+ (NSArray *)printListFromTailToHeadByInsert:(NSArray *)numbers {
    LinkedArray *linkedArray = [[LinkedArray alloc] initLiknedArrayWithNunbers:numbers];
    // 第一个节点
    ListNode *listNode = [linkedArray getFirstListNode];
    
    // 头插法构建逆序链表
    ListNode *head = [[ListNode alloc] init];
    while (listNode != nil) {
        ListNode *memo = listNode.next;
        listNode.next = head.next;
        head.next = listNode;
        listNode = memo;
    }
    // 构建 ArrayList
    NSMutableArray *values = [NSMutableArray array];
    head = head.next;
    while (head != nil) {
        [values addObject:head.content];
        head = head.next;
    }
    
    return values;
}
测试案例代码
// 3.使用头表插入法
NSArray *arr = [PrintListFromTailToHead_06 printListFromTailToHeadByInsert:@[@1,@2,@3]];
NSLog(@"arr = %@",arr);
运行结果
6.3头插入法.png
6.4 使用 Collections.reverse()
详细代码如下
/** 使用Collection reverse*/
+ (NSArray *)printListFromTailToHeadByReverse:(NSArray *)numbers {
    LinkedArray *linkedArray = [[LinkedArray alloc] initLiknedArrayWithNunbers:numbers];
    // 第一个节点
    ListNode *listNode = [linkedArray getFirstListNode];
    
    // 构建 ArrayList
    NSMutableArray *values = [NSMutableArray array];
    while (listNode != nil) {
        [values addObject:listNode.content];
        listNode = listNode.next;
    }
    
    NSArray *newArr = [[values reverseObjectEnumerator] allObjects];
    
    return newArr;
}
测试案例代码
// 4.使用reverse 反序
NSArray *arr = [PrintListFromTailToHead_06 printListFromTailToHeadByReverse:@[@1,@2,@3]];
NSLog(@"arr = %@",arr);
运行结果
6.4使用反序.png

7重建二叉树

题目描述

根据二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

preorder = [3,9,20,15,7]
inorder =  [9,3,15,20,7]
image.png
解题思路

前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果。

详细代码如下
+ (BinaryTreeNode *)reConstructBinaryTree:(NSArray *)preorders inorders:(NSArray *)inorders {
    // 初始化哈希表
    HashMap *indexForInOrders = [[HashMap alloc] init];
    
    for (int i = 0; i < inorders.count; i++) {
        [indexForInOrders put:[inorders[i] intValue] index:i];
    }
    
    return [self reConstructBinaryTreeWithOrders:indexForInOrders preorders:preorders preL:0 preR:(int)preorders.count - 1 inL:0];
}

+ (BinaryTreeNode *)reConstructBinaryTreeWithOrders:(HashMap *)indexForInOrders preorders:(NSArray *)preorders preL:(int)preL preR:(int)preR inL:(int)inL {
    if (preL > preR) {
        return nil;
    }
    
    // 取左边二叉树的值构成一个新的节点
    BinaryTreeNode *root = [BinaryTreeNode binaryTreeNodeWithValue:[preorders[preL] integerValue]];
    int inIndex = [indexForInOrders get:(int)root.value];
    int leftTreeSize = inIndex - inL;
    
    root.leftNode = [self reConstructBinaryTreeWithOrders:indexForInOrders preorders:preorders preL:preL + 1 preR:preL + leftTreeSize inL:inL];
    root.rightNode = [self reConstructBinaryTreeWithOrders:indexForInOrders preorders:preorders preL:preL + leftTreeSize + 1 preR:preR inL:inL + leftTreeSize + 1];
    
    return root;
}
测试案例代码
// 7.重建二叉树
- (void)reConstructBinaryTree {
    NSArray *preorders = @[@3,@9,@20,@15,@7];
    NSArray *inorders = @[@9,@3,@15,@20,@7];
    BinaryTreeNode *treeNode = [ReConstructBinaryTree_07 reConstructBinaryTree:preorders inorders:inorders];
    NSLog(@"treeNode = %@",treeNode);
}
运行结果
image.png

8. 二叉树的下一个结点

题目描述

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

解题思路
  • 如果一个节点的右子树不为空，那么该节点的下一个节点是右子树的最左节点；
image.png
  • 否则，向上找第一个左链接指向的树包含该节点的祖先节点。
image.png
详细代码如下
测试案例代码
运行结果

9.用两个栈实现队列

题目描述

用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。

解题思路

in 栈用来处理入栈（push）操作，out 栈用来处理出栈（pop）操作。一个元素进入 in 栈之后，出栈的顺序被反转。当元素要出栈时，需要先进入 out 栈，此时元素出栈顺序再一次被反转，因此出栈顺序就和最开始入栈顺序是相同的，先进入的元素先退出，这就是队列的顺序。

image.png
详细代码如下
+ (NSNumber *)twoStackToQueue:(NSArray *)numbers {
    Stack *inStack = [[Stack alloc] init];
    Stack *outStack = [[Stack alloc] init];
    
    // 先将所有元素入栈
    for (NSNumber *number in numbers) {
        [inStack push:number];
    }
    
    if (outStack.isEmpty) {
        while (!inStack.isEmpty) {
            [outStack push:inStack.popObj];
        }
    }
    
    if (outStack.isEmpty) {
        NSLog(@"queue is empty");
    }
    
    return outStack.popObj;
}
测试案例代码
// 9.用两个栈实现队列
- (void)twoStackToQueue {
    NSArray *numbers = @[@1,@2,@3,@4];
    NSNumber *lastNumber = [TwoStackQueue twoStackToQueue:numbers];
    NSLog(@"lastNumber = %@",lastNumber);
}
运行结果
image.png

10.1 斐波那契数列

题目描述

求斐波那契数列的第 n 项，n <= 39。

image.png

如果使用递归求解，会重复计算一些子问题。例如，计算 f(10) 需要计算 f(9) 和 f(8)，计算 f(9) 需要计算 f(8) 和 f(7)，可以看到 f(8) 被重复计算了。

image.png
解题思路

考虑到第 i 项只与第 i-1 和第 i-2 项有关，因此只需要存储前两项的值就能求解第 i 项，从而将空间复杂度由 O(N) 降低为 O(1)。

详细代码如下
+ (int)Fibonacci:(int)number {
    if (number <= 1) {
        return number;
    }
    
    int pre2 = 0, pre1 = 1, fib = 0;
    
    for (int i = 2; i < number + 1; i++) {
        fib = pre1 + pre2;
        pre2 = pre1;
        pre1 = fib;
    }
    
    return fib;
}
测试案例代码
// 10.1 斐波那契数列
- (void)fibonacci {
    for (int i = 0; i < 20; i++) {
        NSLog(@"i = %d, total = %d",i,[Fibonacci Fibonacci:i]);
    }
}
运行结果
10.1斐波那契数列.png

10.2 跳台阶

题目描述

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

解题思路

参考上一题思路

详细代码如下
+ (int)jumpFloor:(int)number {
    if (number <= 2) {
        return number;
    }
    
    int pre1 = 2, pre2 = 1;
    int result = 1;
    
    for (int i = 2; i < number; i++) {
        result = pre2 + pre1;
        pre2 = pre1;
        pre1 = result;
    }
    
    return result;
}
测试案例代码
// 10.2 跳台阶
- (void)jumpFloor {
    for (int i = 0; i < 10; i++) {
        NSLog(@"i = %d, total = %d",i,[Fibonacci jumpFloor:i]);
    }
}
运行结果
10.2跳台阶.png

10.3 变态跳台阶

题目描述

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级... 它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

解题思路

参考10.1实现思路

详细代码如下
+ (int)jumpFloor2:(int)number {
    if (number <= 0) {
        return 0;
    }
    // 1.构建数组
    NSMutableArray *arrM = [NSMutableArray array];
    for (int i = 0; i < number; i++) {
        [arrM addObject:[NSNumber numberWithInt:1]];
    }
    
    // 2.
    for (int i = 1; i < number; i++) {
        for (int j = 0; j < i; j++) {
            arrM[i] = [NSNumber numberWithInt:[arrM[i] intValue] + [arrM[j] intValue]];
        }
    }
    
    return [arrM[number - 1] intValue];
}
测试案例代码
// 10.3 变态跳台阶
- (void)jumpFloorII {
    for (int i = 0; i < 10; i++) {
        NSLog(@"i = %d, total = %d",i,[Fibonacci jumpFloor2:i]);
    }
}
运行结果
10.3变态跳台阶.png

10.4 矩形覆盖

题目描述

我们可以用 21 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 21 的小矩形无重叠地覆盖一个 2*n 的大矩形，总共有多少种方法？

解题思路

参考10.1实现思路

详细代码如下
+ (int)rectCover:(int)number {
    if (number <= 2) {
        return number;
    }
    
    int pre1 = 2, pre2 = 1;
    int result = 0;
    
    for (int i = 3; i < number + 1; i++) {
        result = pre2 + pre1;
        pre2 = pre1;
        pre1 = result;
    }
    
    return result;
}
测试案例代码
// 10.4 矩形覆盖
- (void)rectCover {
    for (int i = 0; i < 10; i++) {
        NSLog(@"i = %d, total = %d",i,[Fibonacci rectCover:i]);
    }
}
运行结果
10.4矩形覆盖.png

本文参考CS_Nodes 剑指 offer 题解.md 非常感谢该作者

相关知识点文章参考链接地址

  • 更多OC算法详解文章请持续关注作者，本人会在接下来的时间陆续整理。

如有错误，欢迎指正，多多点赞，打赏更佳，您的支持是我写作的动力。

项目连接地址 - ArithmeticDemo

相关文章

网友评论

本文标题：iOS-算法集锦-剑指offer-百题详解之一

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

延伸阅读

深度阅读

  • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

栏目导航

热点阅读

数据结构与算法

算法

关于我们|服务条款|联系我们|iOS-算法集锦-剑指offer-百题详解之一|投稿指南|网站地图|RSS订阅|排版工具|手机版

提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！