前言
用OC刷剑指offer
代码基于macOS命令行编写，测试用例已编写在单元测试中，若有遗漏的用例，欢迎留言指正。
第一题
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
- 二维数组为空时，直接返回 NO
- 第一个数大于 number 或最后一个数小于 number，则该整数不存在
- 从第一行最后一个数 A 开始查找
- number > A => 该整数一定在下一行
- number <= A => 该整数就在这一行
- 找到整数可能所在的行，往回便利该行
- number == A => 找到该整数
- number < A => 继续往回遍历
- number < A && j == 0 => 该整数不存在
- 最后一行的最后一个数也小于 number，则该数不存在
/**
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
@param maxtrix 输入二维矩阵
@param number 输入整数
@return 整数是否存在
*/
+ (BOOL)isExistInMatrix:(NSArray *> *)maxtrix number:(NSInteger)number {
if ([maxtrix.className isEqualToString:@"NSNull"] || !maxtrix.count || maxtrix == nil) { //鲁棒性
return NO;
}
if ([[maxtrix firstObject] firstObject].integerValue > number || [[maxtrix lastObject] lastObject].integerValue < number) {
return NO;
}
for (int i = 0; i < maxtrix.count; i++) {
NSArray *array = maxtrix[i];
for (NSInteger j = array.count - 1; j >= 0; j--) {
if (array[j].integerValue < number) {
break;
} else if (array[j].integerValue == number) {
return YES;
} else if (j == 0 && array[j].integerValue > number) {
return NO;
}
}
}
return NO;
}
第二题
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为we are coders.则经过替换之后的字符串为we%20are%20coders。
/**
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
@param string 旧字符串
@param length 字符串长度
@return 替换之后的字符串
*/
+ (NSString *)replaceSpace:(NSString *)string length:(NSUInteger)length {
NSUInteger spaceLen = [self getSpaceLength:string length:length];
// 获取新字符串长度
NSUInteger newLen = length + 2 * spaceLen;
// 初始化新字符串
NSMutableString *newString = [NSMutableString stringWithCapacity:newLen];
NSUInteger i = 0;
NSUInteger j = 0;
while (i < length && j < newLen) { // NSMutableString无法往后插入
if ([self isSpace:string index:i]) { // 空格插入 %2d
[newString insertString:@"%" atIndex:j++];
[newString insertString:@"2" atIndex:j++];
[newString insertString:@"d" atIndex:j++];
i++;
} else { // 非空格插入旧字符
[newString insertString:[string substringWithRange:NSMakeRange(i++, 1)] atIndex:j++];
}
}
return [newString copy];
}
/**
获取空格数
@param string 旧字符串
@param length 字符串长度
@return 空格数
*/
+ (NSUInteger)getSpaceLength:(NSString *)string length:(NSUInteger)length {
NSUInteger spaceLen = 0;
NSUInteger oldLen = length;
while (oldLen > 0) {
if ([string characterAtIndex:oldLen - 1] == ' ') {
spaceLen++;
}
oldLen--;
}
return spaceLen;
}
/**
是否是空格
@param string 旧字符串
@param i 当前位置
@return isSpace
*/
+ (BOOL)isSpace:(NSString *)string index:(NSUInteger)i {
return [string characterAtIndex:i] == ' ';
}
第三题
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
解题思路：
从尾到头排序很容易想到使用栈来实现，即将链表存入栈中，利用栈的先入后出（FILO）倒序输出数组。以下是算法实现，另外笔者实现了简单的栈与链表结构，有兴趣的读者可到github上查看源码。
/**
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
@param head 链表头
@return 倒序数组
*/
+ (NSArray *)getListFromTailToHead:(ListNode *)head {
TZStack *stack = [[TZStack alloc] init];
while (head) {
[stack push:@(head->value)];
head = head->next;
}
NSMutableArray *list = [NSMutableArray array];
while (!stack.empty) {
[list addObject:[stack pop]];
}
return [list copy];
}
第四题
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
解题思路：
- 前序遍历的第一个数 => 根节点A
- 中序遍历被根节点A分为左子树的中序遍历（DBE）和右子树的中序遍历（FCG）
- 前序遍历根据中序遍历A的位置，将前序遍历分为左子树的前序遍历（BDE）和右子树的前序遍历（CFG）
- 递归
- 左子树：前序遍历BDE、中序遍历DBE
- 右子树：前序遍历CFG、中序遍历FCG
+ (TreeNode *)reConstructBinaryTree:(NSArray *)pre vin:(NSArray *)vin {
if (pre.count == 0 || vin.count == 0) { // 长度为0，为空节点
return NULL;
}
TreeNode *root = malloc(sizeof(TreeNode));
int rootVal = [pre firstObject].intValue;
root->value = rootVal;
// 获取middle节点
int leftVinIndex = 0;
for (int i = 0; i < vin.count; i++) {
leftVinIndex++;
if (vin[i].intValue == rootVal) {
break;
}
}
NSArray *subPreLeft = [pre subarrayWithRange:NSMakeRange(1, leftVinIndex - 1)];
NSArray *subVinLeft = [vin subarrayWithRange:NSMakeRange(0, leftVinIndex - 1)];
NSArray *subPreRight = [pre subarrayWithRange:NSMakeRange(leftVinIndex, pre.count - leftVinIndex)];
NSArray *subVinRight = [vin subarrayWithRange:NSMakeRange(leftVinIndex, vin.count - leftVinIndex)];
// 递归左右子树
root->left = [self reConstructBinaryTree:subPreLeft vin:subVinLeft];
root->right = [self reConstructBinaryTree:subPreRight vin:subVinRight];
return root;
}
第五题
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为NSNumber类型。
解题思路：
栈：先进后出(First In Last Out, FILO)
队列：先进先出(First In First Out, FIFO)
因此可以利用两个栈实现队列：
- pushStack 保存push进来的元素 [1, 2, 3, 4, 5]
- 再逆序将pushStack元素保存到popStack中[5, 4, 3, 2, 1]，这样popStack的栈顶就是1了
- pop出popStack的栈顶
@interface NumberFive()
/**
保存入队的元素
*/
@property (nonatomic, strong) TZStack *pushStack;
/**
保存出队的元素
*/
@property (nonatomic, strong) TZStack *popStack2;
@end
@implementation NumberFive
- (NSNumber *)pop {
// 用于pop的栈为空时，倒序插入pushStack
if (self.popStack2.empty) {
while (!self.pushStack.empty) {
[self.popStack2 push:[self.pushStack pop]];
}
}
// 出队列
return [self.popStack2 pop];
}
- (void)push:(NSNumber *)node {
[self.pushStack push:node];
}
- (TZStack *)pushStack {
if (!_pushStack) {
_pushStack = [[TZStack alloc] init];
}
return _pushStack;
}
- (TZStack *)popStack2 {
if (!_popStack2) {
_popStack2 = [[TZStack alloc] init];
}
return _popStack2;
}
@end
