排序：排序
鏈表：iOS單向鏈表數(shù)據(jù)結構、判斷兩個鏈表是否相交并找出交點
求解1-100之間的所有素數(shù)/質數(shù)：https://zhidao.baidu.com/question/1430132761736407379.html
字符串反轉
- 要求：
給定字符串“hello,word”，實現(xiàn)將其反轉。
輸出結果："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--;
}
}
調用：
//字符串數(shù)組
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獲得某一個區(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);
鏈表反轉
-
要求：
鏈表反轉 思路：
1.原本的聯(lián)調頭結點為Head；
2.生成一個新的頭節(jié)點NewH，作為反轉后鏈表的頭結點；
3.生成一個臨時節(jié)點P，用來保存操作節(jié)點的下一個節(jié)點。例如目前要操作的節(jié)點是1，p就指向的是2；
4.先把內容為1的節(jié)點拿出來，作為新鏈表的頭結點。頭結點NewH指向內容為1的節(jié)點。
5.把p節(jié)點指向2的下一個節(jié)點。
6.內容為2的節(jié)點拿出來，作為新鏈表的頭結點。頭結點NewH指向內容為2的節(jié)點。依次類推。（每一個節(jié)點都插入到新鏈表，作為新鏈表的頭結點）
鏈表反轉
鏈表反轉
鏈表反轉
.h:
// 定義一個節(jié)點
struct Node {
int data;//節(jié)點數(shù)據(jù)
struct Node *next;//鏈表的下一個節(jié)點
};
@interface ReverseList : NSObject
// 鏈表反轉
struct Node* reverseList(struct Node *head);
// 構造一個鏈表
struct Node* constructList(void);
// 打印鏈表中的數(shù)據(jù)
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;
}
// 打印鏈表中的數(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
調用：
// 單鏈表反轉
struct Node* head = constructList();
printList(head);
printf("---------\n");
struct Node* newHead = reverseList(head);
printList(newHead);
有序數(shù)組合并
-
要求：
如下，有兩個有序數(shù)組。分別是[1,4,6,7,9]、[2、3、5、6、8、10、11、12]
有序數(shù)組合并
1.兩個數(shù)組a、b。用一個新的數(shù)組c放合并的結果。比如p存放數(shù)組a遍歷到的位數(shù)，q存放b數(shù)組遍歷到的位數(shù)。
2.a[p]和b[q]進行比較，假如a[p]小，就把a[p]放到數(shù)組c中，并且把p+1。反之，如果b[q]小，就把b[q]放到數(shù)組里面,q+1。
3.然后再用新的p和q進行比較。直到某一個數(shù)組變量完后，看哪個數(shù)組沒有變量完，把沒有變量完的部分放到數(shù)組c里面。
有序數(shù)組合并
有序數(shù)組合并
有序數(shù)組合并
@interface MergeSortedList : NSObject
// 將有序數(shù)組a和b的值合并到一個數(shù)組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; // 遍歷數(shù)組a的指針
int q = 0; // 遍歷數(shù)組b的指針
int i = 0; // 記錄當前存儲位置
// 任一數(shù)組沒有到達邊界則進行遍歷
while (p < aLen && q < bLen) {
// 如果a數(shù)組對應位置的值小于b數(shù)組對應位置的值
if (a[p] <= b[q]) {
// 存儲a數(shù)組的值
result[i] = a[p];
// 移動a數(shù)組的遍歷指針
p++;
}
else{
// 存儲b數(shù)組的值
result[i] = b[q];
// 移動b數(shù)組的遍歷指針
q++;
}
// 指向合并結果的下一個存儲位置
I++;
}
// 如果a數(shù)組有剩余
while (p < aLen) {
// 將a數(shù)組剩余部分拼接到合并結果的后面
result[i] = a[p++];
I++;
}
// 如果b數(shù)組有剩余
while (q < bLen) {
// 將b數(shù)組剩余部分拼接到合并結果的后面
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]);
}
兩個有序數(shù)組，求第K大的數(shù)
也是和上面的一題思想一樣，遞歸合并兩個數(shù)組，直到合并數(shù)組到第K個位置結束。
初始化兩個指針 i 和 j 分別指向兩個數(shù)組的開頭，表示當前考慮的區(qū)間范圍。
比較兩個指針所指向的元素，將較小的那個元素加入到一個新的數(shù)組中。
移動指針，將被選擇的元素所在數(shù)組的指針向后移動一位。
重復步驟 2 和 3，直到新數(shù)組中有 k 個元素為止。
Hash算法
查找一個字符串中，第一個只出現(xiàn)一次的字符
- 一個字符長度是8，每一位有0、1兩種組成可能，所以1個字符有2的8次方個可能，就是256個可能。
采用hash算法思想：
- 定義一個256大小的數(shù)組，數(shù)組中存儲的是每個字符出現(xiàn)的次數(shù)。
-
每個字母根據(jù)ascii碼值，把次數(shù)放到對應的位置。例如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}; // 用于存儲每個字符的出現(xiàn)次數(shù)
// 計數(shù)每個字符的出現(xiàn)次數(shù)
for (int i = 0; i < strlen(s); i++) {
char_count[s[i]]++;
}
// 找到第一個只出現(xiàn)一次的字符
for (int i = 0; i < strlen(s); i++) {
if (char_count[s[i]] == 1) {
return s[i];
}
}
// 如果沒有找到只出現(xiàn)一次的字符，則返回空字符
return '\0';
}
int main() {
char input_str[] = "leetcode";
char result = first_unique_char(input_str);
if (result != '\0') {
printf("第一個只出現(xiàn)一次的字符是: %c\n", result);
} else {
printf("沒有找到只出現(xiàn)一次的字符\n");
}
return 0;
}
查找兩個子視圖的共同父視圖
- 要求：
有C、D兩個視圖。要查找這兩個視圖的共同父視圖。
圖中箭頭代表父視圖。如A是C的父視圖。
查找兩個子視圖的共同父視圖
-
思路：
遍歷出兩個view的父視圖放到兩個數(shù)組里面。從后往前遍歷兩個數(shù)組中的值。
查找兩個自視圖共同的父視圖
.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;
// 保存結果的數(shù)組
NSMutableArray *result = [NSMutableArray array];
while (temp) {
[result addObject:temp];
// 順著superview指針一直向上查找
temp = temp.superview;
}
return result;
}
@end
快速排序
具體看鏈接快速排序
@implementation QuickSort
//a[]:數(shù)組 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) {//從左邊開始尋找，找到比參考值大的值，就停止；注意，必須是<=，如果設置為<，左邊的第一個數(shù)作為參考值了，比較的時候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);
}
求無序數(shù)組當中的中位數(shù)
方法1：排序算法+中位數(shù)：
冒泡、快速、堆排序、二分查找
中位數(shù)的定義：
當n為奇數(shù)的時候，中位數(shù) = (n -1)/2 的這位數(shù)就是中位數(shù)。
eg：2、4、6、7、9、20、22 。一共有7位數(shù)， 中位數(shù)就是第（7-1）/2 = 3位上面的數(shù) 7。
當n為偶數(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ù)是哪個位置上的。
- 數(shù)組個數(shù)為奇數(shù)：(n-1)/2 就是中位
取數(shù)組中的一個值作為關鍵值，進行快速排序，看他在快速排序后的位置。如果剛好是中位數(shù)的位置，中位數(shù)就是這個值。
如果位置< (n-1)/2,那么中位數(shù)就在這個位置的左邊
如果位置> (n-1)/2,那么中位數(shù)就在這個位置的右邊
又再去新指定的區(qū)域找一個關鍵字值，進行快速排序。重復以上步驟。
- 數(shù)組個數(shù)為偶數(shù)數(shù)：(n-1)/2、 (n-1)/2 +1 兩個位置上的數(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) {//值在右側，查找右側區(qū)域
div = partSort(a, div + 1, alength -1);
}else{//值在左側，查找左側區(qū)域
div= partSort(a, 0, div -1);
}
}
//如果是偶數(shù)，找到(n-1)/2 + 1位置的數(shù)
if (alength%2 == 0) {//數(shù)組是偶數(shù)個
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ù)組中的個數(shù)為偶數(shù)：a[div]:%d~~~[newLoc]:%d\n",a[div],a[newDiv]);
return (a[div] + a[newLoc])/2;
}else{//數(shù)組中的個數(shù)為奇數(shù)
printf("數(shù)組中的個數(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
調用：
// 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個數(shù)) 中位數(shù)為第（7 - 1）/2 = 3位，8
//5 6 7 8 9 10 11 20 （8個數(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
算法步驟:
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。
針對所有的元素重復以上的步驟，除了最后一個。
持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
抽象類的應用場景.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;
// 訪問優(yōu)先級：根節(jié)點 -> 左子樹 -> 右子樹
arr[(*size)++] = root->val;
preOrder(root->left, size);
preOrder(root->right, size);
}
/* 中序遍歷 */
void inOrder(TreeNode *root, int *size) {
if (root == NULL)
return;
// 訪問優(yōu)先級：左子樹 -> 根節(jié)點 -> 右子樹
inOrder(root->left, size);
arr[(*size)++] = root->val;
inOrder(root->right, size);
}
/* 后序遍歷 */
void postOrder(TreeNode *root, int *size) {
if (root == NULL)
return;
// 訪問優(yōu)先級：左子樹 -> 右子樹 -> 根節(jié)點
postOrder(root->left, size);
postOrder(root->right, size);
arr[(*size)++] = root->val;
}
翻轉二叉樹
思路：
顯然，我們從根節(jié)點開始，遞歸地對樹進行遍歷，并從葉子節(jié)點先開始翻轉。如果當前遍歷到的節(jié)點 root\textit{root}root 的左右兩棵子樹都已經(jīng)翻轉，那么我們只需要交換兩棵子樹的位置，即可完成以 root\textit{root}root 為根節(jié)點的整棵子樹的翻轉。java解法-遞歸：
class Solution {
public TreeNode invertTree(TreeNode root) {
//遞歸函數(shù)的終止條件，節(jié)點為空時返回
if(root==null) {
return null;
}
//下面三句是將當前節(jié)點的左右子樹交換
TreeNode tmp = root.right;
root.right = root.left;
root.left = tmp;
//遞歸交換當前節(jié)點的 左子樹
invertTree(root.left);
//遞歸交換當前節(jié)點的 右子樹
invertTree(root.right);
//函數(shù)返回時就表示當前這個節(jié)點，以及它的左右子樹
//都已經(jīng)交換完了
return root;
}
}
二分查找：
1.折半查找算法
原理：取中間元素與查找元素進行比較，如果查找元素比中間元素大，則在中間元素右邊查找，如果查找元素比中間元素小，則在中間元
素的左邊查找。
代碼例子：
#include <stdio.h>
/**
* 折半查找函數(shù)
*
* @param arr 數(shù)組
* @param len 數(shù)組長度
* @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;
}
