排序：排序
链表：iOS单向链表数据结构、判断两个链表是否相交并找出交点
求解1-100之间的所有素数/质数：https://zhidao.baidu.com/question/1430132761736407379.html
字符串反转
- 要求：
给定字符串“hello,word”，实现将其反转。
输出结果："drow,olleh"
-思路：
begin指针指向第一个字符；
end指针指向最后一个字符；
交换两个指针的内容，begin指针向后移动一位、end指针向前移动一位，交互下一对；
beign>=end的时候才交换，否则停止；
指针初始位置
指针移动
beign>=end的时候才交换
void char_reverse(char* cha)
{
// 指向第一个字符
char* begin = cha;
// 指向最后一个字符
char* end = cha + strlen(cha) - 1;
while (begin < end) {
// 交换前后两个字符
char temp = *begin;
*begin = *end;
*end = temp;
// 同时移动指针
begin++;
end--;
}
}
调用：
//字符串数组
char ch[] = "hello,world";/*char * ch = "hello,world"; 不可以*/
char_reverse(ch);
printf(ch);
OC的方法1
使用characterAtIndex获得String某一个位置的字符；
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获得某一个区间的字符串；
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);
链表反转
-
要求：
链表反转 思路：
1.原本的联调头结点为Head；
2.生成一个新的头节点NewH，作为反转后链表的头结点；
3.生成一个临时节点P，用来保存操作节点的下一个节点。例如目前要操作的节点是1，p就指向的是2；
4.先把内容为1的节点拿出来，作为新链表的头结点。头结点NewH指向内容为1的节点。
5.把p节点指向2的下一个节点。
6.内容为2的节点拿出来，作为新链表的头结点。头结点NewH指向内容为2的节点。依次类推。（每一个节点都插入到新链表，作为新链表的头结点）
链表反转
链表反转
链表反转
.h:
// 定义一个节点
struct Node {
int data;//节点数据
struct Node *next;//链表的下一个节点
};
@interface ReverseList : NSObject
// 链表反转
struct Node* reverseList(struct Node *head);
// 构造一个链表
struct Node* constructList(void);
// 打印链表中的数据
void printList(struct Node *head);
@end
.m:
@implementation ReverseList
/*
传入：原链表的头结点
返回：新链表的头结点
*/
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 = 1; i < 5; i++) {
struct Node *node = malloc(sizeof(struct Node));
node->data = I;
// 头结点为空，新结点即为头结点
if (head == NULL) {
head = node;
}
// 当前结点的next为新结点
else{
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;
}
}
@end
调用：
// 单链表反转
struct Node* head = constructList();
printList(head);
printf("---------\n");
struct Node* newHead = reverseList(head);
printList(newHead);
有序数组合并
-
要求：
如下，有两个有序数组。分别是[1,4,6,7,9]、[2、3、5、6、8、10、11、12]
有序数组合并
1.两个数组a、b。用一个新的数组c放合并的结果。比如p存放数组a遍历到的位数，q存放b数组遍历到的位数。
2.a[p]和b[q]进行比较，假如a[p]小，就把a[p]放到数组c中，并且把p+1。反之，如果b[q]小，就把b[q]放到数组里面,q+1。
3.然后再用新的p和q进行比较。直到某一个数组变量完后，看哪个数组没有变量完，把没有变量完的部分放到数组c里面。
有序数组合并
有序数组合并
有序数组合并
@interface MergeSortedList : NSObject
// 将有序数组a和b的值合并到一个数组result当中，且仍然保持有序
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; // 遍历数组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++;
}
}
@end
调用：
// 用于存储归并结果
int result[13];
// 归并操作g
mergeList(a, 5, b, 8, result);
// 打印归并结果
printf("merge result is ");
for (int i = 0; i < 13; i++) {
printf("%d ", result[I]);
}
两个有序数组，求第K大的数
也是和上面的一题思想一样，递归合并两个数组，直到合并数组到第K个位置结束。
初始化两个指针 i 和 j 分别指向两个数组的开头，表示当前考虑的区间范围。
比较两个指针所指向的元素，将较小的那个元素加入到一个新的数组中。
移动指针，将被选择的元素所在数组的指针向后移动一位。
重复步骤 2 和 3，直到新数组中有 k 个元素为止。
Hash算法
查找一个字符串中，第一个只出现一次的字符
- 一个字符长度是8，每一位有0、1两种组成可能，所以1个字符有2的8次方个可能，就是256个可能。
采用hash算法思想：
- 定义一个256大小的数组，数组中存储的是每个字符出现的次数。
-
每个字母根据ascii码值，把次数放到对应的位置。例如a的ascii值是97,数组的第97位就存放a出现的次数。
image.png
#include <stdio.h>
#include <string.h>
char first_unique_char(char *s) {
int char_count[256] = {0}; // 用于存储每个字符的出现次数
// 计数每个字符的出现次数
for (int i = 0; i < strlen(s); i++) {
char_count[s[i]]++;
}
// 找到第一个只出现一次的字符
for (int i = 0; i < strlen(s); i++) {
if (char_count[s[i]] == 1) {
return s[i];
}
}
// 如果没有找到只出现一次的字符，则返回空字符
return '\0';
}
int main() {
char input_str[] = "leetcode";
char result = first_unique_char(input_str);
if (result != '\0') {
printf("第一个只出现一次的字符是: %c\n", result);
} else {
printf("没有找到只出现一次的字符\n");
}
return 0;
}
查找两个子视图的共同父视图
- 要求：
有C、D两个视图。要查找这两个视图的共同父视图。
图中箭头代表父视图。如A是C的父视图。
查找两个子视图的共同父视图
-
思路：
遍历出两个view的父视图放到两个数组里面。从后往前遍历两个数组中的值。
查找两个自视图共同的父视图
.h:
@interface CommonSuperFind : NSObject
// 查找两个视图的共同父视图
- (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];
// 查找第一个视图的所有父视图
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;
}
@end
快速排序
具体看链接快速排序
@implementation QuickSort
//a[]:数组 begin：开始排序的位置 end：结束排序的位置
void quickSort(int a[],int begin,int end){
if (begin > end) {
return;
}
int i = begin;//左边开始寻找的位置
int j = end;//右边开始寻找的位置
int key = a[i];//设置左边的第一个值为参考值
while (i!=j) {//当i和j相遇时，交换相遇位置的值和参考值即可；不相等时，进行位置交换
while (i<j && a[j] > key) {//从右边开始寻找，找到比参考值小的值，就停止
j--;
}
while (i<j && a[i] <= key) {//从左边开始寻找，找到比参考值大的值，就停止；注意，必须是<=，如果设置为<，左边的第一个数作为参考值了，比较的时候i就不会进行移动了
I++;
}
if (i < j) {//如果i = j，进行交换没有意义
//把找到的值进行交换，小的放到前面，大的放到后面
int tmp = a[I];
a[i] = a[j];
a[j] = tmp;
}
}
//移动参考值的位置，让参考值前面的值都比他小，后面的值都比他大
int tmp = a[begin];
a[begin] = a[j];
a[j] = tmp;
for (int i = 0; i < 8; i++) {
printf("%d ", a[I]);
}
printf("----------");
//对参考值左边的进行排序
quickSort(a, begin, j - 1);
//对参考值右边的进行排序
quickSort(a, j + 1, end);
}
@end
- (void)viewDidLoad {
[super viewDidLoad];
int a[] = {9,8,10,20,7,6,5,11};
quickSort(a, 0, 7);
}
求无序数组当中的中位数
方法1：排序算法+中位数：
冒泡、快速、堆排序、二分查找
中位数的定义：
当n为奇数的时候，中位数 = (n -1)/2 的这位数就是中位数。
eg：2、4、6、7、9、20、22 。一共有7位数， 中位数就是第（7-1）/2 = 3位上面的数 7。
当n为偶数的时候，中位数就是中间两位数之和的一半，就是中位数。
中位数 = （(n -1)/2 + ( (n - 1)/2 + 1) ）/2
eg：2、4、6、7、9、20、22 、25。一共有8位数， 中位数两位数是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(@"数组的中位数是: %.2f", median);
}
return 0;
}
方法2：利用快排思想
思路：
已知中位数是哪个位置上的。
- 数组个数为奇数：(n-1)/2 就是中位
取数组中的一个值作为关键值，进行快速排序，看他在快速排序后的位置。如果刚好是中位数的位置，中位数就是这个值。
如果位置< (n-1)/2,那么中位数就在这个位置的左边
如果位置> (n-1)/2,那么中位数就在这个位置的右边
又再去新指定的区域找一个关键字值，进行快速排序。重复以上步骤。
- 数组个数为偶数数：(n-1)/2、 (n-1)/2 +1 两个位置上的数之和的平均数就是中位
@implementation MediaFund
int mediaFund(int a[],int alength){
//找到(n-1)/2位置的数
int media = (alength - 1)/2;
int div = partSort(a, 0, alength - 1);
while (div != media) {
if (div < media) {//值在右侧，查找右侧区域
div = partSort(a, div + 1, alength -1);
}else{//值在左侧，查找左侧区域
div= partSort(a, 0, div -1);
}
}
//如果是偶数，找到(n-1)/2 + 1位置的数
if (alength%2 == 0) {//数组是偶数个
int newLoc = div + 1;
int newDiv = partSort(a, newLoc, alength - 1);
while (newLoc != newDiv) {
if (newDiv > newLoc) {
newDiv = partSort(a, newLoc, newDiv - 1);
}
}
printf("数组中的个数为偶数：a[div]:%d~~~[newLoc]:%d\n",a[div],a[newDiv]);
return (a[div] + a[newLoc])/2;
}else{//数组中的个数为奇数
printf("数组中的个数为奇数：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
调用：
// 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个数) 中位数为第（7 - 1）/2 = 3位，8
//5 6 7 8 9 10 11 20 （8个数） 中位数为第4位+第5位之和/2
int div = mediaFund(a, 8);
printf("中位数是：%d\n",div);
printf("排序后的数组是：");
for (int i = 0; i < 8; i++) {
printf("%d ", a[I]);
}
冒泡排序：
https://www.runoob.com/w3cnote/bubble-sort.html
算法步骤:
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
抽象类的应用场景.png
#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;
}
二叉树
二叉树详解：https://www.hello-algo.com/chapter_tree/binary_tree/
遍历二叉树：
https://www.hello-algo.com/chapter_tree/binary_tree_traversal/
-
层序遍历
层序遍历
-
前序 中序 后序
二叉树遍历
/* 前序遍历 */
void preOrder(TreeNode *root, int *size) {
if (root == NULL)
return;
// 访问优先级：根节点 -> 左子树 -> 右子树
arr[(*size)++] = root->val;
preOrder(root->left, size);
preOrder(root->right, size);
}
/* 中序遍历 */
void inOrder(TreeNode *root, int *size) {
if (root == NULL)
return;
// 访问优先级：左子树 -> 根节点 -> 右子树
inOrder(root->left, size);
arr[(*size)++] = root->val;
inOrder(root->right, size);
}
/* 后序遍历 */
void postOrder(TreeNode *root, int *size) {
if (root == NULL)
return;
// 访问优先级：左子树 -> 右子树 -> 根节点
postOrder(root->left, size);
postOrder(root->right, size);
arr[(*size)++] = root->val;
}
翻转二叉树
思路：
显然，我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 root\textit{root}root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root\textit{root}root 为根节点的整棵子树的翻转。java解法-递归：
class Solution {
public TreeNode invertTree(TreeNode root) {
//递归函数的终止条件，节点为空时返回
if(root==null) {
return null;
}
//下面三句是将当前节点的左右子树交换
TreeNode tmp = root.right;
root.right = root.left;
root.left = tmp;
//递归交换当前节点的 左子树
invertTree(root.left);
//递归交换当前节点的 右子树
invertTree(root.right);
//函数返回时就表示当前这个节点，以及它的左右子树
//都已经交换完了
return root;
}
}
二分查找：
1.折半查找算法
原理：取中间元素与查找元素进行比较，如果查找元素比中间元素大，则在中间元素右边查找，如果查找元素比中间元素小，则在中间元
素的左边查找。
代码例子：
#include <stdio.h>
/**
* 折半查找函数
*
* @param arr 数组
* @param len 数组长度
* @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[]) {
//数组必须是有序数组
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;
}
