美文网首页iOS-进阶题目
iOS面试常见算法题2020(一)

iOS面试常见算法题2020(一)

作者: 执笔时光er | 来源:发表于2020-04-06 16:50 被阅读0次

    现在面试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

    相关文章

      网友评论

        本文标题:iOS面试常见算法题2020(一)

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