asunquan.com

不忘初心 不止于行

职场新人 iOS菜鸟 就职于搜狐畅游 从事iOS/tvOS的SDK开发 对于游戏市场有点点了解 平日和一只小Corgi同吃同睡


[转]面试题: 寻找最近公共View

前言

最近在巧叔的微信公众号上看到了巧叔开始更新了iOS开发面试题系列, 特此转载学习. 多谢巧叔. 闲话少说下面进入正题.

题目

找出两个 UIView 的最近的公共 View, 如果不存在, 则输出 nil

分析及答案

这其实是数据结构里面的找最近公共祖先的问题

一个 UIViewController 中的所有 view 之间的关系其实可以看成一颗树, UIViewController 的 view 变量是这颗树的根节点, 其它的 view 都是根节点的直接或间接子节点.

所以我们可以通过 view 的 superview 属性, 一直找到根节点. 需要注意的是, 在代码中, 我们还需要考虑各种非法输入, 如果输入了 nil, 则也需要处理, 避免异常. 以下是找到指定 view 到根 view 的路径代码:

+ (NSArray *)superViews:(UIView *)view 
{
    if (view == nil) 
    {
        return @[];
    }
  
    NSMutableArray *result = [NSMutableArray array];
    while (view != nil) 
    {
        [result addObject:view];
        view = view.superview;
    }
    return [result copy];
}

然后对于两个 view A 和 view B, 我们可以得到两个路径, 而本题中我们要找的是这里面最近的一个公共节点.

一个简单直接的办法: 拿第一个路径中的所有节点, 去第二个节点中查找.

假设路径的平均长度是 N, 因为每个节点都要找 N 次, 一共有 N 个节点, 所以这个办法的时间复杂度是 O ( N ^ 2 )

+ (UIView *)commonView_1:(UIView *)viewA andView:(UIView *)viewB 
{
    NSArray *arr1 = [self superViews:viewA];
    NSArray *arr2 = [self superViews:viewB];
  
    for (NSUInteger i = 0; i < arr1.count; ++i) 
    {
        UIView *targetView = arr1[i];
        for (NSUInteger j = 0; j < arr2.count; ++j) 
        {
            if (targetView == arr2[j]) 
            {
                return targetView;
            }
        }
    }
    return nil;
}

一个改进的办法: 我们将一个路径中的所有点先放进 NSSet 中. 因为 NSSet 的内部实现是一个 hash 表, 所以查找元素的时间复杂度变成了 O (1), 我们一共有 N 个节点, 所以总时间复杂度优化到了 O (N).

+ (UIView *)commonView_2:(UIView *)viewA andView:(UIView *)viewB 
{
    NSArray *arr1 = [self superViews:viewA];
    NSArray *arr2 = [self superViews:viewB];
    NSSet *set = [NSSet setWithArray:arr2];
  
    for (NSUInteger i = 0; i < arr1.count; ++i) 
    {
        UIView *targetView = arr1[i];
        if ([set containsObject:targetView]) 
        {
            return targetView;
        }
    }
    return nil;
}

除了使用 NSSet 外, 我们还可以使用类似归并排序的思想.

用两个指针, 分别指向两个路径的根节点, 然后从根节点开始, 找第一个不同的节点, 第一个不同节点的上一个公共节点, 就是我们的答案.

代码如下

/* O(N) Solution */
+ (UIView *)commonView_3:(UIView *)viewA andView:(UIView *)viewB 
{
    NSArray *arr1 = [self superViews:viewA];
    NSArray *arr2 = [self superViews:viewB];
    NSInteger p1 = arr1.count - 1;
    NSInteger p2 = arr2.count - 1;
    UIView *answer = nil;
    
    while (p1 >= 0 && p2 >= 0) 
    {
        if (arr1[p1] == arr2[p2]) 
        {
            answer = arr1[p1];
        }
        p1--;
        p2--;
    }
    return answer;
}

我们还可以使用 UIView 的 isDescendant 方法来简化我们的代码, 不过这样写的话, 时间复杂度应该也是 O ( N ^ 2 ) 的.

lexrus 提供了如下的 Swift 版本的代码:

// without flatMap
extension UIView {    
func commonSuperview(of view: UIView) -> UIView? {        
    if let s = superview {            
       if view.isDescendant(of: s) {                
                 return s
            } else {                
                 return s.commonSuperview(of: view)
            }
        }        
       return nil
    }
}

特别地, 如果我们利用 Optinal 的 flatMap 方法, 可以将上面的代码简化得更短, 基本上算是一行代码搞定.

extension UIView {
    func commonSuperview(of view: UIView) -> UIView? {
        return superview.flatMap { 
           view.isDescendant(of: $0) ? 
             $0 : $0.commonSuperview(of: view) 
        }
    }
}
最近的文章

[转]面试题: block中关于self的一些问题

题目我们知道, 在使用 block 的时候, 为了避免产生循环引用, 通常需要使用 weakSelf 与 strongSelf, 写下面这样的代码:__weak typeof(self) weakSelf = self;[self doSomeBlockJob:^{ __strong typeof(weakSelf) strongSelf = weakSelf; if (strongSelf) { ... }}];那么请问: 什么时候在 block 里面用 ...…

iOS开发面试题继续阅读
更早的文章

关于Apple圣诞节休息的通知

前言有快到了一年一度的圣诞节, 在西方圣诞节就和我们的春节一样重要, Apple也例行在PST12月23日到12月27日暂时关闭iTunes Connect的提交和更新功能.Get Your Apps Ready for the Holidays公告中表名, 在此期间苹果不接受任何新App的提交和现有App的更新(苹果审核团队放大假休息, 没人来搞), 所以各位如果有上线需求请提前提审安排. 同时需要注意在不久之后的2017年1月1日起应用必须使用HTTPS访问. 勿忘! 同时祝苹果团队节...…

iOS开发继续阅读