字符串反轉(zhuǎn)

Q：給定字符串"Hello,world"，實(shí)現(xiàn)將其反轉(zhuǎn)
輸出結(jié)果：dlrow,olleH。

解決思路：使用兩個(gè)指針，一個(gè)指向字符串的首部begin，一個(gè)指向字符串尾部end，遍歷過(guò)程逐漸交換兩個(gè)指針指向的字符，結(jié)束條件begin大于等于end，以下分別為 OC 實(shí)現(xiàn)和C實(shí)現(xiàn)過(guò)程

oc代碼實(shí)現(xiàn)

- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view.

    NSString *str = @"Hello,World";
    NSMutableString *mutableStr = [NSMutableString stringWithString:str];
    NSInteger middle = [str length] / 2;
    for (int i = 0; i <= middle; i++)
    {
        NSString *startStr = [str substringWithRange:NSMakeRange(i, 1)];
        NSString *endStr = [str substringWithRange:NSMakeRange([str length] - 1 - i, 1)];
        [mutableStr replaceCharactersInRange:NSMakeRange(i, 1) withString:endStr];
        [mutableStr replaceCharactersInRange:NSMakeRange([str length] - 1 - i, 1) withString:startStr];
    }
    NSLog(@"%@",mutableStr);
}

C代碼實(shí)現(xiàn)

- (void)charReverse
{
    NSString * string = @"hello,world";

    char ch[100];
    memcpy(ch, [string cStringUsingEncoding:NSUTF8StringEncoding], [string length]);

   //設(shè)置兩個(gè)指針，一個(gè)指向字符串開頭，一個(gè)指向字符串末尾
    char * begin = ch
    char * end = ch + strlen(ch) - 1;

//遍歷字符數(shù)組，逐步交換兩個(gè)指針?biāo)赶虻膬?nèi)容，同時(shí)移動(dòng)指針到對(duì)應(yīng)的下個(gè)位置，直至begin>=end 
    while (begin < end) 
        char temp = *begin;
        *(begin++) = *end;
        *(end--) = temp;
    }

    NSLog(@"reverseChar[]:%s",ch);
}

鏈表反轉(zhuǎn)

反轉(zhuǎn)前：1->2->3->4->NULL
反轉(zhuǎn)后：4->3->2->1->NULL

/**  定義一個(gè)鏈表  */
struct Node {

    NSInteger data;

    struct Node * next;
};

- (void)listReverse
{
    struct Node * p = [self constructList];

    [self printList:p];

    //反轉(zhuǎn)后的鏈表頭部
    struct Node * newH = NULL;
    //頭插法
    while (p != NULL) {

        //記錄下一個(gè)結(jié)點(diǎn)
        struct Node * temp = p->next;
        //當(dāng)前結(jié)點(diǎn)的next指向新鏈表的頭部
        p->next = newH;
        //更改新鏈表頭部為當(dāng)前結(jié)點(diǎn)
        newH = p;
        //移動(dòng)p到下一個(gè)結(jié)點(diǎn)
        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");
}

/**  構(gòu)造鏈表  */
- (struct Node *)constructList
{
    //頭結(jié)點(diǎn)
    struct Node *head = NULL;
    //尾結(jié)點(diǎn)
    struct Node *cur = NULL;

    for (NSInteger i = 0; i < 10; i++) {

        struct Node *node = malloc(sizeof(struct Node));

        node->data = i;

        //頭結(jié)點(diǎn)為空，新結(jié)點(diǎn)即為頭結(jié)點(diǎn)
        if (head == NULL) {

            head = node;

        }else{
            //當(dāng)前結(jié)點(diǎn)的next為尾結(jié)點(diǎn)
            cur->next = node;
        }

        //設(shè)置當(dāng)前結(jié)點(diǎn)為新結(jié)點(diǎn)
        cur = node;
    }

    return head;
}

有序數(shù)組合并

以下為有序數(shù)組合并的OC實(shí)現(xiàn)

- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view.

    NSMutableArray *totalArray = [NSMutableArray array];
    NSInteger index1 = 0;
    NSInteger index2 = 0;
    while (index1 < [firstArray count] && index2 < [secondArray count])
    {
        NSInteger value1 = [firstArray[index1] integerValue];
        NSInteger value2 = [secondArray[index2] integerValue];
        if (value1 < value2)
        {
            index1++;
            [totalArray addObject: @(value1)];
        }
        else
        {
            index2++;
            [totalArray addObject:@(value2)];
        }
    }
    
    while (index1 < [firstArray count]) {
        [totalArray addObject:firstArray[index1]];
        index1++;
    }
    
    while (index2 < [secondArray count]) {
        [totalArray addObject:secondArray[index2]];
        index2++;
    }
    
    NSLog(@"%@",totalArray);
}

Hash算法

考題：在一個(gè)字符串中找到第一個(gè)只出現(xiàn)一次的字符，如：輸入"abfaccdeff"，則輸出b。

算法思路：

• 字符(char)是一個(gè)長(zhǎng)度為8的數(shù)據(jù)類型，因此總共有256種可能。
• 每個(gè)字母根據(jù)其ASCII碼值作為數(shù)組下標(biāo)對(duì)應(yīng)數(shù)組種的一個(gè)數(shù)字。
• 數(shù)組中存儲(chǔ)的是每個(gè)字符出現(xiàn)的次數(shù)。

即利用哈希函數(shù)的特點(diǎn)建立 ASCII碼值和 index 的聯(lián)系，存儲(chǔ)和查找都通過(guò)該函數(shù)，有效提高查找效率

這里要注意遍歷的時(shí)候不是256個(gè)全部遍歷，僅遍歷字符串的長(zhǎng)度，代碼實(shí)現(xiàn)如下：

- (void)viewDidLoad {
    [super viewDidLoad];
    NSString *str = @"gabfaccdeff";
    int array[256] = {};
    
    char *cStr = (char *)[str cStringUsingEncoding:NSUTF8StringEncoding];
    for (int i = 0; i < [str length]; i++)
    {

        char cSubStr = cStr[i];
        int index = cSubStr;
        array[index] = array[index] + 1;
    }
    
    for (int i = 0; i < [str length]; i++)
    {
        char cSubStr = cStr[i];
        int index = cSubStr;
        if (array[index] == 1)
        {
            printf("%c",cSubStr);
            break;
        }
    }
}

查找兩個(gè)子視圖的共同父視圖

查找思路：先找出這兩個(gè)視圖所有的父視圖，然后通過(guò)倒序遍歷的方式找出他們共同的父視圖

代碼實(shí)現(xiàn)如下：

- (NSMutableArray *)findSuperViews:(UIView *)view
{
    UIView *supView = view.superview;
    
    NSMutableArray *superViewArray = [NSMutableArray array];
    while (supView != nil)
    {
        [superViewArray addObject:supView];
        supView = supView.superview;
    }
    return superViewArray;
}

- (NSMutableArray *)findCommonSuperView:(UIView *)viewOne other:(UIView *)otherView
{
    //查找第一個(gè)視圖的所有父視圖
    NSMutableArray *oneViewSupers = [self findSuperViews:viewOne];
    //查找第十個(gè)視圖的所有父視圖
    NSMutableArray *otherViewSupers = [self findSuperViews:otherView];
    
    NSMutableArray *array = [NSMutableArray array];
    
    NSInteger count = MIN([oneViewSupers count], [otherViewSupers count]);
    for (int i = 0; i < count;i++)
    {
        UIView *oneSuperView = oneViewSupers[[oneViewSupers count] - i - 1];
        UIView *otherSuperView = otherViewSupers[[otherViewSupers count] - i - 1];
        if (oneSuperView == otherSuperView)
        {
            [array addObject:oneSuperView];
        }
        else
        {
            break;
        }
    }
    return array;
}

求無(wú)序數(shù)組當(dāng)中的中位數(shù)

這個(gè)算法有兩種解題思路：

• 排序算法 + 中位數(shù)
• 利用快排思想（分治思想）

快排思想
任意挑一個(gè)元素，以該元素為支點(diǎn)，劃分集合為兩部分
如果左側(cè)集合長(zhǎng)度恰為 (n-1)/2，那么支點(diǎn)恰為中位數(shù)
如果左側(cè)長(zhǎng)度 <(n - 1)/2，那么中位數(shù)在右側(cè)；反之，中位數(shù)在左側(cè)

核心代碼如下：

int findMedia(int a[],int aLen) {
    int low = 0;
    int high = aLen - 1;
    int mid = (aLen - 1)/2;//中位點(diǎn)
    int tempMedia = 0;
    while (tempMedia != mid) {
        tempMedia = partSort(a, low, high);
        if (tempMedia > mid) {//快排的思想確定當(dāng)前基準(zhǔn)數(shù)
            high = tempMedia - 1;
        }else if (tempMedia < mid) {
            low = tempMedia + 1;
        }else {
            break;
        }
    }
    return a[tempMedia];
}

int partSort(int a[],int start, int end) {
    int low = start;
    int high = end;
    int key = a[end];
    while (low < high) {
        while (low < high) {//左邊找比key大的值
            if (a[low] <= key) {
                low++;
            }else {
                int temp = a[low];
                a[high] = temp;
                break;
            }
        }
        while (low < high) {//右邊找比key小的值
            if (a[high] >= key) {
                high--;
            }else {
                int temp = a[high];
                a[low] = temp;
                break;
            }
        }
    }
    a[low] = key;
    return low;
}

總結(jié)

鏈表反轉(zhuǎn)（貝殼、美團(tuán)面試題）
有序數(shù)組合并
Hash算法
查找兩個(gè)子視圖的共同父視圖（必考）