现在面试iOS中高级开发，算法题已是必然会出现的一个环节了，这里把面试遇到的算法题和LeetCode上一些比较经典的算法题做一个汇总，希望对大家有用。大部分公司视频面试是通过牛客网来进行，是可以直接手写算法题的，这块儿的能力不容忽略的。
- 1 实现一个方法，计算100的阶乘。(KS一面)
- 2 编程实现字符串拷贝，要考虑下内存重叠问题。(SG输入法笔试题)
- 3 对输入的字符串，去除其中的字符‘b’以及连续出现的‘a’和‘c’(ZJTD面试题)
- 4 如何求两个View的最近公共父类(ZJTD面试题)
- 彩蛋：如何用两个骰子表示一个月的完整日期
1 实现一个方法，计算100的阶乘。(KS一面)
这个问题太过简单，主要考虑到通用性，还有就是尽量不要使用递归，会导致方法栈空间占用过大。所以采用for循环的方式进行计算就OK。
#import <Foundation/Foundation.h>
long long dofactorial(int min, int max){
if(min > max){
return 0;
}
if(min == 0){
if(max == 0){
//0的阶乘是1
return 1;
}else{
min = 1;
}
}
long long result = 1;
for (int i = min; i <= max; i++) {
result *= i;
if(result > INT_MAX){
//考虑溢出
return -1;
}
}
return result;
}
int main(int argc, const char * argv[]) {
int result = dofactorial(0, 100);
printf("result = %lld", result);
return 0;
}
2 编程实现字符串拷贝，要考虑下内存重叠问题。(SG输入法笔试题)
解决思路：既然要考虑内存重叠的问题，就是说可能目标地址的起始位置是在源字符串的后半段，或者目标的结束位置在源字符串的前半段。第一种情况，从末尾开始复制可以解决问题，同理：第二种情况，从首位开始复制可以解决问题，代码如下：
char *memcpy_qi(char *dst, const char* src, int cl)
{
assert(dst != NULL && src != NULL);
char *ret = dst;
if (dst >= src && dst <= src+ cl-1) //内存重叠，从高地址开始复制
{
//挪开空间
dst = dst+ cl-1;
//将指针挪到结尾
src = src+ cl-1;
while (cl—)
*dst— = *src—;
}
else //正常情况，从低地址开始复制
{
while (cl—)
*dst++ = *src++;
}
return ret;
}
char * strcpy_qi(char *dst,const char *src)
{
assert(dst != NULL && src != NULL);
char *ret = dst;
memcpy_qi(dst, src, strlen(src)+1);
return ret;
}
3 对输入的字符串，去除其中的字符‘b’以及连续出现的‘a’和‘c’(ZJTD面试题)
样例：
‘aacbd’ -> 'ad'
'aabcd' -> 'ad'
'aaabbccc' -> ''
不允许使用类似string.replace函数
要求时间、空间复杂度尽量优化
4 如何求两个View的最近公共父类(ZJTD面试题)
解决思路：
首先，这个问题必然不能按照常规的方式去对一个VIew的所有父类去进行for循环比较，那这个题出的就没有意义。
再，每个类的所有父类组成了一个继承链，而在UIKit下，所有的UIView的最终父类也必然是NSObject，其实就相当于这两个类的继承链从NSObject开始向下一直是重合的，直到最后的一个公共父类才开始分开，这个最后的公共父类也是最近的公共父类，这是典型的倒Y字型链表组合。那么解题思路就很好做了，具体代码如下：
- (void)viewDidLoad {
[super viewDidLoad];
Class commonClass = [self commonClass1:[ViewA class] andClass:[ViewB class]];
NSLog(@"最近公共父类为:%@",commonClass);
}
// 获取所有父类
- (NSArray *)superClasses:(Class)class {
if (class == nil) {
return @[];
}
NSMutableArray *result = [NSMutableArray array];
while (class != nil) {
[result addObject:class];
class = [class superclass];
}
return [result copy];
}
//对两条链表进行比对
- (Class)commonClass1:(Class)classA andClass:(Class)classB {
NSArray *arr1 = [self superClasses:classA];
NSArray *arr2 = [self superClasses:classB];
NSInteger count = arr1.count < arr2.count ? arr1.count : arr2.count;
Class resultClass;
for (NSUInteger i = 0; i < arr1.count; ++i) {
Class classA = arr1[arr1.count - i - 1];
Class classB = arr2[arr2.count - i - 1];
if(classA == classB){
resultClass = classA;
}else{
break;
}
}
return resultClass;
}
如何用两个骰子表示一个月的完整日期
分享个以前朋友给我出的问题，问题是这样的：现有两个骰子，每个骰子6个面，全是空的，现在需要用这两个骰子表示年月日中的日的全部情况(1-31),1号算01，一个骰子只能表示一位，且不能两位都用同一个骰子，那么在这种情况下，每个骰子的六个面上该怎么刻数字呢？
解决思路：
一、月份的日期，是从1号到31号的，那十位上的所有可能性就是0、1、2、3.个位上也是包含这几个数的，那么0、1、2、3必然两个骰子上都有。
二、但是，十位为3的情况只有30，31，在两个骰子上都有0、1、2的情况下，3只在一个骰子有也可以表示出来的，颠倒位置即可，那么就是0、1、2必须每个骰子上都有。
三、两头骰子此时还剩下6个面，日期必须的数字此时还剩下，3、4、5、6、7、8、9一共7个数，数字比面数多一个，那就是还得想办法再节省一个。这个时候就要考虑下6和9能不用共用一个面了。
答案：
骰子A ： 0、1、2、3、4、5
骰子B ： 0、1、2、6、7、8
