iOS算法

作者: Li_Po | 来源:发表于2020-10-20 11:42 被阅读0次
    • 字符串反转

       //调用
       char cha[] = "hello,word";
       char_reverse(cha);
       printf("revers result is %s",cha);
      
       //实现
       void char_reverse(char * cha){
           char * begin = cha;
           char * end = cha + strlen(cha)-1;
           while (begin<end) {
               char temp = *begin;
               *(begin++) = *end;
               *(end--) = temp;
           }
       }
      
    • 链表反转

       //调用
       struct Node * head = constructList();
       printList(head);
       struct Node * newH = reversList(head);
       printList(newH);
      
       //.h文件
       struct Node {
           int data;
           struct Node * next;
       };
       @interface ReversList : NSObject
       //链表反转
       struct Node * reversList(struct  Node * head);
       //构建链表
       struct Node * constructList(void);
       //打印链表中的数据
       void printList(struct Node * head);
       @end
      
       //.m文件
       #import "ReversList.h"
       @implementation ReversList
      
       //链表反转
       struct Node * reversList(struct  Node * head){
           //定义遍历指针,初始化为头节点
           struct Node * p = head;
           //反转后的链表头部
           struct Node * newHead = NULL;
           //遍历链表
           while (p != NULL) {
               // 记录下一个节点
               struct Node * temp = p->next;
               //当前节点指的next指向新的链表头部
               p->next = newHead;
               //更改新链表头部为当前节点
               newHead = p;
               //移动p指针
               p = temp;
           }
           
           //返回反转后的头节点
           return newHead;
       }
       //构建链表
       struct Node * constructList(void){
           //头节点定义
           struct Node * head = NULL;
           //记录当前尾节点
           struct Node * cur = NULL;
           
           for (int i=1; i<5; 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;
           
       }
       //打印链表中的数据
       void printList(struct Node * head){
           struct Node * tmp = head;
           while (tmp != NULL) {
               printf("node id %d \n",tmp->data);
               tmp = tmp->next;
           }
       }
       @end
      
    • 有序数组合并

            //有序数组合并  归并算法 调用
            int a[5] = {1,4,6,7,9};
            int b[8] = {2,3,5,6,8,10,11,12};
            int result[13];
            mergeList(a, 5, b, 8, result);
            for (int i=0; i<13; i++) {
                printf("%d,",result[I]);
            }
        //有序数组合并  归并算法 实现
        void mergeList(int a[],int aLen,int b[],int bLen,int result[]){
            int p = 0;
            int q = 0;
            int i = 0;
            while (p<aLen && q<bLen) {
                if (a[p]<=b[q]) {
                    result[i] = a[p++];
                }else{
                    result[i] = b[q++];
                }
                I++;
            }
            while (p<aLen) {
                result[i] = a[p++];
                I++;
            }
            while (q<bLen) {
                result[i] = b[q++];
                I++;
            }
        }
      
    • hash 哈希算法

           char cha[] = "abaccdef";
           char result = findFirstChar(cha);
           printf("this is %c",result);
      
       //hash 哈希算法 找出第一个只出现一次的字母
       char findFirstChar(char * cha){
           char result = '\0';
           int array[256];
           for (int i=0; i<256; i++) {
               array[i] = 0;
           }
           char *p = cha;
           while (*p != '\0') {
               array[*(p++)]++;
           }
           p = cha;
           while (*p != '\0') {
               if (array[*p]==1) {
                   result = *p;
                   break;
               }
               p++;
           }
           return result;
       }
      
    • 查找无需数组的中位数
      1.排序算法+中位数
      当数组个数n为基数时:中位数=array[(n/2)]
      当数组个数n为偶数时:中位数=(array[(n/2-1)]+array[(n/2)])/2
      2.利用快排思想

    image.png
          //利用快排思想求中位数
          |2|4|6|8|
          //调用
            int list[9] = {12,3,10,8,6,7,11,13,9};
            int median = medianFind(list, 9);
            printf("the median is %d",median);
            
          //求一个无需数组的我中位数
        int medianFind(int a[],int len)
        {
            int low = 0;
            int high = len-1;
            
            int mid = (len-1)/2;
            int div = PartSort(a,low,high);
            
            while (div != mid) {
                if (mid<div) {
                    //左半区查找
                    div = PartSort(a,low,div-1);
                }else{
                    //右半区查找
                    div = PartSort(a,div+1,high);
                }
            }
            //找到了
            return a[mid];
        }
    
        //
        int PartSort(int a[],int start,int end){
            int low = start;
            int high = end;
            
            int key = a[end];
            while (low<high) {
                //左边找比key大的值
                while (low<high&& a[low]<=key) {
                    ++low;
                }
                //右边找比key小的值
                while (low<high&& a[end]>=key) {
                    --high;
                }
                //找到之后交换左右的值
                if (low<high) {
                    int tmp = a[low];
                    a[low] = a[high];
                    a[high] = tmp;
                }
            }
            
            int tmp = a[high];
            a[high] = a[end];
            a[end] = tmp;
            
            return low;
        }
    
    • 查找两个子视图共同所有的父视图

        -(NSArray<UIView *> *)findCommonSuperView:(UIView *)view1 :(UIView *)view2{
            NSArray * arr1 = [self findSuperView:view1];
            NSArray * arr2 = [self findSuperView:view2];
            
            NSMutableArray * results = [NSMutableArray array];
            
            int I=0;
            
            while (i<MIN(arr1.count, arr2.count)) {
                if (arr1[arr1.count-i-1] == arr2[arr2.count-i-1]) {
                    [results addObject:arr1[arr1.count-i-1]];
                    I++;
                }else{
                    break;
                }
            }
            return results;
            
        }
        -(NSArray<UIView *> *)findSuperView:(UIView *)view{
            NSMutableArray * results = [NSMutableArray array];
            UIView * v1 = view.superview;
            while (v1) {
                [results addObject:v1];
                v1 = v1.superview;
            }
            return results;
        }
      
    • m*n的矩阵点(m>0,n>0),m为x坐标,n为y坐标(x轴向右,y轴向下),从(0,0)位置,初始方向向右移动,移动到边或者下一节点已经走过时,需要改变方向,改变的顺序为顺时针。
      求最后走到的点坐标。

      #import "matrixObject.h"
       @interface matrixObject()
       @property (nonatomic,strong)NSMutableArray * poinaArray;
       @end
       @implementation matrixObject
       - (instancetype)init
       {
           self = [super init];
           if (self) {
               _poinaArray =  [NSMutableArray array];
               [self testSatrtArray:@[@0,@0] endArray:@[@3,@3]];//调用
           }
           return self;
       }
      
       #pragma mark -- 递归
       -(void)testSatrtArray:(NSArray *)startArray endArray:(NSArray *)pointArray{
           //起点(startX,startY) 矩阵点(m,n) 移动的点(x,y)
           int x= [startArray[0] intValue];
           int startX= [startArray[0] intValue];
           
           int y = [startArray[1] intValue];
           int startY = [startArray[1] intValue];
           
           int m = [pointArray[0] intValue];
           int n = [pointArray[1] intValue];
      
           while (x<m && y<n) {
               NSString * pointStr = [NSString stringWithFormat:@"%d,%d",x,y];
      
               if (![_poinaArray containsObject: pointStr]) {
                   if (x<m && y<n) {
                       //向右移动 x++
                       while (x<m) {
                           [_poinaArray addObject:[NSString stringWithFormat:@"%d,%d",x,y]];
                           x++;
                       }
                   }
                   if (x==m && y<n) {
                       //向下移动 y++
                       while (y<n) {
                           [_poinaArray addObject:[NSString stringWithFormat:@"%d,%d",x,y]];
                           y++;
                       }
                   }
                   if (x==m && y==n) {
                       //向左移动 x--
                       while (x>startX) {
                           [_poinaArray addObject:[NSString stringWithFormat:@"%d,%d",x,y]];
                           x--;
                       }
      
                   }
                   if (x==startX && y==n) {
                       //向上移动 y--
                       while (y>startY) {
                           [_poinaArray addObject:[NSString stringWithFormat:@"%d,%d",x,y]];
                           y--;
                       }
                   }
               }else{
                   ++x;
                   ++y;
                   --m;
                   --n;
                   if (x<m && y<n) {
                       [self testSatrtArray:@[@(x),@(y)] endArray:@[@(m),@(n)]];
                   }else{
                       if (x==m && y==n) {//当起点和矩阵点相同时只记录原点
                           [_poinaArray addObject:[NSString stringWithFormat:@"%d,%d",x,y]];
                       }
                       NSLog(@"最后走到的点坐标:%@",[_poinaArray lastObject]);//(1,2)
                       NSLog(@"x:%d y:%d   m:%d n:%d  \n _poinaArray:(%@)",x,y,m,n,[_poinaArray componentsJoinedByString:@")("]);
                       //x:2 y:2   m:1 n:1
                       //_poinaArray:(0,0)(1,0)(2,0)(3,0)(3,1)(3,2)(3,3)(2,3)(1,3)(0,3)(0,2)(0,1)(1,1)(2,1)(2,2)(1,2)
                       break;
                   }
               }
           };
       }
      
       @end

    相关文章

      网友评论

          本文标题:iOS算法

          本文链接:https://www.haomeiwen.com/subject/wbykmktx.html