[ 题 : ] 栈-思路
//入栈 stack
- (void)stackPush:(NSObject *)obj {
[_array addObject:obj];
}
//出栈 - 先进后出first in, last out
- (NSObject *)stackPop {
if (_array.count > 0) {
return [_array lastObject]; //最后加入的数据先取出
}
return nil;
}
[ 题 : ] 队列queue-思路
//加入队列
- (void)queuePush:(NSObject *)obj {
[_array addObject:obj];
}
//出队列 - 先进先出first in, first out
- (NSObject *)queuePop {
if (_array.count > 0) {
return [_array firstObject];//最先加入的先取出
}
return nil;
}
[ 题 : ] 冒泡排序
【冒泡排序】：相邻元素两两比较，比较完一趟，最(大或小)值出现在末尾
(1) 升序冒泡排序思路 : 从左往右依次对比, 大的往后换位置, 循环5-1 = 4次
排序前 2,1,4,5,3 => 排序后 1,2,3,4,5
第1轮 : 2,1,4,5,3
(2,1)->2比1大, 要交换 : 1,2,4,5,3
(2,4)->2比4小, 不交换 : 1,2, 4,5,3
(4,5)->4比5小, 不交换 : 1,2, 4,5,3
(5,3)->5比3大, 要交换 : 1,2, 4,3,5
第1轮结束时:最后 1位最大值5已完成
第2轮 : 1,2,4,3,5
(1,2)->1比2小,不交换 : 1,2,4,3,5
(2,4)->2比4小,不交换 : 1,2, 4,3,5
(4,3)->4比3大,要交换 : 1,2, 3,4,5
第2轮结束时:倒数第2位值4已完成
(另外: 此处进行两轮其实已经结束了,所以不用在轮询了, 判断排好序就结束 )
依次类推.
//冒泡排序 1
- (void)bublleSort:(NSMutableArray *)arr{
for(int i = 0; i < arr.count - 1; i++) { //趟数
for(int j = 0; j < arr.count - i - 1; j++) { //比较次数
//如果左边 > 右边 就交换位置
if(arr[j] > arr[j+1]){
NSNumber *temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
//else 直接下一次比较
}
}
}
//冒泡排序 2 -改良
- (void)bublleSortNew:(NSMutableArray *)arr{
//加一个标识
int endTag = 0;
for(int i = 0; i < arr.count - 1; i++) { //趟数
for(int j = 0; j < arr.count - i - 1; j++) { //比较次数
//如果左边 > 右边 就交换位置
if(arr[j] > arr[j+1]){
NSNumber *temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
//发生了交换,更新tag值
endTag = i;
}
}
//如果没有发生交换,说明已经排好序了, 直接退出循环
if (endTag < i) {
break;
}
}
}
[ 题 : ] 选择排序
【选择排序】：最值出现在起始端(每次轮询右移一位)
(1) 升序排序思路 : 从左往右依次两两对比, 小的值 跟第1位换位置, 循环5-1 = 4次
排序前 2,1,4,5,3 => 排序后 1,2,3,4,5
(2)降序排序思路 : 从左往右依次两两对比, 大的值 跟第1位换位置, 循环5-1 = 4次
排序前 2,1,4,5,3 => 排序后 5,4,3,2,1
升序排序演练 :
第1轮 : 2,1,4,5,3
(2),(1)->2比1大, 要交换 : 1,2,4,5,3
(1),(4)->1比4小, 不交换 : 1,2, 4,5,3
(1),(5)->1比5小, 不交换 : 1,2, 4,5,3
(1),(3)->1比3小, 不交换 : 1,2, 4,5,3
第1轮结束时:最后 1位最小值1已完成
第2轮 : 1,2,4,5,3
第2轮结束时:没有交换(第2位是第二大)
第3轮 : 1,2,3,4,5
第3轮结束时: 排序完成(3和4交换位置)
(另外: 此处进行两轮其实已经结束了,所以不用在轮询了, 判断排好序就结束 )
依次类推.
//选择排序-升序
- (void)selectSortAsc:(NSMutableArray *)arr{
for(int i = 0; i < arr.count - 2; i++) { //趟数
NSNumber *temp = arr[i];//参考的对象
for(int j = i + 1; j < arr.count - 1; j++) { //比较次数
//比参考值小 就交换位置
if(arr[j] < temp){
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
降序同理
[ 题 : ] 二分法查找（折半查找）
从已排序的数中找到对应的值(即已知最大值,最小值, 找其中的值)
(假如A有68块钱)
A: 猜猜我有几块钱 ? 不超过100块 .
B: 30块?
A:不止(猜小了)
B:90块?
A:多了(猜大了)
...
....(猜了20次, B绝望了)...
二分法思路演练: (B每次都猜剩余区间的中间值)
(假如A有68块钱)
A: 猜猜我有几块钱 ? 不超过100块 .
B: 50 块? (100的一半 )
A:不止(猜小了)
B:75块? (51 -100的中间 , 50被排除了,现在最小值是51)
A:多了(猜大了)
B: 62 块? (50 -74的中间 )
A:不止(猜小了)
B:68块? (63 -74的中间 )
A:猜对了
题: arr = @[3,4,5,....200]; 找到 num = 120 的位置index
//二分查找 :
- (int)midFind:(NSMutableArray *)arr num:(int)num {
int min = 0;//最小值位置
int max = (int)arr.count - 1;//最大值位置
while (min <= max) {
int mid = (min + max)/2;//中间位置
if ([arr[mid] intValue] < num) {//猜小了
min = mid + 1;//mid值被排除了,所以最小值是mid + 1
} else if ([arr[mid] intValue] > num) {//猜大了
max = mid - 1;//mid值被排除了,所以最大值是mid - 1
} else {
return mid;
}
//如果最小值=最大值也找不到的话,说明没有这个对象
if (min == max && min != num) {
return -1;
}
}
return -1;
}
[ 题 : ] 递归
从0数到100
//从0数到100
[self recursionSort:0];
//递归
- (void)recursionSort:(int)num {
if (num < 100) {
num += 1;
[self recursionSort:num];
}
}
[ 题 : ] 快速排序
第一步: 随机取一个值作为参考值
第二步: 小于参考值的数都放左侧, 大于放右侧
第三步: 递归对左右两侧分别执行上述两步(排序数<2时退出)
演示简单排序: [6,5,7] 快速排序
第一步: 随机取一个值6 作为参考值
第二步: 小于6的数都放左侧, 大于6放右侧
演示排序2 : [4,1,8,6,3,2,5,7,9] 快速排序
第一步:选取参考值(4).
第二步:创建三个数组分别存储,[<4] , [=4], [>4]
第三步:分别对[<4] , [>4] 递归调用该方法.
第四步:分别拼接返回.
调用:
NSArray *dataA = [self quickSorting:@[@4,@1,@8,@6,@3,@6,@3,@2,@5,@7,@9]];
NSLog(@"quickSorting : %@",dataA);
OC算法:
/**
:快速排序
1.为了简化, 这里忽略一些判断,空值,count=0 等等
要求 : 快速排序NSArray *dataA = [quickSorting:@[4,1,8,6,3,2,5,7,9]];
*/
- (NSMutableArray *)quickSorting:(NSArray *)array {
if (array.count > 1) {
//取随机数[0,count)
long random = arc4random() % array.count;
//基准数
int baseNum = [array[random] intValue];
//左侧待存放数组
NSMutableArray *leftArr = @[].mutableCopy;
//存放相等的数组
NSMutableArray *sameArr = @[].mutableCopy;
//右侧待存放数组
NSMutableArray *rightArr = @[].mutableCopy;
for (int i=0; i<array.count; i++) {
if ([array[i] intValue] < baseNum) {
//小于基准数
[leftArr addObject:array[i]];
} else if ([array[i] intValue] == baseNum) {
//等于基准数
[sameArr addObject:array[i]];
} else if ([array[i] intValue] > baseNum) {
//大于基准数
[rightArr addObject:array[i]];
}
}
//递归排序左侧数组- 个数>1
NSMutableArray *sortLeftArr = leftArr.count > 1 ? [self quickSorting:leftArr] : leftArr;
//递归排序右侧数组
NSMutableArray *sortRightArr = rightArr.count > 1 ? [self quickSorting:rightArr] : rightArr;
//拼接-左侧, 相等值
[sortLeftArr addObjectsFromArray:sameArr];
//拼接-右侧
[sortLeftArr addObjectsFromArray:sortRightArr];
//最后返回排序结果
return sortLeftArr;
}
return [array mutableCopy];
}
[ 题 : ] 字符串翻转
字符串的逆序输出:
输入字符串为“hello world”,输出结果应当为“world hello”。
例如:
//翻转"123456789"
[self overturnStr:@"123456789"];
//字符串翻转
- (void)overturnStr:(NSString *)str {
NSString *turnStr = @"";
for (NSInteger i=str.length-1; i>=0; i--) {
turnStr = [turnStr stringByAppendingString:[str substringWithRange:NSMakeRange(i, 1)]];
}
NSLog(@"翻转结果 : %@",turnStr);
}
[ 题 : ] 单链表结构
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
[ 题 : ] 单链表翻转
1.定义链表结点结构:
typedef struct Node
{
int data;
struct Node *next; //next指向下一个结点
} Node,*pnode;
2.递归实现逻辑
void reverse(Node node,Node pre) {
if(node == null) return;
Node next = node.next;
node.next = pre;
reverse(next, node();//递归
}
实现 :
void main(string[] args) {
//生成链表
Node p1 = new Node(1);
Node p2 = new Node(2);
Node p3 = new Node(3);
p1.next = p2;
p2.next = p3;
//翻转实现
reverse(p1, null);
}
[ 题 : ] 二叉树
(1)空二叉树——如图(a)；
(2)只有一个根结点的二叉树——如图(b)；
(3)只有左子树——如图(c)；
(4)只有右子树——如图(d)；
(5)完全二叉树——如图(e)。
其他术语 :
树的结点（node）：包含一个数据元素及若干指向子树的分支；
孩子结点（child node）：结点的子树的根称为该结点的孩子；
双亲结点：B 结点是A 结点的孩子，则A结点是B 结点的双亲；
兄弟结点：同一双亲的孩子结点； 堂兄结点：同一层上结点；
祖先结点: 从根到该结点的所经分支上的所有结点
子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙
结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；
树的深度：树中最大的结点层
结点的度：结点子树的个数
树的度： 树中最大的结点度。
叶子结点：也叫终端结点，是度为 0 的结点；
分枝结点：度不为0的结点；
有序树：子树有序的树，如：家族树；
无序树：不考虑子树的顺序；
[ 题 : ] 二叉树的深度(层数)
基本思路是递归，从根节点出发，求其左右子树的深度，取左右子树的深度+1的较大者为当前树的深度（求所有子树深度的时候使用递归）。如果到达叶子结点，那么返回0。
Python:
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def TreeDepth(self, pRoot):
# write code here
if pRoot is None:
return 0
llength = self.TreeDepth(pRoot.left)
rlength = self.TreeDepth(pRoot.right)
return max(llength + 1, rlength + 1)
[ 题 : ] 二叉树的三种遍历方式(前,中,后)
二叉树的三种遍历方式代码都是一样的,只是在获取该值的时机不一样:
每个结点都是三进三出
1.前序遍历 : 第一次被访问时(从其它结点第一次进入) , 获取该值88
2.中序遍历 : 第二次被访问时(从其它结点第二次进入) , 获取该值88
3.后序遍历 : 第三次被访问时(从其它结点第三次进入) , 获取该值88
存储结构
顺序存储方式 : 连续的存储地址, 下面以数组(分配连续存储空间)存放
typenode=record
data:datatype
l,r:integer;
end;
vartr:array[1..n]ofnode;
链表存储方式 : 结点之间存储地址不是连续的, 通过指针寻找
typebtree=^node；
node=record
data:datatye;
lchild,rchild:btree;
end;
L、D、R分别表示遍历左子树、访问根结点和遍历右子树
[ 题 : ] 遍历二叉树
void XXBL(tree *root){
//左子树递归遍历
if(root->lchild!=NULL) {
XXBL(root->lchild);
}
//右子树递归遍历
if(root->rchild!=NULL) {
XXBL(root->rchild);
}
}
[ 题 : ] 三种遍历
代码: 在上面遍历的基础上, 三种不同时机获取该值,分别为前,中,后
void XXBL(tree *root){
方式1. 如果在此处打印就是 先序遍历
print(root.data);
//左子树递归遍历
if(root->lchild!=NULL) {
XXBL(root->lchild);
}
方式2. 如果在此处打印就是 中序遍历
print(root.data);
//右子树递归遍历
if(root->rchild!=NULL) {
XXBL(root->rchild);
}
方式3. 如果在此处打印就是 后序遍历
print(root.data);
}
根据二叉树某两种遍历结果,反推二叉树
1.前序+中序 -> 可求 二叉树
2.后序+中序 -> 可求 二叉树
(前序+后序 -> 不可求 二叉树)
1.前序+中序 -> 求 二叉树结构:
1.前序遍历 = 根结点 + 左子树(前序遍历) + 右子树(前序遍历)
2.中序遍历 = 左子树(中序遍历) + 根结点 + 右子树(中序遍历)
解题思路:
第一步: 得到根结点:
前序遍历结果的第一个结点位置(0)就是根结点root,
然后在中序结果里根据根结点root找到中序结果里根结点的位置(2)
第二步: 在中序结果里, 以根结点为界限,拆分左右两边得到左子树中序lNode, 右子树中序rNode,
再以该两子树结果,到先序遍历结果中拆分找出左右先序结果
第三步: 递归上述两步
public class Solution {
public static TreeNode reConstructBinaryTree(int [] prev,int [] in) {
//不管什么遍历方式，结果长度肯定是一样的，都是总结点数
if(prev.length!= in.length || prev.length<1){
return null;
}
//只有一个节点，那就是根节点
if(prev.length == 1){
return new TreeNode(prev[0]);
}
//在中序遍历结果中找根节点
int index = -1;
for(int i=0;i<in.length;i++){
if(in[i]==prev[0]){
index=i;
break;
}
}
//没找到，说明数据有问题
if(index==-1){
return null;
}
//找到根节点了
TreeNode root = new TreeNode(prev[0]);
//得到左子树的前序遍历结果
int[] lChildPrev = new int[index];
System.arraycopy(prev,1,lChildPrev,0,index);
//得到左子树的中序遍历结果
int[] lChildin = new int[index];
System.arraycopy(in,0,lChildin,0,index);
//通过递归，得到左子树结构
root.left=reConstructBinaryTree(lChildPrev,lChildin);
//得到右子树的前序遍历结果
int[] rChildPrev = new int[in.length-1-index];
System.arraycopy(prev,index+1,rChildPrev,0,in.length-1-index);
//得到右子树的中序遍历结果
int[] rChildin = new int[in.length-1-index];
System.arraycopy(in,index+1,rChildin,0,in.length-1-index);
//通过递归，得到右子树结构
root.right=reConstructBinaryTree(rChildPrev,rChildin);
//得到完整的二叉树结构
return root;
}
//测试
public static void main(String[] args){
int[] prev = {1,2,4,7,3,5,6,8};
int[] in = {4,7,2,1,5,3,8,6};
TreeNode root = reConstructBinaryTree(prev,in);
prevPrintTreeNode(root);
System.out.println();
inPrintTreeNode(root);
}
//测试结果
//1 2 4 7 3 5 6 8
//4 7 2 1 5 3 8 6
}
2.后序+中序 -> 求 二叉树结构:
1.中序遍历 = 左子树(中序遍历) + 根结点 + 右子树(中序遍历)
2.后序遍历 = 左子树(前序遍历) + 右子树(前序遍历) + 根结点
解题思路:
跟前面思路类似, 只不过 根结点在后序遍历的最后一个位置 , 其他逻辑原理同(前+中)一样
[ 题 : ] 查找第一个只出现一次的字符
给定一个字符串，输出本字符串中只出现一次并且最靠前的那个字符的位置？
如“abaccddeeef”,字符是b,输出应该是2。
查询: "Badadd"
存储结构:
{
"B": {"count":"1","index":"0"},
"a": {"count":"2","index":"3"},
"d": {"count":"3","index":"5"},
}
返回位置 0 .
oc函数:
调用:
NSInteger index = [self searchStr:@"Badadd"];
实现:
//返回第一次出现一次的字符位置
- (NSInteger)searchStr:(NSString *)str {
NSMutableDictionary *dic = @{}.mutableCopy;
//赋值
for (NSInteger i=0; i<str.length; i++) {
NSString *subStr = [str substringWithRange:NSMakeRange(i, 1)];
NSMutableDictionary *subDic = dic[subStr] ? dic[subStr] : @{}.mutableCopy;
NSInteger count = [subDic[@"count"] integerValue] + 1;
subDic[@"count"] = @(count);
subDic[@"index"] = @(i);
}
//返回第一次出现一次的字符位置
NSInteger index = 0;
NSArray *keyArr = dic.allKeys;
for (NSInteger i=0; i<keyArr.count; i++) {
NSMutableDictionary *subDic = dic[keyArr[i]];
if ([subDic[@"count"] integerValue] == 1) {
index = [subDic[@"index"] integerValue];
}
}
return index;
}
[ 题 : ] 打印2-100之间的素数
所谓素数是指除了1和它本身以外，不能被任何整数整除的数，例如17就是素数，因为它不能被2 ~ 16的任一整数整除。因此判断一个整数m是否是素数，只需把m被2 ~ m-1之间的每一个整数去除，如果都不能被整除，那么m就是一个素数
另外判断方法还可以简化。m不必呗2 ~ m-1之间的每一个整数去除，只需被2 ~ √m之间的每一个整数去除就可以了。如果m不能被2 ~ √m间任一整数整除，m必定是素数。
例如判别17是是否为素数，只需使17被2 ~ 4之间的每一个整数去除，由于都不能整除，可以判定17是素数。（原因：因为如果m能被2 ~ m-1之间任一整数整除，其二个因子必定有一个小于或等于√m，另一个大于或等于√m。例如16能被2,4,8整除，16=28,2小于4,8大于4，16=44,4=√16，因此只需判定在2 ~ 4之间有无因子即可）
#pragma mark- 9:求2-100间的 素数
- (void)Algorithm8 {
for (int i = 2; i < 100; i++) {
int r = isPrime(i);
if (r == 1) {
printf("%d ", i);
}
}
}
int isPrime(int n) {
int i;
for(i = 2; i <= sqrt(n); i++) {
if(n % i == 0) {
return 0;
}
}
return 1;
}
[ 题 : ] 交换A和B的值
// 1.中间变量
void swap(int a, int b) {
int temp = a;
a = b;
b = temp;
}
// 2.加法
void swap(int a, int b) {
a = a + b;
b = a - b;
a = a - b;
}
// 3.异或（相同为0，不同为1. 可以理解为不进位加法）
void swap(int a, int b) {
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
[ 题 : ] 求最大公约数
例如 : 12、16的公约数有1、2、4，其中最大的一个是4，4是12与16的最大公约数，一般记为（12，16）= 4。
/** 1.直接遍历法 */
int maxCommonDivisor(int a, int b) {
int max = 0;
for (int i = 1; i <=b; i++) {
if (a % i == 0 && b % i == 0) {
//取余=0
max = i;
}
}
return max;
}
/** 2.辗转相除法 */
int maxCommonDivisor(int a, int b) {
int r;
while(a % b > 0) {
r = a % b;
a = b;
b = r;
}
return b;
}
[ 题 : ] 最小公倍数
例如 : 12、16的最小公倍数 : 12 = 3*4 , 16 = 4*4 , 3* 4 * 4 = 48 (包含所有因子) , 最小公倍数 = A * (B / 最大公约数) = B * (A / 最大公约数) = A * B / 最大公约数
//最小公倍数
int minMultiple = 12 * 16 * maxCommonDivisor(12,16) ;
