iOS之【算法调试一二叉树、快排】

作者: NJ_墨 | 来源:发表于2020-05-24 22:43 被阅读0次

iOS之【算法调试一二叉树、快排】
iOS算法之快排
iOS之【算法快排、堆排】
iOSer必须了解的数据结构
京东高级java现场三面，包含：算法、数据库、设计模式、java
数据结构与算法
Java基础算法：堆排，快排，二分查找
排序算法之快排
排序算法之快排
iOS开发之Xcode常用调试技巧总结

import "TestArithmetic.h"

@interface TreeNode : NSObject

@property (nonatomic, assign) NSInteger value;
@property (nonatomic, copy) NSString    *valueString;

@property (nonatomic, strong) TreeNode *left;
@property (nonatomic, strong) TreeNode *right;

@end

@implementation TreeNode
    

@end

@implementation TestArithmetic

<数组中任意找两个数，看其和是否=sum>

/**
【方法一】穷举法

从数组中任意找两个数，看其和是否=sum。时间复杂度O(N^2)


【方法二】先排序，然后定义两个指针，一个i=0指向数组头，一个j=len-1指向数组的尾，看其和是否==sum；若==，则查找成功返回；若>sum，则尾指针j--；若<sum，则头指针i++。

时间复杂度：快排O(NlogN)，查找O(N)；所以总的时间复杂度为：O(NlogN)
 
 【方法三】hash表
 给定一个数，根据hash表查找另一个数只需要O(1)的时间。但需要空间换时间，空间复杂度为O(n)；
*/
- (void)testABEqual0 {
    NSArray *testNums = @[@"-1",@"-1",@"0",@"1",@"2"];
    NSInteger sum = 3;

    for (NSInteger i=0, j=testNums.count-1; i<j; ) {
        if ([testNums[i] integerValue] + [testNums[j] integerValue] == sum) {
            NSLog(@"---%@ %@",testNums[i],testNums[j]);
            return;
        } else if([testNums[i] integerValue] + [testNums[j] integerValue] < sum){
            i++;
        } else {
            j--;
        }
    }
    
}

<abc三和为0的集合>

- (void)testABCEqual0{
    NSArray *testNums = @[@"-1",@"-1",@"0",@"1",@"2"];

    NSMutableArray *resutl = [[NSMutableArray alloc] init];
    
    for (int i=0; i<testNums.count; i++) {
        NSInteger target = -[testNums[i] integerValue];
        
        if (target < 0) {
            break;
        }
        if (i>0 && [testNums[i] isEqualToString:testNums[i-1]]) {
            continue;
        }
        
        NSInteger j = i + 1;
        NSInteger k = testNums.count-1;
        while (j < k) {
            if ([testNums[j] integerValue] + [testNums[k] integerValue] == target) {
                while (j<k && [testNums[j] isEqualToString:testNums[j+1]]) {
                    ++j;
                }
                while (j<k && [testNums[k] isEqualToString:testNums[k-1]]) {
                    --k;
                }
                NSArray *tempArr = @[testNums[i],testNums[j++],testNums[k--]];
                [resutl addObject:tempArr];
                
            } else if([testNums[j] integerValue] + [testNums[k] integerValue] < target) {
                j++;
            } else {
                k--;
            }
        }
    }
    
    NSLog(@"----abc三和为0的集合：%@",resutl);
}

<字符串之出现一次第一个字符>

- (void)testShowOneTimeAbced {
    NSString *testAbc = @"hhaabcddefgghkmkzw";
    char testCh[100];
    memcpy(testCh,[testAbc cStringUsingEncoding:NSUTF8StringEncoding],[testAbc length]);
    int list[256];
    for (int i=0; i<256; i++) {
        list[i] = 0;
    }
    
    char *p = testCh;
    char result = '\0';
    while (*p != result) {
        list[*(p++)]++;
    }
    
    p = testCh;
    while (*p != result) {
        if (list[*p] == 1) {
            result = *p;
            break;
        }
        p++;
    }
    NSLog(@"字符串之出现一次第一个字符： %c %i",result,*list);
}

<链表翻转>

struct Node {
    NSInteger data;
    struct Node * next;
};

- (void)testListReverse {
    struct Node *p = [self constructList];
    [self pirntList:p];
    
    struct Node *newH = NULL;
    while (p != NULL) {
        struct Node *temp = p->next;
        p->next = newH;
        newH = p;
        p = temp;
    }
    [self pirntList:newH];

}

- (struct Node *)constructList {
    struct Node *head = NULL;
    struct Node *cur = NULL;
    
    for (NSInteger i=0; i<10; i++) {
        struct Node *node = malloc(sizeof(struct Node));
        node->data = i;
        if (head == NULL) {
            head = node;
        } else {
            cur->next = node;
        }
        
        cur = node;
    }
    return head;
}

- (void)pirntList:(struct Node *)head {
    struct Node *temp = head;
    NSLog(@"list is : ");
    
//    while (temp != NULL) {
//        if (temp) {
//            NSLog(@"%zd",temp->data);
//            temp = temp->next;
//        }
//    }
    NSLog(@"\n");
}

#####<创建二叉树>
- (TreeNode *)createMidTreeArray {
    
    TreeNode *treeNode = [[TreeNode alloc] init];
    NSArray *arr = @[@"1",@"",@"2",@"3",@"4",@"5",@"",@"6"];
    for (NSString *str in arr) {
        [self createTreeStr:str treeModel:treeNode];
    }
    
    return treeNode;
}

- (void)createTreeStr:(NSString *)value treeModel:(TreeNode *)model {
    if (!model.valueString && [value isEqualToString:@""]) {
        model.valueString = @"";
        return;
    } else if(!model.valueString) {
        model.valueString = value;
        return;
    } else if([model.valueString isEqualToString:@""]) {
        return;
    } else if(model.valueString) {
        
        if (!model.left) {
            model.left = [[TreeNode alloc] init];
            model.left.valueString = value;
        } else if(model.left && model.left.valueString && ![model.left.valueString isEqualToString:@""]) {
            [self createTreeStr:value treeModel:model.left];
               
        }  else if(!model.right) {
            model.right = [[TreeNode alloc] init];
            model.right.valueString = value;
        }else if(model.right && model.right.valueString && ![model.right.valueString isEqualToString:@""]) {
            [self createTreeStr:value treeModel:model.right];
        }
    }
}

- (void)testTree {
    [self createTreeArray];
}

<二叉树翻转>

输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1

- (void)testTreeInvert {
    TreeNode *rootTree = [self createTreeArray];
    [self invertTree:rootTree];
    NSLog(@"--- %@",rootTree);
    
}

- (void)invertTree:(TreeNode *)rootTree {
    if (!rootTree) {
        return;
    }
    TreeNode *tempNode = rootTree.left;
    rootTree.left = rootTree.right;
    rootTree.right = tempNode;
    [self invertTree:rootTree.left];
    [self invertTree:rootTree.right];
}

<前序递归、迭代>

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
简单说其遍历顺序就是:根--左--右

- (void)forwardSortTree {
    TreeNode *treeNode = [self createTreeArray];
    NSMutableArray *results = [[NSMutableArray alloc] init];
    [self forwardTreeResults:results treeNode:treeNode];
    
    NSString *resutlString = [results componentsJoinedByString:@","];
    NSLog(@"---前序递归：%@",resutlString);
    
    NSMutableArray *resultsTwo = [[NSMutableArray alloc] init];
    NSMutableArray *tempArray = [[NSMutableArray alloc] init];
    
    while (treeNode) {
        [resultsTwo addObject:[NSString stringWithFormat:@"%li",(long)treeNode.value]];
        
        if (treeNode.left) {
            
            if (treeNode.right) {
                [tempArray addObject:treeNode.right];
            }
            treeNode = treeNode.left;
            
            if (!treeNode.left && !treeNode.right) {
                [resultsTwo addObject:[NSString stringWithFormat:@"%li",(long)treeNode.value]];
                treeNode = tempArray.lastObject;
                if (tempArray.count > 0) {
                    [tempArray removeLastObject];
                }
            } else if(!treeNode.left && treeNode.right) {
                [resultsTwo addObject:[NSString stringWithFormat:@"%li",(long)treeNode.value]];
                treeNode = treeNode.right;
            }
            
        } else if(treeNode.right) {
            
            treeNode = treeNode.right;
            if (!treeNode.left && !treeNode.right) {
                [resultsTwo addObject:[NSString stringWithFormat:@"%li",(long)treeNode.right.value]];
                treeNode = tempArray.lastObject;
                if (tempArray.count > 0) {
                    [tempArray removeLastObject];
                }
            }
            
        } else {
            
            treeNode = tempArray.lastObject;
            if (tempArray.count > 0) {
                [tempArray removeLastObject];
            }
        }
    }
    
    NSString *resutlStringTwo = [resultsTwo componentsJoinedByString:@","];
    NSLog(@"---前序迭代：%@",resutlStringTwo);
}


- (void)forwardTreeResults:(NSMutableArray *)resultes treeNode:(TreeNode *)node {
    
    if (node.value) {
        [resultes addObject:[NSString stringWithFormat:@"%li",(long)node.value]];
    }
    if (node.left) {
        [self forwardTreeResults:resultes treeNode:node.left];
    }
    if (node.right) {
        [self forwardTreeResults:resultes treeNode:node.right];
    }
    return;
}

- (void)forwardSortTreeTwo{
    TreeNode *treeNode = [self createTreeArray];
    NSMutableArray *resultsTwo = [[NSMutableArray alloc] init];
    NSMutableArray *tempArray = [[NSMutableArray alloc] init];
    
    while (treeNode) {
        [resultsTwo addObject:[NSString stringWithFormat:@"%li",(long)treeNode.value]];

        if (!treeNode.left && !treeNode.right) {
            treeNode = tempArray.lastObject;
            [tempArray removeLastObject];
        } else if(treeNode.left) {
            if (treeNode.right) {
                [tempArray addObject:treeNode.right];
            }
            treeNode = treeNode.left;
        } else if(treeNode.right) {
            treeNode = treeNode.right;
        }
    }
    
    NSString *resutlStringTwo = [resultsTwo componentsJoinedByString:@","];
    NSLog(@"---前序迭代2：%@",resutlStringTwo);

}

- (void)forwardSortTreeThree {
    TreeNode *treeNode = [self createTreeArray];
    NSMutableArray *resultsTwo = [[NSMutableArray alloc] init];
    NSMutableArray *tempArray = [[NSMutableArray alloc] init];
    
    while (treeNode || tempArray.count) {
        while (treeNode) {
            [resultsTwo addObject:[NSString stringWithFormat:@"%li",(long)treeNode.value]];
            [tempArray addObject:treeNode];
            treeNode = treeNode.left;
        }
        
        if (tempArray.count) {
            treeNode = tempArray.lastObject;
            [tempArray removeLastObject];
            treeNode = treeNode.right;
        }
    }
    
    NSString *resutlStringTwo = [resultsTwo componentsJoinedByString:@","];
    NSLog(@"---前序迭代3：%@",resutlStringTwo);
}

<二叉树中序递归、迭代>

中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。若二叉树为空则结束返回，否则：
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树
简单说其遍历顺序就是:左--根--右

- (void)minSort {
    [self createMidTreeArray];
    
        TreeNode *treeNode = [self createTreeArray];
    NSMutableArray *results = [[NSMutableArray alloc] init];
    [self mindSortTreeResults:results treeNode:treeNode];
    NSString *resutlString = [results componentsJoinedByString:@","];
    NSLog(@"---中序递归1：%@",resutlString);
    
    // 方法二 太复杂
    NSMutableArray *resultsTwo = [[NSMutableArray alloc] init];
    NSMutableArray *tempArrays = [[NSMutableArray alloc] init];

    [tempArrays addObject:treeNode];
    while (treeNode) {
        
        TreeNode *leftNode = treeNode.left;
        while (leftNode) {
            [tempArrays addObject:leftNode];
            if (!leftNode.left) {
                treeNode = leftNode;
            }
            leftNode = leftNode.left;
        }

        if (treeNode.right) {
            if (!treeNode.left) {
                [resultsTwo addObject:[NSString stringWithFormat:@"%ld",(long)treeNode.value]];
            }
            [tempArrays removeLastObject];
            [tempArrays addObject:treeNode.right];
            treeNode = treeNode.right;

        } else {

            [resultsTwo addObject:[NSString stringWithFormat:@"%ld",(long)treeNode.value]];
            [tempArrays removeLastObject];
            if (tempArrays.count == 0) {
                break;
            }
            treeNode = tempArrays.lastObject;
            [resultsTwo addObject:[NSString stringWithFormat:@"%ld",(long)treeNode.value]];
            
            while (treeNode && !treeNode.right) {
                [tempArrays removeLastObject];
                treeNode = tempArrays.lastObject;
                if (treeNode) {
                    [resultsTwo addObject:[NSString stringWithFormat:@"%ld",(long)treeNode.value]];
                }
            }
            
            if (treeNode.right) {
                if (tempArrays.count > 0) {
                    [tempArrays removeLastObject];
                }
                treeNode = treeNode.right;
                [tempArrays addObject:treeNode];
            }
        }
    }
    
    NSString *resutlStringTwo = [resultsTwo componentsJoinedByString:@","];
       NSLog(@"---中序迭代2：%@",resutlStringTwo);
    
    
    // 方法三
    treeNode = [self createTreeArray];
    NSMutableArray *resultsThree = [[NSMutableArray alloc] init];
    [tempArrays removeAllObjects];
    while (treeNode || tempArrays.count) {
        while (treeNode) {
            [tempArrays addObject:treeNode];
            treeNode = treeNode.left;
        }
        
        if (tempArrays.count) {
            treeNode = tempArrays.lastObject;
            [tempArrays removeLastObject];
            [resultsThree addObject:[NSString stringWithFormat:@"%ld",(long)treeNode.value]];
            treeNode = treeNode.right;
        }
    }
    
    NSString *resutlStringThree = [resultsThree componentsJoinedByString:@","];
    NSLog(@"---中序迭代3：%@",resutlStringThree);

}

- (void)mindSortTreeResults:(NSMutableArray *)results treeNode:(TreeNode *)node {
    
    if (node.left) {
        [self mindSortTreeResults:results treeNode:node.left];
    }
    
    [results addObject:[NSString stringWithFormat:@"%ld",(long)node.value]];
    
    if (node.right) {
        [self mindSortTreeResults:results treeNode:node.right];
    }
    return;
}

<二叉树后序递归、迭代>

后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即：
若二叉树为空则结束返回，否则：
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根结点
简单说其遍历顺序就是:左--右--根

- (void)postorderTraversal {
    TreeNode *treeNode = [self createTreeArray];
    NSMutableArray *results = [self postorderHelper:treeNode results:[[NSMutableArray alloc] init]];
    NSString *resutlString = [results componentsJoinedByString:@","];
    NSLog(@"---后序递归：%@",resutlString);
    
    //方法二 迭代
    NSMutableArray *resultsTwo = [[NSMutableArray alloc] init];
    NSMutableArray *tempArrays = [[NSMutableArray alloc] init];
    TreeNode *tempNode;
    
    if (treeNode) {
        [tempArrays addObject:treeNode];
        while (tempArrays.count) {
            treeNode = tempArrays.lastObject;
            
            if ((!treeNode.left && !treeNode.right) || (tempNode && (tempNode == treeNode.left || tempNode == treeNode.right))) {
                [tempArrays removeLastObject];
                [resultsTwo addObject:[NSString stringWithFormat:@"%ld",(long)treeNode.value]];
                tempNode = treeNode;
                
            } else {
                if (treeNode.right) {
                    [tempArrays addObject:treeNode.right];
                }
                if (treeNode.left) {
                    [tempArrays addObject:treeNode.left];
                }
                
            }
        }
    }
    
    NSString *resutlStringTwo = [resultsTwo componentsJoinedByString:@","];
    NSLog(@"---后序迭代：%@",resutlStringTwo);
    
}

- (NSMutableArray *)postorderHelper:(TreeNode *)treeNode results:(NSMutableArray *)result {
    if (!treeNode) {
        return result;
    }
    [self postorderHelper:treeNode.left results:result];
    [self postorderHelper:treeNode.right results:result];
    [result addObject:[NSString stringWithFormat:@"%ld",(long)treeNode.value]];
    return result;
}

- (TreeNode *)createTreeArray {
    
    TreeNode *treeNode = [[TreeNode alloc] init];
    NSArray *arr = @[@"4",@"2",@"7",@"6",@"3",@"8",@"9",@"11",@"5",@"1",@"6",@"10"];
    for (int i=0; i<arr.count; i++) {
        [self createTree:[arr[i] integerValue] treeModel:treeNode];
    }
    return treeNode;
}

//NSArray *arr = @[@"4",@"2",@"7",@"6",@"3",@"8",@"9",@"11",@"5",@"1",@"6",@"10"];
 
//-------------------4--------------------------------//
//-----------------/--\-------------------------------//
//----------------2---------------7-------------------//
//--------------/--\------------/--\------------------//
//-------------1----3----------6----8-----------------//
//----------------------------/-\-----\---------------//
//---------------------------5---6-----9--------------//
//---------------------------------------\------------//
//----------------------------------------11----------//
//---------------------------------------/------------//
//--------------------------------------10-----------//
- (void)createTree:(NSInteger)value treeModel:(TreeNode *)model {
    if (model.value <= 0) {
        model.value = value;
        return;
    }
    
    NSInteger midValue = model.value;
    if (value < midValue) {
        if(model.left == nil) {
            model.left = [[TreeNode alloc] init];
            model.left.value = value;
            return;
        } else {
            [self createTree:value treeModel:model.left];
        }
    } else {
        if (model.right == nil || model.right.value == 0) {
            model.right = [[TreeNode alloc] init];
            model.right.value = value;
            return;
        } else {
            [self createTree:value treeModel:model.right];
        }
    }
}

<快速排序>

- (NSArray *)quickSort:(NSArray *)sort {
    
    if (![sort isKindOfClass:[NSArray class]]) {
        return @[];
    }
    if (sort.count < 2) {
        return sort;
    }
    
    NSMutableArray *mutSort = [[NSMutableArray alloc] initWithArray:sort];
    
    NSMutableArray *leftArray = [[NSMutableArray alloc] init];
    NSMutableArray *rightArray = [[NSMutableArray alloc] init];
    
    if (sort.count > 3) {//长度大于3的数组值得使用随机锚点
        int midIndex = arc4random()%mutSort.count;
        //将随机找到的元素与位置为0的元素交换
        [mutSort exchangeObjectAtIndex:0 withObjectAtIndex:midIndex];
    }
    
    //设定锚点为位置0的元素，在这用固定位置的锚也是可行的，但易被特殊数据针对
    int mid = [mutSort[0] intValue];
    for (int i=1; i<mutSort.count; i++) {
        if ([mutSort[i] intValue] < mid) {
            //当元素小于锚点值 就把它推入左边
            [leftArray addObject:mutSort[i]];
        } else {
            //大于或等于锚点值的元素推入右边
            [rightArray addObject:mutSort[i]];
        }
    }
    
    NSMutableArray *resultArray = [[NSMutableArray alloc] init];

    //递归左右段，最后将所有锚点拼起来
    [resultArray addObjectsFromArray: [self quickSort:leftArray]];
    [resultArray addObject:mutSort[0]];
    [resultArray addObjectsFromArray: [self quickSort:rightArray]];

    return resultArray;
    
}

<一个无序数组中第一次出现最多次数的元素>

- (void)firstMoreTimes {
    //一个无序数组中第一次出现最多次数的元素
    NSArray *sourceArray = @[@"a",@"b",@"kk",@"b",@"kk",@"cc",@"kk",@"m",@"cc",@"cc"];
    NSMutableDictionary *containerDic = [[NSMutableDictionary alloc] init];
    __block NSMutableArray *results = [[NSMutableArray alloc] init];
    
    [sourceArray enumerateObjectsUsingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        if (containerDic[obj]) {
            NSInteger count = [containerDic[obj] integerValue] + 1;
            [containerDic setObject:@(count) forKey:obj];
        } else {
            [containerDic setObject:@(1) forKey:obj];
        }
    }];
    
    __block NSInteger tempCount = 1;
    [containerDic.allKeys enumerateObjectsUsingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        if ([containerDic[obj] integerValue] > tempCount) {
            [results removeAllObjects];
            tempCount = [containerDic[obj] integerValue];
            [results addObject:obj];
        } else if([containerDic[obj] integerValue] == tempCount) {
            [results addObject:obj];
        }
    }];
    
    __block NSInteger resultIndex = -1;
    [results enumerateObjectsUsingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        NSInteger index = [sourceArray indexOfObject:obj];
        if(resultIndex == -1) {
            resultIndex = index;
        } else if(index < resultIndex) {
            resultIndex = index;
        }
    }];
    
    NSLog(@"\n-----一个无序数组中第一次出现最多次数的元素: %@",sourceArray[resultIndex]);
    
}

@end

iOS之【算法调试一二叉树、快排】
import "TestArithmetic.h" @implementation TestArithmetic ...
iOS算法之快排
详细代码请参考Algorithm。参考代码比文字好理解。快速排序（Quicksort）是对冒泡排序的一种改进。它...
iOS之【算法快排、堆排】
快排序把数组第一个当作基数，从右开始执行一趟排序得到1.如果当前被选中的值小于基数从左向右填充2.如果当前被选中...
iOSer必须了解的数据结构
数据结构：哈希表、堆、栈、队列、链表、二叉树操作系统（iOS）的堆、栈算法：排序、冒泡、快排、二分查找数...
京东高级java现场三面，包含：算法、数据库、设计模式、java
京东技术面试(一)：算法面试：二叉树怎么实现的知道哪些排序算法快排怎么实现堆排序怎么实现一道算法题：两...
数据结构与算法
今天任务：快排，冒泡，堆排，归并排序，二分查找，二叉树的遍历，二叉树增删查改晚上回去写总结，算法才是灵魂，数据结构...
Java基础算法：堆排，快排，二分查找
Java基础算法：堆排，快排，二分查找 1. 堆排满二叉树：所有叶结点都有同样的深度，每个内部结点都有两个儿子 ...
排序算法之快排
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部...
排序算法之快排
快速排序（Quicksort）是对冒泡排序[https://baike.baidu.com/item/%E5%86...
iOS开发之Xcode常用调试技巧总结
iOS开发之Xcode常用调试技巧总结 iOS开发之Xcode常用调试技巧总结

iOS之【算法调试一二叉树、快排】

import "TestArithmetic.h"

<数组中任意找两个数，看其和是否=sum>

<abc三和为0的集合>

<字符串之出现一次第一个字符>

<链表翻转>

<二叉树翻转>

<前序递归、迭代>

<二叉树中序递归、迭代>

<二叉树后序递归、迭代>

<快速排序>

<一个无序数组中第一次出现最多次数的元素>

相关文章

iOS之【算法调试一二叉树、快排】

iOS算法之快排

iOS之【算法快排、堆排】

iOSer必须了解的数据结构

京东高级java现场三面，包含：算法、数据库、设计模式、java

数据结构与算法

Java基础算法：堆排，快排，二分查找

排序算法之快排

排序算法之快排

iOS开发之Xcode常用调试技巧总结

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读