iOS---算法相关

  • 字符串反转
  • 链表反转
  • 有序数组合并
  • Hash算法
  • 查找两个子视图的共同父视图
  • 求无序数组当中的中位数

一、字符串反转
给定字符串 "hello,world",实现将其反转。输出结果：dlrow,olleh

- (void)charReverse
{
    NSString * string = @"hello,world";
    
    NSLog(@"%@",string);
    
    NSMutableString * reverString = [NSMutableString stringWithString:string];
    
    for (NSInteger i = 0; i < (string.length + 1)/2; i++) {
        
        [reverString replaceCharactersInRange:NSMakeRange(i, 1) withString:[string substringWithRange:NSMakeRange(string.length - i - 1, 1)]];
        
        [reverString replaceCharactersInRange:NSMakeRange(string.length - i - 1, 1) withString:[string substringWithRange:NSMakeRange(i, 1)]];
    }
    
    NSLog(@"reverString:%@",reverString);
    
    //C
    char ch[100];
    
    memcpy(ch, [string cStringUsingEncoding:NSUTF8StringEncoding], [string length]);

   //设置两个指针，一个指向字符串开头，一个指向字符串末尾
    char * begin = ch;
    
    char * end = ch + strlen(ch) - 1;
   
//遍历字符数组，逐步交换两个指针所指向的内容，同时移动指针到对应的下个位置，直至begin>=end 
    while (begin < end) {
        
        char temp = *begin;
        
        *(begin++) = *end;
        
        *(end--) = temp;
    }
    
    NSLog(@"reverseChar[]:%s",ch);
}

二、链表反转
反转前：1->2->3->4->NULL
反转后：4->3->2->1->NULL

/**  定义一个链表  */
struct Node {
    
    NSInteger data;
    
    struct Node * next;
};

- (void)listReverse
{
    struct Node * p = [self constructList];
    
    [self printList:p];
    
    //反转后的链表头部
    struct Node * newH = NULL;
    //头插法
    while (p != NULL) {
        
        //记录下一个结点
        struct Node * temp = p->next;
        //当前结点的next指向新链表的头部
        p->next = newH;
        //更改新链表头部为当前结点
        newH = p;
        //移动p到下一个结点
        p = temp;
    }
    
    [self printList:newH];
}
/**
 打印链表

 @param head 给定链表
 */
- (void)printList:(struct Node *)head
{
    struct Node * temp = head;
    
    printf("list is : ");
    
    while (temp != NULL) {
        
        printf("%zd ",temp->data);
        
        temp = temp->next;
    }
    
    printf("\n");
}


/**  构造链表  */
- (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{
            //当前结点的next为尾结点
            cur->next = node;
        }
        
        //设置当前结点为新结点
        cur = node;
    }
    
    return head;
}

三、有序数组合并
将有序数组 {1,4,6,7,9} 和 {2,3,5,6,8,9,10,11,12} 合并为
{1,2,3,4,5,6,6,7,8,9,9,10,11,12}

- (void)orderListMerge
{
    int aLen = 5,bLen = 9;
    
    int a[] = {1,4,6,7,9};
    
    int b[] = {2,3,5,6,8,9,10,11,12};
    
    [self printList:a length:aLen];
    
    [self printList:b length:bLen];
    
    int result[14];
    
    int p = 0,q = 0,i = 0;//p和q分别为a和b的下标，i为合并结果数组的下标
    
    //任一数组没有达到s边界则进行遍历
    while (p < aLen && q < bLen) {
        
        //如果a数组对应位置的值小于b数组对应位置的值,则存储a数组的值，并移动a数组的下标与合并结果数组的下标
        if (a[p] < b[q]) result[i++] = a[p++];
        
        //否则存储b数组的值，并移动b数组的下标与合并结果数组的下标
        else result[i++] = b[q++];
    }
    
    //如果a数组有剩余，将a数组剩余部分拼接到合并结果数组的后面
    while (++p < aLen) {
        
        result[i++] = a[p];
    }
    
    //如果b数组有剩余，将b数组剩余部分拼接到合并结果数组的后面
    while (q < bLen) {
        
        result[i++] = b[q++];
    }
    
    [self printList:result length:aLen + bLen];
}
- (void)printList:(int [])list length:(int)length
{
    for (int i = 0; i < length; i++) {
        
        printf("%d ",list[i]);
    }
    
    printf("\n");
}

四、HASH算法

  • 哈希表
    例：给定值是字母a，对应ASCII码值是97，数组索引下标为97。
    这里的ASCII码，就算是一种哈希函数，存储和查找都通过该函数，有效地提高查找效率。
  • 在一个字符串中找到第一个只出现一次的字符。如输入"abaccdeff"，输出'b'
    字符(char)是一个长度为8的数据类型，因此总共有256种可能。每个字母根据其ASCII码值作为数组下标对应数组种的一个数字。数组中存储的是每个字符出现的次数。
- (void)hashTest
{
    NSString * testString = @"hhaabccdeef";
    
    char testCh[100];
    
    memcpy(testCh, [testString cStringUsingEncoding:NSUTF8StringEncoding], [testString 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++;
    }
    
    printf("result:%c",result);
}

五、查找两个子视图的共同父视图
思路:分别记录两个子视图的所有父视图并保存到数组中，然后倒序寻找,直至找到第一个不一样的父视图。

- (void)findCommonSuperViews:(UIView *)view1 view2:(UIView *)view2
{
    NSArray * superViews1 = [self findSuperViews:view1];
    
    NSArray * superViews2 = [self findSuperViews:view2];
    
    NSMutableArray * resultArray = [NSMutableArray array];
    
    int i = 0;
    
    while (i < MIN(superViews1.count, superViews2.count)) {
        
        UIView *super1 = superViews1[superViews1.count - i - 1];
        
        UIView *super2 = superViews2[superViews2.count - i - 1];
        
        if (super1 == super2) {
            
            [resultArray addObject:super1];
            
            i++;
            
        }else{
            
            break;
        }
    }
    
    NSLog(@"resultArray:%@",resultArray);
    
}
- (NSArray <UIView *>*)findSuperViews:(UIView *)view
{
    UIView * temp = view.superview;
    
    NSMutableArray * result = [NSMutableArray array];
    
    while (temp) {
        
        [result addObject:temp];
        
        temp = temp.superview;
    }
    
    return result;
}

六、求无序数组中的中位数
中位数：当数组个数n为奇数时，为(n + 1)/2，即是最中间那个数字；当n为偶数时，为(n/2 + (n/2 + 1))/2,即是中间两个数字的平均数。
首先要先去了解一些几种排序算法:iOS排序算法
思路:

  • 1.排序算法+中位数
    首先用冒泡排序、快速排序、堆排序、希尔排序等排序算法将所给数组排序，然后取出其中位数即可。
  • 2.利用快排思想
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,921评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,635评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,393评论 0赞 338
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,836评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,833评论 5赞 368
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,685评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,043评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,694评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 42,671评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,670评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,779评论 1赞 332
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,424评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,027评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,984评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,214评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,108评论 2赞 351
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,517评论 2赞 343