01-算法-iOS面試中熟悉常見(jiàn)算法

1凿将、 對(duì)以下一組數(shù)據(jù)進(jìn)行降序排序(冒泡排序)〖燮ⅲ“24,17笛匙,85侨把,13犀变,9,54秋柄,76获枝,45,5骇笔,63”

int main(int argc, char *argv[]) {

    int array[10] = {24, 17, 85, 13, 9, 54, 76, 45, 5, 63};

    int num = sizeof(array)/sizeof(int);

    for(int i = 0; i < num-1; i++) {

        for(int j = 0; j < num - 1 - i; j++) {

            if(array[j] < array[j+1]) {

                int tmp = array[j];

                array[j] = array[j+1];

                array[j+1] = tmp;

            }

        }

    }

    for(int i = 0; i < num; i++) {

        printf("%d", array[i]);

        if(i == num-1) {

            printf("\n");

        }

        else {

            printf(" ");

        }

    }

}

2省店、 對(duì)以下一組數(shù)據(jù)進(jìn)行升序排序(選擇排序)”看ィ“86, 37, 56, 29, 92, 73, 15, 63, 30, 8”

void sort(int a[],int n)
{

    int i, j, index;

    for(i = 0; i < n - 1; i++) {

        index = i;

        for(j = i + 1; j < n; j++) {

            if(a[index] > a[j]) {

                index = j;

            }

        }

        if(index != i) {

            int temp = a[i];

            a[i] = a[index];

            a[index] = temp;

        }

    }

}

int main(int argc, const char * argv[]) {

    int numArr[10] = {86, 37, 56, 29, 92, 73, 15, 63, 30, 8};

    sort(numArr, 10);

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

        printf("%d, ", numArr[i]);

    }

    printf("\n");

    return 0;

}

3懦傍、 快速排序算法

void sort(int *a, int left, int right) {

if(left >= right) {

return ;

}

int i = left;

int j = right;

int key = a[left];

while (i < j) {

while (i < j && key >= a[j]) {

j--;

}

a[i] = a[j];

while (i < j && key <= a[i]) {

    i++;

}

a[j] = a[i];

}

a[i] = key;

sort(a, left, i-1);

sort(a, i+1, right);

}

4、 歸并排序

void merge(int sourceArr[], int tempArr[], int startIndex, int midIndex, int endIndex) {

    int i = startIndex;

    int j = midIndex + 1;

    int k = startIndex;

    while (i != midIndex + 1 && j != endIndex + 1) {

        if (sourceArr[i] >= sourceArr[j]) {

            tempArr[k++] = sourceArr[j++];

        } else {

            tempArr[k++] = sourceArr[i++];

        }

    }

    while (i != midIndex + 1) {

        tempArr[k++] = sourceArr[i++];

    }

    while (j != endIndex + 1) {

        tempArr[k++] = sourceArr[j++];

    }

    for (i = startIndex; i <= endIndex; i++) {

        sourceArr[i] = tempArr[i];

    }

}


void sort(int souceArr[], int tempArr[], int startIndex, int endIndex) {

    int midIndex;

    if (startIndex < endIndex) {

        midIndex = (startIndex + endIndex) / 2;

        sort(souceArr, tempArr, startIndex, midIndex);

        sort(souceArr, tempArr, midIndex + 1, endIndex);

        merge(souceArr, tempArr, startIndex, midIndex, endIndex);

    }

}


int main(int argc, const char * argv[]) {

    int numArr[10] = {86, 37, 56, 29, 92, 73, 15, 63, 30, 8};

    int tempArr[10];

    sort(numArr, tempArr, 0, 9);

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

        printf("%d, ", numArr[i]);

    }

    printf("\n");

    return 0;

}

5芦劣、 實(shí)現(xiàn)二分查找算法(編程語(yǔ)言不限)

int bsearchWithoutRecursion(int array[],int low,int high,int target) {

while(low <= high) {

int mid = (low + high) / 2;

if(array[mid] > target)

high = mid - 1;

else if(array[mid] < target)

low = mid + 1;

else    //findthetarget

return mid;

}

//the array does not contain the target

return -1;

}

遞歸實(shí)現(xiàn)

int binary_search(const int arr[],int low,int high,int key)
{

int mid=low + (high - low) / 2;

if(low > high)

return -1;

else{

if(arr[mid] == key)

return mid;

else if(arr[mid] > key)

return binary_search(arr, low, mid-1, key);

else

return binary_search(arr, mid+1, high, key);

}

}

6粗俱、 如何實(shí)現(xiàn)鏈表翻轉(zhuǎn)(鏈表逆序)?

思路:每次把第二個(gè)元素提到最前面來(lái)虚吟。

#include <stdio.h>

#include <stdlib.h>


typedef struct NODE {

    struct NODE *next;

    int num;

}node;


node *createLinkList(int length) {

    if (length <= 0) {

        return NULL;

    }

    node *head,*p,*q;

    int number = 1;

    head = (node *)malloc(sizeof(node));

    head->num = 1;

    head->next = head;

    p = q = head;

    while (++number <= length) {

        p = (node *)malloc(sizeof(node));

        p->num = number;

        p->next = NULL;

        q->next = p;

        q = p;

    }

    return head;
}


void printLinkList(node *head) {

    if (head == NULL) {

        return;

    }

    node *p = head;

    while (p) {

        printf("%d ", p->num);

        p = p -> next;

    }

    printf("\n");

}


node *reverseFunc1(node *head) {

    if (head == NULL) {

        return head;


    }


    node *p,*q;

    p = head;

    q = NULL;

    while (p) {

        node *pNext = p -> next;

        p -> next = q;

        q = p;

        p = pNext;

    }

    return q;

}


int main(int argc, const char * argv[]) {

    node *head = createLinkList(7);

    if (head) {

        printLinkList(head);

        node *reHead = reverseFunc1(head);

        printLinkList(reHead);

        free(reHead);

    }

    free(head);

    return 0;

}

7寸认、 實(shí)現(xiàn)一個(gè)字符串“how are you”的逆序輸出(編程語(yǔ)言不限)。如給定字符串為“hello world”,輸出結(jié)果應(yīng)當(dāng)為“world hello”串慰。

int spliterFunc(char *p) {

    char c[100][100];

    int i = 0;

    int j = 0;


    while (*p != '\0') {

        if (*p == ' ') {

            i++;

            j = 0;

        } else {

            c[i][j] = *p;

            j++;

        }

        p++;


    }


    for (int k = i; k >= 0; k--) {

        printf("%s", c[k]);

        if (k > 0) {

            printf(" ");

        } else {

            printf("\n");

        }

    }

    return 0;


}

8偏塞、 給定一個(gè)字符串,輸出本字符串中只出現(xiàn)一次并且最靠前的那個(gè)字符的位置邦鲫?如“abaccddeeef”,字符是b,輸出應(yīng)該是2灸叼。

char *strOutPut(char *);


int compareDifferentChar(char, char *);


int main(int argc, const char * argv[]) {


    char *inputStr = "abaccddeeef";

    char *outputStr = strOutPut(inputStr);

    printf("%c \n", *outputStr);

    return 0;

}


char *strOutPut(char *s) {

    char str[100];

    char *p = s;

    int index = 0;

    while (*s != '\0') {

        if (compareDifferentChar(*s, p) == 1) {

            str[index] = *s;

            index++;

        }

        s++;

    }

    return &str;
}


int compareDifferentChar(char c, char *s) {

    int i = 0;

    while (*s != '\0' && i<= 1) {

        if (*s == c) {

            i++;

        }

        s++;
    }

    if (i == 1) {

        return 1;

    } else {

        return 0;

    }

}

9、 二叉樹(shù)的先序遍歷為FBACDEGH,中序遍歷為:ABDCEFGH,請(qǐng)寫(xiě)出這個(gè)二叉樹(shù)的后序遍歷結(jié)果掂碱。

ADECBHGF

先序+中序遍歷還原二叉樹(shù):先序遍歷是:ABDEGCFH 中序遍歷是:DBGEACHF

首先從先序得到第一個(gè)為A怜姿,就是二叉樹(shù)的根,回到中序疼燥,可以將其分為三部分:

左子樹(shù)的中序序列DBGE沧卢,根A,右子樹(shù)的中序序列CHF

接著將左子樹(shù)的序列回到先序可以得到B為根醉者,這樣回到左子樹(shù)的中序再次將左子樹(shù)分割為三部分:

左子樹(shù)的左子樹(shù)D但狭,左子樹(shù)的根B,左子樹(shù)的右子樹(shù)GE

同樣地撬即,可以得到右子樹(shù)的根為C

類(lèi)似地將右子樹(shù)分割為根C立磁,右子樹(shù)的右子樹(shù)HF,注意其左子樹(shù)為空

如果只有一個(gè)就是葉子不用再進(jìn)行了剥槐,剛才的GE和HF再次這樣運(yùn)作唱歧,就可以將二叉樹(shù)還原了。

10、 打印2-100之間的素?cái)?shù)颅崩。

int main(int argc, const char * argv[]) {

    for (int i = 2; i < 100; i++) {

        int r = isPrime(i);

        if (r == 1) {

            printf("%ld ", i);

        }

    }

    return 0;

}


int isPrime(int n)
{

    int i, s;

    for(i = 2; i <= sqrt(n); i++)

        if(n % i == 0)  return 0;

    return 1;

}
  

11几于、 求兩個(gè)整數(shù)的最大公約數(shù)。

int gcd(int a, int b) {

    int temp = 0;

    if (a < b) {

        temp = a;

        a = b;

        b = temp;

    }

    while (b != 0) {

        temp = a % b;

        a = b;

        b = temp;

    }

    return a;

}

轉(zhuǎn)載請(qǐng)注明出處:https://www.yangshebing.com/2016/04/24/iosmian-shi-ti-xi-lie-zhi-chang-jian-suan-fa/

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末沿后,一起剝皮案震驚了整個(gè)濱河市沿彭,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌尖滚,老刑警劉巖喉刘,帶你破解...
    沈念sama閱讀 222,378評(píng)論 6 516
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異漆弄,居然都是意外死亡睦裳,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,970評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門(mén)置逻,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)推沸,“玉大人,你說(shuō)我怎么就攤上這事券坞△薮撸” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 168,983評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵恨锚,是天一觀的道長(zhǎng)宇驾。 經(jīng)常有香客問(wèn)我,道長(zhǎng)猴伶,這世上最難降的妖魔是什么课舍? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 59,938評(píng)論 1 299
  • 正文 為了忘掉前任,我火速辦了婚禮他挎,結(jié)果婚禮上筝尾,老公的妹妹穿的比我還像新娘。我一直安慰自己办桨,他們只是感情好筹淫,可當(dāng)我...
    茶點(diǎn)故事閱讀 68,955評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著呢撞,像睡著了一般损姜。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上殊霞,一...
    開(kāi)封第一講書(shū)人閱讀 52,549評(píng)論 1 312
  • 那天摧阅,我揣著相機(jī)與錄音,去河邊找鬼绷蹲。 笑死棒卷,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播娇跟,決...
    沈念sama閱讀 41,063評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼岩齿,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了苞俘?” 一聲冷哼從身側(cè)響起,我...
    開(kāi)封第一講書(shū)人閱讀 39,991評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤龄章,失蹤者是張志新(化名)和其女友劉穎吃谣,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體做裙,經(jīng)...
    沈念sama閱讀 46,522評(píng)論 1 319
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡岗憋,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,604評(píng)論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了锚贱。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片仔戈。...
    茶點(diǎn)故事閱讀 40,742評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖拧廊,靈堂內(nèi)的尸體忽然破棺而出监徘,到底是詐尸還是另有隱情,我是刑警寧澤吧碾,帶...
    沈念sama閱讀 36,413評(píng)論 5 351
  • 正文 年R本政府宣布凰盔,位于F島的核電站,受9級(jí)特大地震影響倦春,放射性物質(zhì)發(fā)生泄漏户敬。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,094評(píng)論 3 335
  • 文/蒙蒙 一睁本、第九天 我趴在偏房一處隱蔽的房頂上張望尿庐。 院中可真熱鬧,春花似錦呢堰、人聲如沸抄瑟。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,572評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)锐借。三九已至,卻和暖如春往衷,著一層夾襖步出監(jiān)牢的瞬間钞翔,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,671評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工席舍, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留布轿,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,159評(píng)論 3 378
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像汰扭,于是被迫代替她去往敵國(guó)和親稠肘。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,747評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容

  • 樹(shù)的概述 樹(shù)是一種非常常用的數(shù)據(jù)結(jié)構(gòu)萝毛,樹(shù)與前面介紹的線性表项阴,棧,隊(duì)列等線性結(jié)構(gòu)不同笆包,樹(shù)是一種非線性結(jié)構(gòu) 1.樹(shù)的定...
    Jack921閱讀 4,462評(píng)論 1 31
  • 第一章 緒論 什么是數(shù)據(jù)結(jié)構(gòu)环揽? 數(shù)據(jù)結(jié)構(gòu)的定義:數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 第二章...
    SeanCheney閱讀 5,784評(píng)論 0 19
  • 課程介紹 先修課:概率統(tǒng)計(jì)庵佣,程序設(shè)計(jì)實(shí)習(xí)歉胶,集合論與圖論 后續(xù)課:算法分析與設(shè)計(jì),編譯原理巴粪,操作系統(tǒng)通今,數(shù)據(jù)庫(kù)概論,人...
    ShellyWhen閱讀 2,299評(píng)論 0 3
  • 1 序 2016年6月25日夜肛根,帝都辫塌,天下著大雨,拖著行李箱和同學(xué)在校門(mén)口照了最后一張合照晶通,搬離寢室打車(chē)去了提前租...
    RichardJieChen閱讀 5,108評(píng)論 0 12
  • 1璃氢、 對(duì)以下一組數(shù)據(jù)進(jìn)行降序排序(冒泡排序)∈桑“24一也,80,35喉脖,8椰苟,9,54树叽,76舆蝴,45,5题诵,63” int ...
    面條168閱讀 677評(píng)論 0 3