一般算法.png
算法
字符串反转算法
//核心思想交换前后两个字符，同时移动指针
void char_reverse(char *cha){
char *begin = cha; //指向第一个字符
char *end = cha + strlen(cha)-1; //指向最后一个字符
while (begin < end) {
//交换前后两个字符，同时移动指针
char temp = *begin;
*(begin++) = *end; //将*end的的值赋值给 *begin begin+1
*(end--) = temp; //将temp的值赋值给 *end end-1
}
}
链表反转算法
链表反转.png
struct Node{
int data;
struct Node *next;
};
//链表反转
struct Node* reverseList(struct Node *head){
//定义遍历指针，初始化为头节点
struct Node *p = head;
//反转后的链表头部
struct Node *newH = NULL;
//遍历链表
while (p != NULL) {
//记录下一个节点
struct Node * temp = p->next;
//当前节点的next指向新链表头部
p->next = newH;
//更改新链表头部当前节点
newH = p;
//移动p指针
p = temp;
}
return newH;
}
//构造一个链表
struct Node * constructList(void){
//头部点定义
struct Node *head = NULL;
//记录当前尾节点
struct Node *cur = NULL;
for (int i = 0; i<5; i++) {
struct Node *node = malloc(sizeof(struct Node));
node->data = i;
//头节点为空，新节点即为头节点
if(head == NULL){
head = node;
}else{
//当前节点的next为新节点
cur->next = node;
}
cur = node;
}
return head;
}
//打印链表中的数据
void printList(struct Node *head){
struct Node * temp = head;
while (temp != NULL) {
printf("node is %d \n",temp->data);
temp = temp->next;
}
}
有序数组合并
有序数组合并.png
void OrderMergeList(int a[], int aLen, int b[], int bLen, int result[]){
int p = 0; // 遍历数组a的指针
int q = 0; // 遍历数组b的指针
int i = 0; // 记录当前存储位置
// 任一数组没有到达边界则进行遍历
while (p < aLen && q < bLen) {
// 如果a数组对应位置的值小于b数组对应位置的值
if (a[p] <= b[q]) {
// 存储a数组的值
result[i] = a[p];
// 移动a数组的遍历指针
p++;
}
else{
// 存储b数组的值
result[i] = b[q];
// 移动b数组的遍历指针
q++;
}
// 指向合并结果的下一个存储位置
i++;
}
// 如果a数组有剩余
while (p < aLen) {
// 将a数组剩余部分拼接到合并结果的后面
result[i] = a[p++];
i++;
}
// 如果b数组有剩余
while (q < bLen) {
// 将b数组剩余部分拼接到合并结果的后面
result[i] = b[q++];
i++;
}
}
排序算法
（1）冒泡排序是比较相邻位置的两个数，而选择排序是按顺序比较，找最大值或者最小值；
（2）冒泡排序每一轮比较后，位置不对都需要换位置，选择排序每一轮比较都只需要换一次位置；
（3）冒泡排序是通过数去找位置，选择排序是给定位置去找数；
-
冒泡排序优缺点：
- 优点:比较简单，空间复杂度较低，是稳定的；
- 缺点:时间复杂度太高，效率慢；
-
选择排序优缺点：
- 优点：一轮比较只需要换一次位置；
- 缺点：效率慢，不稳定（举个例子5，8，5，2，9 我们知道第一遍选择第一个元素5会和2交换，那么原序列中2个5的相对位置前后顺序就破坏了）。
冒泡
//冒泡
void BubbleSortList(int a[], int aLen){
int i,j;
int temp;
for (i = 0; i<aLen; i++) {
for (j = 0; j< aLen-i-1; j++) {
if(a[j]>a[j+1]){
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
选择
void SelectionSortList(int a[], int aLen){
int i,j;
int temp;
int minIndex;
for (i = 0; i<aLen-1; i++) {
minIndex = i;
for (j = i+1; j<aLen; j++) {
if(a[j]<a[minIndex]){
minIndex = j;
}
}
temp = a[minIndex];
a[minIndex] = a[i];
a[i] = temp;
}
}
插入
插入排序.png
void interSortList(int a[],int alen){
int i,j;
int temp;
for (i = 1; i<alen; i++) {
temp = a[i];
j = i;
if(a[j-1]>temp){
while (j>=1 && a[j-1]>temp) {
a[j] = a[j-1];
j--;
}
}
a[j] = temp;
}
}
Hash算法
哈希算法原理.png
- 字母(char)是一个长度为8的数据类型，因此总共有可能256种可能。
- 每个字母根据其ASCII码值作为数组的下标对应数组的一个数字。
- 数组中存储的是每个字符出现的次数。
char findFirstChar(char* cha)
{
char result = '\0';
// 定义一个数组 用来存储各个字母出现次数
int array[256];
// 对数组进行初始化操作
for (int i=0; i<256; i++) {
array[i] =0;
}
// 定义一个指针 指向当前字符串头部
char* p = cha;
// 遍历每个字符
while (*p != '\0') {
// 在字母对应存储位置 进行出现次数+1操作
array[*(p++)]++;
}
// 将P指针重新指向字符串头部
p = cha;
// 遍历每个字母的出现次数
while (*p != '\0') {
// 遇到第一个出现次数为1的字符，打印结果
if (array[*p] == 1)
{
result = *p;
break;
}
// 反之继续向后遍历
p++;
}
return result;
}
查找两个子视图的共同父视图
查找两个子视图的共同父视图.png
- (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 = [arrayOther objectAtIndex:arrayOther.count - i - 1];
// 比较如果相等 则为共同父视图
if (superOne == superOther) {
[result addObject:superOne];
i++;
}
// 如果不相等，则结束遍历
else{
break;
}
}
return result;
}
- (NSArray <UIView *> *)findSuperViews:(UIView *)view
{
// 初始化为第一父视图
UIView *temp = view.superview;
// 保存结果的数组
NSMutableArray *result = [NSMutableArray array];
while (temp) {
[result addObject:temp];
// 顺着superview指针一直向上查找
temp = temp.superview;
}
return result;
}
求无序数组当中的中位数
-
中位数
- 当n为奇数时， (n+1)/2
- 当n为偶数时， (n/2+(n/2 +1))/2
-
排序算法 + 中位数
- 冒牌排序、快速排序、堆排序...
-
利用快排思想(分治思想)
- 选取关键字，高低交替扫描
利用快排思想
任意挑一个元素，以该元素为支点，划分集合为两部分
如果左侧集合长度恰为(n-1)/2,那么支点就是中位数
如果左侧长度<(n-1)/2，那么中位点在右侧；反之，中位数在左侧
进入相应的一侧继续寻找中位点
//求一个无序数组的中位数
int findMedian(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)
{
//左半区间找
div = PartSort(a, low, div - 1);
}
else
{
//右半区间找
div = PartSort(a, div + 1, high);
}
}
//找到了
return a[mid];
}
int PartSort(int a[], int start, int end)
{
int low = start;
int high = end;
//选取关键字
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;
}
网友评论