主要算法大綱
問題一： 請實現(xiàn)字符串反轉(zhuǎn)的算法突颊。
主要思路：兩個指針分別指向字符串的一頭一尾地址，然后交換兩個指針的內(nèi)容光涂，交換完畢后，指針從兩端向中間移動拧烦，重復(fù)交換和移動操作忘闻。直到 begin 指針的地址大于等于 end 指針，就結(jié)束程序完成交互恋博。
// code
void characterReverse(char* cha) {
char* begin = &cha[0];
char* end = cha + strlen(cha) - 1;
while (begin < end) {
char temp = *begin;
*(begin++) = *end;
*(end--) = temp;
}
}
// usage
- (void)learnCharacterReverse {
char cha[]= "Hello,World";
characterReverse(cha);
printf("reverse result is %s \n", cha);
}
問題二： 請實現(xiàn)鏈表的反轉(zhuǎn)齐佳。
主要思路：創(chuàng)建兩個指針，一個用來存放反轉(zhuǎn)的新鏈表交播，一個用來存當(dāng)前鏈表重虑。利用頭插法，把舊鏈表上的數(shù)據(jù)一個個插入新鏈表的頭部秦士。特別注意一點在于，要先存鏈表的下一個結(jié)點永高，不然插入之后會丟失鏈表數(shù)據(jù)隧土。
// .h
#import <Foundation/Foundation.h>
struct Node {
int data;
struct Node* next;
};
@interface ChainReverse : NSObject
// 鏈表反轉(zhuǎn)
struct Node* chain_reverse(struct Node* head);
// 構(gòu)建一個列表
struct Node* constructionChains(void);
// 打印鏈表
void printChain(struct Node *head);
@end
// .m文件
#import "ChainReverse.h"
@implementation ChainReverse
// 鏈表反轉(zhuǎn)
struct Node* chain_reverse(struct Node* head) {
// 定義遍歷指針,初始化頭結(jié)點
struct Node* p = head;
// 反轉(zhuǎn)后的鏈表頭部
struct Node *newH = NULL;
// 遍歷鏈表
while (p != NULL) {
// 先記錄下一個結(jié)點
struct Node* temp = p->next;
// 當(dāng)前結(jié)點的 nex 執(zhí)行新鏈表的頭部
p->next = newH;
// 更改新鏈表頭部為當(dāng)前結(jié)點
newH = p;
// 移動 p 指針
p = temp;
}
return newH;
};
// 構(gòu)建一個列表
struct Node* constructionChains(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;
node->next = NULL;
if (head == NULL) {
head = node;
} else {
cur->next = node;
}
cur = node;
}
return head;
}
// 打印鏈表
void printChain(struct Node *head) {
struct Node* cur = NULL;
cur = head;
while (cur != NULL) {
printf("%i \n", cur->data);
cur = cur->next;
};
printf("===============\n");
}
@end
// 用法
- (void)learnChainReverse {
struct Node* head = constructionChains();
printChain(head);
struct Node* newHead = chain_reverse(head);
printChain(newHead);
}
問題三：請實現(xiàn)兩個有序數(shù)組合并成一個有序數(shù)據(jù)的算法。
算法思路：分別從兩個有序數(shù)組頭部開始取數(shù)組命爬，對比大小曹傀，把小的值插入新數(shù)組，然后小的值所在數(shù)據(jù)角標(biāo)+1饲宛，如此重復(fù)皆愉，直到其中一方數(shù)組沒有數(shù)據(jù)了，把另一個數(shù)組剩余的值全部插入新數(shù)組，完成合并幕庐。
// 將有序數(shù)據(jù) a 和 b 的值合并到一個數(shù)據(jù) result當(dāng)中,且仍然保持有序
void mergeList(int a[], int aLen, int b[], int bLen, int result[]) {
int p = 0; // 記錄數(shù)組 a 的位置
int q = 0; // j遍歷數(shù)組 b 的位置
int i = 0; // 記錄當(dāng)前存儲 z 位置
while (p < aLen && q < bLen) {
if (a[p] < b[q]) {
result[i] = a[p];
p++;
} else {
result[i] = b[q];
q++;
}
i++;
}
while (p < aLen) {
result[i] = a[p];
p++;
i++;
}
while (q < bLen) {
result[i] = b[q];
q++;
i++;
}
}
問題四：請用哈希算法來實現(xiàn)查找字符串中第一個只出現(xiàn)一次的字符久锥。
算法思路：所謂 hash 算法，就是利用哈希函數(shù)做一個映射异剥，從而由 key 經(jīng)過 f(key) 高效的找到結(jié)果瑟由。所以我們可以把字符當(dāng)成 ASCII 碼作為 key 并且當(dāng)成一個數(shù)組的腳本，數(shù)組的 value 就是出現(xiàn)的次數(shù)冤寿。
char findFirstChar(char *cha) {
// 用來移動的指針
char *p = cha;
// 初始化一個數(shù)組
int array[256];
for (int i = 0 ; i < 256; i++) {
array[i] = 0;
}
// 結(jié)果存放處
char result = '\0';
// 遍歷并且給數(shù)組賦值
while (*p != '\0') {
array[*(p++)]++;
}
p = cha;
// 查找value 為 1 的字符
while (*p != '\0') {
if (array[*p] == 1) {
result = *p;
break;
}
p++;
}
return result;
}
問題五：查找兩個子視圖的共同父視圖歹苦。
算法思路：先遍歷找出兩個子視圖的所有父視圖，存于兩個數(shù)組督怜；將兩個數(shù)組進行反序殴瘦，然后從下標(biāo) 0 的位置開始對比兩個數(shù)組，將相同的視圖存在另一個新數(shù)組中号杠，直到兩個數(shù)組第一次出現(xiàn)不同視圖蚪腋，就可以終止循環(huán)。
- (void)learnFindCommonSupperView {
NSMutableArray *mutableArray_A = [NSMutableArray new];
NSMutableArray *mutableArray_B = [NSMutableArray new];
NSMutableArray *mutableArray_Common = [NSMutableArray new];
UIView *currentA = self.labelA;
while (currentA.superview != nil) {
[mutableArray_A addObject:currentA.superview];
currentA = currentA.superview;
}
UIView *currentB = self.labelB;
while (currentB.superview != nil) {
[mutableArray_B addObject:currentB.superview];
currentB = currentB.superview;
}
// 步驟的關(guān)鍵在于反序查找,直到第一個不同的視圖終止
mutableArray_A = [[[mutableArray_A reverseObjectEnumerator] allObjects] mutableCopy];
mutableArray_B = [[[mutableArray_B reverseObjectEnumerator] allObjects] mutableCopy];
for (int i = 0; i < mutableArray_A.count && i < mutableArray_B.count; i++) {
UIView *a = mutableArray_A[i];
UIView *b = mutableArray_B[i];
if (a == b) {
[mutableArray_Common addObject:a];
// 為了標(biāo)記已經(jīng)找到的共同父視圖,標(biāo)記為紅色
a.backgroundColor = [UIColor redColor];
a.layer.borderWidth = 1;
a.layer.borderColor = [UIColor whiteColor].CGColor;
} else {
break;
}
}
NSLog(@"一共有 %lu 個父視圖", (unsigned long)mutableArray_Common.count);
}
