前言

作为一名资深iOS开发者，你已经掌握了Objective-C语言的核心特性和iOS平台的开发技能。然而，算法能力是区分普通开发者和卓越开发者的关键因素之一。本书旨在帮助你通过LeetCode上的中高难度算法题目，提升算法思维和解决复杂问题的能力，同时展示这些算法在iOS实际开发中的应用场景。

每个算法题目都包含以下几个部分：

问题描述：清晰地描述算法问题
Objective-C实现：提供完整的Objective-C代码实现
算法分析：分析时间复杂度和空间复杂度
实际工程应用：展示算法在iOS开发中的实际应用场景

通过本书，你将不仅能够在算法面试中表现出色，更能将这些算法思想应用到日常开发工作中，提高代码质量和性能。让我们开始这段从iOS到LeetCode的学习之旅！

从iOS到LeetCode：资深开发者的算法实战指南

第一章：数组与字符串算法

1.1 中高难度数组算法

1.1.1 [LeetCode 15] 三数之和（Medium）

问题描述：
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a, b, c ，使得 a + b + c = 0。请你找出所有和为 0 且不重复的三元组。

Objective-C 实现：

@interface Solution : NSObject
- (NSArray<NSArray<NSNumber *> *> *)threeSum:(NSArray<NSNumber *> *)nums;
@end

@implementation Solution
- (NSArray<NSArray<NSNumber *> *> *)threeSum:(NSArray<NSNumber *> *)nums {
    // 结果数组
    NSMutableArray<NSArray<NSNumber *> *> *result = [NSMutableArray array];
    
    // 边界条件检查
    if (nums.count < 3) {
        return result;
    }
    
    // 排序数组（使用系统排序方法）
    NSArray<NSNumber *> *sortedNums = [nums sortedArrayUsingSelector:@selector(compare:)];
    
    // 遍历数组
    for (NSInteger i = 0; i < sortedNums.count - 2; i++) {
        // 跳过重复元素
        if (i > 0 && [sortedNums[i] isEqualToNumber:sortedNums[i-1]]) {
            continue;
        }
        
        NSInteger left = i + 1;
        NSInteger right = sortedNums.count - 1;
        
        while (left < right) {
            NSInteger sum = [sortedNums[i] integerValue] + [sortedNums[left] integerValue] + [sortedNums[right] integerValue];
            
            if (sum < 0) {
                left++;
            } else if (sum > 0) {
                right--;
            } else {
                // 找到一组解
                [result addObject:@[sortedNums[i], sortedNums[left], sortedNums[right]]];
                
                // 跳过重复元素
                while (left < right && [sortedNums[left] isEqualToNumber:sortedNums[left+1]]) {
                    left++;
                }
                while (left < right && [sortedNums[right] isEqualToNumber:sortedNums[right-1]]) {
                    right--;
                }
                
                left++;
                right--;
            }
        }
    }
    
    return result;
}
@end

算法分析：

时间复杂度：O(n²)，其中排序的复杂度为O(nlogn)，双指针遍历的复杂度为O(n²)
空间复杂度：O(1)，不考虑存储结果的空间

实际工程应用：
三数之和算法在iOS开发中有多种实际应用场景：

金融应用中的交易匹配：在股票交易或加密货币应用中，可用于快速找出能够平衡账户的交易组合。
图像处理中的颜色平衡：在图像处理应用中，可用于寻找RGB颜色通道的平衡组合，实现特定的色彩效果。
游戏开发中的资源分配：在策略游戏中，可用于计算资源的最优分配方案，使得多个资源指标达到平衡。
数据分析应用：在数据可视化应用中，可用于寻找数据集中相互抵消的数据点，帮助识别数据模式。

1.1.2 [LeetCode 11] 盛最多水的容器（Medium）

问题描述：
给你 n 个非负整数 a₁, a₂, …, aₙ，每个数代表坐标中的一个点 (i, aᵢ)。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, aᵢ) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

Objective-C 实现：

@interface Solution : NSObject
- (NSInteger)maxArea:(NSArray<NSNumber *> *)height;
@end

@implementation Solution
- (NSInteger)maxArea:(NSArray<NSNumber *> *)height {
    NSInteger maxWater = 0;
    NSInteger left = 0;
    NSInteger right = height.count - 1;
    
    while (left < right) {
        // 计算当前容器的水量
        NSInteger h = MIN([height[left] integerValue], [height[right] integerValue]);
        NSInteger width = right - left;
        NSInteger water = h * width;
        
        // 更新最大水量
        maxWater = MAX(maxWater, water);
        
        // 移动较短的那一侧
        if ([height[left] integerValue] < [height[right] integerValue]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxWater;
}
@end

算法分析：

时间复杂度：O(n)，只需要遍历一次数组
空间复杂度：O(1)，只使用了常数级别的额外空间

实际工程应用：
盛最多水的容器算法在iOS开发中的实际应用：

UI布局优化：在自适应UI设计中，可用于计算最佳的组件布局方案，使得屏幕空间利用最大化。
资源调度系统：在后台任务调度中，可用于优化资源分配，找到最佳的任务执行时间窗口。
图像裁剪算法：在图像处理应用中，可用于确定最佳的裁剪区域，保留图像中最重要的内容。
数据可视化：在数据分析应用中，可用于确定最佳的数据展示区间，使得关键数据特征最为明显。

1.1.3 [LeetCode 42] 接雨水（Hard）

问题描述：
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

Objective-C 实现：

@interface Solution : NSObject
- (NSInteger)trap:(NSArray<NSNumber *> *)height;
@end

@implementation Solution
- (NSInteger)trap:(NSArray<NSNumber *> *)height {
    if (height.count <= 2) {
        return 0;
    }
    
    NSInteger left = 0;
    NSInteger right = height.count - 1;
    NSInteger leftMax = [height[left] integerValue];
    NSInteger rightMax = [height[right] integerValue];
    NSInteger result = 0;
    
    while (left < right) {
        if (leftMax < rightMax) {
            left++;
            NSInteger current = [height[left] integerValue];
            leftMax = MAX(leftMax, current);
            result += leftMax - current;
        } else {
            right--;
            NSInteger current = [height[right] integerValue];
            rightMax = MAX(rightMax, current);
            result += rightMax - current;
        }
    }
    
    return result;
}
@end

算法分析：

时间复杂度：O(n)，只需要遍历一次数组
空间复杂度：O(1)，只使用了常数级别的额外空间

实际工程应用：
接雨水算法在iOS开发中的实际应用：

内存管理优化：在内存密集型应用中，可用于分析内存使用模式，找出内存”洼地”，优化内存分配策略。
网络流量分析：在网络应用中，可用于分析网络流量波动，识别流量峰谷，优化数据传输策略。
图像处理中的轮廓检测：在计算机视觉应用中，可用于检测图像中的凹陷区域，辅助物体识别。
金融应用中的价格分析：在股票或加密货币应用中，可用于分析价格波动，识别潜在的支撑位和阻力位。

1.1.4 实际应用：高效内存管理与缓存设计

上述数组算法在iOS开发中的内存管理和缓存设计方面有重要应用：

高效的图片缓存系统：
在图片加载和缓存库（如SDWebImage的替代实现）中，可以结合使用这些算法优化内存使用：

@interface ImageCache : NSObject

@property (nonatomic, strong) NSCache *memoryCache;
@property (nonatomic, assign) NSInteger maxMemoryUsage;

- (void)optimizeMemoryUsage;

@end

@implementation ImageCache

- (instancetype)init {
    self = [super init];
    if (self) {
        _memoryCache = [[NSCache alloc] init];
        _maxMemoryUsage = 100 * 1024 * 1024; // 100MB
        
        // 注册内存警告通知
        [[NSNotificationCenter defaultCenter] addObserver:self
                                                 selector:@selector(handleMemoryWarning)
                                                     name:UIApplicationDidReceiveMemoryWarningNotification
                                                   object:nil];
    }
    return self;
}

- (void)handleMemoryWarning {
    [self optimizeMemoryUsage];
}

- (void)optimizeMemoryUsage {
    // 获取当前缓存的所有图片及其大小和访问频率
    NSArray<NSDictionary *> *cacheItems = [self getAllCacheItemsWithSizeAndFrequency];
    
    // 使用类似"接雨水"的算法分析内存使用模式
    NSArray<NSDictionary *> *memoryPattern = [self analyzeMemoryPattern:cacheItems];
    
    // 基于分析结果优化缓存
    [self adjustCacheBasedOnPattern:memoryPattern];
}

// 其他方法实现...

@end

数据预加载策略：
在列表滚动优化中，可以使用类似”盛最多水的容器”的思想来确定最佳的预加载窗口：

@interface DataPreloader : NSObject

- (NSRange)optimalPreloadRangeForVisibleRange:(NSRange)visibleRange
                                   totalItems:(NSInteger)totalItems
                                 scrollingUp:(BOOL)isScrollingUp;

@end

@implementation DataPreloader

- (NSRange)optimalPreloadRangeForVisibleRange:(NSRange)visibleRange
                                   totalItems:(NSInteger)totalItems
                                 scrollingUp:(BOOL)isScrollingUp {
    // 当前可见范围
    NSInteger visibleStart = visibleRange.location;
    NSInteger visibleEnd = NSMaxRange(visibleRange) - 1;
    
    // 使用双指针思想确定最佳预加载范围
    NSInteger preloadStart, preloadEnd;
    
    if (isScrollingUp) {
        // 向上滚动时，更多地预加载上方内容
        preloadStart = MAX(0, visibleStart - 20);
        preloadEnd = MIN(totalItems - 1, visibleEnd + 10);
    } else {
        // 向下滚动时，更多地预加载下方内容
        preloadStart = MAX(0, visibleStart - 10);
        preloadEnd = MIN(totalItems - 1, visibleEnd + 20);
    }
    
    return NSMakeRange(preloadStart, preloadEnd - preloadStart + 1);
}

@end

这些实际应用展示了如何将LeetCode上的算法思想应用到iOS开发的实际场景中，提高应用性能和用户体验。

1.2 字符串处理算法

1.2.1 [LeetCode 5] 最长回文子串（Medium）

问题描述：
给你一个字符串 s，找到 s 中最长的回文子串。

Objective-C 实现：

@interface Solution : NSObject
- (NSString *)longestPalindrome:(NSString *)s;
@end

@implementation Solution
- (NSString *)longestPalindrome:(NSString *)s {
    if (s.length < 2) {
        return s;
    }
    
    NSInteger start = 0;
    NSInteger maxLength = 1;
    
    // 辅助函数：从中心向两边扩展寻找回文
    void (^expandAroundCenter)(NSInteger, NSInteger) = ^(NSInteger left, NSInteger right) {
        while (left >= 0 && right < s.length && 
               [s characterAtIndex:left] == [s characterAtIndex:right]) {
            if (right - left + 1 > maxLength) {
                start = left;
                maxLength = right - left + 1;
            }
            left--;
            right++;
        }
    };
    
    for (NSInteger i = 0; i < s.length; i++) {
        // 奇数长度回文
        expandAroundCenter(i, i);
        // 偶数长度回文
        expandAroundCenter(i, i + 1);
    }
    
    return [s substringWithRange:NSMakeRange(start, maxLength)];
}
@end

算法分析：

时间复杂度：O(n²)，其中n是字符串长度
空间复杂度：O(1)，只使用了常数级别的额外空间

实际工程应用：
最长回文子串算法在iOS开发中的实际应用：

文本编辑器中的智能选择：在文本编辑应用中，可用于实现智能选择功能，当用户点击某个单词时，自动选中最长的回文结构。
自然语言处理：在语音识别或文本分析应用中，可用于识别语言中的回文结构，提高语义理解准确性。
DNA序列分析应用：在生物信息学应用中，可用于识别DNA序列中的回文结构，这在基因分析中具有重要意义。
输入法优化：在自定义键盘或输入法应用中，可用于预测用户可能输入的回文结构，提高输入效率。

1.2.2 [LeetCode 76] 最小覆盖子串（Hard）

问题描述：
给你一个字符串 s 和一个字符串 t，请你找出 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “”。

Objective-C 实现：

@interface Solution : NSObject
- (NSString *)minWindow:(NSString *)s t:(NSString *)t;
@end

@implementation Solution
- (NSString *)minWindow:(NSString *)s t:(NSString *)t {
    if (s.length == 0 || t.length == 0 || s.length < t.length) {
        return @"";
    }
    
    // 记录t中每个字符出现的次数
    NSMutableDictionary<NSNumber *, NSNumber *> *targetDict = [NSMutableDictionary dictionary];
    for (NSInteger i = 0; i < t.length; i++) {
        unichar c = [t characterAtIndex:i];
        NSNumber *key = @(c);
        targetDict[key] = @([targetDict[key] integerValue] + 1);
    }
    
    // 滑动窗口
    NSInteger left = 0;
    NSInteger right = 0;
    NSInteger formed = 0;  // 已经匹配的字符种类数
    NSInteger required = targetDict.count;  // 需要匹配的字符种类数
    
    // 记录窗口中每个字符出现的次数
    NSMutableDictionary<NSNumber *, NSNumber *> *windowDict = [NSMutableDictionary dictionary];
    
    // 记录最小窗口的起始位置和长度
    NSInteger minLen = NSIntegerMax;
    NSInteger minStart = 0;
    
    while (right < s.length) {
        // 扩大窗口
        unichar c = [s characterAtIndex:right];
        NSNumber *key = @(c);
        windowDict[key] = @([windowDict[key] integerValue] + 1);
        
        // 检查当前字符是否是目标字符，且出现次数是否达到要求
        if (targetDict[key] && [windowDict[key] integerValue] == [targetDict[key] integerValue]) {
            formed++;
        }
        
        // 尝试缩小窗口
        while (left <= right && formed == required) {
            // 更新最小窗口
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minStart = left;
            }
            
            // 移除左边界字符
            unichar leftChar = [s characterAtIndex:left];
            NSNumber *leftKey = @(leftChar);
            windowDict[leftKey] = @([windowDict[leftKey] integerValue] - 1);
            
            // 检查是否影响了匹配结果
            if (targetDict[leftKey] && [windowDict[leftKey] integerValue] < [targetDict[leftKey] integerValue]) {
                formed--;
            }
            
            left++;
        }
        
        right++;
    }
    
    return minLen == NSIntegerMax ? @"" : [s substringWithRange:NSMakeRange(minStart, minLen)];
}
@end

算法分析：

时间复杂度：O(n)，其中n是字符串s的长度
空间复杂度：O(k)，其中k是字符集大小，通常为常数

实际工程应用：
最小覆盖子串算法在iOS开发中的实际应用：

搜索功能优化：在应用内搜索功能中，可用于实现模糊匹配，找出包含所有搜索关键词的最小文本片段。
智能摘要生成：在内容聚合或新闻应用中，可用于从长文本中提取包含特定关键词的最小摘要。
用户行为分析：在分析用户会话数据时，可用于找出包含所有关键行为的最短时间段，帮助理解用户行为模式。
网络请求优化：在网络应用中，可用于优化批量请求，找出能够覆盖所有必要数据的最小请求集合。

1.2.3 [LeetCode 10] 正则表达式匹配（Hard）

问题描述：
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素

Objective-C 实现：

@interface Solution : NSObject
- (BOOL)isMatch:(NSString *)s pattern:(NSString *)p;
@end

@implementation Solution
- (BOOL)isMatch:(NSString *)s pattern:(NSString *)p {
    NSInteger m = s.length;
    NSInteger n = p.length;
    
    // dp[i][j] 表示 s 的前 i 个字符与 p 的前 j 个字符是否匹配
    BOOL dp[m + 1][n + 1];
    memset(dp, 0, sizeof(dp));
    
    // 空字符串与空模式匹配
    dp[0][0] = YES;
    
    // 处理 s 为空，p 不为空的情况，例如 p = "a*" 可以匹配空字符串
    for (NSInteger j = 1; j <= n; j++) {
        if ([p characterAtIndex:j - 1] == '*') {
            dp[0][j] = dp[0][j - 2];
        }
    }
    
    for (NSInteger i = 1; i <= m; i++) {
        for (NSInteger j = 1; j <= n; j++) {
            unichar sc = [s characterAtIndex:i - 1];
            unichar pc = [p characterAtIndex:j - 1];
            
            if (pc == '.' || pc == sc) {
                // 当前字符匹配
                dp[i][j] = dp[i - 1][j - 1];
            } else if (pc == '*') {
                // 处理 '*'
                unichar prevPc = [p characterAtIndex:j - 2];
                
                // '*' 匹配零次前面的元素
                dp[i][j] = dp[i][j - 2];
                
                // '*' 匹配一次或多次前面的元素
                if (prevPc == '.' || prevPc == sc) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            }
        }
    }
    
    return dp[m][n];
}
@end

算法分析：

时间复杂度：O(m*n)，其中m和n分别是字符串s和p的长度
空间复杂度：O(m*n)，需要一个二维数组来存储中间状态

实际工程应用：
正则表达式匹配算法在iOS开发中的实际应用：

表单验证：在用户输入验证中，可用于实现自定义的复杂验证规则，如邮箱格式、密码强度等。
文本解析器：在开发文本编辑器或Markdown解析器时，可用于识别和处理特定格式的文本模式。
日志分析工具：在开发调试工具时，可用于从日志中提取特定模式的信息，帮助开发者快速定位问题。
自然语言处理：在语音识别或文本分析应用中，可用于识别特定的语言模式，提高语义理解准确性。

1.2.4 实际应用：iOS文本处理与搜索优化

上述字符串算法在iOS开发中的文本处理和搜索优化方面有重要应用：

高效的全文搜索引擎：
在应用内搜索功能中，可以结合使用这些算法优化搜索体验：

@interface TextSearchEngine : NSObject

@property (nonatomic, strong) NSArray<NSString *> *documents;
@property (nonatomic, strong) NSMutableDictionary *invertedIndex;

- (NSArray<NSString *> *)searchResultsForQuery:(NSString *)query;
- (NSArray<NSString *> *)highlightedSnippetsForResults:(NSArray<NSString *> *)results query:(NSString *)query;

@end

@implementation TextSearchEngine

- (instancetype)initWithDocuments:(NSArray<NSString *> *)documents {
    self = [super init];
    if (self) {
        _documents = [documents copy];
        [self buildInvertedIndex];
    }
    return self;
}

- (void)buildInvertedIndex {
    self.invertedIndex = [NSMutableDictionary dictionary];
    
    for (NSInteger docId = 0; docId < self.documents.count; docId++) {
        NSString *document = self.documents[docId];
        NSArray<NSString *> *words = [self tokenizeDocument:document];
        
        for (NSString *word in words) {
            if (!self.invertedIndex[word]) {
                self.invertedIndex[word] = [NSMutableSet set];
            }
            [self.invertedIndex[word] addObject:@(docId)];
        }
    }
}

- (NSArray<NSString *> *)searchResultsForQuery:(NSString *)query {
    NSArray<NSString *> *queryWords = [self tokenizeDocument:query];
    NSMutableSet *resultDocIds;
    
    // 使用类似最小覆盖子串的思想找出包含所有查询词的文档
    for (NSString *word in queryWords) {
        NSSet *docIds = self.invertedIndex[word];
        
        if (!docIds) {
            return @[];  // 如果有一个词没有匹配的文档，则返回空结果
        }
        
        if (!resultDocIds) {
            resultDocIds = [docIds mutableCopy];
        } else {
            [resultDocIds intersectSet:docIds];  // 取交集
        }
        
        if (resultDocIds.count == 0) {
            return @[];  // 如果交集为空，则返回空结果
        }
    }
    
    // 将文档ID转换为文档内容
    NSMutableArray<NSString *> *results = [NSMutableArray array];
    for (NSNumber *docId in resultDocIds) {
        [results addObject:self.documents[docId.integerValue]];
    }
    
    return results;
}

- (NSArray<NSString *> *)highlightedSnippetsForResults:(NSArray<NSString *> *)results query:(NSString *)query {
    NSArray<NSString *> *queryWords = [self tokenizeDocument:query];
    NSMutableArray<NSString *> *snippets = [NSMutableArray array];
    
    for (NSString *document in results) {
        // 使用最小覆盖子串算法找出包含所有查询词的最小片段
        NSString *snippet = [self findMinimumSnippet:document containingWords:queryWords];
        [snippets addObject:snippet];
    }
    
    return snippets;
}

- (NSString *)findMinimumSnippet:(NSString *)document containingWords:(NSArray<NSString *> *)words {
    // 实现类似最小覆盖子串的算法
    // 这里简化处理，实际实现会更复杂
    
    // 将文档分词
    NSArray<NSString *> *tokens = [self tokenizeDocument:document];
    NSMutableDictionary *wordCount = [NSMutableDictionary dictionary];
    
    for (NSString *word in words) {
        wordCount[word] = @0;
    }
    
    NSInteger left = 0;
    NSInteger right = 0;
    NSInteger formed = 0;
    NSInteger required = words.count;
    NSInteger minLen = NSIntegerMax;
    NSInteger minStart = 0;
    
    while (right < tokens.count) {
        NSString *rightWord = tokens[right];
        
        if (wordCount[rightWord] != nil) {
            wordCount[rightWord] = @([wordCount[rightWord] integerValue] + 1);
            if ([wordCount[rightWord] integerValue] == 1) {
                formed++;
            }
        }
        
        while (formed == required && left <= right) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minStart = left;
            }
            
            NSString *leftWord = tokens[left];
            if (wordCount[leftWord] != nil) {
                wordCount[leftWord] = @([wordCount[leftWord] integerValue] - 1);
                if ([wordCount[leftWord] integerValue] == 0) {
                    formed--;
                }
            }
            
            left++;
        }
        
        right++;
    }
    
    if (minLen == NSIntegerMax) {
        return @"";
    }
    
    // 构建片段
    NSMutableString *snippet = [NSMutableString string];
    for (NSInteger i = minStart; i < minStart + minLen; i++) {
        [snippet appendFormat:@"%@ ", tokens[i]];
    }
    
    return snippet;
}

- (NSArray<NSString *> *)tokenizeDocument:(NSString *)document {
    // 简化的分词实现
    return [document componentsSeparatedByCharactersInSet:[NSCharacterSet whitespaceAndNewlineCharacterSet]];
}

@end

智能文本编辑器：
在文本编辑应用中，可以使用回文子串算法实现智能选择功能：

@interface SmartTextEditor : NSObject

- (NSRange)smartSelectionAtPosition:(NSInteger)position inText:(NSString *)text;
- (NSString *)autoCompleteForText:(NSString *)text atPosition:(NSInteger)position;

@end

@implementation SmartTextEditor

- (NSRange)smartSelectionAtPosition:(NSInteger)position inText:(NSString *)text {
    // 基本单词选择
    NSRange wordRange = [self wordRangeAtPosition:position inText:text];
    
    // 检查是否是回文结构
    NSRange palindromeRange = [self palindromeRangeAtPosition:position inText:text];
    
    // 如果找到回文结构且比单词范围大，则返回回文范围
    if (palindromeRange.length > wordRange.length) {
        return palindromeRange;
    }
    
    return wordRange;
}

- (NSRange)wordRangeAtPosition:(NSInteger)position inText:(NSString *)text {
    // 简化实现，实际应用中会更复杂
    NSCharacterSet *wordSet = [NSCharacterSet alphanumericCharacterSet];
    
    NSInteger start = position;
    while (start > 0 && [wordSet characterIsMember:[text characterAtIndex:start - 1]]) {
        start--;
    }
    
    NSInteger end = position;
    while (end < text.length && [wordSet characterIsMember:[text characterAtIndex:end]]) {
        end++;
    }
    
    return NSMakeRange(start, end - start);
}

- (NSRange)palindromeRangeAtPosition:(NSInteger)position inText:(NSString *)text {
    // 使用最长回文子串算法
    NSInteger maxLength = 0;
    NSInteger start = 0;
    
    // 辅助函数：从中心向两边扩展寻找回文
    void (^expandAroundCenter)(NSInteger, NSInteger) = ^(NSInteger left, NSInteger right) {
        while (left >= 0 && right < text.length && 
               [text characterAtIndex:left] == [text characterAtIndex:right]) {
            if (right - left + 1 > maxLength && 
                left <= position && right >= position) {  // 确保包含当前位置
                start = left;
                maxLength = right - left + 1;
            }
            left--;
            right++;
        }
    };
    
    // 检查以当前位置为中心的回文
    expandAroundCenter(position, position);  // 奇数长度
    expandAroundCenter(position, position + 1);  // 偶数长度
    
    return NSMakeRange(start, maxLength);
}

- (NSString *)autoCompleteForText:(NSString *)text atPosition:(NSInteger)position {
    // 使用正则表达式匹配算法实现智能补全
    // 这里简化实现，实际应用中会更复杂
    
    // 获取当前正在输入的单词
    NSString *currentWord = [self getCurrentWordFromText:text atPosition:position];
    
    // 根据常见模式预测可能的补全
    NSArray<NSString *> *completions = [self predictCompletionsForWord:currentWord];
    
    return completions.firstObject ?: @"";
}

- (NSString *)getCurrentWordFromText:(NSString *)text atPosition:(NSInteger)position {
    NSRange wordRange = [self wordRangeAtPosition:position inText:text];
    return [text substringWithRange:wordRange];
}

- (NSArray<NSString *> *)predictCompletionsForWord:(NSString *)word {
    // 简化实现，实际应用中会使用更复杂的预测算法
    NSMutableDictionary<NSString *, NSArray<NSString *> *> *completionDict = [NSMutableDictionary dictionary];
    completionDict[@"func"] = @[@"function", @"functional", @"functionality"];
    completionDict[@"var"] = @[@"variable", @"variance", @"variant"];
    completionDict[@"let"] = @[@"letter", @"letting", @"lethal"];
    
    return completionDict[word] ?: @[];
}

@end

这些实际应用展示了如何将LeetCode上的字符串算法应用到iOS开发的实际场景中，提高文本处理和搜索功能的效率和用户体验。

从iOS到LeetCode：资深开发者的算法实战指南

第二章：链表与树结构算法

2.1 链表操作算法

2.1.1 [LeetCode 19] 删除链表的倒数第N个节点（Medium）

问题描述：
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

Objective-C 实现：

// 链表节点定义
@interface ListNode : NSObject
@property (nonatomic, assign) NSInteger val;
@property (nonatomic, strong) ListNode *next;
- (instancetype)initWithValue:(NSInteger)val;
@end

@implementation ListNode
- (instancetype)initWithValue:(NSInteger)val {
    self = [super init];
    if (self) {
        _val = val;
        _next = nil;
    }
    return self;
}
@end

@interface Solution : NSObject
- (ListNode *)removeNthFromEnd:(ListNode *)head n:(NSInteger)n;
@end

@implementation Solution
- (ListNode *)removeNthFromEnd:(ListNode *)head n:(NSInteger)n {
    // 创建哑节点，简化边界情况处理
    ListNode *dummy = [[ListNode alloc] initWithValue:0];
    dummy.next = head;
    
    // 使用快慢指针
    ListNode *fast = dummy;
    ListNode *slow = dummy;
    
    // 快指针先前进n+1步
    for (NSInteger i = 0; i <= n; i++) {
        fast = fast.next;
    }
    
    // 同时移动快慢指针，直到快指针到达末尾
    while (fast != nil) {
        fast = fast.next;
        slow = slow.next;
    }
    
    // 此时慢指针指向要删除节点的前一个节点
    slow.next = slow.next.next;
    
    return dummy.next;
}
@end

算法分析：

时间复杂度：O(n)，其中n是链表长度，只需要遍历一次链表
空间复杂度：O(1)，只使用了常数级别的额外空间

实际工程应用：
删除链表倒数第N个节点算法在iOS开发中的实际应用：

消息队列管理：在聊天应用中，可用于管理消息队列，例如删除最近N条消息中的特定消息。
撤销功能实现：在编辑器应用中，可用于实现撤销功能，维护操作历史链表并能够回退特定步骤。
网络请求队列优化：在网络库中，可用于管理请求队列，例如取消倒数第N个未完成的请求以优化资源使用。
图片缓存管理：在图片加载库中，可用于实现LRU（最近最少使用）缓存策略，移除倒数第N个最少使用的图片。

2.1.2 [LeetCode 142] 环形链表II（Medium）

问题描述：
给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

Objective-C 实现：

@interface Solution : NSObject
- (ListNode *)detectCycle:(ListNode *)head;
@end

@implementation Solution
- (ListNode *)detectCycle:(ListNode *)head {
    if (!head || !head.next) {
        return nil;
    }
    
    // 使用快慢指针检测是否有环
    ListNode *slow = head;
    ListNode *fast = head;
    BOOL hasCycle = NO;
    
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow == fast) {
            hasCycle = YES;
            break;
        }
    }
    
    // 如果没有环，返回nil
    if (!hasCycle) {
        return nil;
    }
    
    // 找到环的入口
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    
    return slow;
}
@end

算法分析：

时间复杂度：O(n)，其中n是链表长度
空间复杂度：O(1)，只使用了常数级别的额外空间

实际工程应用：
环形链表检测算法在iOS开发中的实际应用：

内存泄漏检测：在ARC环境下，可用于检测循环引用导致的内存泄漏，通过构建对象引用图并检测环。
任务依赖检测：在任务调度系统中，可用于检测任务依赖中的循环依赖，避免死锁。
网络拓扑分析：在网络监控应用中，可用于检测网络拓扑中的环形结构，帮助优化网络路由。
UI导航流程验证：在复杂的应用导航系统中，可用于检测导航流程中的循环路径，避免用户陷入无法退出的导航循环。

2.1.3 [LeetCode 23] 合并K个排序链表（Hard）

问题描述：
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

Objective-C 实现：

@interface Solution : NSObject
- (ListNode *)mergeKLists:(NSArray<ListNode *> *)lists;
@end

@implementation Solution
- (ListNode *)mergeKLists:(NSArray<ListNode *> *)lists {
    if (lists.count == 0) {
        return nil;
    }
    
    return [self mergeListsInRange:lists start:0 end:lists.count - 1];
}

// 分治法合并链表
- (ListNode *)mergeListsInRange:(NSArray<ListNode *> *)lists start:(NSInteger)start end:(NSInteger)end {
    if (start == end) {
        return lists[start];
    }
    
    if (start + 1 == end) {
        return [self mergeTwoLists:lists[start] list2:lists[end]];
    }
    
    NSInteger mid = start + (end - start) / 2;
    ListNode *left = [self mergeListsInRange:lists start:start end:mid];
    ListNode *right = [self mergeListsInRange:lists start:mid + 1 end:end];
    
    return [self mergeTwoLists:left list2:right];
}

// 合并两个有序链表
- (ListNode *)mergeTwoLists:(ListNode *)list1 list2:(ListNode *)list2 {
    ListNode *dummy = [[ListNode alloc] initWithValue:0];
    ListNode *current = dummy;
    
    while (list1 && list2) {
        if (list1.val < list2.val) {
            current.next = list1;
            list1 = list1.next;
        } else {
            current.next = list2;
            list2 = list2.next;
        }
        current = current.next;
    }
    
    current.next = list1 ? list1 : list2;
    
    return dummy.next;
}
@end

算法分析：

时间复杂度：O(N log k)，其中k是链表数量，N是所有链表中节点的总数
空间复杂度：O(log k)，递归调用的栈空间

实际工程应用：
合并K个排序链表算法在iOS开发中的实际应用：

多路数据合并：在数据同步应用中，可用于合并来自多个数据源的有序数据流，如日志合并或时间线合并。
多线程下载管理：在下载管理器中，可用于合并多个线程下载的文件片段，保持整体有序。
分布式计算结果整合：在分布式计算应用中，可用于整合多个计算节点返回的有序结果集。
多传感器数据融合：在物联网或健康监测应用中，可用于融合多个传感器按时间戳排序的数据流。

2.1.4 实际应用：iOS内存管理与数据结构设计

上述链表算法在iOS开发中的内存管理和数据结构设计方面有重要应用：

高效的图片加载队列：
在图片加载库中，可以使用链表算法优化内存管理：

@interface ImageLoadOperation : NSObject
@property (nonatomic, strong) NSURL *imageURL;
@property (nonatomic, copy) void (^completionBlock)(UIImage *image, NSError *error);
@property (nonatomic, strong) ImageLoadOperation *next;
@end

@interface ImageLoadQueue : NSObject

@property (nonatomic, strong) ImageLoadOperation *head;
@property (nonatomic, strong) ImageLoadOperation *tail;
@property (nonatomic, assign) NSInteger count;
@property (nonatomic, assign) NSInteger maxConcurrentOperations;
@property (nonatomic, assign) NSInteger runningOperations;

- (void)addOperationWithURL:(NSURL *)url completion:(void (^)(UIImage *image, NSError *error))completion;
- (void)cancelOperationWithURL:(NSURL *)url;
- (void)cancelLastNOperations:(NSInteger)n;
- (void)detectAndBreakCyclicDependencies;

@end

@implementation ImageLoadQueue

- (instancetype)init {
    self = [super init];
    if (self) {
        _head = nil;
        _tail = nil;
        _count = 0;
        _maxConcurrentOperations = 4;
        _runningOperations = 0;
    }
    return self;
}

- (void)addOperationWithURL:(NSURL *)url completion:(void (^)(UIImage *image, NSError *error))completion {
    ImageLoadOperation *operation = [[ImageLoadOperation alloc] init];
    operation.imageURL = url;
    operation.completionBlock = completion;
    
    // 添加到队列尾部
    if (!self.head) {
        self.head = operation;
        self.tail = operation;
    } else {
        self.tail.next = operation;
        self.tail = operation;
    }
    
    self.count++;
    
    [self processQueue];
}

- (void)processQueue {
    while (self.runningOperations < self.maxConcurrentOperations && self.head) {
        ImageLoadOperation *operation = self.head;
        self.head = self.head.next;
        if (!self.head) {
            self.tail = nil;
        }
        
        self.count--;
        self.runningOperations++;
        
        // 执行图片加载操作
        [self loadImageWithOperation:operation];
    }
}

- (void)loadImageWithOperation:(ImageLoadOperation *)operation {
    // 模拟图片加载
    dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
        // 实际应用中，这里会进行网络请求或从缓存加载图片
        UIImage *image = [self loadImageFromURL:operation.imageURL];
        
        dispatch_async(dispatch_get_main_queue(), ^{
            if (operation.completionBlock) {
                operation.completionBlock(image, nil);
            }
            
            self.runningOperations--;
            [self processQueue];
        });
    });
}

- (UIImage *)loadImageFromURL:(NSURL *)url {
    // 实际实现会从网络或缓存加载图片
    // 这里简化处理
    return [[UIImage alloc] init];
}

- (void)cancelOperationWithURL:(NSURL *)url {
    if (!self.head) {
        return;
    }
    
    // 如果头节点是要取消的操作
    if ([self.head.imageURL isEqual:url]) {
        self.head = self.head.next;
        if (!self.head) {
            self.tail = nil;
        }
        self.count--;
        return;
    }
    
    // 查找并删除链表中的操作
    ImageLoadOperation *current = self.head;
    while (current.next) {
        if ([current.next.imageURL isEqual:url]) {
            if (current.next == self.tail) {
                self.tail = current;
            }
            current.next = current.next.next;
            self.count--;
            return;
        }
        current = current.next;
    }
}

- (void)cancelLastNOperations:(NSInteger)n {
    // 使用类似删除链表倒数第N个节点的算法
    if (n <= 0 || !self.head) {
        return;
    }
    
    // 如果要取消的操作数大于等于队列长度，清空队列
    if (n >= self.count) {
        self.head = nil;
        self.tail = nil;
        self.count = 0;
        return;
    }
    
    // 找到倒数第n+1个节点
    ImageLoadOperation *fast = self.head;
    ImageLoadOperation *slow = self.head;
    
    // 快指针先前进n步
    for (NSInteger i = 0; i < n; i++) {
        fast = fast.next;
    }
    
    // 如果快指针已经到达尾部，说明要删除的是头节点
    if (!fast) {
        self.head = self.head.next;
        self.count--;
        return;
    }
    
    // 同时移动快慢指针，直到快指针到达末尾
    while (fast.next) {
        fast = fast.next;
        slow = slow.next;
    }
    
    // 此时慢指针指向倒数第n+1个节点
    // 将倒数第n个节点及之后的所有节点删除
    self.tail = slow;
    slow.next = nil;
    self.count = self.count - n;
}

- (void)detectAndBreakCyclicDependencies {
    // 使用环形链表检测算法
    if (!self.head || !self.head.next) {
        return;
    }
    
    ImageLoadOperation *slow = self.head;
    ImageLoadOperation *fast = self.head;
    BOOL hasCycle = NO;
    
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow == fast) {
            hasCycle = YES;
            break;
        }
    }
    
    if (!hasCycle) {
        return;
    }
    
    // 找到环的入口
    slow = self.head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    
    // 找到环的最后一个节点（指向入口的节点）
    ImageLoadOperation *cycleEnd = slow;
    while (cycleEnd.next != slow) {
        cycleEnd = cycleEnd.next;
    }
    
    // 打破环
    cycleEnd.next = nil;
    
    // 重新计算队列长度
    NSInteger newCount = 0;
    ImageLoadOperation *current = self.head;
    while (current) {
        newCount++;
        if (!current.next) {
            self.tail = current;
        }
        current = current.next;
    }
    
    self.count = newCount;
}

@end

高效的多数据源合并：
在数据同步应用中，可以使用合并K个排序链表的算法优化数据合并：

@interface DataSource : NSObject
@property (nonatomic, strong) NSString *identifier;
@property (nonatomic, strong) NSArray<NSDictionary *> *data;
@property (nonatomic, assign) NSInteger currentIndex;
@end

@interface DataMerger : NSObject

- (NSArray<NSDictionary *> *)mergeDataFromSources:(NSArray<DataSource *> *)dataSources
                                     sortByKey:(NSString *)sortKey
                                     ascending:(BOOL)ascending
                                        limit:(NSInteger)limit;

@end

@implementation DataMerger

- (NSArray<NSDictionary *> *)mergeDataFromSources:(NSArray<DataSource *> *)dataSources
                                     sortByKey:(NSString *)sortKey
                                     ascending:(BOOL)ascending
                                        limit:(NSInteger)limit {
    // 创建结果数组
    NSMutableArray<NSDictionary *> *result = [NSMutableArray array];
    
    // 创建最小/最大堆（根据排序方向）
    NSMutableArray<DataSource *> *heap = [NSMutableArray array];
    
    // 初始化堆
    for (DataSource *source in dataSources) {
        if (source.data.count > 0) {
            source.currentIndex = 0;
            [heap addObject:source];
        }
    }
    
    // 堆化
    [self heapifyArray:heap sortByKey:sortKey ascending:ascending];
    
    // 合并数据
    while (heap.count > 0 && result.count < limit) {
        // 取出堆顶元素（最小/最大值）
        DataSource *source = heap[0];
        [result addObject:source.data[source.currentIndex]];
        
        // 更新数据源索引
        source.currentIndex++;
        
        // 如果数据源已经用完，从堆中移除
        if (source.currentIndex >= source.data.count) {
            [heap removeObjectAtIndex:0];
        }
        
        // 重新堆化
        [self siftDownInArray:heap atIndex:0 sortByKey:sortKey ascending:ascending];
    }
    
    return result;
}

// 堆化数组
- (void)heapifyArray:(NSMutableArray<DataSource *> *)array sortByKey:(NSString *)sortKey ascending:(BOOL)ascending {
    for (NSInteger i = array.count / 2 - 1; i >= 0; i--) {
        [self siftDownInArray:array atIndex:i sortByKey:sortKey ascending:ascending];
    }
}

// 下沉操作
- (void)siftDownInArray:(NSMutableArray<DataSource *> *)array atIndex:(NSInteger)index sortByKey:(NSString *)sortKey ascending:(BOOL)ascending {
    NSInteger size = array.count;
    NSInteger parent = index;
    
    while (2 * parent + 1 < size) {
        NSInteger child = 2 * parent + 1;
        
        // 选择较小/较大的子节点
        if (child + 1 < size) {
            id value1 = array[child].data[array[child].currentIndex][sortKey];
            id value2 = array[child + 1].data[array[child + 1].currentIndex][sortKey];
            
            NSComparisonResult result = [value1 compare:value2];
            
            if ((ascending && result == NSOrderedDescending) || (!ascending && result == NSOrderedAscending)) {
                child++;
            }
        }
        
        // 比较父节点和选中的子节点
        id parentValue = array[parent].data[array[parent].currentIndex][sortKey];
        id childValue = array[child].data[array[child].currentIndex][sortKey];
        
        NSComparisonResult result = [parentValue compare:childValue];
        
        if ((ascending && result == NSOrderedAscending) || (!ascending && result == NSOrderedDescending)) {
            break;
        }
        
        // 交换父子节点
        [array exchangeObjectAtIndex:parent withObjectAtIndex:child];
        parent = child;
    }
}

@end

这些实际应用展示了如何将LeetCode上的链表算法应用到iOS开发的实际场景中，提高内存管理效率和数据结构设计的合理性。

2.2 二叉树算法

2.2.1 [LeetCode 236] 二叉树的最近公共祖先（Medium）

问题描述：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。最近公共祖先的定义为：”对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

Objective-C 实现：

// 二叉树节点定义
@interface TreeNode : NSObject
@property (nonatomic, assign) NSInteger val;
@property (nonatomic, strong) TreeNode *left;
@property (nonatomic, strong) TreeNode *right;
- (instancetype)initWithValue:(NSInteger)val;
@end

@implementation TreeNode
- (instancetype)initWithValue:(NSInteger)val {
    self = [super init];
    if (self) {
        _val = val;
        _left = nil;
        _right = nil;
    }
    return self;
}
@end

@interface Solution : NSObject
- (TreeNode *)lowestCommonAncestor:(TreeNode *)root p:(TreeNode *)p q:(TreeNode *)q;
@end

@implementation Solution
- (TreeNode *)lowestCommonAncestor:(TreeNode *)root p:(TreeNode *)p q:(TreeNode *)q {
    // 基本情况
    if (!root || root == p || root == q) {
        return root;
    }
    
    // 在左子树中查找
    TreeNode *left = [self lowestCommonAncestor:root.left p:p q:q];
    
    // 在右子树中查找
    TreeNode *right = [self lowestCommonAncestor:root.right p:p q:q];
    
    // 如果左右子树都找到了节点，说明当前节点就是最近公共祖先
    if (left && right) {
        return root;
    }
    
    // 如果只在左子树中找到，返回左子树的结果
    if (left) {
        return left;
    }
    
    // 如果只在右子树中找到，返回右子树的结果
    return right;
}
@end

算法分析：

时间复杂度：O(n)，其中n是二叉树中的节点数
空间复杂度：O(h)，其中h是二叉树的高度，最坏情况下为O(n)

实际工程应用：
二叉树的最近公共祖先算法在iOS开发中的实际应用：

UI视图层次结构分析：在UI调试工具中，可用于找出两个视图的最近公共父视图，帮助分析视图层次结构。
组件树依赖分析：在组件化架构中，可用于分析两个组件的最近公共依赖，帮助优化依赖关系。
文件系统导航：在文件浏览器应用中，可用于找出两个文件或文件夹的最近公共目录，简化导航操作。
组织架构图分析：在企业管理应用中，可用于找出两个员工的最近公共上级，帮助理解组织结构。

2.2.2 [LeetCode 124] 二叉树中的最大路径和（Hard）

问题描述：
路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。路径和是路径中各节点值的总和。给你一个二叉树的根节点 root，返回其最大路径和。

Objective-C 实现：

@interface Solution : NSObject
- (NSInteger)maxPathSum:(TreeNode *)root;
@end

@implementation Solution
- (NSInteger)maxPathSum:(TreeNode *)root {
    NSInteger maxSum = NSIntegerMin;
    [self maxGain:root maxSum:&maxSum];
    return maxSum;
}

// 计算以node为起点的最大贡献值
- (NSInteger)maxGain:(TreeNode *)node maxSum:(NSInteger *)maxSum {
    if (!node) {
        return 0;
    }
    
    // 递归计算左右子节点的最大贡献值
    // 只有在最大贡献值大于0时，才会选取对应子节点
    NSInteger leftGain = MAX(0, [self maxGain:node.left maxSum:maxSum]);
    NSInteger rightGain = MAX(0, [self maxGain:node.right maxSum:maxSum]);
    
    // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
    NSInteger priceNewPath = node.val + leftGain + rightGain;
    
    // 更新答案
    *maxSum = MAX(*maxSum, priceNewPath);
    
    // 返回节点的最大贡献值
    return node.val + MAX(leftGain, rightGain);
}
@end

算法分析：

时间复杂度：O(n)，其中n是二叉树中的节点数
空间复杂度：O(h)，其中h是二叉树的高度，最坏情况下为O(n)

实际工程应用：
二叉树中的最大路径和算法在iOS开发中的实际应用：

网络流量优化：在网络应用中，可用于分析网络拓扑图，找出最大带宽路径，优化数据传输。
资源分配优化：在资源管理系统中，可用于分析资源依赖图，找出最优资源分配路径，提高系统效率。
游戏AI路径规划：在游戏开发中，可用于AI角色的路径规划，找出收益最大的行动路径。
推荐系统优化：在推荐引擎中，可用于分析用户兴趣图，找出最大兴趣路径，提高推荐准确性。

2.2.3 [LeetCode 297] 二叉树的序列化与反序列化（Hard）

问题描述：
序列化是将一个数据结构或者对象转换为一个字符串的过程，以便可以在文件中存储或通过网络传输，然后在以后重建。设计一个算法来序列化和反序列化二叉树。

Objective-C 实现：

@interface Codec : NSObject
- (NSString *)serialize:(TreeNode *)root;
- (TreeNode *)deserialize:(NSString *)data;
@end

@implementation Codec
// 序列化二叉树为字符串
- (NSString *)serialize:(TreeNode *)root {
    NSMutableString *result = [NSMutableString string];
    [self serializeHelper:root result:result];
    return result;
}

- (void)serializeHelper:(TreeNode *)node result:(NSMutableString *)result {
    if (!node) {
        [result appendString:@"null,"];
        return;
    }
    
    [result appendFormat:@"%ld,", (long)node.val];
    [self serializeHelper:node.left result:result];
    [self serializeHelper:node.right result:result];
}

// 从字符串反序列化为二叉树
- (TreeNode *)deserialize:(NSString *)data {
    NSArray<NSString *> *values = [data componentsSeparatedByString:@","];
    NSInteger index = 0;
    return [self deserializeHelper:values index:&index];
}

- (TreeNode *)deserializeHelper:(NSArray<NSString *> *)values index:(NSInteger *)index {
    if (*index >= values.count) {
        return nil;
    }
    
    NSString *value = values[*index];
    (*index)++;
    
    if ([value isEqualToString:@"null"]) {
        return nil;
    }
    
    TreeNode *node = [[TreeNode alloc] initWithValue:[value integerValue]];
    node.left = [self deserializeHelper:values index:index];
    node.right = [self deserializeHelper:values index:index];
    
    return node;
}
@end

算法分析：

时间复杂度：O(n)，其中n是二叉树中的节点数
空间复杂度：O(n)，需要存储序列化后的字符串

实际工程应用：
二叉树的序列化与反序列化算法在iOS开发中的实际应用：

应用状态持久化：在应用中，可用于将复杂的状态树序列化后保存到磁盘，在下次启动时恢复。
UI布局存储与恢复：在自定义UI编辑器中，可用于将视图层次结构序列化后保存，方便后续编辑或分享。
网络传输优化：在客户端-服务器通信中，可用于高效传输树形结构数据，如组织架构或文件系统。
配置管理系统：在配置管理应用中，可用于存储和恢复层次化的配置信息，支持版本控制和回滚。

2.2.4 实际应用：iOS视图层次结构与组件树管理

上述二叉树算法在iOS开发中的视图层次结构和组件树管理方面有重要应用：

视图层次结构分析工具：
在UI调试工具中，可以使用二叉树算法优化视图层次结构分析：

@interface ViewHierarchyAnalyzer : NSObject

- (UIView *)findCommonAncestorOfView:(UIView *)view1 andView:(UIView *)view2;
- (NSInteger)maxPathSumInViewHierarchy:(UIView *)rootView valueBlock:(NSInteger (^)(UIView *view))valueBlock;
- (NSString *)serializeViewHierarchy:(UIView *)rootView;
- (UIView *)deserializeViewHierarchy:(NSString *)serializedData;

@end

@implementation ViewHierarchyAnalyzer

// 找出两个视图的最近公共祖先
- (UIView *)findCommonAncestorOfView:(UIView *)view1 andView:(UIView *)view2 {
    if (!view1 || !view2) {
        return nil;
    }
    
    // 获取view1的所有祖先视图
    NSMutableSet<UIView *> *ancestors = [NSMutableSet set];
    UIView *current = view1;
    while (current) {
        [ancestors addObject:current];
        current = current.superview;
    }
    
    // 查找view2的祖先中第一个也是view1的祖先的视图
    current = view2;
    while (current) {
        if ([ancestors containsObject:current]) {
            return current;
        }
        current = current.superview;
    }
    
    return nil;
}

// 计算视图层次结构中的最大路径和
// valueBlock用于自定义每个视图的"价值"计算方式
- (NSInteger)maxPathSumInViewHierarchy:(UIView *)rootView valueBlock:(NSInteger (^)(UIView *view))valueBlock {
    NSInteger maxSum = NSIntegerMin;
    [self maxGainForView:rootView maxSum:&maxSum valueBlock:valueBlock];
    return maxSum;
}

- (NSInteger)maxGainForView:(UIView *)view maxSum:(NSInteger *)maxSum valueBlock:(NSInteger (^)(UIView *view))valueBlock {
    if (!view) {
        return 0;
    }
    
    // 计算当前视图的价值
    NSInteger viewValue = valueBlock(view);
    
    // 递归计算子视图的最大贡献值
    NSInteger maxChildGain = 0;
    NSInteger secondMaxChildGain = 0;
    
    for (UIView *subview in view.subviews) {
        NSInteger gain = [self maxGainForView:subview maxSum:maxSum valueBlock:valueBlock];
        if (gain > maxChildGain) {
            secondMaxChildGain = maxChildGain;
            maxChildGain = gain;
        } else if (gain > secondMaxChildGain) {
            secondMaxChildGain = gain;
        }
    }
    
    // 更新最大路径和
    *maxSum = MAX(*maxSum, viewValue + maxChildGain + secondMaxChildGain);
    
    // 返回以当前视图为起点的最大贡献值
    return viewValue + maxChildGain;
}

// 序列化视图层次结构
- (NSString *)serializeViewHierarchy:(UIView *)rootView {
    NSMutableString *result = [NSMutableString string];
    [self serializeViewHelper:rootView result:result];
    return result;
}

- (void)serializeViewHelper:(UIView *)view result:(NSMutableString *)result {
    if (!view) {
        [result appendString:@"null,"];
        return;
    }
    
    // 序列化视图的基本信息
    NSString *className = NSStringFromClass([view class]);
    CGRect frame = view.frame;
    NSString *viewInfo = [NSString stringWithFormat:@"%@:%f:%f:%f:%f,", 
                          className, frame.origin.x, frame.origin.y, frame.size.width, frame.size.height];
    [result appendString:viewInfo];
    
    // 序列化子视图
    for (UIView *subview in view.subviews) {
        [self serializeViewHelper:subview result:result];
    }
    
    // 标记子视图列表结束
    [result appendString:@"end,"];
}

// 反序列化视图层次结构
- (UIView *)deserializeViewHierarchy:(NSString *)serializedData {
    NSArray<NSString *> *tokens = [serializedData componentsSeparatedByString:@","];
    NSInteger index = 0;
    return [self deserializeViewHelper:tokens index:&index];
}

- (UIView *)deserializeViewHelper:(NSArray<NSString *> *)tokens index:(NSInteger *)index {
    if (*index >= tokens.count) {
        return nil;
    }
    
    NSString *token = tokens[*index];
    (*index)++;
    
    if ([token isEqualToString:@"null"]) {
        return nil;
    }
    
    if ([token isEqualToString:@"end"]) {
        return nil;
    }
    
    // 解析视图信息
    NSArray<NSString *> *viewInfo = [token componentsSeparatedByString:@":"];
    if (viewInfo.count < 5) {
        return nil;
    }
    
    NSString *className = viewInfo[0];
    CGFloat x = [viewInfo[1] floatValue];
    CGFloat y = [viewInfo[2] floatValue];
    CGFloat width = [viewInfo[3] floatValue];
    CGFloat height = [viewInfo[4] floatValue];
    
    // 创建视图
    Class viewClass = NSClassFromString(className);
    UIView *view = [[viewClass alloc] initWithFrame:CGRectMake(x, y, width, height)];
    
    // 添加子视图
    while (*index < tokens.count && ![tokens[*index] isEqualToString:@"end"]) {
        UIView *subview = [self deserializeViewHelper:tokens index:index];
        if (subview) {
            [view addSubview:subview];
        }
    }
    
    // 跳过"end"标记
    if (*index < tokens.count && [tokens[*index] isEqualToString:@"end"]) {
        (*index)++;
    }
    
    return view;
}

@end

组件树依赖管理：
在组件化架构中，可以使用二叉树算法优化组件依赖管理：

@interface Component : NSObject
@property (nonatomic, strong) NSString *identifier;
@property (nonatomic, strong) NSString *name;
@property (nonatomic, strong) NSArray<Component *> *dependencies;
@end

@interface ComponentDependencyManager : NSObject

- (Component *)findCommonDependency:(Component *)component1 and:(Component *)component2;
- (NSArray<Component *> *)findOptimalInitializationOrder:(Component *)rootComponent;
- (NSString *)serializeComponentTree:(Component *)rootComponent;
- (Component *)deserializeComponentTree:(NSString *)serializedData;
- (BOOL)detectCircularDependencies:(Component *)rootComponent;

@end

@implementation ComponentDependencyManager

// 找出两个组件的最近公共依赖
- (Component *)findCommonDependency:(Component *)component1 and:(Component *)component2 {
    if (!component1 || !component2) {
        return nil;
    }
    
    // 获取component1的所有依赖
    NSMutableSet<NSString *> *dependencyIds = [NSMutableSet set];
    [self collectDependencyIds:component1 intoSet:dependencyIds];
    
    // 查找component2的依赖中第一个也是component1依赖的组件
    NSMutableArray<Component *> *component2Dependencies = [NSMutableArray array];
    [self collectDependencies:component2 intoArray:component2Dependencies];
    
    for (Component *dependency in component2Dependencies) {
        if ([dependencyIds containsObject:dependency.identifier]) {
            return dependency;
        }
    }
    
    return nil;
}

- (void)collectDependencyIds:(Component *)component intoSet:(NSMutableSet<NSString *> *)dependencyIds {
    if (!component) {
        return;
    }
    
    [dependencyIds addObject:component.identifier];
    
    for (Component *dependency in component.dependencies) {
        [self collectDependencyIds:dependency intoSet:dependencyIds];
    }
}

- (void)collectDependencies:(Component *)component intoArray:(NSMutableArray<Component *> *)dependencies {
    if (!component) {
        return;
    }
    
    [dependencies addObject:component];
    
    for (Component *dependency in component.dependencies) {
        [self collectDependencies:dependency intoArray:dependencies];
    }
}

// 找出组件的最优初始化顺序
- (NSArray<Component *> *)findOptimalInitializationOrder:(Component *)rootComponent {
    NSMutableArray<Component *> *result = [NSMutableArray array];
    NSMutableSet<NSString *> *visited = [NSMutableSet set];
    
    [self topologicalSort:rootComponent visited:visited result:result];
    
    return result;
}

- (void)topologicalSort:(Component *)component visited:(NSMutableSet<NSString *> *)visited result:(NSMutableArray<Component *> *)result {
    if (!component || [visited containsObject:component.identifier]) {
        return;
    }
    
    [visited addObject:component.identifier];
    
    for (Component *dependency in component.dependencies) {
        [self topologicalSort:dependency visited:visited result:result];
    }
    
    [result addObject:component];
}

// 序列化组件树
- (NSString *)serializeComponentTree:(Component *)rootComponent {
    NSMutableString *result = [NSMutableString string];
    [self serializeComponentHelper:rootComponent result:result];
    return result;
}

- (void)serializeComponentHelper:(Component *)component result:(NSMutableString *)result {
    if (!component) {
        [result appendString:@"null,"];
        return;
    }
    
    // 序列化组件的基本信息
    [result appendFormat:@"%@:%@,", component.identifier, component.name];
    
    // 序列化依赖
    [result appendString:@"["];
    for (Component *dependency in component.dependencies) {
        [self serializeComponentHelper:dependency result:result];
    }
    [result appendString:@"],"];
}

// 反序列化组件树
- (Component *)deserializeComponentTree:(NSString *)serializedData {
    NSArray<NSString *> *tokens = [serializedData componentsSeparatedByString:@","];
    NSInteger index = 0;
    return [self deserializeComponentHelper:tokens index:&index];
}

- (Component *)deserializeComponentHelper:(NSArray<NSString *> *)tokens index:(NSInteger *)index {
    if (*index >= tokens.count) {
        return nil;
    }
    
    NSString *token = tokens[*index];
    (*index)++;
    
    if ([token isEqualToString:@"null"]) {
        return nil;
    }
    
    if ([token isEqualToString:@"["]) {
        // 开始解析依赖列表
        NSMutableArray<Component *> *dependencies = [NSMutableArray array];
        
        while (*index < tokens.count && ![tokens[*index] isEqualToString:@"]"]) {
            Component *dependency = [self deserializeComponentHelper:tokens index:index];
            if (dependency) {
                [dependencies addObject:dependency];
            }
        }
        
        // 跳过"]"标记
        if (*index < tokens.count && [tokens[*index] isEqualToString:@"]"]) {
            (*index)++;
        }
        
        return nil;
    }
    
    if ([token isEqualToString:@"]"]) {
        return nil;
    }
    
    // 解析组件信息
    NSArray<NSString *> *componentInfo = [token componentsSeparatedByString:@":"];
    if (componentInfo.count < 2) {
        return nil;
    }
    
    Component *component = [[Component alloc] init];
    component.identifier = componentInfo[0];
    component.name = componentInfo[1];
    
    // 解析依赖
    if (*index < tokens.count && [tokens[*index] isEqualToString:@"["]) {
        (*index)++; // 跳过"["
        
        NSMutableArray<Component *> *dependencies = [NSMutableArray array];
        
        while (*index < tokens.count && ![tokens[*index] isEqualToString:@"]"]) {
            Component *dependency = [self deserializeComponentHelper:tokens index:index];
            if (dependency) {
                [dependencies addObject:dependency];
            }
        }
        
        component.dependencies = dependencies;
        
        // 跳过"]"标记
        if (*index < tokens.count && [tokens[*index] isEqualToString:@"]"]) {
            (*index)++;
        }
    }
    
    return component;
}

// 检测循环依赖
- (BOOL)detectCircularDependencies:(Component *)rootComponent {
    NSMutableSet<NSString *> *visiting = [NSMutableSet set];
    NSMutableSet<NSString *> *visited = [NSMutableSet set];
    
    return [self hasCycle:rootComponent visiting:visiting visited:visited];
}

- (BOOL)hasCycle:(Component *)component visiting:(NSMutableSet<NSString *> *)visiting visited:(NSMutableSet<NSString *> *)visited {
    if (!component) {
        return NO;
    }
    
    if ([visiting containsObject:component.identifier]) {
        return YES; // 发现循环依赖
    }
    
    if ([visited containsObject:component.identifier]) {
        return NO; // 已经检查过，没有循环
    }
    
    [visiting addObject:component.identifier];
    
    for (Component *dependency in component.dependencies) {
        if ([self hasCycle:dependency visiting:visiting visited:visited]) {
            return YES;
        }
    }
    
    [visiting removeObject:component.identifier];
    [visited addObject:component.identifier];
    
    return NO;
}

@end

这些实际应用展示了如何将LeetCode上的二叉树算法应用到iOS开发的实际场景中，提高视图层次结构分析和组件依赖管理的效率。

从iOS到LeetCode：资深开发者的算法实战指南

第三章：动态规划算法

3.1 基础动态规划

3.1.1 [LeetCode 322] 零钱兑换（Medium）

问题描述：
给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。

Objective-C 实现：

@interface Solution : NSObject
- (NSInteger)coinChange:(NSArray<NSNumber *> *)coins amount:(NSInteger)amount;
@end

@implementation Solution
- (NSInteger)coinChange:(NSArray<NSNumber *> *)coins amount:(NSInteger)amount {
    // 特殊情况处理
    if (amount == 0) {
        return 0;
    }
    
    if (coins.count == 0) {
        return -1;
    }
    
    // dp[i]表示凑成金额i所需的最少硬币数
    NSMutableArray<NSNumber *> *dp = [NSMutableArray arrayWithCapacity:amount + 1];
    
    // 初始化dp数组，初始值设为amount+1（一个不可能达到的值）
    for (NSInteger i = 0; i <= amount; i++) {
        dp[i] = @(amount + 1);
    }
    
    // 基础情况：凑成金额0需要0个硬币
    dp[0] = @0;
    
    // 动态规划过程
    for (NSInteger i = 1; i <= amount; i++) {
        for (NSNumber *coin in coins) {
            NSInteger coinValue = [coin integerValue];
            
            // 如果当前硬币面值小于等于当前金额，才能使用
            if (coinValue <= i) {
                // 状态转移方程：dp[i] = min(dp[i], dp[i - coinValue] + 1)
                dp[i] = @(MIN([dp[i] integerValue], [dp[i - coinValue] integerValue] + 1));
            }
        }
    }
    
    // 如果dp[amount]的值仍然是初始值，说明无法凑出amount
    return [dp[amount] integerValue] > amount ? -1 : [dp[amount] integerValue];
}
@end

算法分析：

时间复杂度：O(amount * n)，其中n是硬币种类数，amount是总金额
空间复杂度：O(amount)，需要一个长度为amount+1的数组来存储中间状态

实际工程应用：
零钱兑换算法在iOS开发中的实际应用：

支付系统优化：在电子钱包或支付应用中，可用于计算最优支付方式，例如使用最少的代金券、积分或现金组合完成支付。
资源分配优化：在资源管理系统中，可用于计算满足特定需求的最少资源组合，如服务器资源分配。
时间调度优化：在任务调度应用中，可用于计算完成特定工作量所需的最少时间单元组合。
游戏内经济系统：在游戏开发中，可用于设计游戏内货币和物品的兑换系统，确保游戏经济平衡。

3.1.2 [LeetCode 300] 最长递增子序列（Medium）

问题描述：
给你一个整数数组 nums，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。

Objective-C 实现：

@interface Solution : NSObject
- (NSInteger)lengthOfLIS:(NSArray<NSNumber *> *)nums;
@end

@implementation Solution
- (NSInteger)lengthOfLIS:(NSArray<NSNumber *> *)nums {
    if (nums.count == 0) {
        return 0;
    }
    
    // dp[i]表示以nums[i]结尾的最长递增子序列的长度
    NSMutableArray<NSNumber *> *dp = [NSMutableArray arrayWithCapacity:nums.count];
    
    // 初始化dp数组，每个元素至少是长度为1的子序列
    for (NSInteger i = 0; i < nums.count; i++) {
        dp[i] = @1;
    }
    
    NSInteger maxLength = 1;
    
    // 动态规划过程
    for (NSInteger i = 1; i < nums.count; i++) {
        for (NSInteger j = 0; j < i; j++) {
            // 如果当前元素大于之前的元素，可以形成更长的递增子序列
            if ([nums[i] integerValue] > [nums[j] integerValue]) {
                // 状态转移方程：dp[i] = max(dp[i], dp[j] + 1)
                dp[i] = @(MAX([dp[i] integerValue], [dp[j] integerValue] + 1));
            }
        }
        
        // 更新最长递增子序列的长度
        maxLength = MAX(maxLength, [dp[i] integerValue]);
    }
    
    return maxLength;
}
@end

优化实现（二分查找）：

@implementation Solution
- (NSInteger)lengthOfLIS:(NSArray<NSNumber *> *)nums {
    if (nums.count == 0) {
        return 0;
    }
    
    // tails[i]表示长度为i+1的递增子序列的末尾元素的最小值
    NSMutableArray<NSNumber *> *tails = [NSMutableArray array];
    tails[0] = nums[0];
    
    NSInteger length = 1;
    
    for (NSInteger i = 1; i < nums.count; i++) {
        NSInteger num = [nums[i] integerValue];
        
        // 如果当前元素大于tails中的最后一个元素，直接添加到tails末尾
        if (num > [tails[length - 1] integerValue]) {
            tails[length] = nums[i];
            length++;
        } else {
            // 二分查找，找到tails中第一个大于等于num的位置
            NSInteger left = 0;
            NSInteger right = length - 1;
            
            while (left < right) {
                NSInteger mid = left + (right - left) / 2;
                
                if ([tails[mid] integerValue] < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            
            // 更新tails[left]
            tails[left] = nums[i];
        }
    }
    
    return length;
}
@end

算法分析：

动态规划解法：
- 时间复杂度：O(n²)，其中n是数组长度
- 空间复杂度：O(n)，需要一个长度为n的数组来存储中间状态
二分查找优化解法：
- 时间复杂度：O(n log n)，其中n是数组长度
- 空间复杂度：O(n)，需要一个长度为n的数组来存储中间状态

实际工程应用：
最长递增子序列算法在iOS开发中的实际应用：

用户行为分析：在数据分析应用中，可用于识别用户活动中的递增模式，如消费金额、使用频率等的增长趋势。
股票分析工具：在金融应用中，可用于识别股票价格的上升趋势，帮助投资决策。
文本相似度比较：在文档比较或版本控制应用中，可用于找出两个文本之间的最长公共子序列，辅助差异比较。
网络包序列重组：在网络应用中，可用于重组乱序到达的网络包，恢复原始数据流。

3.1.3 [LeetCode 72] 编辑距离（Hard）

问题描述：
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：插入一个字符、删除一个字符、替换一个字符。

Objective-C 实现：

@interface Solution : NSObject
- (NSInteger)minDistance:(NSString *)word1 to:(NSString *)word2;
@end

@implementation Solution
- (NSInteger)minDistance:(NSString *)word1 to:(NSString *)word2 {
    NSInteger m = word1.length;
    NSInteger n = word2.length;
    
    // 特殊情况处理
    if (m == 0) {
        return n;
    }
    if (n == 0) {
        return m;
    }
    
    // dp[i][j]表示word1的前i个字符转换到word2的前j个字符需要的最少操作数
    NSMutableArray<NSMutableArray<NSNumber *> *> *dp = [NSMutableArray arrayWithCapacity:m + 1];
    
    // 初始化dp数组
    for (NSInteger i = 0; i <= m; i++) {
        NSMutableArray<NSNumber *> *row = [NSMutableArray arrayWithCapacity:n + 1];
        for (NSInteger j = 0; j <= n; j++) {
            row[j] = @0;
        }
        dp[i] = row;
    }
    
    // 边界情况：word1的前i个字符转换到空字符串需要i次删除操作
    for (NSInteger i = 1; i <= m; i++) {
        dp[i][0] = @(i);
    }
    
    // 边界情况：空字符串转换到word2的前j个字符需要j次插入操作
    for (NSInteger j = 1; j <= n; j++) {
        dp[0][j] = @(j);
    }
    
    // 动态规划过程
    for (NSInteger i = 1; i <= m; i++) {
        for (NSInteger j = 1; j <= n; j++) {
            // 如果当前字符相同，不需要额外操作
            if ([word1 characterAtIndex:i - 1] == [word2 characterAtIndex:j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // 否则，取三种操作中的最小值：
                // 1. 替换操作：dp[i-1][j-1] + 1
                // 2. 删除操作：dp[i-1][j] + 1
                // 3. 插入操作：dp[i][j-1] + 1
                NSInteger replace = [dp[i - 1][j - 1] integerValue] + 1;
                NSInteger delete = [dp[i - 1][j] integerValue] + 1;
                NSInteger insert = [dp[i][j - 1] integerValue] + 1;
                
                dp[i][j] = @(MIN(replace, MIN(delete, insert)));
            }
        }
    }
    
    return [dp[m][n] integerValue];
}
@end

算法分析：

时间复杂度：O(m*n)，其中m和n分别是两个字符串的长度
空间复杂度：O(m*n)，需要一个m+1行n+1列的二维数组来存储中间状态

实际工程应用：
编辑距离算法在iOS开发中的实际应用：

拼写检查与自动更正：在文本编辑应用中，可用于实现拼写检查和自动更正功能，找出与错误单词最相似的正确单词。
搜索引擎优化：在应用内搜索功能中，可用于实现模糊匹配，即使用户输入有误也能返回相关结果。
DNA序列比较：在生物信息学应用中，可用于比较DNA序列的相似度，找出基因突变。
版本差异比较：在版本控制应用中，可用于计算两个文本版本之间的差异，显示最小的编辑操作集。

3.1.4 实际应用：iOS应用中的缓存策略与资源预加载

上述基础动态规划算法在iOS开发中的缓存策略和资源预加载方面有重要应用：

智能缓存管理系统：
在图片加载和缓存库中，可以使用动态规划算法优化缓存策略：

@interface CacheItem : NSObject
@property (nonatomic, strong) NSString *key;
@property (nonatomic, strong) id value;
@property (nonatomic, assign) NSInteger size;
@property (nonatomic, assign) NSInteger frequency;
@property (nonatomic, assign) NSTimeInterval lastAccessTime;
@end

@interface SmartCacheManager : NSObject

@property (nonatomic, assign) NSInteger maxCacheSize;
@property (nonatomic, strong) NSMutableDictionary<NSString *, CacheItem *> *cache;
@property (nonatomic, assign) NSInteger currentCacheSize;

- (instancetype)initWithMaxSize:(NSInteger)maxSize;
- (id)objectForKey:(NSString *)key;
- (void)setObject:(id)object forKey:(NSString *)key size:(NSInteger)size;
- (void)optimizeCacheWithPredictedAccess:(NSArray<NSString *> *)predictedAccessKeys;

@end

@implementation SmartCacheManager

- (instancetype)initWithMaxSize:(NSInteger)maxSize {
    self = [super init];
    if (self) {
        _maxCacheSize = maxSize;
        _cache = [NSMutableDictionary dictionary];
        _currentCacheSize = 0;
    }
    return self;
}

- (id)objectForKey:(NSString *)key {
    CacheItem *item = self.cache[key];
    if (item) {
        // 更新访问统计
        item.frequency++;
        item.lastAccessTime = [NSDate timeIntervalSinceReferenceDate];
        return item.value;
    }
    return nil;
}

- (void)setObject:(id)object forKey:(NSString *)key size:(NSInteger)size {
    // 如果对象已存在，先移除
    [self removeObjectForKey:key];
    
    // 如果新对象太大，无法缓存
    if (size > self.maxCacheSize) {
        return;
    }
    
    // 如果缓存空间不足，需要清理
    while (self.currentCacheSize + size > self.maxCacheSize && self.cache.count > 0) {
        [self evictOneItem];
    }
    
    // 添加新对象到缓存
    CacheItem *item = [[CacheItem alloc] init];
    item.key = key;
    item.value = object;
    item.size = size;
    item.frequency = 1;
    item.lastAccessTime = [NSDate timeIntervalSinceReferenceDate];
    
    self.cache[key] = item;
    self.currentCacheSize += size;
}

- (void)removeObjectForKey:(NSString *)key {
    CacheItem *item = self.cache[key];
    if (item) {
        self.currentCacheSize -= item.size;
        [self.cache removeObjectForKey:key];
    }
}

- (void)evictOneItem {
    // 使用动态规划思想选择要移除的项
    // 这里使用一个简化的策略：移除最近最少使用的项
    NSString *keyToRemove = nil;
    NSTimeInterval oldestAccessTime = DBL_MAX;
    
    for (NSString *key in self.cache) {
        CacheItem *item = self.cache[key];
        if (item.lastAccessTime < oldestAccessTime) {
            oldestAccessTime = item.lastAccessTime;
            keyToRemove = key;
        }
    }
    
    if (keyToRemove) {
        [self removeObjectForKey:keyToRemove];
    }
}

- (void)optimizeCacheWithPredictedAccess:(NSArray<NSString *> *)predictedAccessKeys {
    // 使用类似于"零钱兑换"的动态规划思想优化缓存
    // 目标是在有限的缓存空间内，最大化命中率
    
    // 获取所有缓存项
    NSMutableArray<CacheItem *> *allItems = [NSMutableArray array];
    for (NSString *key in self.cache) {
        [allItems addObject:self.cache[key]];
    }
    
    // 获取预测将要访问的项
    NSMutableArray<CacheItem *> *predictedItems = [NSMutableArray array];
    for (NSString *key in predictedAccessKeys) {
        CacheItem *item = self.cache[key];
        if (item) {
            [predictedItems addObject:item];
        }
    }
    
    // 如果预测的访问项总大小小于缓存容量，直接返回
    NSInteger predictedTotalSize = 0;
    for (CacheItem *item in predictedItems) {
        predictedTotalSize += item.size;
    }
    
    if (predictedTotalSize <= self.maxCacheSize) {
        return;
    }
    
    // 使用动态规划解决背包问题
    // dp[i][j]表示前i个项目在容量为j的情况下能获得的最大价值（这里的价值是访问频率）
    NSInteger n = predictedItems.count;
    NSMutableArray<NSMutableArray<NSNumber *> *> *dp = [NSMutableArray arrayWithCapacity:n + 1];
    
    for (NSInteger i = 0; i <= n; i++) {
        NSMutableArray<NSNumber *> *row = [NSMutableArray arrayWithCapacity:self.maxCacheSize + 1];
        for (NSInteger j = 0; j <= self.maxCacheSize; j++) {
            row[j] = @0;
        }
        dp[i] = row;
    }
    
    for (NSInteger i = 1; i <= n; i++) {
        CacheItem *item = predictedItems[i - 1];
        for (NSInteger j = 1; j <= self.maxCacheSize; j++) {
            if (item.size > j) {
                // 当前项太大，无法放入容量为j的背包
                dp[i][j] = dp[i - 1][j];
            } else {
                // 选择放入或不放入当前项
                NSInteger notTake = [dp[i - 1][j] integerValue];
                NSInteger take = [dp[i - 1][j - item.size] integerValue] + item.frequency;
                dp[i][j] = @(MAX(notTake, take));
            }
        }
    }
    
    // 根据动态规划结果，确定要保留的项
    NSMutableSet<NSString *> *keysToKeep = [NSMutableSet set];
    NSInteger capacity = self.maxCacheSize;
    
    for (NSInteger i = n; i > 0; i--) {
        if ([dp[i][capacity] integerValue] != [dp[i - 1][capacity] integerValue]) {
            // 当前项被选中
            CacheItem *item = predictedItems[i - 1];
            [keysToKeep addObject:item.key];
            capacity -= item.size;
        }
    }
    
    // 移除未被选中的项
    NSMutableArray<NSString *> *keysToRemove = [NSMutableArray array];
    for (NSString *key in predictedAccessKeys) {
        if (![keysToKeep containsObject:key] && self.cache[key]) {
            [keysToRemove addObject:key];
        }
    }
    
    for (NSString *key in keysToRemove) {
        [self removeObjectForKey:key];
    }
}

@end

智能资源预加载系统：
在应用启动优化中，可以使用动态规划算法优化资源预加载：

@interface Resource : NSObject
@property (nonatomic, strong) NSString *identifier;
@property (nonatomic, strong) NSString *path;
@property (nonatomic, assign) NSInteger size;
@property (nonatomic, assign) NSInteger priority;
@property (nonatomic, assign) NSTimeInterval loadTime;
@property (nonatomic, strong) NSArray<NSString *> *dependencies;
@end

@interface ResourcePreloader : NSObject

@property (nonatomic, strong) NSMutableDictionary<NSString *, Resource *> *resources;
@property (nonatomic, assign) NSTimeInterval maxPreloadTime;

- (instancetype)initWithMaxPreloadTime:(NSTimeInterval)maxTime;
- (void)registerResource:(Resource *)resource;
- (void)optimizePreloadSequence;
- (void)startPreloading;

@end

@implementation ResourcePreloader

- (instancetype)initWithMaxPreloadTime:(NSTimeInterval)maxTime {
    self = [super init];
    if (self) {
        _resources = [NSMutableDictionary dictionary];
        _maxPreloadTime = maxTime;
    }
    return self;
}

- (void)registerResource:(Resource *)resource {
    self.resources[resource.identifier] = resource;
}

- (void)optimizePreloadSequence {
    // 使用类似于"最长递增子序列"的动态规划思想优化预加载顺序
    // 目标是在有限的时间内，最大化预加载的资源价值
    
    // 获取所有资源
    NSArray<Resource *> *allResources = self.resources.allValues;
    
    // 构建依赖图
    NSMutableDictionary<NSString *, NSMutableSet<NSString *> *> *dependencyGraph = [NSMutableDictionary dictionary];
    for (Resource *resource in allResources) {
        dependencyGraph[resource.identifier] = [NSMutableSet set];
        for (NSString *dependency in resource.dependencies) {
            [dependencyGraph[resource.identifier] addObject:dependency];
        }
    }
    
    // 拓扑排序
    NSMutableArray<Resource *> *sortedResources = [NSMutableArray array];
    NSMutableSet<NSString *> *visited = [NSMutableSet set];
    NSMutableSet<NSString *> *temp = [NSMutableSet set];
    
    for (Resource *resource in allResources) {
        if (![visited containsObject:resource.identifier]) {
            [self topologicalSort:resource.identifier
                  dependencyGraph:dependencyGraph
                         visited:visited
                            temp:temp
                  sortedResources:sortedResources];
        }
    }
    
    // 使用动态规划解决背包问题
    // dp[i][j]表示前i个资源在时间为j的情况下能获得的最大价值
    NSInteger n = sortedResources.count;
    NSInteger timeLimit = (NSInteger)self.maxPreloadTime;
    NSMutableArray<NSMutableArray<NSNumber *> *> *dp = [NSMutableArray arrayWithCapacity:n + 1];
    
    for (NSInteger i = 0; i <= n; i++) {
        NSMutableArray<NSNumber *> *row = [NSMutableArray arrayWithCapacity:timeLimit + 1];
        for (NSInteger j = 0; j <= timeLimit; j++) {
            row[j] = @0;
        }
        dp[i] = row;
    }
    
    for (NSInteger i = 1; i <= n; i++) {
        Resource *resource = sortedResources[i - 1];
        NSInteger loadTime = (NSInteger)resource.loadTime;
        
        for (NSInteger j = 1; j <= timeLimit; j++) {
            if (loadTime > j) {
                // 当前资源加载时间太长，无法在时间j内加载
                dp[i][j] = dp[i - 1][j];
            } else {
                // 选择加载或不加载当前资源
                NSInteger notLoad = [dp[i - 1][j] integerValue];
                NSInteger load = [dp[i - 1][j - loadTime] integerValue] + resource.priority;
                dp[i][j] = @(MAX(notLoad, load));
            }
        }
    }
    
    // 根据动态规划结果，确定要预加载的资源
    NSMutableArray<Resource *> *resourcesToPreload = [NSMutableArray array];
    NSInteger remainingTime = timeLimit;
    
    for (NSInteger i = n; i > 0; i--) {
        if ([dp[i][remainingTime] integerValue] != [dp[i - 1][remainingTime] integerValue]) {
            // 当前资源被选中
            Resource *resource = sortedResources[i - 1];
            [resourcesToPreload addObject:resource];
            remainingTime -= (NSInteger)resource.loadTime;
        }
    }
    
    // 反转数组，按照依赖顺序排列
    NSArray<Resource *> *reversedResources = [[resourcesToPreload reverseObjectEnumerator] allObjects];
    
    // 更新资源列表，只保留要预加载的资源
    [self.resources removeAllObjects];
    for (Resource *resource in reversedResources) {
        self.resources[resource.identifier] = resource;
    }
}

- (void)topologicalSort:(NSString *)resourceId
        dependencyGraph:(NSDictionary<NSString *, NSSet<NSString *> *> *)dependencyGraph
               visited:(NSMutableSet<NSString *> *)visited
                  temp:(NSMutableSet<NSString *> *)temp
        sortedResources:(NSMutableArray<Resource *> *)sortedResources {
    
    if ([temp containsObject:resourceId]) {
        // 检测到循环依赖，跳过
        return;
    }
    
    if ([visited containsObject:resourceId]) {
        return;
    }
    
    [temp addObject:resourceId];
    
    for (NSString *dependency in dependencyGraph[resourceId]) {
        [self topologicalSort:dependency
              dependencyGraph:dependencyGraph
                     visited:visited
                        temp:temp
              sortedResources:sortedResources];
    }
    
    [temp removeObject:resourceId];
    [visited addObject:resourceId];
    
    [sortedResources addObject:self.resources[resourceId]];
}

- (void)startPreloading {
    // 按优化后的顺序预加载资源
    for (Resource *resource in self.resources.allValues) {
        [self preloadResource:resource];
    }
}

- (void)preloadResource:(Resource *)resource {
    // 实际的资源预加载实现
    // 这里简化处理，实际应用中会异步加载资源
    NSLog(@"Preloading resource: %@", resource.identifier);
    
    // 模拟加载过程
    dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
        // 实际加载资源的代码
        NSLog(@"Resource loaded: %@", resource.identifier);
    });
}

@end

这些实际应用展示了如何将LeetCode上的基础动态规划算法应用到iOS开发的实际场景中，提高缓存策略和资源预加载的效率。

3.2 高级动态规划

3.2.1 [LeetCode 312] 戳气球（Hard）

问题描述：
有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i-1] * nums[i] * nums[i+1] 个硬币。这里的 i-1 和 i+1 代表和 i 相邻的两个气球的序号。如果 i-1或 i+1 超出了数组的边界，那么就当它是一个数字为 1 的气球。求所能获得硬币的最大数量。

Objective-C 实现：

@interface Solution : NSObject
- (NSInteger)maxCoins:(NSArray<NSNumber *> *)nums;
@end

@implementation Solution
- (NSInteger)maxCoins:(NSArray<NSNumber *> *)nums {
    // 特殊情况处理
    if (nums.count == 0) {
        return 0;
    }
    
    // 添加边界值1
    NSMutableArray<NSNumber *> *newNums = [NSMutableArray arrayWithCapacity:nums.count + 2];
    [newNums addObject:@1];
    [newNums addObjectsFromArray:nums];
    [newNums addObject:@1];
    
    NSInteger n = newNums.count;
    
    // dp[i][j]表示戳破开区间(i,j)中的所有气球能获得的最大硬币数
    NSMutableArray<NSMutableArray<NSNumber *> *> *dp = [NSMutableArray arrayWithCapacity:n];
    
    for (NSInteger i = 0; i < n; i++) {
        NSMutableArray<NSNumber *> *row = [NSMutableArray arrayWithCapacity:n];
        for (NSInteger j = 0; j < n; j++) {
            row[j] = @0;
        }
        dp[i] = row;
    }
    
    // 动态规划过程
    // 区间长度从3开始，因为需要至少一个气球(加上两个边界)
    for (NSInteger len = 3; len <= n; len++) {
        // 区间起点
        for (NSInteger i = 0; i <= n - len; i++) {
            // 区间终点
            NSInteger j = i + len - 1;
            
            // 枚举区间内最后一个被戳破的气球位置k
            for (NSInteger k = i + 1; k < j; k++) {
                // 计算戳破气球k的收益
                NSInteger coins = [newNums[i] integerValue] * [newNums[k] integerValue] * [newNums[j] integerValue];
                
                // 加上戳破左右两个子区间的最大收益
                coins += [dp[i][k] integerValue] + [dp[k][j] integerValue];
                
                // 更新dp[i][j]
                dp[i][j] = @(MAX([dp[i][j] integerValue], coins));
            }
        }
    }
    
    return [dp[0][n - 1] integerValue];
}
@end

算法分析：

时间复杂度：O(n³)，其中n是气球数量
空间复杂度：O(n²)，需要一个n×n的二维数组来存储中间状态

实际工程应用：
戳气球算法在iOS开发中的实际应用：

游戏关卡设计：在休闲游戏开发中，可用于设计最优的游戏关卡难度曲线，使玩家获得最大的游戏体验。
资源调度优化：在多任务处理系统中，可用于确定任务执行的最优顺序，最大化系统吞吐量。
广告投放策略：在广告系统中，可用于确定广告展示的最优顺序，最大化点击率和转化率。
内容推荐系统：在内容推荐引擎中，可用于确定内容展示的最优顺序，最大化用户参与度。

3.2.2 [LeetCode 10] 正则表达式匹配（Hard）

问题描述：
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素

Objective-C 实现：

@interface Solution : NSObject
- (BOOL)isMatch:(NSString *)s pattern:(NSString *)p;
@end

@implementation Solution
- (BOOL)isMatch:(NSString *)s pattern:(NSString *)p {
    NSInteger m = s.length;
    NSInteger n = p.length;
    
    // dp[i][j] 表示 s 的前 i 个字符与 p 的前 j 个字符是否匹配
    BOOL dp[m + 1][n + 1];
    memset(dp, 0, sizeof(dp));
    
    // 空字符串与空模式匹配
    dp[0][0] = YES;
    
    // 处理 s 为空，p 不为空的情况，例如 p = "a*" 可以匹配空字符串
    for (NSInteger j = 1; j <= n; j++) {
        if ([p characterAtIndex:j - 1] == '*') {
            dp[0][j] = dp[0][j - 2];
        }
    }
    
    for (NSInteger i = 1; i <= m; i++) {
        for (NSInteger j = 1; j <= n; j++) {
            unichar sc = [s characterAtIndex:i - 1];
            unichar pc = [p characterAtIndex:j - 1];
            
            if (pc == '.' || pc == sc) {
                // 当前字符匹配
                dp[i][j] = dp[i - 1][j - 1];
            } else if (pc == '*') {
                // 处理 '*'
                unichar prevPc = [p characterAtIndex:j - 2];
                
                // '*' 匹配零次前面的元素
                dp[i][j] = dp[i][j - 2];
                
                // '*' 匹配一次或多次前面的元素
                if (prevPc == '.' || prevPc == sc) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            }
        }
    }
    
    return dp[m][n];
}
@end

算法分析：

时间复杂度：O(m*n)，其中m和n分别是字符串s和p的长度
空间复杂度：O(m*n)，需要一个m+1行n+1列的二维数组来存储中间状态

实际工程应用：
正则表达式匹配算法在iOS开发中的实际应用：

自定义输入验证：在表单验证中，可用于实现复杂的输入格式验证，如邮箱、电话号码、密码强度等。
文本解析与提取：在文档处理应用中，可用于从非结构化文本中提取结构化信息，如日期、地址、链接等。
日志分析工具：在开发调试工具中，可用于分析日志文件，提取特定模式的错误信息或警告。
搜索功能增强：在搜索功能中，可用于支持高级搜索语法，允许用户使用通配符和模式匹配进行搜索。

3.2.3 [LeetCode 115] 不同的子序列（Hard）

问题描述：
给定一个字符串 s 和一个字符串 t，计算在 s 的子序列中 t 出现的个数。字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。

Objective-C 实现：

@interface Solution : NSObject
- (NSInteger)numDistinct:(NSString *)s t:(NSString *)t;
@end

@implementation Solution
- (NSInteger)numDistinct:(NSString *)s t:(NSString *)t {
    NSInteger m = s.length;
    NSInteger n = t.length;
    
    // 特殊情况处理
    if (n > m) {
        return 0;
    }
    
    if (n == 0) {
        return 1;
    }
    
    // dp[i][j] 表示 s 的前 i 个字符中，t 的前 j 个字符出现的次数
    NSMutableArray<NSMutableArray<NSNumber *> *> *dp = [NSMutableArray arrayWithCapacity:m + 1];
    
    for (NSInteger i = 0; i <= m; i++) {
        NSMutableArray<NSNumber *> *row = [NSMutableArray arrayWithCapacity:n + 1];
        for (NSInteger j = 0; j <= n; j++) {
            row[j] = @0;
        }
        dp[i] = row;
    }
    
    // 空字符串 t 是任何字符串的子序列，且只有一种方式
    for (NSInteger i = 0; i <= m; i++) {
        dp[i][0] = @1;
    }
    
    // 动态规划过程
    for (NSInteger i = 1; i <= m; i++) {
        for (NSInteger j = 1; j <= n; j++) {
            // 如果当前字符相同，有两种选择：
            // 1. 使用当前字符匹配：dp[i-1][j-1]
            // 2. 不使用当前字符匹配：dp[i-1][j]
            if ([s characterAtIndex:i - 1] == [t characterAtIndex:j - 1]) {
                dp[i][j] = @([dp[i - 1][j - 1] integerValue] + [dp[i - 1][j] integerValue]);
            } else {
                // 当前字符不同，只能不使用当前字符
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    
    return [dp[m][n] integerValue];
}
@end

算法分析：

时间复杂度：O(m*n)，其中m和n分别是字符串s和t的长度
空间复杂度：O(m*n)，需要一个m+1行n+1列的二维数组来存储中间状态

实际工程应用：
不同的子序列算法在iOS开发中的实际应用：

文本相似度分析：在文档比较应用中，可用于计算两个文本之间的相似度，找出一个文本在另一个文本中出现的所有可能方式。
用户行为模式识别：在用户分析系统中，可用于识别用户行为序列中包含特定模式的次数，帮助理解用户习惯。
基因序列分析：在生物信息学应用中，可用于分析DNA序列中特定基因片段出现的次数和方式。
自然语言处理：在NLP应用中，可用于分析文本中特定词组或句式的出现模式，辅助语义理解。

3.2.4 实际应用：iOS中的推荐算法与预测模型

上述高级动态规划算法在iOS开发中的推荐算法和预测模型方面有重要应用：

智能内容推荐系统：
在内容推荐应用中，可以使用动态规划算法优化推荐策略：

@interface ContentItem : NSObject
@property (nonatomic, strong) NSString *identifier;
@property (nonatomic, strong) NSString *title;
@property (nonatomic, strong) NSString *category;
@property (nonatomic, assign) NSInteger popularity;
@property (nonatomic, assign) NSTimeInterval duration;
@property (nonatomic, strong) NSArray<NSString *> *tags;
@end

@interface UserProfile : NSObject
@property (nonatomic, strong) NSString *userId;
@property (nonatomic, strong) NSMutableDictionary<NSString *, NSNumber *> *categoryPreferences;
@property (nonatomic, strong) NSMutableDictionary<NSString *, NSNumber *> *tagPreferences;
@property (nonatomic, strong) NSMutableArray<NSString *> *viewHistory;
@property (nonatomic, assign) NSTimeInterval averageViewDuration;
@end

@interface ContentRecommender : NSObject

@property (nonatomic, strong) NSArray<ContentItem *> *contentLibrary;
@property (nonatomic, strong) UserProfile *userProfile;
@property (nonatomic, assign) NSInteger maxRecommendations;
@property (nonatomic, assign) NSTimeInterval maxTotalDuration;

- (instancetype)initWithContentLibrary:(NSArray<ContentItem *> *)library
                           userProfile:(UserProfile *)profile
                    maxRecommendations:(NSInteger)maxRecommendations
                      maxTotalDuration:(NSTimeInterval)maxDuration;

- (NSArray<ContentItem *> *)generateRecommendations;
- (NSArray<ContentItem *> *)generateDiverseRecommendations;
- (NSArray<NSArray<ContentItem *> *> *)generateSequentialRecommendations;

@end

@implementation ContentRecommender

- (instancetype)initWithContentLibrary:(NSArray<ContentItem *> *)library
                           userProfile:(UserProfile *)profile
                    maxRecommendations:(NSInteger)maxRecommendations
                      maxTotalDuration:(NSTimeInterval)maxDuration {
    self = [super init];
    if (self) {
        _contentLibrary = library;
        _userProfile = profile;
        _maxRecommendations = maxRecommendations;
        _maxTotalDuration = maxDuration;
    }
    return self;
}

- (NSArray<ContentItem *> *)generateRecommendations {
    // 使用类似于"零钱兑换"的动态规划思想优化推荐
    // 目标是在有限的推荐数量和总时长内，最大化用户满意度
    
    // 计算每个内容项的用户满意度得分
    NSMutableArray<NSNumber *> *scores = [NSMutableArray arrayWithCapacity:self.contentLibrary.count];
    NSMutableArray<NSNumber *> *durations = [NSMutableArray arrayWithCapacity:self.contentLibrary.count];
    
    for (ContentItem *item in self.contentLibrary) {
        NSInteger score = [self calculateScoreForItem:item];
        scores[scores.count] = @(score);
        durations[durations.count] = @(item.duration);
    }
    
    // 使用动态规划解决背包问题
    // dp[i][j][k]表示从前i个内容中选择j个，总时长不超过k时的最大得分
    NSInteger n = self.contentLibrary.count;
    NSInteger m = self.maxRecommendations;
    NSInteger t = (NSInteger)self.maxTotalDuration;
    
    // 创建三维dp数组
    NSMutableArray<NSMutableArray<NSMutableArray<NSNumber *> *> *> *dp = [NSMutableArray arrayWithCapacity:n + 1];
    
    for (NSInteger i = 0; i <= n; i++) {
        NSMutableArray<NSMutableArray<NSNumber *> *> *dim2 = [NSMutableArray arrayWithCapacity:m + 1];
        for (NSInteger j = 0; j <= m; j++) {
            NSMutableArray<NSNumber *> *dim3 = [NSMutableArray arrayWithCapacity:t + 1];
            for (NSInteger k = 0; k <= t; k++) {
                dim3[k] = @0;
            }
            dim2[j] = dim3;
        }
        dp[i] = dim2;
    }
    
    // 动态规划过程
    for (NSInteger i = 1; i <= n; i++) {
        NSInteger itemIndex = i - 1;
        NSInteger itemScore = [scores[itemIndex] integerValue];
        NSInteger itemDuration = [durations[itemIndex] integerValue];
        
        for (NSInteger j = 1; j <= m; j++) {
            for (NSInteger k = 1; k <= t; k++) {
                // 不选当前内容
                dp[i][j][k] = dp[i - 1][j][k];
                
                // 选择当前内容（如果时长允许）
                if (itemDuration <= k) {
                    NSInteger newScore = [dp[i - 1][j - 1][k - itemDuration] integerValue] + itemScore;
                    dp[i][j][k] = @(MAX([dp[i][j][k] integerValue], newScore));
                }
            }
        }
    }
    
    // 根据动态规划结果，确定要推荐的内容
    NSMutableArray<ContentItem *> *recommendations = [NSMutableArray array];
    NSInteger remainingItems = m;
    NSInteger remainingDuration = t;
    
    for (NSInteger i = n; i > 0 && remainingItems > 0; i--) {
        if ([dp[i][remainingItems][remainingDuration] integerValue] != 
            [dp[i - 1][remainingItems][remainingDuration] integerValue]) {
            // 当前内容被选中
            ContentItem *item = self.contentLibrary[i - 1];
            [recommendations addObject:item];
            remainingItems--;
            remainingDuration -= (NSInteger)item.duration;
        }
    }
    
    return recommendations;
}

- (NSArray<ContentItem *> *)generateDiverseRecommendations {
    // 使用类似于"不同的子序列"的动态规划思想优化多样性推荐
    // 目标是在保证用户满意度的同时，增加推荐内容的多样性
    
    // 获取用户已查看过的内容类别
    NSMutableSet<NSString *> *viewedCategories = [NSMutableSet set];
    for (NSString *itemId in self.userProfile.viewHistory) {
        for (ContentItem *item in self.contentLibrary) {
            if ([item.identifier isEqualToString:itemId]) {
                [viewedCategories addObject:item.category];
                break;
            }
        }
    }
    
    // 计算每个内容项的用户满意度得分和多样性得分
    NSMutableArray<NSNumber *> *satisfactionScores = [NSMutableArray arrayWithCapacity:self.contentLibrary.count];
    NSMutableArray<NSNumber *> *diversityScores = [NSMutableArray arrayWithCapacity:self.contentLibrary.count];
    
    for (ContentItem *item in self.contentLibrary) {
        NSInteger satisfactionScore = [self calculateScoreForItem:item];
        NSInteger diversityScore = [viewedCategories containsObject:item.category] ? 0 : 100;
        
        satisfactionScores[satisfactionScores.count] = @(satisfactionScore);
        diversityScores[diversityScores.count] = @(diversityScore);
    }
    
    // 使用动态规划平衡满意度和多样性
    NSInteger n = self.contentLibrary.count;
    NSInteger m = self.maxRecommendations;
    
    // dp[i][j][k]表示从前i个内容中选择j个，其中k个是新类别的最大满意度得分
    NSMutableArray<NSMutableArray<NSMutableArray<NSNumber *> *> *> *dp = [NSMutableArray arrayWithCapacity:n + 1];
    
    for (NSInteger i = 0; i <= n; i++) {
        NSMutableArray<NSMutableArray<NSNumber *> *> *dim2 = [NSMutableArray arrayWithCapacity:m + 1];
        for (NSInteger j = 0; j <= m; j++) {
            NSMutableArray<NSNumber *> *dim3 = [NSMutableArray arrayWithCapacity:m + 1];
            for (NSInteger k = 0; k <= m; k++) {
                dim3[k] = @(NSIntegerMin);
            }
            dim2[j] = dim3;
        }
        dp[i] = dim2;
    }
    
    // 基础情况
    dp[0][0][0] = @0;
    
    // 动态规划过程
    for (NSInteger i = 1; i <= n; i++) {
        NSInteger itemIndex = i - 1;
        ContentItem *item = self.contentLibrary[itemIndex];
        BOOL isNewCategory = ![viewedCategories containsObject:item.category];
        
        for (NSInteger j = 0; j <= m; j++) {
            for (NSInteger k = 0; k <= j; k++) {
                // 不选当前内容
                if ([dp[i - 1][j][k] integerValue] != NSIntegerMin) {
                    dp[i][j][k] = dp[i - 1][j][k];
                }
                
                // 选择当前内容
                if (j > 0 && [dp[i - 1][j - 1][k - (isNewCategory ? 1 : 0)] integerValue] != NSIntegerMin) {
                    NSInteger newScore = [dp[i - 1][j - 1][k - (isNewCategory ? 1 : 0)] integerValue] + 
                                         [satisfactionScores[itemIndex] integerValue];
                    dp[i][j][k] = @(MAX([dp[i][j][k] integerValue], newScore));
                }
            }
        }
    }
    
    // 找出最佳的多样性比例
    NSInteger bestK = 0;
    NSInteger bestScore = NSIntegerMin;
    
    for (NSInteger k = 0; k <= m; k++) {
        NSInteger combinedScore = [dp[n][m][k] integerValue] + k * 50; // 多样性权重
        if (combinedScore > bestScore && [dp[n][m][k] integerValue] != NSIntegerMin) {
            bestScore = combinedScore;
            bestK = k;
        }
    }
    
    // 根据动态规划结果，确定要推荐的内容
    NSMutableArray<ContentItem *> *recommendations = [NSMutableArray array];
    NSInteger remainingItems = m;
    NSInteger remainingNewCategories = bestK;
    
    for (NSInteger i = n; i > 0 && remainingItems > 0; i--) {
        ContentItem *item = self.contentLibrary[i - 1];
        BOOL isNewCategory = ![viewedCategories containsObject:item.category];
        
        if ([dp[i][remainingItems][remainingNewCategories] integerValue] != 
            [dp[i - 1][remainingItems][remainingNewCategories] integerValue]) {
            // 当前内容被选中
            [recommendations addObject:item];
            remainingItems--;
            if (isNewCategory) {
                remainingNewCategories--;
            }
        }
    }
    
    return recommendations;
}

- (NSArray<NSArray<ContentItem *> *> *)generateSequentialRecommendations {
    // 使用类似于"戳气球"的动态规划思想优化序列推荐
    // 目标是生成一个最优的内容序列，使得用户在观看过程中的满意度最大化
    
    // 筛选出可能的候选内容
    NSMutableArray<ContentItem *> *candidates = [NSMutableArray array];
    for (ContentItem *item in self.contentLibrary) {
        if (![self.userProfile.viewHistory containsObject:item.identifier]) {
            [candidates addObject:item];
        }
    }
    
    // 如果候选内容太少，直接返回
    if (candidates.count <= self.maxRecommendations) {
        return @[candidates];
    }
    
    // 计算内容之间的转换满意度
    NSInteger n = candidates.count;
    NSMutableArray<NSMutableArray<NSNumber *> *> *transitionScores = [NSMutableArray arrayWithCapacity:n];
    
    for (NSInteger i = 0; i < n; i++) {
        NSMutableArray<NSNumber *> *row = [NSMutableArray arrayWithCapacity:n];
        for (NSInteger j = 0; j < n; j++) {
            if (i == j) {
                row[j] = @0;
            } else {
                row[j] = @([self calculateTransitionScoreFrom:candidates[i] to:candidates[j]]);
            }
        }
        transitionScores[i] = row;
    }
    
    // 使用动态规划找出最优序列
    // dp[i][j][k]表示从前i个内容中选择了j个，最后一个是第k个内容的最大满意度
    NSMutableArray<NSMutableArray<NSMutableArray<NSNumber *> *> *> *dp = [NSMutableArray arrayWithCapacity:n + 1];
    
    for (NSInteger i = 0; i <= n; i++) {
        NSMutableArray<NSMutableArray<NSNumber *> *> *dim2 = [NSMutableArray arrayWithCapacity:self.maxRecommendations + 1];
        for (NSInteger j = 0; j <= self.maxRecommendations; j++) {
            NSMutableArray<NSNumber *> *dim3 = [NSMutableArray arrayWithCapacity:n + 1];
            for (NSInteger k = 0; k <= n; k++) {
                dim3[k] = @(NSIntegerMin);
            }
            dim2[j] = dim3;
        }
        dp[i] = dim2;
    }
    
    // 基础情况
    for (NSInteger k = 0; k < n; k++) {
        dp[1][1][k] = @([self calculateScoreForItem:candidates[k]]);
    }
    
    // 动态规划过程
    for (NSInteger i = 2; i <= n; i++) {
        for (NSInteger j = 1; j <= MIN(i, self.maxRecommendations); j++) {
            for (NSInteger k = 0; k < n; k++) {
                // 当前内容是candidates[k]
                for (NSInteger prev = 0; prev < n; prev++) {
                    if (prev != k && [dp[i - 1][j - 1][prev] integerValue] != NSIntegerMin) {
                        NSInteger score = [dp[i - 1][j - 1][prev] integerValue] + 
                                         [self calculateScoreForItem:candidates[k]] + 
                                         [transitionScores[prev][k] integerValue];
                        dp[i][j][k] = @(MAX([dp[i][j][k] integerValue], score));
                    }
                }
            }
        }
    }
    
    // 找出最优的序列长度和最后一个内容
    NSInteger bestJ = 0;
    NSInteger bestK = 0;
    NSInteger bestScore = NSIntegerMin;
    
    for (NSInteger j = 1; j <= self.maxRecommendations; j++) {
        for (NSInteger k = 0; k < n; k++) {
            if ([dp[n][j][k] integerValue] > bestScore) {
                bestScore = [dp[n][j][k] integerValue];
                bestJ = j;
                bestK = k;
            }
        }
    }
    
    // 重建最优序列
    NSMutableArray<ContentItem *> *sequence = [NSMutableArray arrayWithCapacity:bestJ];
    NSInteger currentJ = bestJ;
    NSInteger currentK = bestK;
    NSInteger currentI = n;
    
    while (currentJ > 0) {
        [sequence insertObject:candidates[currentK] atIndex:0];
        
        // 找到前一个内容
        NSInteger prevK = -1;
        for (NSInteger k = 0; k < n; k++) {
            if (k != currentK && [dp[currentI - 1][currentJ - 1][k] integerValue] != NSIntegerMin) {
                NSInteger score = [dp[currentI - 1][currentJ - 1][k] integerValue] + 
                                 [self calculateScoreForItem:candidates[currentK]] + 
                                 [transitionScores[k][currentK] integerValue];
                
                if (score == [dp[currentI][currentJ][currentK] integerValue]) {
                    prevK = k;
                    break;
                }
            }
        }
        
        if (prevK == -1) {
            break;
        }
        
        currentI--;
        currentJ--;
        currentK = prevK;
    }
    
    // 将序列分成多个子序列，每个子序列代表一个推荐组
    NSInteger groupSize = 3; // 每组推荐的内容数量
    NSMutableArray<NSArray<ContentItem *> *> *groups = [NSMutableArray array];
    
    for (NSInteger i = 0; i < sequence.count; i += groupSize) {
        NSInteger endIndex = MIN(i + groupSize, sequence.count);
        NSArray<ContentItem *> *group = [sequence subarrayWithRange:NSMakeRange(i, endIndex - i)];
        [groups addObject:group];
    }
    
    return groups;
}

- (NSInteger)calculateScoreForItem:(ContentItem *)item {
    // 计算内容项的用户满意度得分
    NSInteger score = 0;
    
    // 基础分数：内容流行度
    score += item.popularity;
    
    // 类别偏好
    NSNumber *categoryPreference = self.userProfile.categoryPreferences[item.category];
    if (categoryPreference) {
        score += [categoryPreference integerValue] * 2;
    }
    
    // 标签偏好
    for (NSString *tag in item.tags) {
        NSNumber *tagPreference = self.userProfile.tagPreferences[tag];
        if (tagPreference) {
            score += [tagPreference integerValue];
        }
    }
    
    // 时长偏好：如果接近用户平均观看时长，加分
    NSTimeInterval durationDiff = ABS(item.duration - self.userProfile.averageViewDuration);
    NSTimeInterval durationTolerance = self.userProfile.averageViewDuration * 0.3;
    if (durationDiff < durationTolerance) {
        score += 50;
    }
    
    // 历史记录：如果用户已经看过，减分
    if ([self.userProfile.viewHistory containsObject:item.identifier]) {
        score -= 200;
    }
    
    return score;
}

- (NSInteger)calculateTransitionScoreFrom:(ContentItem *)fromItem to:(ContentItem *)toItem {
    // 计算从一个内容到另一个内容的转换满意度
    NSInteger score = 0;
    
    // 相同类别，适度加分
    if ([fromItem.category isEqualToString:toItem.category]) {
        score += 20;
    } else {
        // 不同类别，适度减分，鼓励多样性
        score -= 10;
    }
    
    // 标签重叠，加分
    NSMutableSet<NSString *> *fromTags = [NSMutableSet setWithArray:fromItem.tags];
    NSMutableSet<NSString *> *toTags = [NSMutableSet setWithArray:toItem.tags];
    NSMutableSet<NSString *> *commonTags = [fromTags mutableCopy];
    [commonTags intersectSet:toTags];
    
    score += commonTags.count * 15;
    
    // 时长变化：如果下一个内容比当前内容短，加分（用户可能更愿意在看完长内容后看短内容）
    if (toItem.duration < fromItem.duration) {
        score += 25;
    }
    
    return score;
}

@end

用户行为预测模型：
在用户分析系统中，可以使用动态规划算法优化行为预测：

@interface UserAction : NSObject
@property (nonatomic, strong) NSString *actionType;
@property (nonatomic, strong) NSString *targetId;
@property (nonatomic, strong) NSDictionary<NSString *, id> *parameters;
@property (nonatomic, assign) NSTimeInterval timestamp;
@end

@interface UserBehaviorPredictor : NSObject

@property (nonatomic, strong) NSArray<UserAction *> *userHistory;
@property (nonatomic, strong) NSMutableDictionary<NSString *, NSMutableArray<UserAction *> *> *userPatterns;

- (instancetype)initWithUserHistory:(NSArray<UserAction *> *)history;
- (void)analyzePatterns;
- (NSArray<NSString *> *)predictNextActions;
- (NSArray<NSString *> *)identifyAnomalousActions;
- (NSTimeInterval)predictTimeToNextAction;

@end

@implementation UserBehaviorPredictor

- (instancetype)initWithUserHistory:(NSArray<UserAction *> *)history {
    self = [super init];
    if (self) {
        _userHistory = [history sortedArrayUsingComparator:^NSComparisonResult(UserAction *a1, UserAction *a2) {
            return a1.timestamp > a2.timestamp ? NSOrderedDescending : NSOrderedAscending;
        }];
        _userPatterns = [NSMutableDictionary dictionary];
    }
    return self;
}

- (void)analyzePatterns {
    // 使用类似于"最长递增子序列"的动态规划思想分析用户行为模式
    
    // 提取用户行为序列
    NSMutableArray<NSString *> *actionSequence = [NSMutableArray arrayWithCapacity:self.userHistory.count];
    for (UserAction *action in self.userHistory) {
        [actionSequence addObject:action.actionType];
    }
    
    // 找出常见的行为模式（长度为2到5的子序列）
    for (NSInteger patternLength = 2; patternLength <= 5; patternLength++) {
        [self findPatternsOfLength:patternLength inSequence:actionSequence];
    }
}

- (void)findPatternsOfLength:(NSInteger)length inSequence:(NSArray<NSString *> *)sequence {
    NSInteger n = sequence.count;
    
    // 如果序列长度小于模式长度，直接返回
    if (n < length) {
        return;
    }
    
    // 使用滑动窗口找出所有长度为length的子序列
    for (NSInteger i = 0; i <= n - length; i++) {
        NSMutableArray<NSString *> *pattern = [NSMutableArray arrayWithCapacity:length];
        for (NSInteger j = 0; j < length; j++) {
            pattern[j] = sequence[i + j];
        }
        
        // 将模式转换为字符串
        NSString *patternKey = [pattern componentsJoinedByString:@","];
        
        // 记录对应的用户行为
        if (!self.userPatterns[patternKey]) {
            self.userPatterns[patternKey] = [NSMutableArray array];
        }
        
        // 添加对应的用户行为
        NSMutableArray<UserAction *> *actions = [NSMutableArray arrayWithCapacity:length];
        for (NSInteger j = 0; j < length; j++) {
            [actions addObject:self.userHistory[i + j]];
        }
        
        [self.userPatterns[patternKey] addObject:actions.lastObject];
    }
}

- (NSArray<NSString *> *)predictNextActions {
    // 使用类似于"正则表达式匹配"的动态规划思想预测下一个行为
    
    // 如果用户历史为空，无法预测
    if (self.userHistory.count == 0) {
        return @[];
    }
    
    // 获取最近的行为序列（最多5个）
    NSInteger recentCount = MIN(5, self.userHistory.count);
    NSMutableArray<NSString *> *recentActions = [NSMutableArray arrayWithCapacity:recentCount];
    
    for (NSInteger i = 0; i < recentCount; i++) {
        [recentActions addObject:self.userHistory[i].actionType];
    }
    
    // 反转数组，使其按时间顺序排列
    NSArray<NSString *> *recentSequence = [[recentActions reverseObjectEnumerator] allObjects];
    
    // 查找匹配的模式
    NSMutableDictionary<NSString *, NSInteger> *nextActionCounts = [NSMutableDictionary dictionary];
    
    for (NSString *patternKey in self.userPatterns) {
        NSArray<NSString *> *pattern = [patternKey componentsSeparatedByString:@","];
        
        // 检查模式是否匹配最近的行为序列
        BOOL isMatch = [self isPattern:pattern matchingEndOfSequence:recentSequence];
        
        if (isMatch) {
            // 统计模式之后的下一个行为
            for (UserAction *action in self.userPatterns[patternKey]) {
                NSInteger index = [self.userHistory indexOfObject:action];
                if (index < self.userHistory.count - 1) {
                    NSString *nextAction = self.userHistory[index + 1].actionType;
                    nextActionCounts[nextAction] = @([nextActionCounts[nextAction] integerValue] + 1);
                }
            }
        }
    }
    
    // 按出现频率排序
    NSArray<NSString *> *sortedNextActions = [nextActionCounts keysSortedByValueUsingComparator:^NSComparisonResult(NSNumber *obj1, NSNumber *obj2) {
        return [obj2 compare:obj1];
    }];
    
    return sortedNextActions;
}

- (BOOL)isPattern:(NSArray<NSString *> *)pattern matchingEndOfSequence:(NSArray<NSString *> *)sequence {
    NSInteger patternLength = pattern.count;
    NSInteger sequenceLength = sequence.count;
    
    if (patternLength > sequenceLength) {
        return NO;
    }
    
    // 检查模式是否匹配序列的末尾
    for (NSInteger i = 0; i < patternLength; i++) {
        if (![pattern[i] isEqualToString:sequence[sequenceLength - patternLength + i]]) {
            return NO;
        }
    }
    
    return YES;
}

- (NSArray<NSString *> *)identifyAnomalousActions {
    // 使用类似于"不同的子序列"的动态规划思想识别异常行为
    
    // 如果用户历史为空，无法识别异常
    if (self.userHistory.count == 0) {
        return @[];
    }
    
    // 计算每种行为类型的频率
    NSMutableDictionary<NSString *, NSNumber *> *actionFrequency = [NSMutableDictionary dictionary];
    for (UserAction *action in self.userHistory) {
        actionFrequency[action.actionType] = @([actionFrequency[action.actionType] integerValue] + 1);
    }
    
    // 计算行为之间的转换频率
    NSMutableDictionary<NSString *, NSMutableDictionary<NSString *, NSNumber *> *> *transitionFrequency = [NSMutableDictionary dictionary];
    
    for (NSInteger i = 0; i < self.userHistory.count - 1; i++) {
        NSString *currentAction = self.userHistory[i].actionType;
        NSString *nextAction = self.userHistory[i + 1].actionType;
        
        if (!transitionFrequency[currentAction]) {
            transitionFrequency[currentAction] = [NSMutableDictionary dictionary];
        }
        
        transitionFrequency[currentAction][nextAction] = @([transitionFrequency[currentAction][nextAction] integerValue] + 1);
    }
    
    // 识别异常行为
    NSMutableArray<NSString *> *anomalousActions = [NSMutableArray array];
    
    for (NSInteger i = 0; i < self.userHistory.count; i++) {
        UserAction *action = self.userHistory[i];
        
        // 检查行为频率
        NSInteger frequency = [actionFrequency[action.actionType] integerValue];
        NSInteger totalActions = self.userHistory.count;
        CGFloat frequencyRatio = (CGFloat)frequency / totalActions;
        
        // 如果行为频率过低，可能是异常
        if (frequencyRatio < 0.01 && frequency <= 2) {
            [anomalousActions addObject:[NSString stringWithFormat:@"%@:%@", action.actionType, action.targetId]];
            continue;
        }
        
        // 检查行为转换
        if (i > 0 && i < self.userHistory.count - 1) {
            NSString *prevAction = self.userHistory[i - 1].actionType;
            NSString *currentAction = action.actionType;
            NSString *nextAction = self.userHistory[i + 1].actionType;
            
            // 检查前后转换是否常见
            NSInteger prevToCurrentFreq = [transitionFrequency[prevAction][currentAction] integerValue];
            NSInteger currentToNextFreq = [transitionFrequency[currentAction][nextAction] integerValue];
            
            NSInteger totalPrevTransitions = 0;
            for (NSNumber *freq in [transitionFrequency[prevAction] allValues]) {
                totalPrevTransitions += [freq integerValue];
            }
            
            NSInteger totalCurrentTransitions = 0;
            for (NSNumber *freq in [transitionFrequency[currentAction] allValues]) {
                totalCurrentTransitions += [freq integerValue];
            }
            
            CGFloat prevToCurrentRatio = totalPrevTransitions > 0 ? (CGFloat)prevToCurrentFreq / totalPrevTransitions : 0;
            CGFloat currentToNextRatio = totalCurrentTransitions > 0 ? (CGFloat)currentToNextFreq / totalCurrentTransitions : 0;
            
            // 如果转换频率过低，可能是异常
            if ((prevToCurrentRatio < 0.05 && prevToCurrentFreq <= 1) || 
                (currentToNextRatio < 0.05 && currentToNextFreq <= 1)) {
                [anomalousActions addObject:[NSString stringWithFormat:@"%@:%@", action.actionType, action.targetId]];
            }
        }
    }
    
    return anomalousActions;
}

- (NSTimeInterval)predictTimeToNextAction {
    // 使用类似于"编辑距离"的动态规划思想预测下一个行为的时间
    
    // 如果用户历史为空，无法预测
    if (self.userHistory.count < 2) {
        return -1;
    }
    
    // 计算用户行为之间的时间间隔
    NSMutableArray<NSNumber *> *intervals = [NSMutableArray arrayWithCapacity:self.userHistory.count - 1];
    
    for (NSInteger i = 0; i < self.userHistory.count - 1; i++) {
        NSTimeInterval interval = self.userHistory[i].timestamp - self.userHistory[i + 1].timestamp;
        [intervals addObject:@(interval)];
    }
    
    // 获取最近的行为序列（最多5个）
    NSInteger recentCount = MIN(5, self.userHistory.count);
    NSMutableArray<NSString *> *recentActions = [NSMutableArray arrayWithCapacity:recentCount];
    
    for (NSInteger i = 0; i < recentCount; i++) {
        [recentActions addObject:self.userHistory[i].actionType];
    }
    
    // 反转数组，使其按时间顺序排列
    NSArray<NSString *> *recentSequence = [[recentActions reverseObjectEnumerator] allObjects];
    
    // 查找匹配的模式
    NSMutableArray<NSNumber *> *matchingIntervals = [NSMutableArray array];
    
    for (NSString *patternKey in self.userPatterns) {
        NSArray<NSString *> *pattern = [patternKey componentsSeparatedByString:@","];
        
        // 检查模式是否匹配最近的行为序列
        BOOL isMatch = [self isPattern:pattern matchingEndOfSequence:recentSequence];
        
        if (isMatch) {
            // 收集模式之后的时间间隔
            for (UserAction *action in self.userPatterns[patternKey]) {
                NSInteger index = [self.userHistory indexOfObject:action];
                if (index > 0) {
                    NSTimeInterval interval = self.userHistory[index - 1].timestamp - self.userHistory[index].timestamp;
                    [matchingIntervals addObject:@(interval)];
                }
            }
        }
    }
    
    // 如果没有匹配的模式，使用整体平均值
    if (matchingIntervals.count == 0) {
        NSTimeInterval sum = 0;
        for (NSNumber *interval in intervals) {
            sum += [interval doubleValue];
        }
        return sum / intervals.count;
    }
    
    // 计算匹配模式的平均时间间隔
    NSTimeInterval sum = 0;
    for (NSNumber *interval in matchingIntervals) {
        sum += [interval doubleValue];
    }
    
    return sum / matchingIntervals.count;
}

@end

这些实际应用展示了如何将LeetCode上的高级动态规划算法应用到iOS开发的实际场景中，提高推荐算法和预测模型的效率和准确性。

从iOS到LeetCode：资深开发者的算法实战指南

第四章：图算法与搜索

4.1 图的表示与基础算法

4.1.1 [LeetCode 207] 课程表（Medium）

问题描述：
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses-1。在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则必须先学习课程 bi。例如，先修课程对 [0, 1] 表示：想要学习课程 0，你需要先完成课程 1。请你判断是否可能完成所有课程的学习？如果可以，返回 true；否则，返回 false。

Objective-C 实现：

@interface Solution : NSObject
- (BOOL)canFinish:(NSInteger)numCourses prerequisites:(NSArray<NSArray<NSNumber *> *> *)prerequisites;
@end

@implementation Solution
- (BOOL)canFinish:(NSInteger)numCourses prerequisites:(NSArray<NSArray<NSNumber *> *> *)prerequisites {
    // 构建邻接表表示图
    NSMutableArray<NSMutableArray<NSNumber *> *> *graph = [NSMutableArray arrayWithCapacity:numCourses];
    for (NSInteger i = 0; i < numCourses; i++) {
        graph[i] = [NSMutableArray array];
    }
    
    // 记录每个节点的入度
    NSMutableArray<NSNumber *> *inDegree = [NSMutableArray arrayWithCapacity:numCourses];
    for (NSInteger i = 0; i < numCourses; i++) {
        inDegree[i] = @0;
    }
    
    // 构建图和计算入度
    for (NSArray<NSNumber *> *prerequisite in prerequisites) {
        NSInteger course = [prerequisite[0] integerValue];
        NSInteger prereq = [prerequisite[1] integerValue];
        
        // 添加边：prereq -> course
        [graph[prereq] addObject:@(course)];
        
        // 增加course的入度
        inDegree[course] = @([inDegree[course] integerValue] + 1);
    }
    
    // 使用队列进行拓扑排序
    NSMutableArray<NSNumber *> *queue = [NSMutableArray array];
    
    // 将所有入度为0的节点加入队列
    for (NSInteger i = 0; i < numCourses; i++) {
        if ([inDegree[i] integerValue] == 0) {
            [queue addObject:@(i)];
        }
    }
    
    NSInteger count = 0; // 记录已访问的节点数
    
    while (queue.count > 0) {
        NSNumber *current = queue[0];
        [queue removeObjectAtIndex:0];
        count++;
        
        // 遍历当前节点的所有邻居
        for (NSNumber *neighbor in graph[[current integerValue]]) {
            // 减少邻居的入度
            NSInteger newInDegree = [inDegree[[neighbor integerValue]] integerValue] - 1;
            inDegree[[neighbor integerValue]] = @(newInDegree);
            
            // 如果入度变为0，加入队列
            if (newInDegree == 0) {
                [queue addObject:neighbor];
            }
        }
    }
    
    // 如果所有节点都被访问，则没有环
    return count == numCourses;
}
@end

算法分析：

时间复杂度：O(V + E)，其中V是课程数量，E是先修课程对的数量
空间复杂度：O(V + E)，需要存储图的邻接表和入度数组

实际工程应用：
课程表算法在iOS开发中的实际应用：

任务依赖管理：在项目管理应用中，可用于检测任务之间的依赖关系是否存在循环依赖，确保任务可以按顺序完成。
构建系统优化：在iOS应用的构建系统中，可用于分析模块间依赖关系，优化编译顺序，提高构建效率。
资源加载顺序：在游戏或复杂应用中，可用于确定资源的最优加载顺序，避免死锁。
工作流程验证：在工作流程管理应用中，可用于验证用户定义的工作流程是否存在循环，确保流程可以正常执行。

4.1.2 [LeetCode 210] 课程表 II（Medium）

问题描述：
现在你总共有 numCourses 门课需要选，记为 0 到 numCourses-1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前必须先选修 bi。请你返回一个合法的选课顺序数组。如果不可能完成所有课程，返回一个空数组。

Objective-C 实现：

@interface Solution : NSObject
- (NSArray<NSNumber *> *)findOrder:(NSInteger)numCourses prerequisites:(NSArray<NSArray<NSNumber *> *> *)prerequisites;
@end

@implementation Solution
- (NSArray<NSNumber *> *)findOrder:(NSInteger)numCourses prerequisites:(NSArray<NSArray<NSNumber *> *> *)prerequisites {
    // 构建邻接表表示图
    NSMutableArray<NSMutableArray<NSNumber *> *> *graph = [NSMutableArray arrayWithCapacity:numCourses];
    for (NSInteger i = 0; i < numCourses; i++) {
        graph[i] = [NSMutableArray array];
    }
    
    // 记录每个节点的入度
    NSMutableArray<NSNumber *> *inDegree = [NSMutableArray arrayWithCapacity:numCourses];
    for (NSInteger i = 0; i < numCourses; i++) {
        inDegree[i] = @0;
    }
    
    // 构建图和计算入度
    for (NSArray<NSNumber *> *prerequisite in prerequisites) {
        NSInteger course = [prerequisite[0] integerValue];
        NSInteger prereq = [prerequisite[1] integerValue];
        
        // 添加边：prereq -> course
        [graph[prereq] addObject:@(course)];
        
        // 增加course的入度
        inDegree[course] = @([inDegree[course] integerValue] + 1);
    }
    
    // 使用队列进行拓扑排序
    NSMutableArray<NSNumber *> *queue = [NSMutableArray array];
    
    // 将所有入度为0的节点加入队列
    for (NSInteger i = 0; i < numCourses; i++) {
        if ([inDegree[i] integerValue] == 0) {
            [queue addObject:@(i)];
        }
    }
    
    NSMutableArray<NSNumber *> *result = [NSMutableArray arrayWithCapacity:numCourses];
    
    while (queue.count > 0) {
        NSNumber *current = queue[0];
        [queue removeObjectAtIndex:0];
        [result addObject:current];
        
        // 遍历当前节点的所有邻居
        for (NSNumber *neighbor in graph[[current integerValue]]) {
            // 减少邻居的入度
            NSInteger newInDegree = [inDegree[[neighbor integerValue]] integerValue] - 1;
            inDegree[[neighbor integerValue]] = @(newInDegree);
            
            // 如果入度变为0，加入队列
            if (newInDegree == 0) {
                [queue addObject:neighbor];
            }
        }
    }
    
    // 如果不能完成所有课程，返回空数组
    return result.count == numCourses ? result : @[];
}
@end

算法分析：

时间复杂度：O(V + E)，其中V是课程数量，E是先修课程对的数量
空间复杂度：O(V + E)，需要存储图的邻接表、入度数组和结果数组

实际工程应用：
课程表II算法在iOS开发中的实际应用：

构建依赖顺序：在CI/CD流程中，可用于确定模块的构建顺序，确保依赖关系正确。
数据迁移计划：在数据库迁移应用中，可用于规划表的迁移顺序，确保外键约束不被违反。
安装步骤生成：在安装向导应用中，可用于根据组件间的依赖关系生成最优的安装步骤顺序。
初始化序列优化：在应用启动过程中，可用于优化服务和组件的初始化顺序，提高启动速度。

4.1.3 [LeetCode 133] 克隆图（Medium）

问题描述：
给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（int）和其邻居的列表（list[Node]）。

Objective-C 实现：

// 图节点定义
@interface Node : NSObject
@property (nonatomic, assign) NSInteger val;
@property (nonatomic, strong) NSMutableArray<Node *> *neighbors;
- (instancetype)initWithVal:(NSInteger)val;
@end

@implementation Node
- (instancetype)initWithVal:(NSInteger)val {
    self = [super init];
    if (self) {
        _val = val;
        _neighbors = [NSMutableArray array];
    }
    return self;
}
@end

@interface Solution : NSObject
- (Node *)cloneGraph:(Node *)node;
@end

@implementation Solution
- (Node *)cloneGraph:(Node *)node {
    if (!node) {
        return nil;
    }
    
    // 使用哈希表存储已克隆的节点
    NSMutableDictionary<NSNumber *, Node *> *visited = [NSMutableDictionary dictionary];
    
    // 使用DFS克隆图
    return [self dfsClone:node visited:visited];
}

- (Node *)dfsClone:(Node *)node visited:(NSMutableDictionary<NSNumber *, Node *> *)visited {
    // 如果节点已经被访问过，直接返回克隆的节点
    if (visited[@(node.val)]) {
        return visited[@(node.val)];
    }
    
    // 创建新节点
    Node *cloneNode = [[Node alloc] initWithVal:node.val];
    
    // 将新节点加入已访问字典
    visited[@(node.val)] = cloneNode;
    
    // 递归克隆所有邻居节点
    for (Node *neighbor in node.neighbors) {
        [cloneNode.neighbors addObject:[self dfsClone:neighbor visited:visited]];
    }
    
    return cloneNode;
}
@end

算法分析：

时间复杂度：O(N + M)，其中N是节点数量，M是边的数量
空间复杂度：O(N)，需要一个哈希表来存储已克隆的节点

实际工程应用：
克隆图算法在iOS开发中的实际应用：

对象深拷贝：在需要对复杂对象图进行深拷贝的场景中，可以应用类似的递归克隆策略。
状态保存与恢复：在应用状态管理中，可用于保存和恢复复杂的状态图，如游戏状态或编辑器状态。
UI组件树复制：在UI编辑器应用中，可用于复制和粘贴复杂的UI组件树。
网络拓扑复制：在网络模拟应用中，可用于复制网络拓扑结构，进行”假设”分析。

4.1.4 实际应用：iOS应用中的依赖注入与模块化架构

上述基础图算法在iOS开发中的依赖注入与模块化架构方面有重要应用：

依赖注入容器实现：
在大型iOS应用中，可以使用图算法实现依赖注入容器：

@interface ServiceDependency : NSObject
@property (nonatomic, strong) NSString *serviceIdentifier;
@property (nonatomic, strong) NSArray<NSString *> *dependsOn;
@end

@implementation ServiceDependency
@end

@interface DependencyContainer : NSObject

@property (nonatomic, strong) NSMutableDictionary<NSString *, Class> *registeredServices;
@property (nonatomic, strong) NSMutableDictionary<NSString *, id> *instances;
@property (nonatomic, strong) NSMutableDictionary<NSString *, ServiceDependency *> *dependencies;

- (void)registerService:(Class)serviceClass withIdentifier:(NSString *)identifier;
- (void)registerService:(Class)serviceClass withIdentifier:(NSString *)identifier dependsOn:(NSArray<NSString *> *)dependencies;
- (id)resolveService:(NSString *)identifier;
- (BOOL)validateDependencies;
- (NSArray<NSString *> *)resolutionOrder;

@end

@implementation DependencyContainer

- (instancetype)init {
    self = [super init];
    if (self) {
        _registeredServices = [NSMutableDictionary dictionary];
        _instances = [NSMutableDictionary dictionary];
        _dependencies = [NSMutableDictionary dictionary];
    }
    return self;
}

- (void)registerService:(Class)serviceClass withIdentifier:(NSString *)identifier {
    [self registerService:serviceClass withIdentifier:identifier dependsOn:@[]];
}

- (void)registerService:(Class)serviceClass withIdentifier:(NSString *)identifier dependsOn:(NSArray<NSString *> *)dependencies {
    self.registeredServices[identifier] = serviceClass;
    
    ServiceDependency *dependency = [[ServiceDependency alloc] init];
    dependency.serviceIdentifier = identifier;
    dependency.dependsOn = dependencies;
    
    self.dependencies[identifier] = dependency;
}

- (id)resolveService:(NSString *)identifier {
    // 如果实例已存在，直接返回
    if (self.instances[identifier]) {
        return self.instances[identifier];
    }
    
    // 检查服务是否已注册
    Class serviceClass = self.registeredServices[identifier];
    if (!serviceClass) {
        NSLog(@"Service not registered: %@", identifier);
        return nil;
    }
    
    // 获取依赖
    ServiceDependency *dependency = self.dependencies[identifier];
    
    // 递归解析所有依赖
    NSMutableDictionary<NSString *, id> *resolvedDependencies = [NSMutableDictionary dictionary];
    for (NSString *dependencyId in dependency.dependsOn) {
        id resolvedDependency = [self resolveService:dependencyId];
        if (!resolvedDependency) {
            NSLog(@"Failed to resolve dependency: %@ for service: %@", dependencyId, identifier);
            return nil;
        }
        resolvedDependencies[dependencyId] = resolvedDependency;
    }
    
    // 创建服务实例
    id instance = nil;
    
    // 检查是否实现了依赖注入初始化方法
    if ([serviceClass respondsToSelector:@selector(initWithDependencies:)]) {
        instance = [serviceClass performSelector:@selector(initWithDependencies:) withObject:resolvedDependencies];
    } else {
        instance = [[serviceClass alloc] init];
        
        // 尝试通过属性注入依赖
        for (NSString *dependencyId in resolvedDependencies) {
            SEL setter = NSSelectorFromString([NSString stringWithFormat:@"set%@:", [dependencyId stringByReplacingCharactersInRange:NSMakeRange(0, 1) withString:[[dependencyId substringToIndex:1] uppercaseString]]]);
            
            if ([instance respondsToSelector:setter]) {
                [instance performSelector:setter withObject:resolvedDependencies[dependencyId]];
            }
        }
    }
    
    // 缓存实例
    self.instances[identifier] = instance;
    
    return instance;
}

- (BOOL)validateDependencies {
    // 构建依赖图
    NSMutableDictionary<NSString *, NSMutableArray<NSString *> *> *graph = [NSMutableDictionary dictionary];
    NSMutableDictionary<NSString *, NSNumber *> *inDegree = [NSMutableDictionary dictionary];
    
    // 初始化图和入度
    for (NSString *serviceId in self.dependencies) {
        graph[serviceId] = [NSMutableArray array];
        inDegree[serviceId] = @0;
    }
    
    // 构建图和计算入度
    for (NSString *serviceId in self.dependencies) {
        ServiceDependency *dependency = self.dependencies[serviceId];
        
        for (NSString *dependencyId in dependency.dependsOn) {
            // 检查依赖是否已注册
            if (!self.registeredServices[dependencyId]) {
                NSLog(@"Unregistered dependency: %@ for service: %@", dependencyId, serviceId);
                return NO;
            }
            
            // 添加边：dependencyId -> serviceId
            [graph[dependencyId] addObject:serviceId];
            
            // 增加serviceId的入度
            inDegree[serviceId] = @([inDegree[serviceId] integerValue] + 1);
        }
    }
    
    // 使用拓扑排序检测循环依赖
    NSMutableArray<NSString *> *queue = [NSMutableArray array];
    
    // 将所有入度为0的节点加入队列
    for (NSString *serviceId in inDegree) {
        if ([inDegree[serviceId] integerValue] == 0) {
            [queue addObject:serviceId];
        }
    }
    
    NSInteger count = 0;
    
    while (queue.count > 0) {
        NSString *current = queue[0];
        [queue removeObjectAtIndex:0];
        count++;
        
        // 遍历当前节点的所有邻居
        for (NSString *neighbor in graph[current]) {
            // 减少邻居的入度
            NSInteger newInDegree = [inDegree[neighbor] integerValue] - 1;
            inDegree[neighbor] = @(newInDegree);
            
            // 如果入度变为0，加入队列
            if (newInDegree == 0) {
                [queue addObject:neighbor];
            }
        }
    }
    
    // 如果访问的节点数小于总节点数，则存在循环依赖
    if (count < self.dependencies.count) {
        NSLog(@"Circular dependency detected");
        return NO;
    }
    
    return YES;
}

- (NSArray<NSString *> *)resolutionOrder {
    // 构建依赖图
    NSMutableDictionary<NSString *, NSMutableArray<NSString *> *> *graph = [NSMutableDictionary dictionary];
    NSMutableDictionary<NSString *, NSNumber *> *inDegree = [NSMutableDictionary dictionary];
    
    // 初始化图和入度
    for (NSString *serviceId in self.dependencies) {
        graph[serviceId] = [NSMutableArray array];
        inDegree[serviceId] = @0;
    }
    
    // 构建图和计算入度
    for (NSString *serviceId in self.dependencies) {
        ServiceDependency *dependency = self.dependencies[serviceId];
        
        for (NSString *dependencyId in dependency.dependsOn) {
            // 添加边：dependencyId -> serviceId
            [graph[dependencyId] addObject:serviceId];
            
            // 增加serviceId的入度
            inDegree[serviceId] = @([inDegree[serviceId] integerValue] + 1);
        }
    }
    
    // 使用拓扑排序获取解析顺序
    NSMutableArray<NSString *> *queue = [NSMutableArray array];
    
    // 将所有入度为0的节点加入队列
    for (NSString *serviceId in inDegree) {
        if ([inDegree[serviceId] integerValue] == 0) {
            [queue addObject:serviceId];
        }
    }
    
    NSMutableArray<NSString *> *result = [NSMutableArray array];
    
    while (queue.count > 0) {
        NSString *current = queue[0];
        [queue removeObjectAtIndex:0];
        [result addObject:current];
        
        // 遍历当前节点的所有邻居
        for (NSString *neighbor in graph[current]) {
            // 减少邻居的入度
            NSInteger newInDegree = [inDegree[neighbor] integerValue] - 1;
            inDegree[neighbor] = @(newInDegree);
            
            // 如果入度变为0，加入队列
            if (newInDegree == 0) {
                [queue addObject:neighbor];
            }
        }
    }
    
    // 如果结果数组长度小于总节点数，则存在循环依赖
    if (result.count < self.dependencies.count) {
        return @[];
    }
    
    return result;
}

@end

模块化架构实现：
在大型iOS应用中，可以使用图算法实现模块化架构：

@interface ModuleDescriptor : NSObject
@property (nonatomic, strong) NSString *moduleId;
@property (nonatomic, strong) NSArray<NSString *> *dependencies;
@property (nonatomic, strong) Class moduleClass;
@end

@implementation ModuleDescriptor
@end

@protocol Module <NSObject>
- (void)initialize;
- (void)start;
- (void)stop;
@end

@interface ModuleManager : NSObject

@property (nonatomic, strong) NSMutableDictionary<NSString *, ModuleDescriptor *> *modules;
@property (nonatomic, strong) NSMutableDictionary<NSString *, id<Module>> *runningModules;

- (void)registerModule:(Class)moduleClass withId:(NSString *)moduleId dependencies:(NSArray<NSString *> *)dependencies;
- (BOOL)validateModuleDependencies;
- (NSArray<NSString *> *)moduleStartupOrder;
- (BOOL)startAllModules;
- (BOOL)stopAllModules;
- (BOOL)startModule:(NSString *)moduleId;
- (BOOL)stopModule:(NSString *)moduleId;

@end

@implementation ModuleManager

- (instancetype)init {
    self = [super init];
    if (self) {
        _modules = [NSMutableDictionary dictionary];
        _runningModules = [NSMutableDictionary dictionary];
    }
    return self;
}

- (void)registerModule:(Class)moduleClass withId:(NSString *)moduleId dependencies:(NSArray<NSString *> *)dependencies {
    ModuleDescriptor *descriptor = [[ModuleDescriptor alloc] init];
    descriptor.moduleId = moduleId;
    descriptor.dependencies = dependencies;
    descriptor.moduleClass = moduleClass;
    
    self.modules[moduleId] = descriptor;
}

- (BOOL)validateModuleDependencies {
    // 构建依赖图
    NSMutableDictionary<NSString *, NSMutableArray<NSString *> *> *graph = [NSMutableDictionary dictionary];
    NSMutableDictionary<NSString *, NSNumber *> *inDegree = [NSMutableDictionary dictionary];
    
    // 初始化图和入度
    for (NSString *moduleId in self.modules) {
        graph[moduleId] = [NSMutableArray array];
        inDegree[moduleId] = @0;
    }
    
    // 构建图和计算入度
    for (NSString *moduleId in self.modules) {
        ModuleDescriptor *descriptor = self.modules[moduleId];
        
        for (NSString *dependencyId in descriptor.dependencies) {
            // 检查依赖是否已注册
            if (!self.modules[dependencyId]) {
                NSLog(@"Unregistered module dependency: %@ for module: %@", dependencyId, moduleId);
                return NO;
            }
            
            // 添加边：dependencyId -> moduleId
            [graph[dependencyId] addObject:moduleId];
            
            // 增加moduleId的入度
            inDegree[moduleId] = @([inDegree[moduleId] integerValue] + 1);
        }
    }
    
    // 使用拓扑排序检测循环依赖
    NSMutableArray<NSString *> *queue = [NSMutableArray array];
    
    // 将所有入度为0的节点加入队列
    for (NSString *moduleId in inDegree) {
        if ([inDegree[moduleId] integerValue] == 0) {
            [queue addObject:moduleId];
        }
    }
    
    NSInteger count = 0;
    
    while (queue.count > 0) {
        NSString *current = queue[0];
        [queue removeObjectAtIndex:0];
        count++;
        
        // 遍历当前节点的所有邻居
        for (NSString *neighbor in graph[current]) {
            // 减少邻居的入度
            NSInteger newInDegree = [inDegree[neighbor] integerValue] - 1;
            inDegree[neighbor] = @(newInDegree);
            
            // 如果入度变为0，加入队列
            if (newInDegree == 0) {
                [queue addObject:neighbor];
            }
        }
    }
    
    // 如果访问的节点数小于总节点数，则存在循环依赖
    if (count < self.modules.count) {
        NSLog(@"Circular module dependency detected");
        return NO;
    }
    
    return YES;
}

- (NSArray<NSString *> *)moduleStartupOrder {
    // 构建依赖图
    NSMutableDictionary<NSString *, NSMutableArray<NSString *> *> *graph = [NSMutableDictionary dictionary];
    NSMutableDictionary<NSString *, NSNumber *> *inDegree = [NSMutableDictionary dictionary];
    
    // 初始化图和入度
    for (NSString *moduleId in self.modules) {
        graph[moduleId] = [NSMutableArray array];
        inDegree[moduleId] = @0;
    }
    
    // 构建图和计算入度
    for (NSString *moduleId in self.modules) {
        ModuleDescriptor *descriptor = self.modules[moduleId];
        
        for (NSString *dependencyId in descriptor.dependencies) {
            // 添加边：dependencyId -> moduleId
            [graph[dependencyId] addObject:moduleId];
            
            // 增加moduleId的入度
            inDegree[moduleId] = @([inDegree[moduleId] integerValue] + 1);
        }
    }
    
    // 使用拓扑排序获取启动顺序
    NSMutableArray<NSString *> *queue = [NSMutableArray array];
    
    // 将所有入度为0的节点加入队列
    for (NSString *moduleId in inDegree) {
        if ([inDegree[moduleId] integerValue] == 0) {
            [queue addObject:moduleId];
        }
    }
    
    NSMutableArray<NSString *> *result = [NSMutableArray array];
    
    while (queue.count > 0) {
        NSString *current = queue[0];
        [queue removeObjectAtIndex:0];
        [result addObject:current];
        
        // 遍历当前节点的所有邻居
        for (NSString *neighbor in graph[current]) {
            // 减少邻居的入度
            NSInteger newInDegree = [inDegree[neighbor] integerValue] - 1;
            inDegree[neighbor] = @(newInDegree);
            
            // 如果入度变为0，加入队列
            if (newInDegree == 0) {
                [queue addObject:neighbor];
            }
        }
    }
    
    // 如果结果数组长度小于总节点数，则存在循环依赖
    if (result.count < self.modules.count) {
        return @[];
    }
    
    return result;
}

- (BOOL)startAllModules {
    // 验证模块依赖
    if (![self validateModuleDependencies]) {
        return NO;
    }
    
    // 获取模块启动顺序
    NSArray<NSString *> *startupOrder = [self moduleStartupOrder];
    if (startupOrder.count == 0) {
        return NO;
    }
    
    // 按顺序启动模块
    for (NSString *moduleId in startupOrder) {
        if (![self startModule:moduleId]) {
            return NO;
        }
    }
    
    return YES;
}

- (BOOL)stopAllModules {
    // 获取模块启动顺序（反向即为停止顺序）
    NSArray<NSString *> *startupOrder = [self moduleStartupOrder];
    if (startupOrder.count == 0) {
        return NO;
    }
    
    // 按反向顺序停止模块
    for (NSString *moduleId in [startupOrder reverseObjectEnumerator]) {
        if (![self stopModule:moduleId]) {
            return NO;
        }
    }
    
    return YES;
}

- (BOOL)startModule:(NSString *)moduleId {
    // 如果模块已经运行，直接返回成功
    if (self.runningModules[moduleId]) {
        return YES;
    }
    
    // 获取模块描述符
    ModuleDescriptor *descriptor = self.modules[moduleId];
    if (!descriptor) {
        NSLog(@"Module not registered: %@", moduleId);
        return NO;
    }
    
    // 确保所有依赖模块都已启动
    for (NSString *dependencyId in descriptor.dependencies) {
        if (!self.runningModules[dependencyId]) {
            if (![self startModule:dependencyId]) {
                return NO;
            }
        }
    }
    
    // 创建模块实例
    id<Module> module = [[descriptor.moduleClass alloc] init];
    
    // 初始化模块
    [module initialize];
    
    // 启动模块
    [module start];
    
    // 将模块添加到运行中的模块字典
    self.runningModules[moduleId] = module;
    
    return YES;
}

- (BOOL)stopModule:(NSString *)moduleId {
    // 如果模块未运行，直接返回成功
    if (!self.runningModules[moduleId]) {
        return YES;
    }
    
    // 获取模块描述符
    ModuleDescriptor *descriptor = self.modules[moduleId];
    if (!descriptor) {
        NSLog(@"Module not registered: %@", moduleId);
        return NO;
    }
    
    // 确保所有依赖于此模块的模块都已停止
    for (NSString *otherModuleId in self.modules) {
        ModuleDescriptor *otherDescriptor = self.modules[otherModuleId];
        if ([otherDescriptor.dependencies containsObject:moduleId] && self.runningModules[otherModuleId]) {
            if (![self stopModule:otherModuleId]) {
                return NO;
            }
        }
    }
    
    // 获取模块实例
    id<Module> module = self.runningModules[moduleId];
    
    // 停止模块
    [module stop];
    
    // 从运行中的模块字典中移除
    [self.runningModules removeObjectForKey:moduleId];
    
    return YES;
}

@end

这些实际应用展示了如何将LeetCode上的基础图算法应用到iOS开发的实际场景中，提高依赖注入和模块化架构的效率和可靠性。

4.2 高级图算法与搜索

4.2.1 [LeetCode 200] 岛屿数量（Medium）

问题描述：
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

Objective-C 实现：

@interface Solution : NSObject
- (NSInteger)numIslands:(NSArray<NSArray<NSString *> *> *)grid;
@end

@implementation Solution
- (NSInteger)numIslands:(NSArray<NSArray<NSString *> *> *)grid {
    if (grid.count == 0 || grid[0].count == 0) {
        return 0;
    }
    
    NSInteger rows = grid.count;
    NSInteger cols = grid[0].count;
    NSInteger count = 0;
    
    // 创建访问标记数组
    NSMutableArray<NSMutableArray<NSNumber *> *> *visited = [NSMutableArray arrayWithCapacity:rows];
    for (NSInteger i = 0; i < rows; i++) {
        NSMutableArray<NSNumber *> *row = [NSMutableArray arrayWithCapacity:cols];
        for (NSInteger j = 0; j < cols; j++) {
            row[j] = @NO;
        }
        visited[i] = row;
    }
    
    // 遍历网格
    for (NSInteger i = 0; i < rows; i++) {
        for (NSInteger j = 0; j < cols; j++) {
            // 如果是陆地且未访问过，进行DFS并增加岛屿计数
            if ([grid[i][j] isEqualToString:@"1"] && ![visited[i][j] boolValue]) {
                count++;
                [self dfs:grid visited:visited row:i col:j rows:rows cols:cols];
            }
        }
    }
    
    return count;
}

- (void)dfs:(NSArray<NSArray<NSString *> *> *)grid 
    visited:(NSMutableArray<NSMutableArray<NSNumber *> *> *)visited 
        row:(NSInteger)row 
        col:(NSInteger)col 
       rows:(NSInteger)rows 
       cols:(NSInteger)cols {
    
    // 边界检查
    if (row < 0 || row >= rows || col < 0 || col >= cols) {
        return;
    }
    
    // 如果不是陆地或已访问过，直接返回
    if (![grid[row][col] isEqualToString:@"1"] || [visited[row][col] boolValue]) {
        return;
    }
    
    // 标记为已访问
    visited[row][col] = @YES;
    
    // 访问上下左右四个方向
    [self dfs:grid visited:visited row:row - 1 col:col rows:rows cols:cols]; // 上
    [self dfs:grid visited:visited row:row + 1 col:col rows:rows cols:cols]; // 下
    [self dfs:grid visited:visited row:row col:col - 1 rows:rows cols:cols]; // 左
    [self dfs:grid visited:visited row:row col:col + 1 rows:rows cols:cols]; // 右
}
@end

算法分析：

时间复杂度：O(M*N)，其中M和N分别是网格的行数和列数
空间复杂度：O(MN)，最坏情况下，递归深度为MN

实际工程应用：
岛屿数量算法在iOS开发中的实际应用：

图像处理：在图像处理应用中，可用于识别和计算图像中的连通区域数量，如识别文档中的段落或图表。
网络拓扑分析：在网络监控应用中，可用于检测网络中的隔离子网数量，帮助诊断网络连接问题。
游戏地图生成：在游戏开发中，可用于生成和分析随机地图，确保地图的连通性和平衡性。
触摸区域识别：在交互式应用中，可用于识别用户触摸的连续区域，实现更智能的触摸响应。

4.2.2 [LeetCode 127] 单词接龙（Hard）

问题描述：
字典 wordList 中从单词 beginWord 和 endWord 的转换序列是一个按下述规格形成的序列：序列中第一个单词是 beginWord，最后一个单词是 endWord。每次转换只能改变一个字母。转换过程中的中间单词必须是字典 wordList 中的单词。给你两个单词 beginWord 和 endWord，以及一个字典 wordList。请你找出并返回从 beginWord 到 endWord 的最短转换序列的长度。如果不存在这样的转换序列，返回 0。

Objective-C 实现：

@interface Solution : NSObject
- (NSInteger)ladderLength:(NSString *)beginWord to:(NSString *)endWord wordList:(NSArray<NSString *> *)wordList;
@end

@implementation Solution
- (NSInteger)ladderLength:(NSString *)beginWord to:(NSString *)endWord wordList:(NSArray<NSString *> *)wordList {
    // 如果endWord不在wordList中，无法完成转换
    if (![wordList containsObject:endWord]) {
        return 0;
    }
    
    // 将wordList转换为NSSet，提高查找效率
    NSMutableSet<NSString *> *wordSet = [NSMutableSet setWithArray:wordList];
    
    // 创建队列，用于BFS
    NSMutableArray<NSString *> *queue = [NSMutableArray array];
    [queue addObject:beginWord];
    
    // 记录已访问的单词
    NSMutableSet<NSString *> *visited = [NSMutableSet setWithObject:beginWord];
    
    // 记录转换序列的长度
    NSInteger level = 1;
    
    // BFS
    while (queue.count > 0) {
        NSInteger size = queue.count;
        
        // 处理当前层的所有单词
        for (NSInteger i = 0; i < size; i++) {
            NSString *currentWord = queue[0];
            [queue removeObjectAtIndex:0];
            
            // 如果找到endWord，返回当前层级
            if ([currentWord isEqualToString:endWord]) {
                return level;
            }
            
            // 尝试改变当前单词的每一个字母
            for (NSInteger j = 0; j < currentWord.length; j++) {
                // 尝试替换为a-z的每一个字母
                for (char c = 'a'; c <= 'z'; c++) {
                    NSMutableString *newWord = [currentWord mutableCopy];
                    [newWord replaceCharactersInRange:NSMakeRange(j, 1) withString:[NSString stringWithFormat:@"%c", c]];
                    
                    // 如果新单词在wordSet中且未访问过，加入队列
                    if ([wordSet containsObject:newWord] && ![visited containsObject:newWord]) {
                        [queue addObject:[newWord copy]];
                        [visited addObject:[newWord copy]];
                    }
                }
            }
        }
        
        // 增加层级
        level++;
    }
    
    // 如果无法找到转换序列，返回0
    return 0;
}
@end

算法分析：

时间复杂度：O(N * L^2)，其中N是wordList的长度，L是单词的平均长度
空间复杂度：O(N)，需要存储wordSet、队列和已访问集合

实际工程应用：
单词接龙算法在iOS开发中的实际应用：

自动更正系统：在文本编辑应用中，可用于实现智能自动更正功能，找出与错误单词最相似的正确单词。
搜索建议引擎：在搜索应用中，可用于生成与用户输入相近的搜索建议，提高用户体验。
游戏AI：在文字游戏中，可用于实现AI对手，帮助AI找出从一个单词到另一个单词的最短路径。
语言学习应用：在语言学习应用中，可用于生成单词学习路径，帮助用户通过相似单词逐步扩展词汇量。

4.2.3 [LeetCode 329] 矩阵中的最长递增路径（Hard）

问题描述：
给定一个整数矩阵，找出最长递增路径的长度。对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

Objective-C 实现：

@interface Solution : NSObject
- (NSInteger)longestIncreasingPath:(NSArray<NSArray<NSNumber *> *> *)matrix;
@end

@implementation Solution
- (NSInteger)longestIncreasingPath:(NSArray<NSArray<NSNumber *> *> *)matrix {
    if (matrix.count == 0 || matrix[0].count == 0) {
        return 0;
    }
    
    NSInteger rows = matrix.count;
    NSInteger cols = matrix[0].count;
    NSInteger maxLength = 0;
    
    // 创建记忆化数组，用于存储每个单元格的最长路径长度
    NSMutableArray<NSMutableArray<NSNumber *> *> *memo = [NSMutableArray arrayWithCapacity:rows];
    for (NSInteger i = 0; i < rows; i++) {
        NSMutableArray<NSNumber *> *row = [NSMutableArray arrayWithCapacity:cols];
        for (NSInteger j = 0; j < cols; j++) {
            row[j] = @0;
        }
        memo[i] = row;
    }
    
    // 对每个单元格进行DFS
    for (NSInteger i = 0; i < rows; i++) {
        for (NSInteger j = 0; j < cols; j++) {
            NSInteger length = [self dfs:matrix memo:memo row:i col:j rows:rows cols:cols];
            maxLength = MAX(maxLength, length);
        }
    }
    
    return maxLength;
}

- (NSInteger)dfs:(NSArray<NSArray<NSNumber *> *> *)matrix 
           memo:(NSMutableArray<NSMutableArray<NSNumber *> *> *)memo 
            row:(NSInteger)row 
            col:(NSInteger)col 
           rows:(NSInteger)rows 
           cols:(NSInteger)cols {
    
    // 如果已经计算过，直接返回
    if ([memo[row][col] integerValue] > 0) {
        return [memo[row][col] integerValue];
    }
    
    // 四个方向的偏移量
    NSArray<NSArray<NSNumber *> *> *directions = @[
        @[@(-1), @0],  // 上
        @[@1, @0],     // 下
        @[@0, @(-1)],  // 左
        @[@0, @1]      // 右
    ];
    
    NSInteger maxLength = 1;
    
    // 尝试四个方向
    for (NSArray<NSNumber *> *dir in directions) {
        NSInteger newRow = row + [dir[0] integerValue];
        NSInteger newCol = col + [dir[1] integerValue];
        
        // 检查边界和递增条件
        if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && 
            [matrix[newRow][newCol] integerValue] > [matrix[row][col] integerValue]) {
            
            NSInteger length = 1 + [self dfs:matrix memo:memo row:newRow col:newCol rows:rows cols:cols];
            maxLength = MAX(maxLength, length);
        }
    }
    
    // 存储结果
    memo[row][col] = @(maxLength);
    
    return maxLength;
}
@end

算法分析：

时间复杂度：O(M*N)，其中M和N分别是矩阵的行数和列数，每个单元格只会被访问一次
空间复杂度：O(M*N)，需要一个与矩阵大小相同的记忆化数组

实际工程应用：
矩阵中的最长递增路径算法在iOS开发中的实际应用：

地形分析：在地图应用中，可用于分析地形高度数据，找出最陡峭的上升路径，帮助规划登山路线。
游戏关卡设计：在游戏开发中，可用于设计具有挑战性的关卡路径，确保玩家必须按照特定的难度递增路径前进。
数据可视化：在数据可视化应用中，可用于识别数据矩阵中的趋势路径，帮助用户理解数据变化。
图像处理：在图像处理应用中，可用于识别图像中的梯度变化路径，辅助边缘检测和特征提取。

4.2.4 实际应用：iOS中的路径规划与空间索引

上述高级图算法在iOS开发中的路径规划与空间索引方面有重要应用：

室内导航系统：
在室内导航应用中，可以使用图算法实现路径规划：

@interface NavigationNode : NSObject
@property (nonatomic, assign) NSInteger nodeId;
@property (nonatomic, assign) CGPoint position;
@property (nonatomic, strong) NSString *name;
@property (nonatomic, strong) NSString *type; // 例如：room, corridor, stairs, elevator
@property (nonatomic, strong) NSMutableDictionary<NSNumber *, NSNumber *> *neighbors; // nodeId -> distance
@end

@implementation NavigationNode
- (instancetype)init {
    self = [super init];
    if (self) {
        _neighbors = [NSMutableDictionary dictionary];
    }
    return self;
}
@end

@interface IndoorNavigationSystem : NSObject

@property (nonatomic, strong) NSMutableDictionary<NSNumber *, NavigationNode *> *nodes;
@property (nonatomic, strong) NSMutableDictionary<NSString *, NSNumber *> *nameToNodeId;
@property (nonatomic, strong) NSMutableDictionary<NSString *, NSMutableArray<NSNumber *> *> *typeToNodeIds;

- (instancetype)initWithMapData:(NSDictionary *)mapData;
- (void)addNode:(NavigationNode *)node;
- (void)addEdge:(NSInteger)fromNodeId to:(NSInteger)toNodeId distance:(CGFloat)distance bidirectional:(BOOL)bidirectional;
- (NSArray<NavigationNode *> *)findShortestPath:(NSInteger)startNodeId to:(NSInteger)endNodeId;
- (NSArray<NavigationNode *> *)findShortestPathByName:(NSString *)startName to:(NSString *)endName;
- (NSArray<NavigationNode *> *)findNearestNodesByType:(NSString *)type fromNode:(NSInteger)nodeId count:(NSInteger)count;
- (NSArray<NSArray<NavigationNode *> *> *)findAllPaths:(NSInteger)startNodeId to:(NSInteger)endNodeId maxDistance:(CGFloat)maxDistance;

@end

@implementation IndoorNavigationSystem

- (instancetype)initWithMapData:(NSDictionary *)mapData {
    self = [super init];
    if (self) {
        _nodes = [NSMutableDictionary dictionary];
        _nameToNodeId = [NSMutableDictionary dictionary];
        _typeToNodeIds = [NSMutableDictionary dictionary];
        
        // 解析地图数据
        [self parseMapData:mapData];
    }
    return self;
}

- (void)parseMapData:(NSDictionary *)mapData {
    // 解析节点
    NSArray<NSDictionary *> *nodeData = mapData[@"nodes"];
    for (NSDictionary *data in nodeData) {
        NavigationNode *node = [[NavigationNode alloc] init];
        node.nodeId = [data[@"id"] integerValue];
        node.position = CGPointMake([data[@"x"] floatValue], [data[@"y"] floatValue]);
        node.name = data[@"name"];
        node.type = data[@"type"];
        
        [self addNode:node];
    }
    
    // 解析边
    NSArray<NSDictionary *> *edgeData = mapData[@"edges"];
    for (NSDictionary *data in edgeData) {
        NSInteger fromNodeId = [data[@"from"] integerValue];
        NSInteger toNodeId = [data[@"to"] integerValue];
        CGFloat distance = [data[@"distance"] floatValue];
        BOOL bidirectional = [data[@"bidirectional"] boolValue];
        
        [self addEdge:fromNodeId to:toNodeId distance:distance bidirectional:bidirectional];
    }
}

- (void)addNode:(NavigationNode *)node {
    self.nodes[@(node.nodeId)] = node;
    
    if (node.name) {
        self.nameToNodeId[node.name] = @(node.nodeId);
    }
    
    if (node.type) {
        if (!self.typeToNodeIds[node.type]) {
            self.typeToNodeIds[node.type] = [NSMutableArray array];
        }
        [self.typeToNodeIds[node.type] addObject:@(node.nodeId)];
    }
}

- (void)addEdge:(NSInteger)fromNodeId to:(NSInteger)toNodeId distance:(CGFloat)distance bidirectional:(BOOL)bidirectional {
    NavigationNode *fromNode = self.nodes[@(fromNodeId)];
    NavigationNode *toNode = self.nodes[@(toNodeId)];
    
    if (!fromNode || !toNode) {
        NSLog(@"Invalid node IDs: %ld, %ld", (long)fromNodeId, (long)toNodeId);
        return;
    }
    
    fromNode.neighbors[@(toNodeId)] = @(distance);
    
    if (bidirectional) {
        toNode.neighbors[@(fromNodeId)] = @(distance);
    }
}

- (NSArray<NavigationNode *> *)findShortestPath:(NSInteger)startNodeId to:(NSInteger)endNodeId {
    NavigationNode *startNode = self.nodes[@(startNodeId)];
    NavigationNode *endNode = self.nodes[@(endNodeId)];
    
    if (!startNode || !endNode) {
        NSLog(@"Invalid node IDs: %ld, %ld", (long)startNodeId, (long)endNodeId);
        return @[];
    }
    
    // 使用Dijkstra算法找最短路径
    NSMutableDictionary<NSNumber *, NSNumber *> *distances = [NSMutableDictionary dictionary];
    NSMutableDictionary<NSNumber *, NSNumber *> *previous = [NSMutableDictionary dictionary];
    NSMutableSet<NSNumber *> *unvisited = [NSMutableSet set];
    
    // 初始化
    for (NSNumber *nodeId in self.nodes) {
        distances[nodeId] = @(CGFLOAT_MAX);
        [unvisited addObject:nodeId];
    }
    
    distances[@(startNodeId)] = @0;
    
    while (unvisited.count > 0) {
        // 找出距离最小的未访问节点
        NSNumber *currentNodeId = nil;
        CGFloat minDistance = CGFLOAT_MAX;
        
        for (NSNumber *nodeId in unvisited) {
            CGFloat distance = [distances[nodeId] floatValue];
            if (distance < minDistance) {
                minDistance = distance;
                currentNodeId = nodeId;
            }
        }
        
        // 如果没有可达的未访问节点，或者已经到达终点，退出循环
        if (!currentNodeId || [currentNodeId isEqual:@(endNodeId)]) {
            break;
        }
        
        [unvisited removeObject:currentNodeId];
        
        // 更新邻居节点的距离
        NavigationNode *currentNode = self.nodes[currentNodeId];
        for (NSNumber *neighborId in currentNode.neighbors) {
            if ([unvisited containsObject:neighborId]) {
                CGFloat distance = [distances[currentNodeId] floatValue] + [currentNode.neighbors[neighborId] floatValue];
                
                if (distance < [distances[neighborId] floatValue]) {
                    distances[neighborId] = @(distance);
                    previous[neighborId] = currentNodeId;
                }
            }
        }
    }
    
    // 如果终点不可达，返回空数组
    if ([distances[@(endNodeId)] floatValue] == CGFLOAT_MAX) {
        return @[];
    }
    
    // 重建路径
    NSMutableArray<NavigationNode *> *path = [NSMutableArray array];
    NSNumber *currentNodeId = @(endNodeId);
    
    while (currentNodeId) {
        [path insertObject:self.nodes[currentNodeId] atIndex:0];
        currentNodeId = previous[currentNodeId];
    }
    
    return path;
}

- (NSArray<NavigationNode *> *)findShortestPathByName:(NSString *)startName to:(NSString *)endName {
    NSNumber *startNodeId = self.nameToNodeId[startName];
    NSNumber *endNodeId = self.nameToNodeId[endName];
    
    if (!startNodeId || !endNodeId) {
        NSLog(@"Invalid node names: %@, %@", startName, endName);
        return @[];
    }
    
    return [self findShortestPath:[startNodeId integerValue] to:[endNodeId integerValue]];
}

- (NSArray<NavigationNode *> *)findNearestNodesByType:(NSString *)type fromNode:(NSInteger)nodeId count:(NSInteger)count {
    NavigationNode *startNode = self.nodes[@(nodeId)];
    
    if (!startNode) {
        NSLog(@"Invalid node ID: %ld", (long)nodeId);
        return @[];
    }
    
    NSArray<NSNumber *> *typeNodes = self.typeToNodeIds[type];
    
    if (!typeNodes || typeNodes.count == 0) {
        NSLog(@"No nodes of type: %@", type);
        return @[];
    }
    
    // 使用Dijkstra算法找最短路径到所有指定类型的节点
    NSMutableDictionary<NSNumber *, NSNumber *> *distances = [NSMutableDictionary dictionary];
    NSMutableSet<NSNumber *> *unvisited = [NSMutableSet set];
    
    // 初始化
    for (NSNumber *nId in self.nodes) {
        distances[nId] = @(CGFLOAT_MAX);
        [unvisited addObject:nId];
    }
    
    distances[@(nodeId)] = @0;
    
    while (unvisited.count > 0) {
        // 找出距离最小的未访问节点
        NSNumber *currentNodeId = nil;
        CGFloat minDistance = CGFLOAT_MAX;
        
        for (NSNumber *nId in unvisited) {
            CGFloat distance = [distances[nId] floatValue];
            if (distance < minDistance) {
                minDistance = distance;
                currentNodeId = nId;
            }
        }
        
        // 如果没有可达的未访问节点，退出循环
        if (!currentNodeId || minDistance == CGFLOAT_MAX) {
            break;
        }
        
        [unvisited removeObject:currentNodeId];
        
        // 更新邻居节点的距离
        NavigationNode *currentNode = self.nodes[currentNodeId];
        for (NSNumber *neighborId in currentNode.neighbors) {
            if ([unvisited containsObject:neighborId]) {
                CGFloat distance = [distances[currentNodeId] floatValue] + [currentNode.neighbors[neighborId] floatValue];
                
                if (distance < [distances[neighborId] floatValue]) {
                    distances[neighborId] = @(distance);
                }
            }
        }
    }
    
    // 筛选出指定类型的节点，并按距离排序
    NSMutableArray<NavigationNode *> *result = [NSMutableArray array];
    
    for (NSNumber *typeNodeId in typeNodes) {
        if ([distances[typeNodeId] floatValue] < CGFLOAT_MAX) {
            NavigationNode *node = self.nodes[typeNodeId];
            [result addObject:node];
        }
    }
    
    // 按距离排序
    [result sortUsingComparator:^NSComparisonResult(NavigationNode *node1, NavigationNode *node2) {
        CGFloat distance1 = [distances[@(node1.nodeId)] floatValue];
        CGFloat distance2 = [distances[@(node2.nodeId)] floatValue];
        
        if (distance1 < distance2) {
            return NSOrderedAscending;
        } else if (distance1 > distance2) {
            return NSOrderedDescending;
        } else {
            return NSOrderedSame;
        }
    }];
    
    // 返回前count个结果
    if (result.count > count) {
        return [result subarrayWithRange:NSMakeRange(0, count)];
    } else {
        return result;
    }
}

- (NSArray<NSArray<NavigationNode *> *> *)findAllPaths:(NSInteger)startNodeId to:(NSInteger)endNodeId maxDistance:(CGFloat)maxDistance {
    NavigationNode *startNode = self.nodes[@(startNodeId)];
    NavigationNode *endNode = self.nodes[@(endNodeId)];
    
    if (!startNode || !endNode) {
        NSLog(@"Invalid node IDs: %ld, %ld", (long)startNodeId, (long)endNodeId);
        return @[];
    }
    
    NSMutableArray<NSArray<NavigationNode *> *> *allPaths = [NSMutableArray array];
    NSMutableArray<NavigationNode *> *currentPath = [NSMutableArray arrayWithObject:startNode];
    NSMutableSet<NSNumber *> *visited = [NSMutableSet setWithObject:@(startNodeId)];
    
    [self dfsAllPaths:startNodeId 
                   to:endNodeId 
         maxDistance:maxDistance 
        currentPath:currentPath 
        currentDistance:0 
             visited:visited 
            allPaths:allPaths];
    
    return allPaths;
}

- (void)dfsAllPaths:(NSInteger)currentNodeId 
                 to:(NSInteger)endNodeId 
       maxDistance:(CGFloat)maxDistance 
      currentPath:(NSMutableArray<NavigationNode *> *)currentPath 
  currentDistance:(CGFloat)currentDistance 
           visited:(NSMutableSet<NSNumber *> *)visited 
          allPaths:(NSMutableArray<NSArray<NavigationNode *> *> *)allPaths {
    
    // 如果到达终点，添加当前路径到结果
    if (currentNodeId == endNodeId) {
        [allPaths addObject:[currentPath copy]];
        return;
    }
    
    // 如果当前距离超过最大距离，停止搜索
    if (currentDistance > maxDistance) {
        return;
    }
    
    NavigationNode *currentNode = self.nodes[@(currentNodeId)];
    
    // 遍历所有邻居
    for (NSNumber *neighborId in currentNode.neighbors) {
        // 如果邻居未访问过
        if (![visited containsObject:neighborId]) {
            NavigationNode *neighbor = self.nodes[neighborId];
            CGFloat distance = [currentNode.neighbors[neighborId] floatValue];
            
            // 如果添加这个邻居后总距离仍在限制内
            if (currentDistance + distance <= maxDistance) {
                // 添加邻居到当前路径
                [currentPath addObject:neighbor];
                [visited addObject:neighborId];
                
                // 继续DFS
                [self dfsAllPaths:[neighborId integerValue] 
                              to:endNodeId 
                    maxDistance:maxDistance 
                   currentPath:currentPath 
               currentDistance:currentDistance + distance 
                        visited:visited 
                       allPaths:allPaths];
                
                // 回溯
                [currentPath removeLastObject];
                [visited removeObject:neighborId];
            }
        }
    }
}

@end

空间索引系统：
在地图应用中，可以使用图算法实现空间索引：

@interface SpatialPoint : NSObject
@property (nonatomic, assign) NSInteger pointId;
@property (nonatomic, assign) CGPoint position;
@property (nonatomic, strong) NSDictionary<NSString *, id> *metadata;
@end

@implementation SpatialPoint
@end

@interface QuadTreeNode : NSObject
@property (nonatomic, assign) CGRect bounds;
@property (nonatomic, strong) NSMutableArray<SpatialPoint *> *points;
@property (nonatomic, strong) QuadTreeNode *northWest;
@property (nonatomic, strong) QuadTreeNode *northEast;
@property (nonatomic, strong) QuadTreeNode *southWest;
@property (nonatomic, strong) QuadTreeNode *southEast;
@property (nonatomic, assign) NSInteger capacity;
@property (nonatomic, assign) BOOL divided;
@end

@implementation QuadTreeNode

- (instancetype)initWithBounds:(CGRect)bounds capacity:(NSInteger)capacity {
    self = [super init];
    if (self) {
        _bounds = bounds;
        _capacity = capacity;
        _points = [NSMutableArray array];
        _divided = NO;
    }
    return self;
}

- (BOOL)insert:(SpatialPoint *)point {
    // 如果点不在当前节点范围内，返回失败
    if (!CGRectContainsPoint(self.bounds, point.position)) {
        return NO;
    }
    
    // 如果当前节点未满且未分裂，直接添加点
    if (self.points.count < self.capacity && !self.divided) {
        [self.points addObject:point];
        return YES;
    }
    
    // 如果当前节点未分裂，进行分裂
    if (!self.divided) {
        [self subdivide];
    }
    
    // 尝试将点插入到子节点
    if ([self.northWest insert:point]) return YES;
    if ([self.northEast insert:point]) return YES;
    if ([self.southWest insert:point]) return YES;
    if ([self.southEast insert:point]) return YES;
    
    // 如果所有子节点都无法插入，返回失败
    return NO;
}

- (void)subdivide {
    CGRect bounds = self.bounds;
    CGFloat x = CGRectGetMinX(bounds);
    CGFloat y = CGRectGetMinY(bounds);
    CGFloat w = CGRectGetWidth(bounds) / 2;
    CGFloat h = CGRectGetHeight(bounds) / 2;
    
    CGRect nwBounds = CGRectMake(x, y + h, w, h);
    CGRect neBounds = CGRectMake(x + w, y + h, w, h);
    CGRect swBounds = CGRectMake(x, y, w, h);
    CGRect seBounds = CGRectMake(x + w, y, w, h);
    
    self.northWest = [[QuadTreeNode alloc] initWithBounds:nwBounds capacity:self.capacity];
    self.northEast = [[QuadTreeNode alloc] initWithBounds:neBounds capacity:self.capacity];
    self.southWest = [[QuadTreeNode alloc] initWithBounds:swBounds capacity:self.capacity];
    self.southEast = [[QuadTreeNode alloc] initWithBounds:seBounds capacity:self.capacity];
    
    self.divided = YES;
    
    // 将当前节点的点重新分配到子节点
    for (SpatialPoint *point in self.points) {
        [self.northWest insert:point];
        [self.northEast insert:point];
        [self.southWest insert:point];
        [self.southEast insert:point];
    }
    
    [self.points removeAllObjects];
}

- (NSArray<SpatialPoint *> *)queryRange:(CGRect)range {
    NSMutableArray<SpatialPoint *> *result = [NSMutableArray array];
    
    // 如果查询范围与当前节点不相交，返回空结果
    if (!CGRectIntersectsRect(self.bounds, range)) {
        return result;
    }
    
    // 检查当前节点中的点
    for (SpatialPoint *point in self.points) {
        if (CGRectContainsPoint(range, point.position)) {
            [result addObject:point];
        }
    }
    
    // 如果当前节点已分裂，递归查询子节点
    if (self.divided) {
        [result addObjectsFromArray:[self.northWest queryRange:range]];
        [result addObjectsFromArray:[self.northEast queryRange:range]];
        [result addObjectsFromArray:[self.southWest queryRange:range]];
        [result addObjectsFromArray:[self.southEast queryRange:range]];
    }
    
    return result;
}

- (NSArray<SpatialPoint *> *)nearestNeighbors:(CGPoint)point count:(NSInteger)count maxDistance:(CGFloat)maxDistance {
    // 创建一个优先队列，按距离排序
    NSMutableArray<SpatialPoint *> *candidates = [NSMutableArray array];
    
    // 收集所有可能的候选点
    [self collectCandidates:point maxDistance:maxDistance candidates:candidates];
    
    // 按距离排序
    [candidates sortUsingComparator:^NSComparisonResult(SpatialPoint *p1, SpatialPoint *p2) {
        CGFloat d1 = [self distanceFrom:point to:p1.position];
        CGFloat d2 = [self distanceFrom:point to:p2.position];
        
        if (d1 < d2) {
            return NSOrderedAscending;
        } else if (d1 > d2) {
            return NSOrderedDescending;
        } else {
            return NSOrderedSame;
        }
    }];
    
    // 返回前count个结果
    if (candidates.count > count) {
        return [candidates subarrayWithRange:NSMakeRange(0, count)];
    } else {
        return candidates;
    }
}

- (void)collectCandidates:(CGPoint)point maxDistance:(CGFloat)maxDistance candidates:(NSMutableArray<SpatialPoint *> *)candidates {
    // 如果当前节点与查询点的最小距离大于最大距离，直接返回
    if ([self minDistanceFrom:point toBounds:self.bounds] > maxDistance) {
        return;
    }
    
    // 检查当前节点中的点
    for (SpatialPoint *p in self.points) {
        CGFloat distance = [self distanceFrom:point to:p.position];
        if (distance <= maxDistance) {
            [candidates addObject:p];
        }
    }
    
    // 如果当前节点已分裂，递归查询子节点
    if (self.divided) {
        [self.northWest collectCandidates:point maxDistance:maxDistance candidates:candidates];
        [self.northEast collectCandidates:point maxDistance:maxDistance candidates:candidates];
        [self.southWest collectCandidates:point maxDistance:maxDistance candidates:candidates];
        [self.southEast collectCandidates:point maxDistance:maxDistance candidates:candidates];
    }
}

- (CGFloat)distanceFrom:(CGPoint)p1 to:(CGPoint)p2 {
    CGFloat dx = p1.x - p2.x;
    CGFloat dy = p1.y - p2.y;
    return sqrt(dx * dx + dy * dy);
}

- (CGFloat)minDistanceFrom:(CGPoint)point toBounds:(CGRect)bounds {
    CGFloat dx = MAX(MAX(CGRectGetMinX(bounds) - point.x, 0), point.x - CGRectGetMaxX(bounds));
    CGFloat dy = MAX(MAX(CGRectGetMinY(bounds) - point.y, 0), point.y - CGRectGetMaxY(bounds));
    return sqrt(dx * dx + dy * dy);
}

@end

@interface SpatialIndexSystem : NSObject

@property (nonatomic, strong) QuadTreeNode *quadTree;
@property (nonatomic, strong) NSMutableDictionary<NSNumber *, SpatialPoint *> *pointsById;

- (instancetype)initWithBounds:(CGRect)bounds capacity:(NSInteger)capacity;
- (BOOL)insertPoint:(SpatialPoint *)point;
- (NSArray<SpatialPoint *> *)queryRange:(CGRect)range;
- (NSArray<SpatialPoint *> *)nearestNeighbors:(CGPoint)point count:(NSInteger)count maxDistance:(CGFloat)maxDistance;
- (NSArray<SpatialPoint *> *)findPath:(CGPoint)start to:(CGPoint)end obstacles:(NSArray<CGRect> *)obstacles;

@end

@implementation SpatialIndexSystem

- (instancetype)initWithBounds:(CGRect)bounds capacity:(NSInteger)capacity {
    self = [super init];
    if (self) {
        _quadTree = [[QuadTreeNode alloc] initWithBounds:bounds capacity:capacity];
        _pointsById = [NSMutableDictionary dictionary];
    }
    return self;
}

- (BOOL)insertPoint:(SpatialPoint *)point {
    BOOL success = [self.quadTree insert:point];
    if (success) {
        self.pointsById[@(point.pointId)] = point;
    }
    return success;
}

- (NSArray<SpatialPoint *> *)queryRange:(CGRect)range {
    return [self.quadTree queryRange:range];
}

- (NSArray<SpatialPoint *> *)nearestNeighbors:(CGPoint)point count:(NSInteger)count maxDistance:(CGFloat)maxDistance {
    return [self.quadTree nearestNeighbors:point count:count maxDistance:maxDistance];
}

- (NSArray<SpatialPoint *> *)findPath:(CGPoint)start to:(CGPoint)end obstacles:(NSArray<CGRect> *)obstacles {
    // 使用A*算法寻找路径
    
    // 创建起点和终点
    SpatialPoint *startPoint = [[SpatialPoint alloc] init];
    startPoint.pointId = -1;
    startPoint.position = start;
    
    SpatialPoint *endPoint = [[SpatialPoint alloc] init];
    endPoint.pointId = -2;
    endPoint.position = end;
    
    // 定义启发式函数（曼哈顿距离）
    CGFloat (^heuristic)(CGPoint, CGPoint) = ^CGFloat(CGPoint a, CGPoint b) {
        return ABS(a.x - b.x) + ABS(a.y - b.y);
    };
    
    // 定义节点结构
    typedef struct {
        CGPoint position;
        CGFloat gScore;
        CGFloat fScore;
        NSInteger cameFrom;
    } PathNode;
    
    // 创建开放列表和关闭列表
    NSMutableArray<PathNode> *openList = [NSMutableArray array];
    NSMutableArray<PathNode> *closedList = [NSMutableArray array];
    
    // 添加起点到开放列表
    PathNode startNode;
    startNode.position = start;
    startNode.gScore = 0;
    startNode.fScore = heuristic(start, end);
    startNode.cameFrom = -1;
    [openList addObject:startNode];
    
    // 定义方向数组（上、右、下、左、右上、右下、左下、左上）
    CGPoint directions[8] = {
        {0, 1}, {1, 0}, {0, -1}, {-1, 0},
        {1, 1}, {1, -1}, {-1, -1}, {-1, 1}
    };
    
    while (openList.count > 0) {
        // 找出f值最小的节点
        NSInteger currentIndex = 0;
        CGFloat minF = openList[0].fScore;
        
        for (NSInteger i = 1; i < openList.count; i++) {
            if (openList[i].fScore < minF) {
                minF = openList[i].fScore;
                currentIndex = i;
            }
        }
        
        // 获取当前节点
        PathNode current = openList[currentIndex];
        
        // 如果到达终点，重建路径
        if (CGPointEqualToPoint(current.position, end)) {
            NSMutableArray<SpatialPoint *> *path = [NSMutableArray array];
            
            // 添加终点
            [path addObject:endPoint];
            
            // 从终点回溯到起点
            NSInteger nodeIndex = closedList.count - 1;
            while (nodeIndex >= 0) {
                if (CGPointEqualToPoint(closedList[nodeIndex].position, current.position)) {
                    SpatialPoint *point = [[SpatialPoint alloc] init];
                    point.pointId = -100 - nodeIndex;
                    point.position = closedList[nodeIndex].position;
                    [path insertObject:point atIndex:0];
                    
                    if (closedList[nodeIndex].cameFrom == -1) {
                        break;
                    }
                    
                    current = closedList[closedList[nodeIndex].cameFrom];
                    nodeIndex = closedList[nodeIndex].cameFrom;
                } else {
                    nodeIndex--;
                }
            }
            
            // 添加起点
            [path insertObject:startPoint atIndex:0];
            
            return path;
        }
        
        // 将当前节点从开放列表移到关闭列表
        [openList removeObjectAtIndex:currentIndex];
        [closedList addObject:current];
        
        // 检查所有相邻节点
        for (NSInteger i = 0; i < 8; i++) {
            CGPoint newPos = CGPointMake(current.position.x + directions[i].x * 10, 
                                        current.position.y + directions[i].y * 10);
            
            // 检查是否在障碍物内
            BOOL isObstacle = NO;
            for (NSValue *obstacleValue in obstacles) {
                CGRect obstacle = [obstacleValue CGRectValue];
                if (CGRectContainsPoint(obstacle, newPos)) {
                    isObstacle = YES;
                    break;
                }
            }
            
            if (isObstacle) {
                continue;
            }
            
            // 检查是否已在关闭列表中
            BOOL inClosedList = NO;
            for (PathNode node in closedList) {
                if (CGPointEqualToPoint(node.position, newPos)) {
                    inClosedList = YES;
                    break;
                }
            }
            
            if (inClosedList) {
                continue;
            }
            
            // 计算从起点到当前相邻节点的距离
            CGFloat tentativeG = current.gScore + sqrt(pow(directions[i].x, 2) + pow(directions[i].y, 2)) * 10;
            
            // 检查是否已在开放列表中
            NSInteger neighborIndex = -1;
            for (NSInteger j = 0; j < openList.count; j++) {
                if (CGPointEqualToPoint(openList[j].position, newPos)) {
                    neighborIndex = j;
                    break;
                }
            }
            
            // 如果不在开放列表中，或者找到了更好的路径
            if (neighborIndex == -1 || tentativeG < openList[neighborIndex].gScore) {
                PathNode neighbor;
                neighbor.position = newPos;
                neighbor.gScore = tentativeG;
                neighbor.fScore = tentativeG + heuristic(newPos, end);
                neighbor.cameFrom = closedList.count - 1;
                
                if (neighborIndex == -1) {
                    [openList addObject:neighbor];
                } else {
                    openList[neighborIndex] = neighbor;
                }
            }
        }
    }
    
    // 如果无法找到路径，返回空数组
    return @[];
}

@end

这些实际应用展示了如何将LeetCode上的高级图算法应用到iOS开发的实际场景中，提高路径规划和空间索引的效率和可靠性。

从iOS到LeetCode：资深开发者的算法实战指南

第五章：高级数据结构

5.1 设计LRU缓存

5.1.1 [LeetCode 146] LRU缓存（Medium）

问题描述：
设计并实现一个LRU（最近最少使用）缓存机制。它应该支持以下操作：获取数据（get）和写入数据（put）。

get(key)：如果关键字存在于缓存中，则获取关键字的值（总是正数），否则返回-1。
put(key, value)：如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据，从而为新数据留出空间。

Objective-C 实现：

// 双向链表节点
@interface DLinkedNode : NSObject
@property (nonatomic, assign) NSInteger key;
@property (nonatomic, assign) NSInteger value;
@property (nonatomic, strong) DLinkedNode *prev;
@property (nonatomic, strong) DLinkedNode *next;
- (instancetype)initWithKey:(NSInteger)key value:(NSInteger)value;
@end

@implementation DLinkedNode
- (instancetype)initWithKey:(NSInteger)key value:(NSInteger)value {
    self = [super init];
    if (self) {
        _key = key;
        _value = value;
        _prev = nil;
        _next = nil;
    }
    return self;
}
@end

@interface LRUCache : NSObject
@property (nonatomic, assign) NSInteger capacity;
@property (nonatomic, assign) NSInteger size;
@property (nonatomic, strong) NSMutableDictionary<NSNumber *, DLinkedNode *> *cache;
@property (nonatomic, strong) DLinkedNode *head;
@property (nonatomic, strong) DLinkedNode *tail;
@end

@implementation LRUCache

- (instancetype)initWithCapacity:(NSInteger)capacity {
    self = [super init];
    if (self) {
        _capacity = capacity;
        _size = 0;
        _cache = [NSMutableDictionary dictionary];
        
        // 使用伪头部和伪尾部节点
        _head = [[DLinkedNode alloc] initWithKey:0 value:0];
        _tail = [[DLinkedNode alloc] initWithKey:0 value:0];
        _head.next = _tail;
        _tail.prev = _head;
    }
    return self;
}

- (NSInteger)get:(NSInteger)key {
    DLinkedNode *node = self.cache[@(key)];
    if (!node) {
        return -1;
    }
    
    // 如果key存在，先通过哈希表定位，再移到头部
    [self moveToHead:node];
    return node.value;
}

- (void)put:(NSInteger)key value:(NSInteger)value {
    DLinkedNode *node = self.cache[@(key)];
    
    if (!node) {
        // 如果key不存在，创建一个新的节点
        DLinkedNode *newNode = [[DLinkedNode alloc] initWithKey:key value:value];
        
        // 添加进哈希表
        self.cache[@(key)] = newNode;
        
        // 添加至双向链表的头部
        [self addToHead:newNode];
        
        // 增加size
        self.size++;
        
        // 如果超出容量，删除双向链表的尾部节点
        if (self.size > self.capacity) {
            // 删除双向链表的尾部节点
            DLinkedNode *removed = [self removeTail];
            
            // 删除哈希表中对应的项
            [self.cache removeObjectForKey:@(removed.key)];
            
            // 减少size
            self.size--;
        }
    } else {
        // 如果key存在，先通过哈希表定位，再修改value，并移到头部
        node.value = value;
        [self moveToHead:node];
    }
}

- (void)addToHead:(DLinkedNode *)node {
    node.prev = self.head;
    node.next = self.head.next;
    self.head.next.prev = node;
    self.head.next = node;
}

- (void)removeNode:(DLinkedNode *)node {
    node.prev.next = node.next;
    node.next.prev = node.prev;
}

- (void)moveToHead:(DLinkedNode *)node {
    [self removeNode:node];
    [self addToHead:node];
}

- (DLinkedNode *)removeTail {
    DLinkedNode *res = self.tail.prev;
    [self removeNode:res];
    return res;
}

@end

算法分析：

时间复杂度：O(1)，get和put操作都是O(1)
空间复杂度：O(capacity)，需要存储capacity个键值对

实际工程应用：
LRU缓存在iOS开发中的实际应用：

图片缓存：在图片加载库中，可以使用LRU缓存来管理内存中的图像，当内存压力大时自动释放最久未使用的图像。

@interface ImageCache : NSObject

@property (nonatomic, strong) LRUCache *memoryCache;
@property (nonatomic, strong) NSString *diskCachePath;
@property (nonatomic, strong) NSOperationQueue *ioQueue;

- (instancetype)initWithCapacity:(NSInteger)capacity;
- (UIImage *)getImageForKey:(NSString *)key;
- (void)setImage:(UIImage *)image forKey:(NSString *)key;
- (void)clearCache;

@end

@implementation ImageCache

- (instancetype)initWithCapacity:(NSInteger)capacity {
    self = [super init];
    if (self) {
        // 使用NSCache作为内存缓存
        _memoryCache = [[LRUCache alloc] initWithCapacity:capacity];
        
        // 设置磁盘缓存路径
        NSArray<NSString *> *paths = NSSearchPathForDirectoriesInDomains(NSCachesDirectory, NSUserDomainMask, YES);
        _diskCachePath = [paths[0] stringByAppendingPathComponent:@"ImageCache"];
        
        // 创建磁盘缓存目录
        if (![[NSFileManager defaultManager] fileExistsAtPath:_diskCachePath]) {
            [[NSFileManager defaultManager] createDirectoryAtPath:_diskCachePath withIntermediateDirectories:YES attributes:nil error:nil];
        }
        
        // 创建IO操作队列
        _ioQueue = [[NSOperationQueue alloc] init];
        _ioQueue.maxConcurrentOperationCount = 1; // 串行队列
    }
    return self;
}

- (UIImage *)getImageForKey:(NSString *)key {
    // 计算key的哈希值
    NSInteger hashKey = [key hash];
    
    // 先从内存缓存中查找
    NSInteger cacheResult = [self.memoryCache get:hashKey];
    if (cacheResult != -1) {
        return (__bridge UIImage *)((void *)cacheResult);
    }
    
    // 如果内存中没有，尝试从磁盘加载
    NSString *filePath = [self.diskCachePath stringByAppendingPathComponent:[NSString stringWithFormat:@"%ld.png", (long)hashKey]];
    if ([[NSFileManager defaultManager] fileExistsAtPath:filePath]) {
        UIImage *image = [UIImage imageWithContentsOfFile:filePath];
        if (image) {
            // 加载成功后，放入内存缓存
            [self.memoryCache put:hashKey value:(NSInteger)(__bridge void *)image];
            return image;
        }
    }
    
    return nil;
}

- (void)setImage:(UIImage *)image forKey:(NSString *)key {
    if (!image || !key) {
        return;
    }
    
    // 计算key的哈希值
    NSInteger hashKey = [key hash];
    
    // 存入内存缓存
    [self.memoryCache put:hashKey value:(NSInteger)(__bridge void *)image];
    
    // 异步存入磁盘缓存
    [self.ioQueue addOperationWithBlock:^{
        NSString *filePath = [self.diskCachePath stringByAppendingPathComponent:[NSString stringWithFormat:@"%ld.png", (long)hashKey]];
        NSData *data = UIImagePNGRepresentation(image);
        [data writeToFile:filePath atomically:YES];
    }];
}

- (void)clearCache {
    // 清除内存缓存
    self.memoryCache = [[LRUCache alloc] initWithCapacity:self.memoryCache.capacity];
    
    // 异步清除磁盘缓存
    [self.ioQueue addOperationWithBlock:^{
        NSError *error = nil;
        [[NSFileManager defaultManager] removeItemAtPath:self.diskCachePath error:&error];
        [[NSFileManager defaultManager] createDirectoryAtPath:self.diskCachePath withIntermediateDirectories:YES attributes:nil error:nil];
    }];
}

@end

网络请求缓存：在网络层中，可以使用LRU缓存来存储最近的API响应，减少重复请求。
数据库查询缓存：在数据库访问层，可以使用LRU缓存来存储最近的查询结果，提高查询性能。
视图复用：在复杂的UI系统中，可以使用LRU缓存来管理离屏渲染的视图，提高滚动性能。

5.2 设计LFU缓存

5.2.1 [LeetCode 460] LFU缓存（Hard）

问题描述：
设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。

get(key)：如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
put(key, value)：如果键不存在，请设置或插入值。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最近最少使用的键。

Objective-C 实现：

// 双向链表节点
@interface DLinkedNode : NSObject
@property (nonatomic, assign) NSInteger key;
@property (nonatomic, assign) NSInteger value;
@property (nonatomic, assign) NSInteger freq;
@property (nonatomic, strong) DLinkedNode *prev;
@property (nonatomic, strong) DLinkedNode *next;
- (instancetype)initWithKey:(NSInteger)key value:(NSInteger)value;
@end

@implementation DLinkedNode
- (instancetype)initWithKey:(NSInteger)key value:(NSInteger)value {
    self = [super init];
    if (self) {
        _key = key;
        _value = value;
        _freq = 1;
        _prev = nil;
        _next = nil;
    }
    return self;
}
@end

// 双向链表
@interface DLinkedList : NSObject
@property (nonatomic, strong) DLinkedNode *head;
@property (nonatomic, strong) DLinkedNode *tail;
@property (nonatomic, assign) NSInteger size;
@end

@implementation DLinkedList
- (instancetype)init {
    self = [super init];
    if (self) {
        _head = [[DLinkedNode alloc] initWithKey:0 value:0];
        _tail = [[DLinkedNode alloc] initWithKey:0 value:0];
        _head.next = _tail;
        _tail.prev = _head;
        _size = 0;
    }
    return self;
}

- (void)addToHead:(DLinkedNode *)node {
    node.prev = self.head;
    node.next = self.head.next;
    self.head.next.prev = node;
    self.head.next = node;
    self.size++;
}

- (void)removeNode:(DLinkedNode *)node {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    self.size--;
}

- (DLinkedNode *)removeTail {
    if (self.size == 0) {
        return nil;
    }
    DLinkedNode *node = self.tail.prev;
    [self removeNode:node];
    return node;
}
@end

@interface LFUCache : NSObject
@property (nonatomic, assign) NSInteger capacity;
@property (nonatomic, assign) NSInteger size;
@property (nonatomic, assign) NSInteger minFreq;
@property (nonatomic, strong) NSMutableDictionary<NSNumber *, DLinkedNode *> *keyToNode;
@property (nonatomic, strong) NSMutableDictionary<NSNumber *, DLinkedList *> *freqToList;
@end

@implementation LFUCache

- (instancetype)initWithCapacity:(NSInteger)capacity {
    self = [super init];
    if (self) {
        _capacity = capacity;
        _size = 0;
        _minFreq = 0;
        _keyToNode = [NSMutableDictionary dictionary];
        _freqToList = [NSMutableDictionary dictionary];
    }
    return self;
}

- (NSInteger)get:(NSInteger)key {
    if (self.capacity == 0) {
        return -1;
    }
    
    DLinkedNode *node = self.keyToNode[@(key)];
    if (!node) {
        return -1;
    }
    
    // 更新节点频率
    [self updateNode:node];
    
    return node.value;
}

- (void)put:(NSInteger)key value:(NSInteger)value {
    if (self.capacity == 0) {
        return;
    }
    
    DLinkedNode *node = self.keyToNode[@(key)];
    
    if (!node) {
        // 如果key不存在，创建一个新的节点
        DLinkedNode *newNode = [[DLinkedNode alloc] initWithKey:key value:value];
        
        // 添加进哈希表
        self.keyToNode[@(key)] = newNode;
        
        // 如果超出容量，删除频率最低的节点
        if (self.size == self.capacity) {
            DLinkedList *minFreqList = self.freqToList[@(self.minFreq)];
            DLinkedNode *removeNode = [minFreqList removeTail];
            
            // 从哈希表中删除
            [self.keyToNode removeObjectForKey:@(removeNode.key)];
            
            self.size--;
        }
        
        // 将新节点添加到频率为1的链表
        if (!self.freqToList[@1]) {
            self.freqToList[@1] = [[DLinkedList alloc] init];
        }
        [self.freqToList[@1] addToHead:newNode];
        
        // 更新最小频率为1
        self.minFreq = 1;
        
        // 增加size
        self.size++;
    } else {
        // 如果key存在，更新值和频率
        node.value = value;
        [self updateNode:node];
    }
}

- (void)updateNode:(DLinkedNode *)node {
    // 从当前频率链表中删除
    NSInteger freq = node.freq;
    DLinkedList *list = self.freqToList[@(freq)];
    [list removeNode:node];
    
    // 如果当前链表为空，且最小频率等于当前频率，更新最小频率
    if (list.size == 0 && self.minFreq == freq) {
        self.minFreq++;
    }
    
    // 增加节点频率
    node.freq++;
    
    // 将节点添加到新频率的链表
    if (!self.freqToList[@(node.freq)]) {
        self.freqToList[@(node.freq)] = [[DLinkedList alloc] init];
    }
    [self.freqToList[@(node.freq)] addToHead:node];
}

@end

算法分析：

时间复杂度：O(1)，get和put操作都是O(1)
空间复杂度：O(capacity)，需要存储capacity个键值对

实际工程应用：
LFU缓存在iOS开发中的实际应用：

智能预加载：在内容推荐应用中，可以使用LFU缓存来预加载用户最常访问的内容，提高用户体验。

@interface ContentPreloader : NSObject

@property (nonatomic, strong) LFUCache *contentCache;
@property (nonatomic, strong) NSOperationQueue *preloadQueue;
@property (nonatomic, strong) NSURLSession *session;

- (instancetype)initWithCapacity:(NSInteger)capacity;
- (void)preloadContentForURL:(NSURL *)url;
- (NSData *)getContentForURL:(NSURL *)url;
- (void)recordUserAccess:(NSURL *)url;

@end

@implementation ContentPreloader

- (instancetype)initWithCapacity:(NSInteger)capacity {
    self = [super init];
    if (self) {
        _contentCache = [[LFUCache alloc] initWithCapacity:capacity];
        _preloadQueue = [[NSOperationQueue alloc] init];
        _preloadQueue.maxConcurrentOperationCount = 3; // 限制并发预加载数量
        
        NSURLSessionConfiguration *config = [NSURLSessionConfiguration defaultSessionConfiguration];
        _session = [NSURLSession sessionWithConfiguration:config];
    }
    return self;
}

- (void)preloadContentForURL:(NSURL *)url {
    // 计算URL的哈希值作为key
    NSInteger urlHash = [url.absoluteString hash];
    
    // 检查缓存中是否已存在
    if ([self.contentCache get:urlHash] != -1) {
        return;
    }
    
    // 异步预加载内容
    [self.preloadQueue addOperationWithBlock:^{
        NSURLSessionDataTask *task = [self.session dataTaskWithURL:url completionHandler:^(NSData * _Nullable data, NSURLResponse * _Nullable response, NSError * _Nullable error) {
            if (data && !error) {
                // 将数据存入缓存
                NSInteger dataPtr = (NSInteger)(__bridge void *)data;
                [self.contentCache put:urlHash value:dataPtr];
            }
        }];
        [task resume];
    }];
}

- (NSData *)getContentForURL:(NSURL *)url {
    // 计算URL的哈希值作为key
    NSInteger urlHash = [url.absoluteString hash];
    
    // 从缓存中获取内容
    NSInteger dataPtr = [self.contentCache get:urlHash];
    if (dataPtr != -1) {
        return (__bridge NSData *)((void *)dataPtr);
    }
    
    // 如果缓存中没有，同步加载
    NSError *error = nil;
    NSData *data = [NSData dataWithContentsOfURL:url options:NSDataReadingMappedIfSafe error:&error];
    
    if (data && !error) {
        // 将数据存入缓存
        NSInteger newDataPtr = (NSInteger)(__bridge void *)data;
        [self.contentCache put:urlHash value:newDataPtr];
    }
    
    return data;
}

- (void)recordUserAccess:(NSURL *)url {
    // 计算URL的哈希值作为key
    NSInteger urlHash = [url.absoluteString hash];
    
    // 更新缓存中的访问频率
    NSInteger dataPtr = [self.contentCache get:urlHash];
    
    // 如果内容不在缓存中，预加载它
    if (dataPtr == -1) {
        [self preloadContentForURL:url];
    }
}

@end

资源优化：在游戏开发中，可以使用LFU缓存来管理纹理和音效资源，保留最常用的资源在内存中。
API响应缓存：在网络层中，可以使用LFU缓存来缓存API响应，优先保留频繁访问的接口数据。
数据库查询优化：在数据库访问层，可以使用LFU缓存来优化查询性能，缓存最常执行的查询结果。

5.3 设计Trie前缀树

5.3.1 [LeetCode 208] 实现Trie前缀树（Medium）

问题描述：
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

insert(word)：向Trie中插入一个单词。
search(word)：如果单词在Trie中，返回true；否则，返回false。
startsWith(prefix)：如果之前已经插入的单词中有以prefix为前缀的，返回true；否则，返回false。

Objective-C 实现：

@interface TrieNode : NSObject
@property (nonatomic, strong) NSMutableDictionary<NSString *, TrieNode *> *children;
@property (nonatomic, assign) BOOL isEnd;
@end

@implementation TrieNode
- (instancetype)init {
    self = [super init];
    if (self) {
        _children = [NSMutableDictionary dictionary];
        _isEnd = NO;
    }
    return self;
}
@end

@interface Trie : NSObject
@property (nonatomic, strong) TrieNode *root;
@end

@implementation Trie

- (instancetype)init {
    self = [super init];
    if (self) {
        _root = [[TrieNode alloc] init];
    }
    return self;
}

- (void)insert:(NSString *)word {
    TrieNode *node = self.root;
    
    for (NSInteger i = 0; i < word.length; i++) {
        NSString *ch = [word substringWithRange:NSMakeRange(i, 1)];
        
        if (!node.children[ch]) {
            node.children[ch] = [[TrieNode alloc] init];
        }
        
        node = node.children[ch];
    }
    
    node.isEnd = YES;
}

- (BOOL)search:(NSString *)word {
    TrieNode *node = [self searchPrefix:word];
    return node != nil && node.isEnd;
}

- (BOOL)startsWith:(NSString *)prefix {
    return [self searchPrefix:prefix] != nil;
}

- (TrieNode *)searchPrefix:(NSString *)prefix {
    TrieNode *node = self.root;
    
    for (NSInteger i = 0; i < prefix.length; i++) {
        NSString *ch = [prefix substringWithRange:NSMakeRange(i, 1)];
        
        if (!node.children[ch]) {
            return nil;
        }
        
        node = node.children[ch];
    }
    
    return node;
}

@end

算法分析：

时间复杂度：
- insert：O(m)，其中m是单词长度
- search：O(m)
- startsWith：O(m)
空间复杂度：O(T)，其中T是所有插入单词的字符总数

实际工程应用：
Trie前缀树在iOS开发中的实际应用：

自动补全：在搜索框或输入框中，可以使用Trie前缀树来实现自动补全功能，提高用户输入效率。

@interface AutoCompleteSystem : NSObject

@property (nonatomic, strong) Trie *trie;
@property (nonatomic, strong) NSMutableDictionary<NSString *, NSNumber *> *wordFrequency;

- (instancetype)initWithWords:(NSArray<NSString *> *)words;
- (NSArray<NSString *> *)getSuggestionsForPrefix:(NSString *)prefix limit:(NSInteger)limit;
- (void)addWord:(NSString *)word;
- (void)recordWordUsage:(NSString *)word;

@end

@implementation AutoCompleteSystem

- (instancetype)initWithWords:(NSArray<NSString *> *)words {
    self = [super init];
    if (self) {
        _trie = [[Trie alloc] init];
        _wordFrequency = [NSMutableDictionary dictionary];
        
        // 初始化Trie和词频字典
        for (NSString *word in words) {
            [self addWord:word];
        }
    }
    return self;
}

- (void)addWord:(NSString *)word {
    [self.trie insert:word];
    
    // 更新词频
    NSNumber *frequency = self.wordFrequency[word];
    if (frequency) {
        self.wordFrequency[word] = @([frequency integerValue] + 1);
    } else {
        self.wordFrequency[word] = @1;
    }
}

- (void)recordWordUsage:(NSString *)word {
    // 更新词频
    NSNumber *frequency = self.wordFrequency[word];
    if (frequency) {
        self.wordFrequency[word] = @([frequency integerValue] + 1);
    } else {
        [self addWord:word];
    }
}

- (NSArray<NSString *> *)getSuggestionsForPrefix:(NSString *)prefix limit:(NSInteger)limit {
    if (prefix.length == 0) {
        return @[];
    }
    
    // 查找所有以prefix为前缀的单词
    NSMutableArray<NSString *> *suggestions = [NSMutableArray array];
    [self collectWordsWithPrefix:prefix node:self.trie.root prefix:@"" result:suggestions];
    
    // 按词频排序
    [suggestions sortUsingComparator:^NSComparisonResult(NSString *word1, NSString *word2) {
        NSInteger freq1 = [self.wordFrequency[word1] integerValue];
        NSInteger freq2 = [self.wordFrequency[word2] integerValue];
        
        if (freq1 > freq2) {
            return NSOrderedAscending;
        } else if (freq1 < freq2) {
            return NSOrderedDescending;
        } else {
            return [word1 compare:word2];
        }
    }];
    
    // 限制结果数量
    if (suggestions.count > limit) {
        return [suggestions subarrayWithRange:NSMakeRange(0, limit)];
    }
    
    return suggestions;
}

- (void)collectWordsWithPrefix:(NSString *)prefix node:(TrieNode *)node prefix:(NSString *)currentPrefix result:(NSMutableArray<NSString *> *)result {
    if (prefix.length == 0) {
        if (node.isEnd) {
            [result addObject:[currentPrefix copy]];
        }
        
        // 继续搜索所有子节点
        for (NSString *ch in node.children) {
            [self collectWordsWithPrefix:@"" node:node.children[ch] prefix:[currentPrefix stringByAppendingString:ch] result:result];
        }
        
        return;
    }
    
    NSString *firstChar = [prefix substringToIndex:1];
    NSString *restPrefix = [prefix substringFromIndex:1];
    
    TrieNode *child = node.children[firstChar];
    if (child) {
        [self collectWordsWithPrefix:restPrefix node:child prefix:[currentPrefix stringByAppendingString:firstChar] result:result];
    }
}

@end

拼写检查：在文本编辑应用中，可以使用Trie前缀树来实现拼写检查功能，快速验证单词是否正确。
IP路由表：在网络应用中，可以使用Trie前缀树来实现高效的IP路由表查找。
文件系统索引：在文件管理应用中，可以使用Trie前缀树来实现文件路径的快速查找和前缀匹配。

5.4 设计并查集

5.4.1 [LeetCode 547] 省份数量（Medium）

问题描述：
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。返回矩阵中省份的数量。

Objective-C 实现：

@interface UnionFind : NSObject
@property (nonatomic, strong) NSMutableArray<NSNumber *> *parent;
@property (nonatomic, strong) NSMutableArray<NSNumber *> *rank;
@property (nonatomic, assign) NSInteger count;
@end

@implementation UnionFind

- (instancetype)initWithSize:(NSInteger)size {
    self = [super init];
    if (self) {
        _parent = [NSMutableArray arrayWithCapacity:size];
        _rank = [NSMutableArray arrayWithCapacity:size];
        _count = size;
        
        // 初始化，每个元素的父节点是自己
        for (NSInteger i = 0; i < size; i++) {
            _parent[i] = @(i);
            _rank[i] = @0;
        }
    }
    return self;
}

- (NSInteger)find:(NSInteger)x {
    if ([self.parent[x] integerValue] != x) {
        // 路径压缩
        self.parent[x] = @([self find:[self.parent[x] integerValue]]);
    }
    return [self.parent[x] integerValue];
}

- (void)union:(NSInteger)x y:(NSInteger)y {
    NSInteger rootX = [self find:x];
    NSInteger rootY = [self find:y];
    
    if (rootX == rootY) {
        return;
    }
    
    // 按秩合并
    if ([self.rank[rootX] integerValue] < [self.rank[rootY] integerValue]) {
        self.parent[rootX] = @(rootY);
    } else if ([self.rank[rootX] integerValue] > [self.rank[rootY] integerValue]) {
        self.parent[rootY] = @(rootX);
    } else {
        self.parent[rootY] = @(rootX);
        self.rank[rootX] = @([self.rank[rootX] integerValue] + 1);
    }
    
    // 合并后，连通分量数量减1
    self.count--;
}

@end

@interface Solution : NSObject
- (NSInteger)findCircleNum:(NSArray<NSArray<NSNumber *> *> *)isConnected;
@end

@implementation Solution
- (NSInteger)findCircleNum:(NSArray<NSArray<NSNumber *> *> *)isConnected {
    NSInteger n = isConnected.count;
    UnionFind *uf = [[UnionFind alloc] initWithSize:n];
    
    for (NSInteger i = 0; i < n; i++) {
        for (NSInteger j = 0; j < n; j++) {
            if ([isConnected[i][j] integerValue] == 1) {
                [uf union:i y:j];
            }
        }
    }
    
    return uf.count;
}
@end

算法分析：

时间复杂度：O(n^2 * α(n))，其中α是阿克曼函数的反函数，可以认为是一个很小的常数
空间复杂度：O(n)，需要存储parent和rank数组

实际工程应用：
并查集在iOS开发中的实际应用：

社交网络分析：在社交应用中，可以使用并查集来分析用户的社交圈，找出相互关联的用户群体。

@interface SocialNetworkAnalyzer : NSObject

@property (nonatomic, strong) UnionFind *userGroups;
@property (nonatomic, strong) NSMutableDictionary<NSString *, NSNumber *> *userIdMap;
@property (nonatomic, strong) NSMutableDictionary<NSNumber *, NSString *> *idUserMap;
@property (nonatomic, assign) NSInteger nextUserId;

- (instancetype)init;
- (void)addFriendship:(NSString *)user1 user2:(NSString *)user2;
- (BOOL)areConnected:(NSString *)user1 user2:(NSString *)user2;
- (NSArray<NSArray<NSString *> *> *)getAllGroups;
- (NSArray<NSString *> *)getUserGroup:(NSString *)user;

@end

@implementation SocialNetworkAnalyzer

- (instancetype)init {
    self = [super init];
    if (self) {
        _userGroups = [[UnionFind alloc] initWithSize:1000]; // 初始容量
        _userIdMap = [NSMutableDictionary dictionary];
        _idUserMap = [NSMutableDictionary dictionary];
        _nextUserId = 0;
    }
    return self;
}

- (NSInteger)getUserId:(NSString *)user {
    if (self.userIdMap[user]) {
        return [self.userIdMap[user] integerValue];
    }
    
    // 为新用户分配ID
    NSInteger userId = self.nextUserId++;
    self.userIdMap[user] = @(userId);
    self.idUserMap[@(userId)] = user;
    
    // 如果超出容量，扩展并查集
    if (userId >= self.userGroups.parent.count) {
        NSInteger oldSize = self.userGroups.parent.count;
        NSInteger newSize = oldSize * 2;
        
        // 创建新的并查集
        UnionFind *newUF = [[UnionFind alloc] initWithSize:newSize];
        
        // 复制原有的父节点和秩信息
        for (NSInteger i = 0; i < oldSize; i++) {
            newUF.parent[i] = self.userGroups.parent[i];
            newUF.rank[i] = self.userGroups.rank[i];
        }
        
        newUF.count = self.userGroups.count;
        self.userGroups = newUF;
    }
    
    return userId;
}

- (void)addFriendship:(NSString *)user1 user2:(NSString *)user2 {
    NSInteger id1 = [self getUserId:user1];
    NSInteger id2 = [self getUserId:user2];
    
    [self.userGroups union:id1 y:id2];
}

- (BOOL)areConnected:(NSString *)user1 user2:(NSString *)user2 {
    if (!self.userIdMap[user1] || !self.userIdMap[user2]) {
        return NO;
    }
    
    NSInteger id1 = [self.userIdMap[user1] integerValue];
    NSInteger id2 = [self.userIdMap[user2] integerValue];
    
    return [self.userGroups find:id1] == [self.userGroups find:id2];
}

- (NSArray<NSArray<NSString *> *> *)getAllGroups {
    NSMutableDictionary<NSNumber *, NSMutableArray<NSString *> *> *groups = [NSMutableDictionary dictionary];
    
    // 遍历所有用户，按根节点分组
    for (NSString *user in self.userIdMap) {
        NSInteger userId = [self.userIdMap[user] integerValue];
        NSInteger rootId = [self.userGroups find:userId];
        
        if (!groups[@(rootId)]) {
            groups[@(rootId)] = [NSMutableArray array];
        }
        
        [groups[@(rootId)] addObject:user];
    }
    
    // 转换为数组返回
    NSMutableArray<NSArray<NSString *> *> *result = [NSMutableArray array];
    for (NSNumber *rootId in groups) {
        [result addObject:[groups[rootId] copy]];
    }
    
    return result;
}

- (NSArray<NSString *> *)getUserGroup:(NSString *)user {
    if (!self.userIdMap[user]) {
        return @[];
    }
    
    NSInteger userId = [self.userIdMap[user] integerValue];
    NSInteger rootId = [self.userGroups find:userId];
    
    NSMutableArray<NSString *> *group = [NSMutableArray array];
    
    // 找出所有属于同一组的用户
    for (NSString *otherUser in self.userIdMap) {
        NSInteger otherUserId = [self.userIdMap[otherUser] integerValue];
        if ([self.userGroups find:otherUserId] == rootId) {
            [group addObject:otherUser];
        }
    }
    
    return group;
}

@end

图像分割：在图像处理应用中，可以使用并查集来实现图像分割，将相似的像素分为一组。
网络连接状态：在网络监控应用中，可以使用并查集来跟踪网络设备的连接状态，检测网络分区。
游戏地图生成：在游戏开发中，可以使用并查集来生成迷宫或地图，确保所有区域都是可达的。

5.5 设计线段树

5.5.1 [LeetCode 307] 区域和检索 - 数组可修改（Medium）

问题描述：
给你一个数组 nums，请你完成两类查询：

更新 nums 中指定下标处的元素
查询 nums 中指定范围内元素的总和

Objective-C 实现：

@interface SegmentTreeNode : NSObject
@property (nonatomic, assign) NSInteger start;
@property (nonatomic, assign) NSInteger end;
@property (nonatomic, assign) NSInteger sum;
@property (nonatomic, strong) SegmentTreeNode *left;
@property (nonatomic, strong) SegmentTreeNode *right;
@end

@implementation SegmentTreeNode
- (instancetype)initWithStart:(NSInteger)start end:(NSInteger)end sum:(NSInteger)sum {
    self = [super init];
    if (self) {
        _start = start;
        _end = end;
        _sum = sum;
        _left = nil;
        _right = nil;
    }
    return self;
}
@end

@interface NumArray : NSObject
@property (nonatomic, strong) SegmentTreeNode *root;
@property (nonatomic, strong) NSArray<NSNumber *> *nums;
@end

@implementation NumArray

- (instancetype)initWithNums:(NSArray<NSNumber *> *)nums {
    self = [super init];
    if (self) {
        _nums = [nums copy];
        if (nums.count > 0) {
            _root = [self buildTree:nums start:0 end:nums.count - 1];
        }
    }
    return self;
}

- (SegmentTreeNode *)buildTree:(NSArray<NSNumber *> *)nums start:(NSInteger)start end:(NSInteger)end {
    if (start > end) {
        return nil;
    }
    
    // 创建叶子节点
    if (start == end) {
        return [[SegmentTreeNode alloc] initWithStart:start end:end sum:[nums[start] integerValue]];
    }
    
    // 创建内部节点
    NSInteger mid = start + (end - start) / 2;
    SegmentTreeNode *left = [self buildTree:nums start:start end:mid];
    SegmentTreeNode *right = [self buildTree:nums start:mid + 1 end:end];
    
    SegmentTreeNode *node = [[SegmentTreeNode alloc] initWithStart:start end:end sum:left.sum + right.sum];
    node.left = left;
    node.right = right;
    
    return node;
}

- (void)update:(NSInteger)index value:(NSInteger)val {
    if (index < 0 || index >= self.nums.count) {
        return;
    }
    
    // 更新原始数组
    NSMutableArray *mutableNums = [self.nums mutableCopy];
    mutableNums[index] = @(val);
    self.nums = [mutableNums copy];
    
    // 更新线段树
    [self updateTree:self.root index:index value:val];
}

- (void)updateTree:(SegmentTreeNode *)node index:(NSInteger)index value:(NSInteger)value {
    if (node.start == node.end) {
        node.sum = value;
        return;
    }
    
    NSInteger mid = node.start + (node.end - node.start) / 2;
    
    if (index <= mid) {
        [self updateTree:node.left index:index value:value];
    } else {
        [self updateTree:node.right index:index value:value];
    }
    
    // 更新当前节点的和
    node.sum = node.left.sum + node.right.sum;
}

- (NSInteger)sumRange:(NSInteger)left right:(NSInteger)right {
    if (left < 0 || right >= self.nums.count || left > right) {
        return 0;
    }
    
    return [self queryTree:self.root start:left end:right];
}

- (NSInteger)queryTree:(SegmentTreeNode *)node start:(NSInteger)start end:(NSInteger)end {
    // 如果当前节点的范围完全包含在查询范围内，直接返回节点的和
    if (node.start >= start && node.end <= end) {
        return node.sum;
    }
    
    // 如果当前节点的范围与查询范围没有交集，返回0
    if (node.end < start || node.start > end) {
        return 0;
    }
    
    // 查询左右子树，并合并结果
    return [self queryTree:node.left start:start end:end] + [self queryTree:node.right start:start end:end];
}

@end

算法分析：

时间复杂度：
- 构建线段树：O(n)
- 更新操作：O(log n)
- 区间查询：O(log n)
空间复杂度：O(n)，需要存储线段树节点

实际工程应用：
线段树在iOS开发中的实际应用：

数据可视化：在数据可视化应用中，可以使用线段树来实现高效的区间统计和动态更新。

@interface DataVisualizationSystem : NSObject

@property (nonatomic, strong) NumArray *dataProcessor;
@property (nonatomic, strong) NSMutableArray<NSNumber *> *rawData;
@property (nonatomic, strong) NSMutableDictionary<NSString *, NSValue *> *visibleRanges;

- (instancetype)initWithData:(NSArray<NSNumber *> *)data;
- (void)updateDataAtIndex:(NSInteger)index value:(NSInteger)value;
- (NSInteger)getRangeSum:(NSInteger)start end:(NSInteger)end;
- (NSArray<NSNumber *> *)getMovingAverage:(NSInteger)windowSize;
- (void)setVisibleRange:(NSString *)chartId start:(NSInteger)start end:(NSInteger)end;
- (NSDictionary<NSString *, NSNumber *> *)getVisibleRangeSums;

@end

@implementation DataVisualizationSystem

- (instancetype)initWithData:(NSArray<NSNumber *> *)data {
    self = [super init];
    if (self) {
        _rawData = [data mutableCopy];
        _dataProcessor = [[NumArray alloc] initWithNums:data];
        _visibleRanges = [NSMutableDictionary dictionary];
    }
    return self;
}

- (void)updateDataAtIndex:(NSInteger)index value:(NSInteger)value {
    if (index < 0 || index >= self.rawData.count) {
        return;
    }
    
    // 更新原始数据
    self.rawData[index] = @(value);
    
    // 更新线段树
    [self.dataProcessor update:index value:value];
}

- (NSInteger)getRangeSum:(NSInteger)start end:(NSInteger)end {
    return [self.dataProcessor sumRange:start right:end];
}

- (NSArray<NSNumber *> *)getMovingAverage:(NSInteger)windowSize {
    if (windowSize <= 0 || windowSize > self.rawData.count) {
        return @[];
    }
    
    NSMutableArray<NSNumber *> *result = [NSMutableArray arrayWithCapacity:self.rawData.count - windowSize + 1];
    
    for (NSInteger i = 0; i <= self.rawData.count - windowSize; i++) {
        NSInteger sum = [self.dataProcessor sumRange:i right:i + windowSize - 1];
        CGFloat average = (CGFloat)sum / windowSize;
        [result addObject:@(average)];
    }
    
    return result;
}

- (void)setVisibleRange:(NSString *)chartId start:(NSInteger)start end:(NSInteger)end {
    if (start < 0 || end >= self.rawData.count || start > end) {
        return;
    }
    
    self.visibleRanges[chartId] = [NSValue valueWithRange:NSMakeRange(start, end - start + 1)];
}

- (NSDictionary<NSString *, NSNumber *> *)getVisibleRangeSums {
    NSMutableDictionary<NSString *, NSNumber *> *result = [NSMutableDictionary dictionary];
    
    for (NSString *chartId in self.visibleRanges) {
        NSRange range = [self.visibleRanges[chartId] rangeValue];
        NSInteger sum = [self.dataProcessor sumRange:range.location right:range.location + range.length - 1];
        result[chartId] = @(sum);
    }
    
    return result;
}

@end

范围查询优化：在数据库应用中，可以使用线段树来优化范围查询，提高查询效率。
游戏碰撞检测：在游戏开发中，可以使用线段树来实现高效的碰撞检测，检查物体是否与其他物体相交。
日程安排：在日历应用中，可以使用线段树来检查时间段是否有冲突，优化日程安排。

5.6 设计跳表

5.6.1 [LeetCode 1206] 设计跳表（Hard）

问题描述：
不使用任何库函数，设计一个跳表。跳表是在O(log n)时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。

Objective-C 实现：

@interface SkipListNode : NSObject
@property (nonatomic, assign) NSInteger val;
@property (nonatomic, strong) NSMutableArray<SkipListNode *> *next;
@end

@implementation SkipListNode
- (instancetype)initWithValue:(NSInteger)val level:(NSInteger)level {
    self = [super init];
    if (self) {
        _val = val;
        _next = [NSMutableArray arrayWithCapacity:level];
        for (NSInteger i = 0; i < level; i++) {
            _next[i] = nil;
        }
    }
    return self;
}
@end

@interface Skiplist : NSObject
@property (nonatomic, assign) NSInteger maxLevel;
@property (nonatomic, assign) CGFloat p;
@property (nonatomic, assign) NSInteger level;
@property (nonatomic, strong) SkipListNode *head;
@end

@implementation Skiplist

- (instancetype)init {
    self = [super init];
    if (self) {
        _maxLevel = 32;
        _p = 0.25;
        _level = 1;
        _head = [[SkipListNode alloc] initWithValue:-1 level:_maxLevel];
    }
    return self;
}

- (BOOL)search:(NSInteger)target {
    SkipListNode *current = self.head;
    
    // 从最高层开始搜索
    for (NSInteger i = self.level - 1; i >= 0; i--) {
        // 在当前层向右移动，直到找到大于等于target的节点
        while (current.next[i] && current.next[i].val < target) {
            current = current.next[i];
        }
    }
    
    // 移动到第0层，检查下一个节点是否等于target
    current = current.next[0];
    
    // 如果找到目标值，返回true
    return current && current.val == target;
}

- (void)add:(NSInteger)num {
    NSMutableArray<SkipListNode *> *update = [NSMutableArray arrayWithCapacity:self.maxLevel];
    for (NSInteger i = 0; i < self.maxLevel; i++) {
        update[i] = self.head;
    }
    
    SkipListNode *current = self.head;
    
    // 从最高层开始搜索
    for (NSInteger i = self.level - 1; i >= 0; i--) {
        // 在当前层向右移动，直到找到大于等于num的节点
        while (current.next[i] && current.next[i].val < num) {
            current = current.next[i];
        }
        update[i] = current;
    }
    
    // 随机生成新节点的层数
    NSInteger newLevel = [self randomLevel];
    
    // 如果新层数大于当前最大层数，更新最大层数
    if (newLevel > self.level) {
        for (NSInteger i = self.level; i < newLevel; i++) {
            update[i] = self.head;
        }
        self.level = newLevel;
    }
    
    // 创建新节点
    SkipListNode *newNode = [[SkipListNode alloc] initWithValue:num level:newLevel];
    
    // 插入新节点
    for (NSInteger i = 0; i < newLevel; i++) {
        newNode.next[i] = update[i].next[i];
        update[i].next[i] = newNode;
    }
}

- (BOOL)erase:(NSInteger)num {
    NSMutableArray<SkipListNode *> *update = [NSMutableArray arrayWithCapacity:self.maxLevel];
    for (NSInteger i = 0; i < self.maxLevel; i++) {
        update[i] = self.head;
    }
    
    SkipListNode *current = self.head;
    
    // 从最高层开始搜索
    for (NSInteger i = self.level - 1; i >= 0; i--) {
        // 在当前层向右移动，直到找到大于等于num的节点
        while (current.next[i] && current.next[i].val < num) {
            current = current.next[i];
        }
        update[i] = current;
    }
    
    // 移动到第0层，检查下一个节点是否等于num
    current = current.next[0];
    
    // 如果没有找到目标值，返回false
    if (!current || current.val != num) {
        return NO;
    }
    
    // 删除节点
    for (NSInteger i = 0; i < self.level; i++) {
        if (update[i].next[i] != current) {
            break;
        }
        update[i].next[i] = current.next[i];
    }
    
    // 更新最大层数
    while (self.level > 1 && !self.head.next[self.level - 1]) {
        self.level--;
    }
    
    return YES;
}

- (NSInteger)randomLevel {
    NSInteger level = 1;
    while (arc4random_uniform(UINT32_MAX) < self.p * UINT32_MAX && level < self.maxLevel) {
        level++;
    }
    return level;
}

@end

算法分析：

时间复杂度：
- 搜索：O(log n)
- 插入：O(log n)
- 删除：O(log n)
空间复杂度：O(n)，需要存储跳表节点

实际工程应用：
跳表在iOS开发中的实际应用：

高性能缓存：在缓存系统中，可以使用跳表来实现高效的键值查找，提高缓存性能。

@interface SkipListCache : NSObject

@property (nonatomic, strong) Skiplist *skiplist;
@property (nonatomic, strong) NSMutableDictionary<NSNumber *, id> *valueMap;
@property (nonatomic, assign) NSInteger capacity;
@property (nonatomic, assign) NSInteger size;

- (instancetype)initWithCapacity:(NSInteger)capacity;
- (id)get:(NSInteger)key;
- (void)put:(NSInteger)key value:(id)value;
- (void)remove:(NSInteger)key;
- (NSArray<NSNumber *> *)getKeysInRange:(NSInteger)start end:(NSInteger)end;

@end

@implementation SkipListCache

- (instancetype)initWithCapacity:(NSInteger)capacity {
    self = [super init];
    if (self) {
        _skiplist = [[Skiplist alloc] init];
        _valueMap = [NSMutableDictionary dictionary];
        _capacity = capacity;
        _size = 0;
    }
    return self;
}

- (id)get:(NSInteger)key {
    if ([self.skiplist search:key]) {
        return self.valueMap[@(key)];
    }
    return nil;
}

- (void)put:(NSInteger)key value:(id)value {
    // 如果key已存在，更新值
    if ([self.skiplist search:key]) {
        self.valueMap[@(key)] = value;
        return;
    }
    
    // 如果缓存已满，删除最小的key
    if (self.size == self.capacity) {
        // 找到最小的key
        NSInteger minKey = [self findMinKey];
        [self remove:minKey];
    }
    
    // 添加新key-value
    [self.skiplist add:key];
    self.valueMap[@(key)] = value;
    self.size++;
}

- (void)remove:(NSInteger)key {
    if ([self.skiplist erase:key]) {
        [self.valueMap removeObjectForKey:@(key)];
        self.size--;
    }
}

- (NSInteger)findMinKey {
    // 获取跳表中的最小key
    SkipListNode *current = self.skiplist.head.next[0];
    if (current) {
        return current.val;
    }
    return -1;
}

- (NSArray<NSNumber *> *)getKeysInRange:(NSInteger)start end:(NSInteger)end {
    NSMutableArray<NSNumber *> *result = [NSMutableArray array];
    
    // 找到第一个大于等于start的节点
    SkipListNode *current = self.skiplist.head;
    for (NSInteger i = self.skiplist.level - 1; i >= 0; i--) {
        while (current.next[i] && current.next[i].val < start) {
            current = current.next[i];
        }
    }
    
    // 移动到第0层
    current = current.next[0];
    
    // 收集范围内的所有key
    while (current && current.val <= end) {
        [result addObject:@(current.val)];
        current = current.next[0];
    }
    
    return result;
}

@end

排行榜系统：在游戏或社交应用中，可以使用跳表来实现高效的排行榜系统，快速查找和更新用户排名。
时间序列数据库：在时间序列数据库中，可以使用跳表来存储和查询时间戳数据，提高查询效率。
地理位置索引：在地图应用中，可以使用跳表来实现地理位置的一维索引，快速查找特定范围内的位置。

5.7 实际应用：iOS中的高性能数据结构

上述高级数据结构在iOS开发中的综合应用：

高性能缓存系统：
在iOS应用中，可以结合多种高级数据结构实现一个高性能的多级缓存系统：

@interface MultiLevelCache : NSObject

@property (nonatomic, strong) LRUCache *level1Cache; // 内存中的LRU缓存
@property (nonatomic, strong) LFUCache *level2Cache; // 内存中的LFU缓存
@property (nonatomic, strong) SkipListCache *level3Cache; // 磁盘中的跳表缓存
@property (nonatomic, strong) NSOperationQueue *diskQueue;

- (instancetype)initWithCapacities:(NSInteger)l1Capacity l2Capacity:(NSInteger)l2Capacity l3Capacity:(NSInteger)l3Capacity;
- (id)get:(NSString *)key;
- (void)put:(NSString *)key value:(id)value;
- (void)remove:(NSString *)key;
- (void)clear;

@end

@implementation MultiLevelCache

- (instancetype)initWithCapacities:(NSInteger)l1Capacity l2Capacity:(NSInteger)l2Capacity l3Capacity:(NSInteger)l3Capacity {
    self = [super init];
    if (self) {
        _level1Cache = [[LRUCache alloc] initWithCapacity:l1Capacity];
        _level2Cache = [[LFUCache alloc] initWithCapacity:l2Capacity];
        _level3Cache = [[SkipListCache alloc] initWithCapacity:l3Capacity];
        _diskQueue = [[NSOperationQueue alloc] init];
        _diskQueue.maxConcurrentOperationCount = 1; // 串行队列
    }
    return self;
}

- (id)get:(NSString *)key {
    NSInteger keyHash = [key hash];
    
    // 先从L1缓存查找
    NSInteger l1Result = [self.level1Cache get:keyHash];
    if (l1Result != -1) {
        return (__bridge id)((void *)l1Result);
    }
    
    // 再从L2缓存查找
    NSInteger l2Result = [self.level2Cache get:keyHash];
    if (l2Result != -1) {
        // 找到后，提升到L1缓存
        id value = (__bridge id)((void *)l2Result);
        [self.level1Cache put:keyHash value:(NSInteger)(__bridge void *)value];
        return value;
    }
    
    // 最后从L3缓存查找
    id l3Result = [self.level3Cache get:keyHash];
    if (l3Result) {
        // 找到后，提升到L1和L2缓存
        [self.level1Cache put:keyHash value:(NSInteger)(__bridge void *)l3Result];
        [self.level2Cache put:keyHash value:(NSInteger)(__bridge void *)l3Result];
        return l3Result;
    }
    
    return nil;
}

- (void)put:(NSString *)key value:(id)value {
    NSInteger keyHash = [key hash];
    
    // 添加到所有缓存层
    [self.level1Cache put:keyHash value:(NSInteger)(__bridge void *)value];
    [self.level2Cache put:keyHash value:(NSInteger)(__bridge void *)value];
    
    // 异步添加到L3缓存
    [self.diskQueue addOperationWithBlock:^{
        [self.level3Cache put:keyHash value:value];
    }];
}

- (void)remove:(NSString *)key {
    NSInteger keyHash = [key hash];
    
    // 从所有缓存层移除
    [self.level1Cache put:keyHash value:-1]; // 使用-1表示无效
    [self.level2Cache put:keyHash value:-1]; // 使用-1表示无效
    
    // 异步从L3缓存移除
    [self.diskQueue addOperationWithBlock:^{
        [self.level3Cache remove:keyHash];
    }];
}

- (void)clear {
    // 清空所有缓存层
    self.level1Cache = [[LRUCache alloc] initWithCapacity:self.level1Cache.capacity];
    self.level2Cache = [[LFUCache alloc] initWithCapacity:self.level2Cache.capacity];
    
    // 异步清空L3缓存
    [self.diskQueue addOperationWithBlock:^{
        [self.level3Cache remove:-1]; // 特殊值-1表示清空所有
    }];
}

@end

搜索引擎索引系统：
在iOS应用中，可以结合Trie前缀树和跳表实现一个高效的搜索引擎索引系统：

@interface SearchIndex : NSObject

@property (nonatomic, strong) Trie *prefixIndex;
@property (nonatomic, strong) Skiplist *rankIndex;
@property (nonatomic, strong) NSMutableDictionary<NSString *, NSNumber *> *documentRanks;
@property (nonatomic, strong) NSMutableDictionary<NSString *, NSMutableSet<NSString *> *> *invertedIndex;

- (instancetype)init;
- (void)indexDocument:(NSString *)documentId content:(NSString *)content rank:(NSInteger)rank;
- (void)updateDocumentRank:(NSString *)documentId rank:(NSInteger)rank;
- (NSArray<NSString *> *)searchPrefix:(NSString *)prefix limit:(NSInteger)limit;
- (NSArray<NSString *> *)searchKeyword:(NSString *)keyword limit:(NSInteger)limit;
- (NSArray<NSString *> *)searchByRankRange:(NSInteger)minRank maxRank:(NSInteger)maxRank limit:(NSInteger)limit;

@end

@implementation SearchIndex

- (instancetype)init {
    self = [super init];
    if (self) {
        _prefixIndex = [[Trie alloc] init];
        _rankIndex = [[Skiplist alloc] init];
        _documentRanks = [NSMutableDictionary dictionary];
        _invertedIndex = [NSMutableDictionary dictionary];
    }
    return self;
}

- (void)indexDocument:(NSString *)documentId content:(NSString *)content rank:(NSInteger)rank {
    // 存储文档排名
    self.documentRanks[documentId] = @(rank);
    
    // 添加到排名索引
    [self.rankIndex add:rank];
    
    // 分词并建立倒排索引
    NSArray<NSString *> *words = [self tokenize:content];
    for (NSString *word in words) {
        // 添加到前缀索引
        [self.prefixIndex insert:word];
        
        // 添加到倒排索引
        if (!self.invertedIndex[word]) {
            self.invertedIndex[word] = [NSMutableSet set];
        }
        [self.invertedIndex[word] addObject:documentId];
    }
}

- (void)updateDocumentRank:(NSString *)documentId rank:(NSInteger)rank {
    NSNumber *oldRank = self.documentRanks[documentId];
    if (oldRank) {
        // 从排名索引中删除旧排名
        [self.rankIndex erase:[oldRank integerValue]];
    }
    
    // 更新文档排名
    self.documentRanks[documentId] = @(rank);
    
    // 添加到排名索引
    [self.rankIndex add:rank];
}

- (NSArray<NSString *> *)searchPrefix:(NSString *)prefix limit:(NSInteger)limit {
    // 使用前缀树查找所有匹配前缀的单词
    NSMutableArray<NSString *> *matchedWords = [NSMutableArray array];
    [self collectWordsWithPrefix:prefix node:self.prefixIndex.root prefix:@"" result:matchedWords];
    
    // 获取包含这些单词的文档
    NSMutableSet<NSString *> *documentSet = [NSMutableSet set];
    for (NSString *word in matchedWords) {
        NSMutableSet<NSString *> *documents = self.invertedIndex[word];
        if (documents) {
            [documentSet unionSet:documents];
        }
    }
    
    // 按排名排序
    NSArray<NSString *> *documents = [documentSet allObjects];
    NSArray<NSString *> *sortedDocuments = [documents sortedArrayUsingComparator:^NSComparisonResult(NSString *doc1, NSString *doc2) {
        NSInteger rank1 = [self.documentRanks[doc1] integerValue];
        NSInteger rank2 = [self.documentRanks[doc2] integerValue];
        
        if (rank1 > rank2) {
            return NSOrderedAscending;
        } else if (rank1 < rank2) {
            return NSOrderedDescending;
        } else {
            return NSOrderedSame;
        }
    }];
    
    // 限制结果数量
    if (sortedDocuments.count > limit) {
        return [sortedDocuments subarrayWithRange:NSMakeRange(0, limit)];
    }
    
    return sortedDocuments;
}

- (NSArray<NSString *> *)searchKeyword:(NSString *)keyword limit:(NSInteger)limit {
    // 获取包含关键词的文档
    NSMutableSet<NSString *> *documentSet = self.invertedIndex[keyword];
    if (!documentSet) {
        return @[];
    }
    
    // 按排名排序
    NSArray<NSString *> *documents = [documentSet allObjects];
    NSArray<NSString *> *sortedDocuments = [documents sortedArrayUsingComparator:^NSComparisonResult(NSString *doc1, NSString *doc2) {
        NSInteger rank1 = [self.documentRanks[doc1] integerValue];
        NSInteger rank2 = [self.documentRanks[doc2] integerValue];
        
        if (rank1 > rank2) {
            return NSOrderedAscending;
        } else if (rank1 < rank2) {
            return NSOrderedDescending;
        } else {
            return NSOrderedSame;
        }
    }];
    
    // 限制结果数量
    if (sortedDocuments.count > limit) {
        return [sortedDocuments subarrayWithRange:NSMakeRange(0, limit)];
    }
    
    return sortedDocuments;
}

- (NSArray<NSString *> *)searchByRankRange:(NSInteger)minRank maxRank:(NSInteger)maxRank limit:(NSInteger)limit {
    NSMutableArray<NSString *> *result = [NSMutableArray array];
    
    // 遍历所有文档，找出排名在指定范围内的文档
    for (NSString *documentId in self.documentRanks) {
        NSInteger rank = [self.documentRanks[documentId] integerValue];
        if (rank >= minRank && rank <= maxRank) {
            [result addObject:documentId];
        }
    }
    
    // 按排名排序
    [result sortUsingComparator:^NSComparisonResult(NSString *doc1, NSString *doc2) {
        NSInteger rank1 = [self.documentRanks[doc1] integerValue];
        NSInteger rank2 = [self.documentRanks[doc2] integerValue];
        
        if (rank1 > rank2) {
            return NSOrderedAscending;
        } else if (rank1 < rank2) {
            return NSOrderedDescending;
        } else {
            return NSOrderedSame;
        }
    }];
    
    // 限制结果数量
    if (result.count > limit) {
        return [result subarrayWithRange:NSMakeRange(0, limit)];
    }
    
    return result;
}

- (NSArray<NSString *> *)tokenize:(NSString *)content {
    // 简单的分词实现，实际应用中可能需要更复杂的分词算法
    NSCharacterSet *separators = [NSCharacterSet whitespaceAndNewlineCharacterSet];
    NSArray<NSString *> *words = [content componentsSeparatedByCharactersInSet:separators];
    
    NSMutableArray<NSString *> *result = [NSMutableArray array];
    for (NSString *word in words) {
        if (word.length > 0) {
            [result addObject:[word lowercaseString]];
        }
    }
    
    return result;
}

- (void)collectWordsWithPrefix:(NSString *)prefix node:(TrieNode *)node prefix:(NSString *)currentPrefix result:(NSMutableArray<NSString *> *)result {
    if (prefix.length == 0) {
        if (node.isEnd) {
            [result addObject:[currentPrefix copy]];
        }
        
        // 继续搜索所有子节点
        for (NSString *ch in node.children) {
            [self collectWordsWithPrefix:@"" node:node.children[ch] prefix:[currentPrefix stringByAppendingString:ch] result:result];
        }
        
        return;
    }
    
    NSString *firstChar = [prefix substringToIndex:1];
    NSString *restPrefix = [prefix substringFromIndex:1];
    
    TrieNode *child = node.children[firstChar];
    if (child) {
        [self collectWordsWithPrefix:restPrefix node:child prefix:[currentPrefix stringByAppendingString:firstChar] result:result];
    }
}

@end

这些实际应用展示了如何将LeetCode上的高级数据结构应用到iOS开发的实际场景中，提高应用的性能和用户体验。通过合理选择和组合这些数据结构，可以解决各种复杂的工程问题。

LeetCode实战指南

目录

前言

从iOS到LeetCode：资深开发者的算法实战指南

第一章：数组与字符串算法

1.1 中高难度数组算法

1.1.1 [LeetCode 15] 三数之和（Medium）

1.1.2 [LeetCode 11] 盛最多水的容器（Medium）

1.1.3 [LeetCode 42] 接雨水（Hard）

1.1.4 实际应用：高效内存管理与缓存设计

1.2 字符串处理算法

1.2.1 [LeetCode 5] 最长回文子串（Medium）

1.2.2 [LeetCode 76] 最小覆盖子串（Hard）

1.2.3 [LeetCode 10] 正则表达式匹配（Hard）

1.2.4 实际应用：iOS文本处理与搜索优化

从iOS到LeetCode：资深开发者的算法实战指南

第二章：链表与树结构算法

2.1 链表操作算法

2.1.1 [LeetCode 19] 删除链表的倒数第N个节点（Medium）

2.1.2 [LeetCode 142] 环形链表II（Medium）

2.1.3 [LeetCode 23] 合并K个排序链表（Hard）

2.1.4 实际应用：iOS内存管理与数据结构设计

2.2 二叉树算法

2.2.1 [LeetCode 236] 二叉树的最近公共祖先（Medium）

2.2.2 [LeetCode 124] 二叉树中的最大路径和（Hard）

2.2.3 [LeetCode 297] 二叉树的序列化与反序列化（Hard）

2.2.4 实际应用：iOS视图层次结构与组件树管理

从iOS到LeetCode：资深开发者的算法实战指南

第三章：动态规划算法

3.1 基础动态规划

3.1.1 [LeetCode 322] 零钱兑换（Medium）

3.1.2 [LeetCode 300] 最长递增子序列（Medium）

3.1.3 [LeetCode 72] 编辑距离（Hard）

3.1.4 实际应用：iOS应用中的缓存策略与资源预加载

3.2 高级动态规划

3.2.1 [LeetCode 312] 戳气球（Hard）

3.2.2 [LeetCode 10] 正则表达式匹配（Hard）

3.2.3 [LeetCode 115] 不同的子序列（Hard）

3.2.4 实际应用：iOS中的推荐算法与预测模型

从iOS到LeetCode：资深开发者的算法实战指南

第四章：图算法与搜索

4.1 图的表示与基础算法

4.1.1 [LeetCode 207] 课程表（Medium）

4.1.2 [LeetCode 210] 课程表 II（Medium）

4.1.3 [LeetCode 133] 克隆图（Medium）

4.1.4 实际应用：iOS应用中的依赖注入与模块化架构

4.2 高级图算法与搜索

4.2.1 [LeetCode 200] 岛屿数量（Medium）

4.2.2 [LeetCode 127] 单词接龙（Hard）

4.2.3 [LeetCode 329] 矩阵中的最长递增路径（Hard）

4.2.4 实际应用：iOS中的路径规划与空间索引

从iOS到LeetCode：资深开发者的算法实战指南

第五章：高级数据结构

5.1 设计LRU缓存

5.1.1 [LeetCode 146] LRU缓存（Medium）

5.2 设计LFU缓存

5.2.1 [LeetCode 460] LFU缓存（Hard）

5.3 设计Trie前缀树

5.3.1 [LeetCode 208] 实现Trie前缀树（Medium）

5.4 设计并查集

5.4.1 [LeetCode 547] 省份数量（Medium）

5.5 设计线段树

5.5.1 [LeetCode 307] 区域和检索 - 数组可修改（Medium）

5.6 设计跳表

5.6.1 [LeetCode 1206] 设计跳表（Hard）

5.7 实际应用：iOS中的高性能数据结构