OC算法面试题及详细答案（实战版）

OC算法面试题及详细答案（实战版）本套题目为iOS/OC开发岗位面试高频算法题，覆盖数组、字符串、链表、递归、排序、哈希等核心考点，难度贴合初中级开发面试，答案采用工程化思路编写，无书面化模板，适配实际面试答题场景。一、基础算法题（入门必考）1、字符串反转（手写实现，禁止调用系统reverse方法）题目描述：输入一段普通字符串，返回完全反转后的字符串，例如输入@"abc123"，输出@"321cba"。解题思路：利用字符数组首尾双指针，首尾字符交换，指针向中间靠拢，直到指针相遇，时间复杂度O(n)，空间复杂度O(n)。OC中字符串不可变，需先转为字符数组操作。参考答案：objective-c

+(NSString*)reverseString:(NSString*)str{

//空值容错处理

if(!str||str.length==0){

return@"";

}

//转为可变字符数组

NSMutableArray*charArr=[NSMutableArrayarray];

for(NSIntegeri=0;i<str.length;i++){

[charArraddObject:[strsubstringWithRange:NSMakeRange(i,1)]];

}

//双指针交换

NSIntegerleft=0;

NSIntegerright=charArr.count-1;

while(left<right){

//首尾交换

[charArrexchangeObjectAtIndex:leftwithObjectAtIndex:right];

left++;

right--;

}

//拼接结果

NSMutableString*result=[NSMutableStringstring];

for(NSString*charStrincharArr){

[resultappendString:charStr];

}

returnresult;

}

面试延伸：如果是超长字符串，该方法效率优于系统简单API，避免一次性全量反转的性能损耗；日常开发可用于文案倒序、密码脱敏等场景。2、数组去重（保留原有顺序）题目描述：给定一个OC数组（元素为字符串/数字），去除重复元素，保留元素第一次出现的顺序，返回新数组。解题思路：用字典记录已出现的元素（字典查询效率O(1)），遍历原数组，未记录的元素存入新数组并标记，最终实现有序去重，时间复杂度O(n)。参考答案：objective-c

+(NSArray*)removeDuplicateInArray:(NSArray*)originArr{

if(!originArr||originArr.count==0){

return@[];

}

NSMutableDictionary*recordDic=[NSMutableDictionarydictionary];

NSMutableArray*resultArr=[NSMutableArrayarray];

for(idobjinoriginArr){

//未记录过则存入结果

if(!recordDic[obj]){

recordDic[obj]=@(YES);

[resultArraddObject:obj];

}

}

returnresultArr.copy;

}

踩坑说明：不可直接用NSSet去重，NSSet会打乱原有数组顺序，面试中大概率会追问该知识点。二、进阶高频算法题（面试核心）1、两数之和题目描述：给定一个整数数组和一个目标值，找出数组中两个相加等于目标值的元素下标，假设每组输入只有唯一解，同一个元素不能使用两次。解题思路：哈希字典存储遍历过的数值和下标，遍历过程中计算差值，若差值已存在，直接返回对应下标，单次遍历即可完成，时间复杂度O(n)。参考答案：objective-c

+(NSArray*)twoSum:(NSArray*)numstarget:(NSInteger)target{

NSMutableDictionary*tempDic=[NSMutableDictionarydictionary];

for(NSIntegeri=0;i<nums.count;i++){

NSIntegernum=[nums[i]integerValue];

NSIntegerdiff=target-num;

//找到匹配的差值，返回下标

if(tempDic[@(diff)]){

return@[tempDic[@(diff)],@(i)];

}

//记录当前数值和下标

tempDic[@(num)]=@(i);

}

return@[];

}

面试追问应答：暴力双层循环时间复杂度O(n²)，数据量大时卡顿严重，哈希解法是最优解，适配项目中批量匹配、数据配对场景。2、冒泡排序（手写原生实现）题目描述：手写冒泡排序，对整数数组进行升序排序，优化低效遍历逻辑。解题思路：相邻元素两两对比，前大于后则交换位置，每轮遍历确定一个最大值；增加有序标记，提前终止遍历，优化最优时间复杂度。参考答案：objective-c

+(NSArray*)bubbleSort:(NSArray*)nums{

if(nums.count<=1){

returnnums;

}

NSMutableArray*arr=nums.mutableCopy;

NSIntegercount=arr.count;

BOOLisSorted;//有序标记

for(NSIntegeri=0;i<count-1;i++){

isSorted=YES;

for(NSIntegerj=0;j<count-1-i;j++){

NSIntegerleft=[arr[j]integerValue];

NSIntegerright=[arr[j+1]integerValue];

if(left>right){

//交换位置

[arrexchangeObjectAtIndex:jwithObjectAtIndex:j+1];

isSorted=NO;

}

}

//已有序，提前退出

if(isSorted){

break;

}

}

returnarr.copy;

}

知识点总结：优化后最优时间复杂度O(n)，最坏O(n²)，空间复杂度O(1)，属于稳定排序，适合小规模数据排序。3、斐波那契数列（非递归优化版）题目描述：斐波那契数列：1、1、2、3、5、8...，输入n，返回第n项数值，禁止低效递归。解题思路：传统递归存在大量重复计算，用迭代方式遍历累加，仅保存前两项数值，空间复杂度优化为O(1)，时间复杂度O(n)。参考答案：objective-c

+(NSInteger)fibonacci:(NSInteger)n{

//边界容错

if(n<=0)return0;

if(n==1||n==2)return1;

NSIntegerfirst=1;

NSIntegersecond=1;

NSIntegerresult=0;

for(NSIntegeri=3;i<=n;i++){

result=first+second;

first=second;

second=result;

}

returnresult;

}

面试考点：考察递归弊端认知，递归解法时间复杂度O(2ⁿ)，极易造成栈溢出，工程中一律使用迭代优化版。三、工程实战算法题（高阶面试）1、查找数组中出现次数最多的元素题目描述：给定任意类型数据数组，找出出现频次最高的元素，若多个元素频次相同，返回第一个出现的元素。解题思路：字典统计元素出现次数，遍历字典记录最大频次及对应元素，兼顾效率和顺序要求。参考答案：objective-c

+(id)findMaxFrequencyElement:(NSArray*)arr{

if(!arr||arr.count==0)returnnil;

NSMutableDictionary*countDic=[NSMutableDictionarydictionary];

//统计频次

for(idobjinarr){

NSIntegercount=[countDic[obj]integerValue];

countDic[obj]=@(count+1);

}

//遍历查找最大值

idmaxObj=nil;

NSIntegermaxCount=0;

for(idkeyincountDic.allKeys){

NSIntegercurrentCount=[countDic[key]integerValue];

if(currentCount>maxCount){

maxCount=currentCount;

maxObj=key;

}

}

returnmaxObj;

}2、判断回文字符串题目描述：判断一个字符串是否为回文串（正读和反读一致），忽略大小写、无特殊字符干扰。解题思路：双指针法，左指针从头部、右指针从尾部遍历，依次对比字符，遇到不一致直接返回NO，全部匹配成功返回YES。参考答案：objective-c

+(BOOL)isPalindrome:(NSString*)str{

if(!str)returnNO;

//统一转为小写，去除空格（适配常规场景）

NSString*lowerStr=[strlowercaseString];

lowerStr=[lowerStrstringByReplacingOccurrencesOfString:@""withString:@""];

NSIntegerleft=0;

NSIntegerright=lowerStr.length-1;

while(left<right){

NSString*leftChar=[lowerStrsubstringWithRange:NSMakeRange(left,1)];

NSString*rightChar=[lowerStrsubstringWithRange:NSMakeRange(right,1)];

if(![leftCharisEqualToString:rightChar]){

returnNO;

}

left++;

right--;

}

returnYES;

}

四、面试高频算法问答（口述题）1、OC中数组遍历方式对比，各自性能场景？1、for循环：性能最优，可控性强，适合复杂逻辑遍历、倒序遍历、需要下标操作的场景；2、for-in快速遍历：语法简洁，底层优化，日常普通遍历首选，不支持中途修改数组；3、enumerateObjectsUsingBlock：支持遍历下标、有序异步遍历，适