11 算法

作者: i爱吃土豆的猫 | 来源:发表于2021-03-27 00:59 被阅读0次

LRU 算法

反转二叉树

image.png

声明节点属性

@interface TreeNode : NSObject
@property (nonatomic, assign) NSInteger val;
@property (nonatomic, strong) TreeNode *left;
@property (nonatomic, strong) TreeNode *right;
@end

实现代码:

- (void)exchangeNode:(TreeNode *)node {

    //判断是否存在node节点
    if(node) {
        //交换左右节点
        TreeNode *temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
}

- (TreeNode *)invertTree:(TreeNode *)root{

    //边界条件 递归结束或输入为空情况
    if(!root) {
       return root;
}
    //递归左右子树
    [self invertTree:root.left];
    [self invertTree:root.right];
    //交换左右子节点
    [self exchangeNode:root];
    return root;
}

image.png

头插入发

链表反转

image.png

1.假设两个数组为A和B
2.A和B都是从小到大的顺序进行排列

1.我们可以直接比较两个数组的首元素，哪个小就把这个小元素放入可变数组。
2.把小元素所在的数组中的这个元素删除。
3.继续比较两个数组中的首元素，直到有一个数组为空。那么就停止进行比较。把另外一个不空的数组元素全部放入可变数组中即可。

复杂度
//(2).
//时间复杂度
//T(n) = O(f(n)):用"T(n)"表示，"O"为数学符号，f(n)为同数量级，一般是算法中频度最大的语句频度。
//时间复杂度:T(n) = O(index);

- (void)merge 1{
/*
 有序数组A：1、4、5、8、10...1000000，有序数组B：2、3、6、7、9...999998，A、B两个数组不相互重复，请合并成一个有序数组C，写出代码和时间复杂度。
 */
 //(1).
NSMutableArray *A = [NSMutableArray arrayWithObjects:@4,@5,@8,@10,@15, nil];
 //    NSMutableArray *B = [NSMutableArray arrayWithObjects:@2,@6,@7,@9,@11,@17,@18, nil];
NSMutableArray *B = [NSMutableArray arrayWithObjects:@2,@6,@7,@9,@11,@12,@13, nil];
NSMutableArray *C = [NSMutableArray array];
int count = (int)A.count+(int)B.count;
int index = 0;
for (int i = 0; i < count; i++) {
    if (A[0]<B[0]) {
        [C addObject:A[0]];
        [A removeObject:A[0]];
    }
    else if (B[0]<A[0]) {
        [C addObject:B[0]];
        [B removeObject:B[0]];
    }
    if (A.count==0) {
        [C addObjectsFromArray:B];
        NSLog(@"C = %@",C);
        index = i+1;
        NSLog(@"index = %d",index);
        return;
    }
    else if (B.count==0) {
        [C addObjectsFromArray:A];
        NSLog(@"C = %@",C);
        index = i+1;
        NSLog(@"index = %d",index);
        return;
    }
}
//(2).
//时间复杂度
//T(n) = O(f(n)):用"T(n)"表示，"O"为数学符号，f(n)为同数量级，一般是算法中频度最大的语句频度。
//时间复杂度:T(n) = O(index);
 }

//合并方法 2

- (void)merge2{

//实例化数组 A
NSMutableArray *arrA = [NSMutableArray arrayWithArray:@[@1,@3,@5,@7,@9,@11]];
//实例化数组 B
NSMutableArray *arrB = [NSMutableArray arrayWithArray:@[@8,@15,@17,@20,@22,@35]];
NSMutableArray *marr = [NSMutableArray array];
for(int i = 0; i< 100 ; i++){
    if (arrA[0] < arrB[0]){
        [marr addObject:arrA[0]];
        [arrA removeObject:arrA[0]];
    }else{
        [marr addObject:arrB[0]];
        [arrB removeObject:arrB[0]];
    }
    NSLog(@"已经循环了--->>%d次",i);
    if (arrA.count == 0){
       [marr addObjectsFromArray:arrB];
       NSLog(@"111新数组--->>%@",marr);
       return;
    }
    if (arrB.count == 0){
        [marr addObjectsFromArray:arrA];
        NSLog(@"222新数组---->> %@",marr);
        return;
    }
}

}

能根据传入的数组准确的算出来推荐的方法

- (NSArray *)mergeOrderArrayWithArray: (NSMutableArray *)array1 array2:(NSMutableArray *)array2 {
// 全为空不处理
if (array1.count == 0 && array2.count == 0) {
    return @[];
}
// 一个为空返回另外一个
if (array1.count == 0) {
    return array2;
}
if (array2.count == 0) {
    return array1;
}
NSMutableArray *endArray = [NSMutableArray array];
while (1) {
    if ([array1[0] integerValue] < [array2[0] integerValue]) {
        [endArray addObject:array1[0]];
        [array1 removeObjectAtIndex:0];
    }else  {
        [endArray addObject:array2[0]];
        [array2 removeObjectAtIndex:0];
    }
    if (array1.count==0) {
        [endArray addObjectsFromArray:array2];
        break;
    }
    if (array2.count==0) {
        [endArray addObjectsFromArray:array1];
        break;
    }
}
   return endArray;
}

image.png

- (NSArray <UIView *> *)findCommonSuperView:(UIView *)viewOne other:(UIView *)viewOther{
NSMutableArray *result = [NSMutableArray array];

// 查找第一个视图的所有父视图
NSArray *arrayOne = [self findSuperViews:viewOne];
// 查找第二个视图的所有父视图
NSArray *arrayOther = [self findSuperViews:viewOther];

int i = 0;
// 越界限制条件
while (i < MIN((int)arrayOne.count, (int)arrayOther.count)) {
    // 倒序方式获取各个视图的父视图
    UIView *superOne = [arrayOne objectAtIndex:arrayOne.count - i - 1];
    UIView *superOther = [arrayOther objectAtIndex:arrayOther.count - i - 1];
    
    // 比较如果相等 则为共同父视图
    if (superOne == superOther) {
        [result addObject:superOne];
        i++;
    }
    // 如果不相等，则结束遍历
    else{
        break;
    }
}

return result;
}

- (NSArray <UIView *> *)findSuperViews:(UIView *)view{
// 初始化为第一父视图
UIView *temp = view.superview;
// 保存结果的数组
NSMutableArray *result = [NSMutableArray array];
while (temp) {
    [result addObject:temp];
    // 顺着superview指针一直向上查找
    temp = temp.superview;
}
return result;
}