現(xiàn)在面試iOS中高級開發(fā)拯勉，算法題已是必然會出現(xiàn)的一個環(huán)節(jié)了，這里把面試遇到的算法題做一個小匯總憔购，希望對大家有用宫峦。大部分公司是需要直接手寫算法題的，這塊兒的能力不容忽略的玫鸟。
- 1：編程實現(xiàn)字符串拷貝导绷，要考慮下內存重疊問題。 (搜狗)
- 2：對輸入的字符串屎飘，去除其中的字符‘b’以及連續(xù)出現(xiàn)的‘a’和‘c’ (字節(jié))
- 3：如何求兩個
View的最近公共父類 (字節(jié))
1：編程實現(xiàn)字符串拷貝妥曲，要考慮下內存重疊問題。(搜狗)
解決思路：既然要考慮內存重疊的問題钦购，就是說可能目標地址的起始位置是在源字符串的后半段檐盟，或者目標的結束位置在源字符串的前半段。第一種情況押桃，從末尾開始復制可以解決問題葵萎，同理：第二種情況，從首位開始復制可以解決問題怨规，代碼如下：
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;
}
2：對輸入的字符串波丰，去除其中的字符‘b’以及連續(xù)出現(xiàn)的‘a’和‘c’ (字節(jié))
樣例：
‘aacbd’ -> 'ad'
'aabcd' -> 'ad'
'aaabbccc' -> ''
不允許使用類似string.replace函數(shù)
要求時間、空間復雜度盡量優(yōu)化
3：如何求兩個View的最近公共父類 (字節(jié))
解決思路：
首先舶得，這個問題必然不能按照常規(guī)的方式去對一個VIew的所有父類去進行for循環(huán)比較掰烟，那這個題出的就沒有意義。
然后，每個類的所有父類組成了一個繼承鏈纫骑，而在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;
}
