排序：排序
鏈表：iOS單向鏈表數(shù)據(jù)結(jié)構(gòu)、判斷兩個(gè)鏈表是否相交并找出交點(diǎn)
求解1-100之間的所有素?cái)?shù)/質(zhì)數(shù)：https://zhidao.baidu.com/question/1430132761736407379.html
字符串反轉(zhuǎn)
- 要求：
給定字符串“hello,word”笛谦，實(shí)現(xiàn)將其反轉(zhuǎn)趾浅。
輸出結(jié)果："drow,olleh"
-思路：
begin指針指向第一個(gè)字符痴颊；
end指針指向最后一個(gè)字符尉姨；
交換兩個(gè)指針的內(nèi)容我擂，begin指針向后移動(dòng)一位择吊、end指針向前移動(dòng)一位促绵，交互下一對(duì)攒庵；
beign>=end的時(shí)候才交換，否則停止败晴；
void char_reverse(char* cha)
{
// 指向第一個(gè)字符
char* begin = cha;
// 指向最后一個(gè)字符
char* end = cha + strlen(cha) - 1;
while (begin < end) {
// 交換前后兩個(gè)字符
char temp = *begin;
*begin = *end;
*end = temp;
// 同時(shí)移動(dòng)指針
begin++;
end--;
}
}
調(diào)用：
//字符串?dāng)?shù)組
char ch[] = "hello,world";/*char * ch = "hello,world"; 不可以*/
char_reverse(ch);
printf(ch);
OC的方法1
使用characterAtIndex獲得String某一個(gè)位置的字符浓冒；
NSString *originalString = @"Hello, World!";
NSMutableString *reversedString = [NSMutableString stringWithCapacity:[originalString length]];
for (NSInteger i = [originalString length] - 1; i >= 0; i--) {
[reversedString appendString:[NSString stringWithFormat:@"%c", [originalString characterAtIndex:i]]];
}
NSLog(@"Reversed String: %@", reversedString);
OC的方法2
使用substringWithRange獲得某一個(gè)區(qū)間的字符串；
NSString *originalString = @"Hello, World!";
NSMutableString *reversedString = [NSMutableString stringWithCapacity:[originalString length]];
for (NSInteger i = [originalString length] - 1; i >= 0; i--) {
NSRange range = NSMakeRange(i, 1);
[reversedString appendString:[originalString substringWithRange:range]];
}
NSLog(@"Reversed String: %@", reversedString);
鏈表反轉(zhuǎn)
-
要求：
鏈表反轉(zhuǎn) 思路：
1.原本的聯(lián)調(diào)頭結(jié)點(diǎn)為Head尖坤；
2.生成一個(gè)新的頭節(jié)點(diǎn)NewH裆蒸，作為反轉(zhuǎn)后鏈表的頭結(jié)點(diǎn)；
3.生成一個(gè)臨時(shí)節(jié)點(diǎn)P糖驴，用來(lái)保存操作節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)僚祷。例如目前要操作的節(jié)點(diǎn)是1，p就指向的是2贮缕；
4.先把內(nèi)容為1的節(jié)點(diǎn)拿出來(lái)辙谜，作為新鏈表的頭結(jié)點(diǎn)。頭結(jié)點(diǎn)NewH指向內(nèi)容為1的節(jié)點(diǎn)感昼。
5.把p節(jié)點(diǎn)指向2的下一個(gè)節(jié)點(diǎn)装哆。
6.內(nèi)容為2的節(jié)點(diǎn)拿出來(lái)，作為新鏈表的頭結(jié)點(diǎn)定嗓。頭結(jié)點(diǎn)NewH指向內(nèi)容為2的節(jié)點(diǎn)蜕琴。依次類推。（每一個(gè)節(jié)點(diǎn)都插入到新鏈表宵溅，作為新鏈表的頭結(jié)點(diǎn)）
.h:
// 定義一個(gè)節(jié)點(diǎn)
struct Node {
int data;//節(jié)點(diǎn)數(shù)據(jù)
struct Node *next;//鏈表的下一個(gè)節(jié)點(diǎn)
};
@interface ReverseList : NSObject
// 鏈表反轉(zhuǎn)
struct Node* reverseList(struct Node *head);
// 構(gòu)造一個(gè)鏈表
struct Node* constructList(void);
// 打印鏈表中的數(shù)據(jù)
void printList(struct Node *head);
@end
.m:
@implementation ReverseList
/*
傳入：原鏈表的頭結(jié)點(diǎn)
返回：新鏈表的頭結(jié)點(diǎn)
*/
struct Node* reverseList(struct Node *head)
{
// 定義遍歷指針凌简，初始化為頭結(jié)點(diǎn)
struct Node *p = head;
// 反轉(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指針
p = temp;
}
// 返回反轉(zhuǎn)后的鏈表頭結(jié)點(diǎn)
return newH;
}
// 構(gòu)造一個(gè)鏈表
struct Node* constructList(void)
{
// 頭結(jié)點(diǎn)定義
struct Node *head = NULL;
// 記錄當(dāng)前尾結(jié)點(diǎn)
struct Node *cur = NULL;
for (int i = 1; i < 5; 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;
}
// 當(dāng)前結(jié)點(diǎn)的next為新結(jié)點(diǎn)
else{
cur->next = node;
}
// 設(shè)置當(dāng)前結(jié)點(diǎn)為新結(jié)點(diǎn)
cur = node;
}
return head;
}
// 打印鏈表中的數(shù)據(jù)
void printList(struct Node *head)
{
struct Node* temp = head;
while (temp != NULL) {
printf("node is %d \n", temp->data);
temp = temp->next;
}
}
@end
調(diào)用：
// 單鏈表反轉(zhuǎn)
struct Node* head = constructList();
printList(head);
printf("---------\n");
struct Node* newHead = reverseList(head);
printList(newHead);
有序數(shù)組合并
-
要求：
如下恃逻，有兩個(gè)有序數(shù)組雏搂。分別是[1,4,6,7,9]、[2寇损、3凸郑、5、6矛市、8芙沥、10、11、12]
有序數(shù)組合并
1.兩個(gè)數(shù)組a而昨、b救氯。用一個(gè)新的數(shù)組c放合并的結(jié)果。比如p存放數(shù)組a遍歷到的位數(shù)配紫，q存放b數(shù)組遍歷到的位數(shù)。
2.a[p]和b[q]進(jìn)行比較午阵，假如a[p]小躺孝，就把a(bǔ)[p]放到數(shù)組c中，并且把p+1底桂。反之植袍，如果b[q]小，就把b[q]放到數(shù)組里面,q+1籽懦。
3.然后再用新的p和q進(jìn)行比較于个。直到某一個(gè)數(shù)組變量完后，看哪個(gè)數(shù)組沒(méi)有變量完暮顺，把沒(méi)有變量完的部分放到數(shù)組c里面厅篓。
@interface MergeSortedList : NSObject
// 將有序數(shù)組a和b的值合并到一個(gè)數(shù)組result當(dāng)中，且仍然保持有序
void mergeList(int a[], int aLen, int b[], int bLen, int result[]);
@end
@implementation MergeSortedList
void mergeList(int a[], int aLen, int b[], int bLen, int result[])
{
int p = 0; // 遍歷數(shù)組a的指針
int q = 0; // 遍歷數(shù)組b的指針
int i = 0; // 記錄當(dāng)前存儲(chǔ)位置
// 任一數(shù)組沒(méi)有到達(dá)邊界則進(jìn)行遍歷
while (p < aLen && q < bLen) {
// 如果a數(shù)組對(duì)應(yīng)位置的值小于b數(shù)組對(duì)應(yīng)位置的值
if (a[p] <= b[q]) {
// 存儲(chǔ)a數(shù)組的值
result[i] = a[p];
// 移動(dòng)a數(shù)組的遍歷指針
p++;
}
else{
// 存儲(chǔ)b數(shù)組的值
result[i] = b[q];
// 移動(dòng)b數(shù)組的遍歷指針
q++;
}
// 指向合并結(jié)果的下一個(gè)存儲(chǔ)位置
I++;
}
// 如果a數(shù)組有剩余
while (p < aLen) {
// 將a數(shù)組剩余部分拼接到合并結(jié)果的后面
result[i] = a[p++];
I++;
}
// 如果b數(shù)組有剩余
while (q < bLen) {
// 將b數(shù)組剩余部分拼接到合并結(jié)果的后面
result[i] = b[q++];
I++;
}
}
@end
調(diào)用：
// 用于存儲(chǔ)歸并結(jié)果
int result[13];
// 歸并操作g
mergeList(a, 5, b, 8, result);
// 打印歸并結(jié)果
printf("merge result is ");
for (int i = 0; i < 13; i++) {
printf("%d ", result[I]);
}
兩個(gè)有序數(shù)組捶码，求第K大的數(shù)
也是和上面的一題思想一樣羽氮，遞歸合并兩個(gè)數(shù)組，直到合并數(shù)組到第K個(gè)位置結(jié)束惫恼。
初始化兩個(gè)指針 i 和 j 分別指向兩個(gè)數(shù)組的開(kāi)頭档押，表示當(dāng)前考慮的區(qū)間范圍。
比較兩個(gè)指針?biāo)赶虻脑仄泶浚瑢⑤^小的那個(gè)元素加入到一個(gè)新的數(shù)組中令宿。
移動(dòng)指針，將被選擇的元素所在數(shù)組的指針向后移動(dòng)一位腕窥。
重復(fù)步驟 2 和 3粒没，直到新數(shù)組中有 k 個(gè)元素為止。
Hash算法
查找一個(gè)字符串中簇爆，第一個(gè)只出現(xiàn)一次的字符
- 一個(gè)字符長(zhǎng)度是8革娄，每一位有0、1兩種組成可能冕碟，所以1個(gè)字符有2的8次方個(gè)可能拦惋，就是256個(gè)可能。
采用hash算法思想：
- 定義一個(gè)256大小的數(shù)組安寺，數(shù)組中存儲(chǔ)的是每個(gè)字符出現(xiàn)的次數(shù)厕妖。
-
每個(gè)字母根據(jù)ascii碼值，把次數(shù)放到對(duì)應(yīng)的位置挑庶。例如a的ascii值是97,數(shù)組的第97位就存放a出現(xiàn)的次數(shù)言秸。
image.png
#include <stdio.h>
#include <string.h>
char first_unique_char(char *s) {
int char_count[256] = {0}; // 用于存儲(chǔ)每個(gè)字符的出現(xiàn)次數(shù)
// 計(jì)數(shù)每個(gè)字符的出現(xiàn)次數(shù)
for (int i = 0; i < strlen(s); i++) {
char_count[s[i]]++;
}
// 找到第一個(gè)只出現(xiàn)一次的字符
for (int i = 0; i < strlen(s); i++) {
if (char_count[s[i]] == 1) {
return s[i];
}
}
// 如果沒(méi)有找到只出現(xiàn)一次的字符软能，則返回空字符
return '\0';
}
int main() {
char input_str[] = "leetcode";
char result = first_unique_char(input_str);
if (result != '\0') {
printf("第一個(gè)只出現(xiàn)一次的字符是: %c\n", result);
} else {
printf("沒(méi)有找到只出現(xiàn)一次的字符\n");
}
return 0;
}
查找兩個(gè)子視圖的共同父視圖
- 要求：
有C、D兩個(gè)視圖举畸。要查找這兩個(gè)視圖的共同父視圖查排。
圖中箭頭代表父視圖。如A是C的父視圖抄沮。
-
思路：
遍歷出兩個(gè)view的父視圖放到兩個(gè)數(shù)組里面跋核。從后往前遍歷兩個(gè)數(shù)組中的值。
查找兩個(gè)自視圖共同的父視圖
.h:
@interface CommonSuperFind : NSObject
// 查找兩個(gè)視圖的共同父視圖
- (NSArray<UIView *> *)findCommonSuperView:(UIView *)view other:(UIView *)viewOther;
@end
.m:
#import "CommonSuperFind.h"
@implementation CommonSuperFind
- (NSArray <UIView *> *)findCommonSuperView:(UIView *)viewOne other:(UIView *)viewOther
{
NSMutableArray *result = [NSMutableArray array];
// 查找第一個(gè)視圖的所有父視圖
NSArray *arrayOne = [self findSuperViews:viewOne];
// 查找第二個(gè)視圖的所有父視圖
NSArray *arrayOther = [self findSuperViews:viewOther];
int i = 0;
// 越界限制條件
while (i < MIN((int)arrayOne.count, (int)arrayOther.count)) {
// 倒序方式獲取各個(gè)視圖的父視圖
UIView *superOne = [arrayOne objectAtIndex:arrayOne.count - i - 1];
UIView *superOther = [arrayOther objectAtIndex:arrayOther.count - i - 1];
// 比較如果相等 則為共同父視圖
if (superOne == superOther) {
[result addObject:superOne];
I++;
}
// 如果不相等叛买，則結(jié)束遍歷
else{
break;
}
}
return result;
}
- (NSArray <UIView *> *)findSuperViews:(UIView *)view
{
// 初始化為第一父視圖
UIView *temp = view.superview;
// 保存結(jié)果的數(shù)組
NSMutableArray *result = [NSMutableArray array];
while (temp) {
[result addObject:temp];
// 順著superview指針一直向上查找
temp = temp.superview;
}
return result;
}
@end
快速排序
具體看鏈接快速排序
@implementation QuickSort
//a[]:數(shù)組 begin：開(kāi)始排序的位置 end：結(jié)束排序的位置
void quickSort(int a[],int begin,int end){
if (begin > end) {
return;
}
int i = begin;//左邊開(kāi)始尋找的位置
int j = end;//右邊開(kāi)始尋找的位置
int key = a[i];//設(shè)置左邊的第一個(gè)值為參考值
while (i!=j) {//當(dāng)i和j相遇時(shí)，交換相遇位置的值和參考值即可率挣；不相等時(shí)刻伊，進(jìn)行位置交換
while (i<j && a[j] > key) {//從右邊開(kāi)始尋找，找到比參考值小的值椒功，就停止
j--;
}
while (i<j && a[i] <= key) {//從左邊開(kāi)始尋找捶箱，找到比參考值大的值，就停止动漾；注意讼呢，必須是<=，如果設(shè)置為<谦炬，左邊的第一個(gè)數(shù)作為參考值了悦屏，比較的時(shí)候i就不會(huì)進(jìn)行移動(dòng)了
I++;
}
if (i < j) {//如果i = j，進(jìn)行交換沒(méi)有意義
//把找到的值進(jìn)行交換键思，小的放到前面础爬，大的放到后面
int tmp = a[I];
a[i] = a[j];
a[j] = tmp;
}
}
//移動(dòng)參考值的位置，讓參考值前面的值都比他小吼鳞，后面的值都比他大
int tmp = a[begin];
a[begin] = a[j];
a[j] = tmp;
for (int i = 0; i < 8; i++) {
printf("%d ", a[I]);
}
printf("----------");
//對(duì)參考值左邊的進(jìn)行排序
quickSort(a, begin, j - 1);
//對(duì)參考值右邊的進(jìn)行排序
quickSort(a, j + 1, end);
}
@end
- (void)viewDidLoad {
[super viewDidLoad];
int a[] = {9,8,10,20,7,6,5,11};
quickSort(a, 0, 7);
}
求無(wú)序數(shù)組當(dāng)中的中位數(shù)
方法1：排序算法+中位數(shù)：
冒泡看蚜、快速、堆排序赔桌、二分查找
中位數(shù)的定義：
當(dāng)n為奇數(shù)的時(shí)候供炎，中位數(shù) = (n -1)/2 的這位數(shù)就是中位數(shù)。
eg：2疾党、4音诫、6、7雪位、9竭钝、20、22 。一共有7位數(shù)香罐， 中位數(shù)就是第（7-1）/2 = 3位上面的數(shù) 7卧波。
當(dāng)n為偶數(shù)的時(shí)候，中位數(shù)就是中間兩位數(shù)之和的一半庇茫，就是中位數(shù)港粱。
中位數(shù) = （(n -1)/2 + ( (n - 1)/2 + 1) ）/2
eg：2、4旦签、6查坪、7、9顷霹、20咪惠、22 击吱、25淋淀。一共有8位數(shù)， 中位數(shù)兩位數(shù)是7覆醇、9 之和的一半8朵纷。
#import <Foundation/Foundation.h>
double findMedian(NSArray *arr) {
NSArray *sortedArr = [arr sortedArrayUsingSelector:@selector(compare:)];
NSUInteger n = [sortedArr count];
if (n % 2 != 0) {
return [sortedArr[n / 2] doubleValue];
} else {
double median = ([sortedArr[n / 2 - 1] doubleValue] + [sortedArr[n / 2] doubleValue]) / 2.0;
return median;
}
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
NSArray *arr = @[@4, @7, @1, @9, @5];
double median = findMedian(arr);
NSLog(@"數(shù)組的中位數(shù)是: %.2f", median);
}
return 0;
}
方法2：利用快排思想
思路：
已知中位數(shù)是哪個(gè)位置上的。
- 數(shù)組個(gè)數(shù)為奇數(shù)：(n-1)/2 就是中位
取數(shù)組中的一個(gè)值作為關(guān)鍵值永脓，進(jìn)行快速排序袍辞，看他在快速排序后的位置。如果剛好是中位數(shù)的位置常摧，中位數(shù)就是這個(gè)值搅吁。
如果位置< (n-1)/2,那么中位數(shù)就在這個(gè)位置的左邊
如果位置> (n-1)/2,那么中位數(shù)就在這個(gè)位置的右邊
又再去新指定的區(qū)域找一個(gè)關(guān)鍵字值，進(jìn)行快速排序落午。重復(fù)以上步驟谎懦。
- 數(shù)組個(gè)數(shù)為偶數(shù)數(shù)：(n-1)/2、 (n-1)/2 +1 兩個(gè)位置上的數(shù)之和的平均數(shù)就是中位
@implementation MediaFund
int mediaFund(int a[],int alength){
//找到(n-1)/2位置的數(shù)
int media = (alength - 1)/2;
int div = partSort(a, 0, alength - 1);
while (div != media) {
if (div < media) {//值在右側(cè)溃斋，查找右側(cè)區(qū)域
div = partSort(a, div + 1, alength -1);
}else{//值在左側(cè)界拦，查找左側(cè)區(qū)域
div= partSort(a, 0, div -1);
}
}
//如果是偶數(shù)，找到(n-1)/2 + 1位置的數(shù)
if (alength%2 == 0) {//數(shù)組是偶數(shù)個(gè)
int newLoc = div + 1;
int newDiv = partSort(a, newLoc, alength - 1);
while (newLoc != newDiv) {
if (newDiv > newLoc) {
newDiv = partSort(a, newLoc, newDiv - 1);
}
}
printf("數(shù)組中的個(gè)數(shù)為偶數(shù)：a[div]:%d~~~[newLoc]:%d\n",a[div],a[newDiv]);
return (a[div] + a[newLoc])/2;
}else{//數(shù)組中的個(gè)數(shù)為奇數(shù)
printf("數(shù)組中的個(gè)數(shù)為奇數(shù)：a[div]:%d",a[div]);
return a[div];
}
}
//單遍快速排序
int partSort (int a[],int begin,int end){
int key = a[begin];
int i = begin;
int j = end;
while (i != j) {
while (i < j & a[j] > key) {
j-- ;
}
while (i<j & a[i] <= key) {//注意梗劫，是<=
I++;
}
if (i < j) {
int tmp = a[I];
a[i] = a[j];
a[j] = tmp;
}
}
a[begin] = a[j];
a[j] = key;
return j;
}
@end
調(diào)用：
// int a[] = {9,8,10,7,6,5,11};
int a[] = {9,8,11,7,6,5,10,20};
//5 6 7 8 9 10 11 (7個(gè)數(shù)) 中位數(shù)為第（7 - 1）/2 = 3位享甸，8
//5 6 7 8 9 10 11 20 （8個(gè)數(shù)） 中位數(shù)為第4位+第5位之和/2
int div = mediaFund(a, 8);
printf("中位數(shù)是：%d\n",div);
printf("排序后的數(shù)組是：");
for (int i = 0; i < 8; i++) {
printf("%d ", a[I]);
}
冒泡排序：
https://www.runoob.com/w3cnote/bubble-sort.html
算法步驟:
比較相鄰的元素。如果第一個(gè)比第二個(gè)大梳侨，就交換他們兩個(gè)蛉威。
對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)走哺。這步做完后瓷翻，最后的元素會(huì)是最大的數(shù)。
針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)齐帚。
持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟妒牙，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
#include <stdio.h>
void bubble_sort(int arr[], int len) {
int i, j, temp;
for (i = 0; i < len - 1; i++)
for (j = 0; j < len - 1 - i; j++)
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, len);
int i;
for (i = 0; i < len; i++)
printf("%d ", arr[i]);
return 0;
}
二叉樹(shù)
二叉樹(shù)詳解：https://www.hello-algo.com/chapter_tree/binary_tree/
遍歷二叉樹(shù)：
https://www.hello-algo.com/chapter_tree/binary_tree_traversal/
-
層序遍歷
層序遍歷
-
前序 中序 后序
二叉樹(shù)遍歷
/* 前序遍歷 */
void preOrder(TreeNode *root, int *size) {
if (root == NULL)
return;
// 訪問(wèn)優(yōu)先級(jí)：根節(jié)點(diǎn) -> 左子樹(shù) -> 右子樹(shù)
arr[(*size)++] = root->val;
preOrder(root->left, size);
preOrder(root->right, size);
}
/* 中序遍歷 */
void inOrder(TreeNode *root, int *size) {
if (root == NULL)
return;
// 訪問(wèn)優(yōu)先級(jí)：左子樹(shù) -> 根節(jié)點(diǎn) -> 右子樹(shù)
inOrder(root->left, size);
arr[(*size)++] = root->val;
inOrder(root->right, size);
}
/* 后序遍歷 */
void postOrder(TreeNode *root, int *size) {
if (root == NULL)
return;
// 訪問(wèn)優(yōu)先級(jí)：左子樹(shù) -> 右子樹(shù) -> 根節(jié)點(diǎn)
postOrder(root->left, size);
postOrder(root->right, size);
arr[(*size)++] = root->val;
}
翻轉(zhuǎn)二叉樹(shù)
思路：
顯然对妄，我們從根節(jié)點(diǎn)開(kāi)始湘今，遞歸地對(duì)樹(shù)進(jìn)行遍歷，并從葉子節(jié)點(diǎn)先開(kāi)始翻轉(zhuǎn)剪菱。如果當(dāng)前遍歷到的節(jié)點(diǎn) root\textit{root}root 的左右兩棵子樹(shù)都已經(jīng)翻轉(zhuǎn)摩瞎，那么我們只需要交換兩棵子樹(shù)的位置，即可完成以 root\textit{root}root 為根節(jié)點(diǎn)的整棵子樹(shù)的翻轉(zhuǎn)孝常。java解法-遞歸：
class Solution {
public TreeNode invertTree(TreeNode root) {
//遞歸函數(shù)的終止條件旗们，節(jié)點(diǎn)為空時(shí)返回
if(root==null) {
return null;
}
//下面三句是將當(dāng)前節(jié)點(diǎn)的左右子樹(shù)交換
TreeNode tmp = root.right;
root.right = root.left;
root.left = tmp;
//遞歸交換當(dāng)前節(jié)點(diǎn)的 左子樹(shù)
invertTree(root.left);
//遞歸交換當(dāng)前節(jié)點(diǎn)的 右子樹(shù)
invertTree(root.right);
//函數(shù)返回時(shí)就表示當(dāng)前這個(gè)節(jié)點(diǎn)，以及它的左右子樹(shù)
//都已經(jīng)交換完了
return root;
}
}
二分查找：
1.折半查找算法
原理：取中間元素與查找元素進(jìn)行比較构灸，如果查找元素比中間元素大上渴，則在中間元素右邊查找，如果查找元素比中間元素小喜颁，則在中間元
素的左邊查找稠氮。
代碼例子：
#include <stdio.h>
/**
* 折半查找函數(shù)
*
* @param arr 數(shù)組
* @param len 數(shù)組長(zhǎng)度
* @param value 查找元素
*
* @return 返回查找元素的位置
*/
int searchItem(int arr[],int len, int value){
int low = 0,high = len-1,mid;
while (low <= high) {
mid = (low + high)/2;
if (value > arr[mid]) {
low = mid+1;
}else if (value < arr[mid]){
high = mid - 1;
}else{
return mid;
}
}
return -1;
}
int main(int argc, const char * argv[]) {
//數(shù)組必須是有序數(shù)組
int a[10] = {1,2,31,45,52,62,73,86,90,100};
//查找86元素
int l = searchItem(a,10,86);
printf("loc = %d\n",l);
return 0;
}
