字符串反轉(zhuǎn)
將字符串hello, world反向輸出
void char_reverse(char*cha){
// 指向第一個字符
char * begin = cha;
// 指向最后一個字符
char * end = cha + strlen(cha) -1;
while (begin < end){
//交換兩個字符的位置，并向中間移動一位
char temp = *begin;
*(begin ++) = *end;
*(end--) = temp;
}
}
char ch[] = "hello,world";
char_reverse(ch);
printf("reverse result is %s",ch);
鏈表反轉(zhuǎn)
鏈表反轉(zhuǎn)
ReverseList.h
#import <Foundation/Foundation.h>
NS_ASSUME_NONNULL_BEGIN
//定義一個鏈表
struct Node {
int data;
struct Node * next;
};
@interface ReverseList : NSObject
//鏈表反轉(zhuǎn)
struct Node * reverseList(struct Node * head);
//構(gòu)造一個鏈表
struct Node * constructList(void);
//打印鏈表中的數(shù)據(jù)
void printList(struct Node * head);
@end
ReverseList.m
#import "ReverseList.h"
@implementation ReverseList
struct Node * reverseList(struct Node * head){
//定義遍歷指針军俊，初始化為頭節(jié)點(diǎn)
struct Node * p = head;
//反轉(zhuǎn)后的b鏈表頭部
struct Node * newH = NULL;
while (p != NULL) {
//記錄下一個節(jié)點(diǎn)
struct Node * temp = p->next;
//當(dāng)前節(jié)點(diǎn)的next指向新鏈表頭部
p->next = newH;
//更改新鏈表頭部為當(dāng)前節(jié)點(diǎn)
newH = p;
//移動p指針
p = temp;
}
//返回反轉(zhuǎn)后的鏈表頭節(jié)點(diǎn)
return newH;
}
//構(gòu)造一個鏈表
struct Node * constructList(void){
//頭節(jié)點(diǎn)定義
struct Node * head = NULL;
//記錄當(dāng)前節(jié)點(diǎn)尾節(jié)點(diǎn)
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{
//當(dāng)前節(jié)點(diǎn)的next為新節(jié)點(diǎn)
cur->next = node;
}
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ù)組合并
有序數(shù)組合并
思想
思想
如上圖热芹，比較p秤掌、q兩個指針分別指向的數(shù)據(jù)大小恒傻，小的填充帶新數(shù)組中澈驼，兵移動相應(yīng)指針走搁，大的數(shù)據(jù)指針不動独柑，然后繼續(xù)這樣比較，當(dāng)一個數(shù)組的數(shù)據(jù)被完全填充后朱盐， 把另一個數(shù)組的數(shù)據(jù)依次填充到新數(shù)組中群嗤。
算法實(shí)現(xiàn)
MergeSortedList.h
#import <Foundation/Foundation.h>
NS_ASSUME_NONNULL_BEGIN
@interface MergeSortedList : NSObject
//將有序數(shù)組a和有序數(shù)組b合并到一個數(shù)組result當(dāng)中，且仍然保持有序
void mergeList(int a[], int aLen, int b[], int bLen, int result[]);
@end
NS_ASSUME_NONNULL_END
MergeSortedList.m
#import "MergeSortedList.h"
@implementation MergeSortedList
//將有序數(shù)組a和有序數(shù)組b合并到一個數(shù)組result當(dāng)中兵琳，且仍然保持有序
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)前儲存位置
//任一數(shù)組沒有達(dá)到邊界遍歷
while (p < aLen && q < bLen) {
//如果a數(shù)組對應(yīng)位置小于b數(shù)組對應(yīng)位置的值
if (a[p] < b[q]) {
//儲存a數(shù)組的b值
result[i] = a[p];
//移動p指針的位置
p++;
}
else{
//儲存b數(shù)組的b值
result[i] = b[q];
//移動q指針的位置
q++;
}
I++;
}
//如果a數(shù)組有剩余
while (p < aLen) {
result[i] = a[p++];
I++;
}
//如果b數(shù)組有剩余
while (q < bLen) {
result[i] = b[q++];
I++;
}
}
@end
算法調(diào)用
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]);
}
Hash算法
在一個字符串中找出第一個只出現(xiàn)一次的字符狂秘；
如：輸入abccdeff，則輸出 b
算法思路
- 字符（char）是一個長度為8的數(shù)據(jù)類型躯肌，因此用功有2^8 =256種可能
- 每個字母根據(jù)其ASCII碼值作為數(shù)組的下標(biāo)對應(yīng)數(shù)組的一個數(shù)字
- 數(shù)組中存儲的是每個字符出現(xiàn)的次數(shù)
哈希表概念
例：給定值是字母a者春，對應(yīng)的ASCII值是97，數(shù)組索引下標(biāo)為97
char ----f(key)---->index
f(key) = key
·存儲和查找都通過該函數(shù)清女，有效提高查找效率·
算法實(shí)現(xiàn)
///查找第一個只出現(xiàn)一次的字符
char findFirstChar(char * cha){
char result = '\0';
//定義一個數(shù)組用來存儲哥哥字母出現(xiàn)的次數(shù)
int array[256];
//對數(shù)組進(jìn)行初始化操作
for (int i = 0; i<256; i++) {
array[i] = 0;
}
//定義一個指針 指向當(dāng)前字符串的頭部
char * p = cha;
//遍歷每個字符
while (*p != '\0') {
//在字母對應(yīng)存儲位置 進(jìn)行出現(xiàn)洗漱+1操作
array[*(p++)]++;
}
// 將P值裝重新指向字符串頭部
p = cha;
// 遍歷每個字母出現(xiàn)的次數(shù)
while (*p != '\0') {
//遇到第一個出現(xiàn)次數(shù)為1的字符打印結(jié)果
if (array[*p] == 1) {
result = *p;
break;
}
//反之繼續(xù)查找
p++;
}
return result;
}
char cha[] = "abaccdeff";
char fc = findFirstChar(cha);
printf("this char is %c \n",fc);
查找兩個子視圖的共同父視圖
思路：
查找兩個子視圖的共同父視圖
算法實(shí)現(xiàn)
///查找兩個視圖的共同父視圖
- (NSArray<UIView *> *)findCommonSuperView:(UIView *)viewOne other:(UIView *)viewOther{
NSMutableArray * result = [NSMutableArray array];
//查找第一個視圖的所有父視圖
NSArray * arrayOne = [self findSuperViews:viewOne];
//查找第二個視圖的所有父視圖
NSArray * arrayOther = [self findSuperViews:viewOther];
int i = 0;
while (i < MIN((int)arrayOne.count, (int)arrayOther.count)) {
//倒序獲取各個視圖的父視圖
UIView * superOne = [arrayOne objectAtIndex:arrayOne.count - i - 1];
UIView * superOther = [arrayOne 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];
temp = temp.superview;
}
return result;
}
無序數(shù)組求中位數(shù)
首先理解一下中位數(shù)，比如[1,3,5,7,8],那么中位數(shù)就為“5”嫡丙，若是[1,3,5,7,8,10],那么中位數(shù)便為中間兩位的平局值拴袭，即（5+7）/2 = 6；
那么無序數(shù)組求中位數(shù)曙博，有哪些方法拥刻？
- 排序算法+中位數(shù)
- 利用快排思想（分治思想）
排序算法+中位數(shù)
冒泡排序、快速排序父泳、堆排序……
中位數(shù)
當(dāng)n為奇數(shù)般哼，為（n+1）/2;
當(dāng)n為偶數(shù)，為（(n/2)+(n/2)+1）/2;
快排思想
選取關(guān)鍵字惠窄，高低交替掃描
快排思想
- 任意挑選一個元素蒸眠，以該元素為支點(diǎn)，劃分集合為兩部分杆融。
- 如果左側(cè)集合長度恰好為(n-1)/2,那么支點(diǎn)恰為中位數(shù)楞卡。
- 如果左側(cè)長度小于(n-1)/2,那么中位點(diǎn)在右側(cè)；反之，中位數(shù)在右側(cè)臀晃。
- 進(jìn)入相應(yīng)一側(cè)繼續(xù)尋找中位點(diǎn)觉渴。
算法實(shí)現(xiàn)
///無序數(shù)組中查找中位數(shù)
float findMideian(int a[], int aLen){
int low = 0;
int high = aLen - 1;
int mid = (aLen - 1)/2;
int div = PartSort(a , low, high);
while (div != mid) {
if (mid < div) {
//左半?yún)^(qū)找
div = PartSort(a, low, div - 1) ;
}
else{
//右半?yún)^(qū)找
div = PartSort(a, div + 1, high) ;
}
}
if (aLen % 2 == 1) {
//若為奇數(shù)
return a[mid];
}
else{
//若為偶數(shù)
int mid1 = (aLen + 1)/2;
while (div != mid1) {
if (mid1 < div) {
//左半?yún)^(qū)找
div = PartSort(a, low, div - 1) ;
}
else{
//右半?yún)^(qū)找
div = PartSort(a, div + 1, high) ;
}
}
return (a[mid] + a[mid1])/2.0;
}
}
///快排
int PartSort(int a[], int start, int end){
int low = start;
int high = end;
//選取關(guān)鍵字
int key = a[end];
while (low < high) {
//左邊找比key大的值
while (low < high && a[low] <= key) {
++low;
}
//右邊找比key小的值
while (low < high && a[high] >= key) {
--high;
}
if (low < high) {
//找到之后交換左右的值
int temp = a[low];
a[low] = a[high];
a[high] = temp;
}
}
int temp = a[high];
a[high] = a[end];
a[end] = temp;
return low;
}
具體源碼可在這里查看。
