常用算法
2016-04-27 » iOS开发基础刷一刷算法题让自己脑子别生锈, 剑指offer、LeetCode 刷题集合，基本用 Swift 或者 C语言
///插入排序
插入排序实际上把待排序的数列分为了两部分，一部分已排好序，另一部分待排序。我们下面还是以一组实际数据为例进行讲解。例如采用直接插入排序算法将无序表{3,1,7,5,2,4,9,6}进行升序排序的过程为：
- 首先需要明确待排序的数列由两部分组成，一部分是已排好序的部分，另一部分是待排序的部分；
- 接着我们每次选择待排序的部分的第 1 个元素，分别与前面的元素进行比较。当大于前面的元素时，可以直接进入已排好序的部分；当小于前面的元素时，需要把这个元素拿出来，将前面的元素后移一位，继续与前面的元素相比，直到比较完数组的第 1 个元素或者出现一个元素小于我们拿出来的这个元素，这时停止比较、移动，直接把这个元素放到当时的空位上；
- 一直重复步骤 2，当待排序的部分已经没有元素可进行插入时，停止操作，当前的数列为已排好序的数列。
代码实现
var array = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70]
func insertion_sort(array: inout [Int]) {
for i in 1..<array.count {
let temp = array[i]
for j in 0..<i {
let p = i - j
if temp < array[p - 1] {
array[p] = array[p - 1]
array[p - 1] = temp
}
}
}
}
假设第一个为最小 i 循环遍历，内部循环从 i+ 1 开始 j， j 与i 值对比，小的往前放，循环往后
///选择排序
func selection_sort(array: inout [Int]) {
var temp: Int = 0
for i in 0..<array.count - 1 {
//假定最小现在是array[i]
for j in (i + 1)..<array.count {
if array[j] < array[i] {
temp = array[i]
array[i] = array[j]
array[j] = temp
}
}
}
}
从0开始往后，两两对比，大的往后冒泡，所以内循环随着外循环而往左收减
///冒泡排序
func bubble_sort(array: inout [Int]) {
var temp: Int = 0
for i in 0..<(array.count - 1) {
for j in 0..<(array.count - 1 - i) {
if array[j] > array[j + 1] {
temp = array[j]
array[j] = array[j + 1]
array[j + 1] = temp
}
}
}
}
折半查找（二分查找）
/**
* 折半查找：优化查找时间（不用遍历全部数据）
*
* 折半查找的原理：
* 1> 数组必须是有序的
* 2> 必须已知min和max（知道范围）
* 3> 动态计算mid的值，取出mid对应的值进行比较
* 4> 如果mid对应的值大于要查找的值，那么max要变小为mid-1
* 5> 如果mid对应的值小于要查找的值，那么min要变大为mid+1
*/
// 已知一个有序数组, 和一个key, 要求从数组中找到key对应的索引位置
int findKey(int *arr, int length, int key) {
int min = 0, max = length - 1, mid;
while (min <= max) {
mid = (min + max) / 2; //计算中间值
if (key > arr[mid]) {
min = mid + 1;
} else if (key < arr[mid]) {
max = mid - 1;
} else {
return mid;
}
}
return -1;
}
快速排序
/**
* 快速排序
*
* 快速排序的原理：
*
*/
var array = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70]
func fast_sort(array: inout [Int], left: Int, right: Int) {
if left >= right {
return
}
let temp = array[left]
var l = left, r = right
while l < r {
while r > l && array[r] >= temp {
r = r - 1
}
array[l] = array[r]
while l < r && array[l] <= temp {
l = l + 1
}
array[r] = array[l]
}
array[l] = temp
fast_sort(array: &array, left: left, right: l)
fast_sort(array: &array, left: l + 1, right: right)
}
不用中间变量,用两种方法交换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;
}
求最大公约数
/** 1.直接遍历法 */
int maxCommonDivisor(int a, int b) {
int max = 0;
for (int i = 1; i <=b; i++) {
if (a % i == 0 && b % i == 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;
}
// 扩展：最小公倍数 = (a * b)/最大公约数
二叉树题：如何反转二叉树？
递归
如何验证两个二叉树是完全相等的？
如何判断二叉树是对称的，给定一个二叉树，检查它是否是镜像对称的。
递归
bool isMirror(struct TreeNode *t1,struct TreeNode *t2)
{
if(t1==NULL&&t2==NULL) return true;
if(t1==NULL||t2==NULL) return false;
return ((*t1).val == (*t2).val) && (isMirror((*t1).right, (*t2).left)) && (isMirror((*t1).left, (*t2).right));
}
bool isSymmetric(struct TreeNode *root) {
return isMirror(root,root);
}
链表题：如何检测链表中是否有环？如何删除链表中等于某个值的所有节点？
追击逻辑，两个指针在链表中走，一个一次一步，一个一次两步，当快指针走完整个链表(next 为nil)，或者快慢指针相遇就说明是有环的
如何快速获取单链表中间节点
同样 两个快慢指针的方式，当快指针走完的时候，慢指针所在位置就是中间节点
数组题：如何在有序数组中找出和等于给定值的两个元素？如何合并两个有序的数组之后保持有序？
摊平为一个字典
遍历一遍数组把各个元素存放到字典里面
key为元素本身，value为下标
然后循环一遍 当 let num = dict[target - key] , num != 当前index的时候，说明找到了
如何获取100以内的质数
散列表
散列表（Hash table，也叫哈希表），是根据关键码值(Key-Value)而直接进行访问的数据结构。
通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。查询时间复杂度O(1)
地址冲突处理：
地址冲突是什么？ 实际上是由数组和链表的方式组合实现的。我们哈希出来的key会放置在数组的某个位置，这个时候如果有其他元素哈希结果也是这个位置的时候，且两个key并不一样。这就是地址冲突。
1、再哈希，重新进行一次全部的哈希，常见于需要扩容的时候，翻倍扩容并重新哈希
2、当key相同的时候，会再数组后面链接一个链表并把值存入
常见hash算法
http://www.cnblogs.com/mengfanrong/p/4034950.html
http://www.cnblogs.com/eniac12/p/5329396.html