![[Study]算法](http://www.konglu.com/aiimages/31/941058.png "[Study]算法")
- 一、排序算法
- 1.1 冒泡排序
- 1.2 选择排序
- 1.3 插入排序
- 1.4 希尔排序
- 1.5 快速排序
- 1.6 归并排序
- 1.7 堆排序
- 1.8 计数排序
- 1.9 桶排序
- 1.10 基数排序
- 1.11 时间复杂度比较
- 二、查找算法
- 2.1 二分查找
- 2.2 插值查找
- 2.3 斐波那契查找
- 三、递归算法
- 3.1 迷宫问题
- 3.2 哈诺塔问题
- 3.3 八皇后问题
- 内部排序：数据记录在内存中进行排序
- 外部排序：数据量很大，内存中一次不能容纳全部的排序记录，在排序过程中需要访问外存
- 排序算法稳定性：数据排序前后 2 个相等数据的相对位置不发生变化则称为稳定排序算法，否则为不稳定算法
冒泡排序算法基本思想：重复走访待排序的序列，依次比较两个元素，如果他们的大小关系不符合排序要求就交换它们的值
public void bubbleSort(int[] array) {
int times = array.length - 1;
// 外层循坏共执行 len - 1 次
for (int i = 0; i < times; i++) {
boolean flag = true;
for (int j = 0; j < times - 1 - i; j++) {
// 如果前一个数比后一个数大则交换
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
flag = false;
}
}
// 优化：如果在某趟排序过程中未发生元素交换则说明数组已有序，可提前结束排序
if (flag) {
break;
}
}
}
1.2 选择排序
选择排序算法基本思想：每次都从待排序的序列中选取一个最小（大）的元素放在已排序序列尾部
public void selectSort(int[] array) {
int len = array.length;
// 外层循环共执行 len - 1 次
for (int i = 0; i < len - 1; i++) {
// 假设本轮选择排序中最大的数的下标为 i
int maxIndex = i;
for (int j = i + 1; j < len; j++) {
// 从后序的数组元素中查找看是否有比当前 array[maxIndex] 更大的数，有则将其下标赋值给 maxIndex
if (array[j] > array[maxIndex]) {
maxIndex = j;
}
}
if (maxIndex != i) {
int temp = array[i];
array[i] = array[maxIndex];
array[maxIndex] = temp;
}
}
}
1.3 插入排序
插入排序算法基本思想：把 n 个待排序的数据看作是一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含 n - 1 个元素，排序过程中每次从无序表中取出第一个元素，把它与有序表中的元素依次比较，插入到合适的位置使得有序表依然有序
public void insertionSort(int[] array) {
int len = array.length;
// 从第二个元素开始依次为每个元素寻找插入位置
for (int rightIndex = 1; rightIndex < len; rightIndex++) {
int waitInsertValue = array[rightIndex];
int leftIndex = rightIndex - 1;
// 从待插入数据的前一个元素向前查找，当左索引大于等于 0 且元素值大于待插入数据时继续向左查找，过程中元素逐次后移
while (leftIndex >= 0 && array[leftIndex] > waitInsertValue) {
// 将大于待插入数据的元素依次后移
array[leftIndex + 1] = array[leftIndex];
--leftIndex;
}
// 查找结束将 waitInsertValue 插入到空位上
array[leftIndex + 1] = waitInsertValue;
}
}
1.4 希尔排序
希尔排序算法是对插入排序的一种更高效的改进版本，插入排序算法存在的问题：当需要插入的数据较小且在数组中靠后时，元素后移的次数明显增多，效率较低。
希尔排序算法的基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 “基本有序” 时，再对全体记录进行一次直接插入排序
public void hillSort(int[] array) {
int len = array.length;
// 依次将数组按 gap 间隔进行分组
for (int gap = len / 2; gap > 0; gap /= 2) {
// 一组一组地进行遍历
for (int i = gap; i < len; i++) {
// 遍历各组元素，并进行简单插入排序
for (int j = i - gap; j >= 0; j -= gap) {
if (array[j] > array[j + gap]) {
int temp = array[j];
array[j] = array[j + gap];
array[j + gap] = temp;
}
}
}
}
}
public void hillSort(int[] array) {
int len = array.length;
// 按 gap 间隔对数组进行分组
for (int gap = len / 2; gap > 0; gap /= 2) {
// 依次遍历每一组元素
for (int i = gap; i < len; i++) {
int waitInsertValue = array[i];
int curIndex = i;
// 若当前数据比前一个数据小，继续向前寻找插入位置
if (array[curIndex] < array[curIndex - gap]) {
// 当未找到当前组的最左端元素且当前元素依旧比等待插入的元素值大时，继续寻找插入位置并将元素后移
while (curIndex - gap >= 0 && array[curIndex - gap] > waitInsertValue) {
array[curIndex] = array[curIndex - gap];
curIndex -= gap;
}
// while 循环结束为当前等待插入的数据找到了插入位置
array[curIndex] = waitInsertValue;
}
}
}
}
1.5 快速排序
快速排序算法基本思想：选取一个基准数，所有比基准值小的元素摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边），“分区” 结束之后该基准就处于数列的中间位置。递归地把小于基准值元素的左子数列和大于基准值元素的右子数列再次进行快排
public void quickSort(int[] array, int begin, int end) {
if (begin > end) {
return;
}
// 每次快排选取最左边的数作为基准数
int baseNum = array[begin];
int leftIndex = begin;
int rightIndex = end;
// 在 [begin,end] 区间范围内寻找比基准数小和比基准数大的数进行交换直至左索引与右索引相遇
while (leftIndex != rightIndex) {
// 在右半区间寻找比基准数小的数
while (array[rightIndex] >= baseNum && rightIndex > leftIndex) {
rightIndex--;
}
// 在左半区间寻找比基准数大的数
while (array[leftIndex] <= baseNum && leftIndex < rightIndex) {
leftIndex++;
}
// 如果左半区间找到的比基准数大的数比右半区间找到的比基准数小的数还大，则他俩交换其值
if (array[leftIndex] > array[rightIndex]) {
int temp = array[leftIndex];
array[leftIndex] = array[rightIndex];
array[rightIndex] = temp;
}
}
// 将本轮基准数移动到 [begin,end] 区间的中间位置
array[begin] = array[leftIndex];
array[leftIndex] = baseNum;
// 对左半部分数据继续进行快排
quickSort(array, begin, leftIndex - 1);
// 对右半部分数据继续进行快排
quickSort(array, rightIndex + 1, end);
}
1.6 归并排序
归并排序算法基本思想：归并排序是建立在归并操作上的一种有效的排序算法，是分治思想的典型应用。归并排序对待排序序列的元素进行逐层折半分组，然后从最小分组开始进行排序，小分组有序后合并成一个大的分组，逐层进行。最终所有的元素都是有序的
public void mergeSort(int[] array, int begin, int end, int[] temp) {
if (begin < end) {
int mid = (begin + end) / 2;
// 向左递归分解左部分
mergeSort(array, begin, mid, temp);
// 向右递归分解右部分
mergeSort(array, mid + 1, end, temp);
// 合并
merge(array, begin, end, temp);
}
}
private void merge(int[] array, int begin, int end, int[] temp) {
// i 为左部分有序表的左索引
int i = begin;
// mid 为本次分解后的中间下标
int mid = (begin + end) / 2;
// j 为右部分有序表的左索引
int j = mid + 1;
// t 为临时数组 temp 的左索引
int t = 0;
// 按升序合并左、右两部分有序表直至一方合并完成，借助临时数组
while (i <= mid && j <= end) {
// 拷贝左部分有序表元素到临时数组
if (array[i] <= array[j]) {
temp[t] = array[i];
t++;
i++;
} else {
// 拷贝右部分有序表元素到临时数组
temp[t] = array[j];
t++;
j++;
}
}
// 将左部分有序表剩余元素拷贝到临时数组
while (i <= mid) {
temp[t] = array[i];
t++;
i++;
}
// 将右部分有序表剩余元素拷贝到临时数组
while (j <= end) {
temp[t] = array[j];
t++;
j++;
}
// 最后将左、右部分有序表合并结果拷贝到原数组中
t = 0;
for (; begin <= end; begin++, t++) {
array[begin] = temp[t];
}
}
1.7 堆排序
-
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序也是一种选择排序，它的最坏、最好、平均时间复杂度均为 O(nlog~2~n)，是不稳定算法
-
大顶堆（升序）：每个父节点的值都大于或等于其左右孩子节点的值（并未要求左右孩子值的大小关系）
-
小顶堆（降序）：每个父节点的值都小于或等于其左右孩子节点的值（并未要求左右孩子值的大小关系）
-
堆排序的基本思想：将待排序序列构建成一个大顶堆，此时整个序列的最大值就是此大顶堆的根节点；再将剩余的 n - 1 个元素重新构建成大顶堆，如此往复，最终可实现对序列的升序排列
-
使用堆排序思想对数组进行排序：对堆中的节点按层从左至右从 0 开始编号映射到数组，有如下规律：array[i] >= array[2 * i + 1] && array[i] >= array[2 * i + 2] 即父节点大于等于左右子节点。排序过程：从最后一个非叶子节点开始（第一个非叶子节点在数组中的下标：array.length / 2 - 1，从左至右、从下至上进行调整，将最大的元素调整到根节点
private void adjustToHeap(int[] array, int fatherIndex, int count) { // 取出当前非叶子节点（父节点）的值 int temp = array[fatherIndex]; // k = fatherIndex * 2 + 1 是以 fatherIndex 下标为父节点的左子节点下标 for (int k = fatherIndex * 2 + 1; k < count; k = k * 2 + 1) { // 左子节点比右子节点小 if (k + 1 < count && array[k] < array[k + 1]) { k++; } // 如果子节点的值比父节点大，交换子父节点的值 if (array[k] > temp) { array[fatherIndex] = array[k]; array[k] = temp; // 将子节点的下标赋给父节点以便从当前子节点再进行判断以完整当前子树的调整 fatherIndex = k; } else { break; } } } public void heapSort(int[] array) { int len = array.length; // 1. 将无序序列构建成一个堆，升序选择构建大顶堆 // i = len / 2 - 1 为 第一个非叶子节点在数组中的下标 for (int i = len / 2 - 1; i >= 0; i--) { adjustToHeap(array, i, array.length); } // 2. 将堆顶元素与数组末尾元素交换，以将最大元素 “沉” 到数组末端，下轮不再参与构建堆 // 3. 重新调整数组结构使其满足堆的定义，继续下沉 for (int j = len - 1; j > 0; j--) { int temp = array[j]; array[j] = array[0]; array[0] = temp; adjustToHeap(array, 0, j); } }
计数排序算法基本思想：计数排序不是比较排序，排序的速度快于任何比较排序算法。但计数排序要求输入的数据必须是有确定范围的整数
private int[] countingSort(int[] array) {
// 获取数组中最大元素的值，得到桶的个数
int bucketLen = getMaxValue(array) + 1;
int[] bucket = new int[bucketLen];
for (int value : array) {
bucket[value]++;
}
int sortedIndex = 0;
for (int j = 0; j < bucketLen; j++) {
while (bucket[j] > 0) {
array[sortedIndex++] = j;
bucket[j]--;
}
}
return array;
}
private int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
1.9 桶排序
桶排序算法基本思想：桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到以下两点：在额外空间充足的情况下，尽量增大桶的数量使得映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中；同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要
private int[] bucketSort(int[] array, int bucketSize) {
if (array.length == 0) {
return array;
}
// 找到待排序数组中的最大值和最小值
int minValue = array[0];
int maxValue = array[0];
for (int value : array) {
if (value < minValue) {
minValue = value;
} else if (value > maxValue) {
maxValue = value;
}
}
// 向上取整，获得桶的个数
int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
int[][] buckets = new int[bucketCount][0];
// 利用映射函数将数据分配到各个桶中
for (int j : array) {
int index = (int) Math.floor((j - minValue) / bucketSize);
buckets[index] = arrAppend(buckets[index], j);
}
int arrIndex = 0;
for (int[] bucket : buckets) {
if (bucket.length <= 0) {
continue;
}
// 对每个桶进行排序，这里使用了插入排序
bucket = insertSort.sort(bucket);
for (int value : bucket) {
array[arrIndex++] = value;
}
}
return array;
}
private int[] arrAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
1.10 基数排序
基数排序算法基本思想：基数排序是对桶排序的扩展。其基本思想是将所有待比较的数值统一为同样长度的数位，数位较短的前面补 0。然后从最低位开始，依次进行一次排序，这样从最低位排序一直到最高位的排序完成以后，数列就已然有序。
基数排序 vs 计数排序 vs 桶排序
- 基数排序：根据键值的每位数字来分配桶
- 计数排序：每个桶只存储单一键值
- 桶排序：每个桶存储一定范围的数值
public void radixSort(int[] array) {
// 获取数组中数字的最大位数
int maxDigits = getMaxDigits(array);
int len = array.length;
// 定义十个桶，编号依次为 0 ~ 9，每个桶依次记录末尾数字与桶编号相同的元素值
int[][] bucket = new int[10][len];
// 定义一维数组存放每个桶放置的元素个数
int[] digitsInBucket = new int[len];
// 循环 maxDigits 轮，依次将数字归到对应的桶中
for (int k = 0; k < maxDigits; k++) {
for (int num : array) {
int lastNumber = (num / (int) Math.pow(10, k)) % 10;
// 将 num 放到对应的桶编号中
bucket[lastNumber][digitsInBucket[lastNumber]] = num;
digitsInBucket[lastNumber]++;
}
// 遍历十个桶，将其中存放的数据重新赋值给 array
int arrayIndex = 0;
for (int i = 0; i < 10; i++) {
// 判断桶中是否有数据，有则遍历取出
if (digitsInBucket[i] != 0) {
for (int j = 0; j < digitsInBucket[i]; j++) {
array[arrayIndex] = bucket[i][j];
arrayIndex++;
}
// 元素取出后对应桶编号中存放的数据个数置 0
digitsInBucket[i] = 0;
}
}
}
}
private int getMaxDigits(int[] array) {
if (array == null || array.length == 0) {
return 0;
}
int maxNum = 0;
for (int num : array) {
if (num > maxNum) {
maxNum = num;
}
}
return (maxNum + "").length();
}
1.11 时间复杂度比较
二、查找算法
平均查找长度 ASL（Average Search Length）：需和指定 key 进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。对于含有 n 个数据元素的查找表，查找成功的平均查找长度：ASL = Pi * Ci 的和
2.1 二分查找
- Pi：查找表中第 i 个数据元素的概率
- Ci：找到第 i 个数据元素时已经比较过的次数
二分查找基本思想：二分查找也称折半查找，用给定值 k 先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据 k 与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，不建议使用二分查找
public Integer binarySearch(int[] array, int begin, int end, int target) {
if (begin > end) {
return -1;
}
int mid = (begin + end) / 2;
// 目标值比中间值大，在后半区间递归查找
if (target > array[mid]) {
return binarySearch(array, mid + 1, end, target);
} else if (target < array[mid]) {
return binarySearch(array, begin, mid - 1, target);
} else {
return mid;
}
}
public int binarySearch(int[] array, int target) {
int low = 0;
int high = array.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (array[mid] == target) {
return mid;
} else if (array[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
2.2 插值查找
插值查找基本思想：基于二分查找算法，将查找点的选择改进为自适应选择 int mid = begin + (end - begin) * (target - array[begin]) / (array[end] - array[begin]);，可以提高查找效率。当然，插值查找也属于有序查找。对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择
public int interpolatedSearch(int[] array, int begin, int end, int target) {
if (begin > end || target < array[0] || target > array[array.length - 1]) {
return -1;
}
int mid = begin + (end - begin) * (target - array[begin]) / (array[end] - array[begin]);
// 目标值比中间值大，在后半区间递归查找
if (target > array[mid]) {
return interpolatedSearch(array, mid + 1, end, target);
} else if (target < array[mid]) {
return interpolatedSearch(array, begin, mid - 1, target);
} else {
return mid;
}
}
2.3 斐波那契查找
-
在介绍斐波那契查找算法之前，先介绍一下很它紧密相连的黄金分割的概念。黄金分割又称黄金比例，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为 1:0.618 或 1.618:1。0.618 被公认为最具有审美意义的比例数字，这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域，而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割
-
斐波那契数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（从第三个数开始，后边每一个数都是前两个数的和），我们发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近 0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中
-
相对于折半查找，一般将待比较的 key 值与第 mid=（low+high）/ 2 位置的元素比较，斐波那契搜索也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法
-
斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小 1，即 n = F(k) - 1。开始时将 k 值与第 F(k-1) 位置的记录进行比较(即 mid = low + F(k-1) - 1)，比较结果也分为三种
- 相等，则 mid 位置的元素即为所求
- 大于，则 low=mid+1，k-=2 ；说明：low=mid+1说明待查找的元素在[mid+1,high]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))=Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找
- 小于，则high=mid-1，k-=1；说明：low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为 F(k-1)-1个，所以可以递归的应用斐波那契查找
-
在最坏情况下，斐波那契查找的时间复杂度还是O(logn)，且其期望复杂度也为O(logn)，但是与折半查找相比，斐波那契查找的优点是它只涉及加法和减法运算，不需要使用除法，而除法比加减法要占用更多的时间，因此，斐波那契查找的运行时间理论上比折半查找小，但是还是得视具体情况而定
public int fibonacciSearch(int[] array, int key) {
int low = 0;
int n = array.length;
int high = n - 1;
int[] fib = fibonacci(20);
int k = 0;
// 计算 n 位于斐波那契数列的位置
while (n > fib[k] - 1) {
++k;
}
// 将数组 array 扩展到 F[k] - 1 的长度
int[] temp = Arrays.copyOf(array, fib[k] - 1);
// 用 array 的最后一个填充新扩充的数组
for (int i = n; i < fib[k] - 1; i++) {
temp[i] = array[high];
}
while (low <= high) {
int mid = low + fib[k - 1] - 1;
if (key < temp[mid]) {
// 在前半部分查找
high = mid - 1;
// // F[k] = F[k-1] + F[k-2]
k--;
} else if (key > temp[mid]) {
// 在后半部分查找
low = mid + 1;
// F[k] = F[k-1] + F[k-2]
k -= 2;
} else {
if (mid < n) {
return mid;
} else {
// 若 mid>=n 则说明是扩展的数值,返回 high
return high;
}
}
}
return -1;
}
public int[] fibonacci(int size) {
int[] fib = new int[size];
fib[0] = 1;
fib[1] = 1;
for (int i = 2; i < size; i++) {
fib[i] = fib[i - 2] + fib[i - 1];
}
return fib;
}
三、递归算法
-
递归定义：递归就是在过程或函数里自己调用自己
-
递归解决的问题
- 数据的定义是按递归定义的，如 Fibonacci 函数
- 问题解法按递归算法实现，如 Hanoi 问题
- 数据的结构形式是按递归定义的，如二叉树、广义表等
-
使用递归需要注意的问题
- 递归调用一次方法时就会开辟一个独立的栈空间，各个栈空间中局部变量相互独立互不影响
- 如果递归方法中的参数是引用类型则递归调用的所有方法共享该变量
- 递归过程必须趋向退出递归的条件逼近
- 当一个方法执行完毕或遇到 return 就会返回到方法调用处，谁调用就将返回值返回给谁
迷宫问题描述：有一个迷宫地图，有一些可达的位置，也有一些不可达的位置（障碍、墙壁、边界）。从一个位置到下一个位置只能通过向上（或者向右、或者向下、或者向左）走一步来实现，从起点出发，如何找到一条到达终点的通路
public class MazeGame {
private static final int ROWS = 25;
private static final int COLS = 25;
private static final int[][] MAP = new int[ROWS][COLS];
public static int[][] getMap() {
return MAP;
}
enum State {
COULD_GO, OBSTACLE, ACCESSIBLE, DON_NOT_GO_AGAIN
}
public void initMap(int[][] map) {
// Initialize the boundary of game map, values is 1.
// Initialize the value of the first row of the two-dimensional game map to 1
for (int i = 0; i < MazeGame.COLS; i++) {
map[0][i] = 1;
}
// Initialize the element value of the last row of the two-dimensional game map to 1
for (int i = 0; i < MazeGame.COLS; i++) {
map[MazeGame.ROWS - 1][i] = 1;
}
// Initialize the value of the first column of the two-dimensional game map to 1
for (int i = 0; i < MazeGame.ROWS; i++) {
map[i][0] = 1;
}
// Initialize the value of the last column of the two-dimensional game map to 1
for (int i = 0; i < MazeGame.ROWS; i++) {
map[i][MazeGame.COLS - 1] = 1;
}
// Randomly insert obstacles，values is 1.
for (int i = 0; i < MazeGame.ROWS; i++) {
// num: Initialized number of obstacles in each row.
int num = ((int) (Math.random() * MazeGame.COLS) + 1) / 2;
for (int j = 0; j < num; j++) {
// Initial position
int location = (int) (Math.random() * MazeGame.COLS);
map[i][location] = State.OBSTACLE.ordinal();
}
}
}
public void printMap(int[][] map) {
for (int i = 0; i < MazeGame.COLS; i++) {
for (int j = 0; j < MazeGame.COLS; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
public boolean findWay(int[][] map, int row, int col) {
// Recursive exit, reaching the end, game is over
if (map[MazeGame.ROWS - 2][MazeGame.COLS - 2] == State.ACCESSIBLE.ordinal()) {
return true;
} else {
// Did not find the recursive exit, continue to recursively find the exit
// Current location was never passed by, you should judge whether it could go.
if (map[row][col] == State.COULD_GO.ordinal()) {
// First, we assumed to be able to go through, make the value is 2
map[row][col] = State.ACCESSIBLE.ordinal();
// To the right of the current position is a path
if (findWay(map, row, col + 1)) {
return true;
} else if (findWay(map, row + 1, col)) {
// Below the current position is a pathway
return true;
} else if (findWay(map, row, col - 1)) {
// To the left of the current position is a path
return true;
} else if (findWay(map, row - 1, col)) {
// Above the current position is a pathway
return true;
} else {
// There is no accessible way of the current location, change its value to 3.
map[row][col] = State.DON_NOT_GO_AGAIN.ordinal();
return false;
}
} else {
// map[row][col] == 1 || 2 || 3
return false;
}
}
}
public static void main(String[] args) {
MazeGame mazeGame = new MazeGame();
mazeGame.initMap(MazeGame.getMap());
System.out.println("The initial game map:");
mazeGame.printMap(MazeGame.getMap());
if (mazeGame.findWay(MazeGame.getMap(), 1, 1)) {
System.out.println("You Win!!!");
} else {
System.out.println("You Lose!!!");
}
mazeGame.printMap(MazeGame.getMap());
}
}
3.2 哈诺塔问题
相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在 A 杆自下而上、由大到小按顺序放置 64 个金盘。
游戏的目标：把 A 杆上的金盘全部移到 C 杆上，并仍保持原有顺序叠好
操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于 A、B、C 任一杆上
public class HanoiTower {
public static void main(String[] args) {
for (int i = 1; i <= objectToInt(args[0], 64); i++) {
new Thread(new Tower(objectToInt(args[1], 64))).start();
}
}
private static int objectToInt(Object obj, int defaultValue) {
try {
return Integer.parseInt(String.valueOf(obj));
} catch (NumberFormatException e) {
return defaultValue;
}
}
}
class Tower implements Runnable {
private final int plateNums;
private int cnt = 0;
public Tower(int plateNums) {
this.plateNums = plateNums;
}
@Override
public void run() {
int move = move(this.plateNums, 'a', 'b', 'c');
System.out.println("==============");
System.out.println("Total move " + move);
System.out.println("==============");
}
public int move(int num, char begin, char middle, char target) {
// 如果只有一个盘，直接从 begin 移动到 target
if (num == 1) {
System.out.println(++cnt + ": " + begin + " -> " + target);
} else {
// 先将剩下的 num - 1 个盘子从 begin 移动到 middle，中间过程借助 target 柱
move(num - 1, begin, target, middle);
// 将 begin 上的最后一个盘移动到 target
System.out.println(++cnt + ": " + begin + " -> " + target);
// 再将 middle 柱上剩下的 num -1 个盘从 middle 移动到 target，中间过程借助 begin 柱
move(num - 1, middle, begin, target);
}
return cnt;
}
}
3.3 八皇后问题
在 8×8 格的国际象棋上摆放 8 个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有 76 种方案。1854 年在柏林的象棋杂志上不同的作者发表了 40 种不同的解，后来有人用图论的方法解出 92 种结果，正确答案确有 92 中摆法
public class EightQueens {f
private static final int QUEENS = 8;
private final int[] array = new int[QUEENS];
private int solution;
public int getSolution() {
return solution;
}
public void place(int queenNum) {
if (queenNum == QUEENS) {
print();
++solution;
return;
}
// 依次放置皇后，同时判断布局是否冲突
for (int i = 0; i < QUEENS; i++) {
// 先将当前皇后放到该行的第 1 列，并判断是否冲突
array[queenNum] = i;
if (isConflict(queenNum)) {
// 不冲突接着放置皇后
place(queenNum + 1);
}
// 冲突则当前皇后后移一个位置
}
}
private boolean isConflict(int queenNum) {
for (int i = 0; i < queenNum; i++) {
// 判断两个皇后是否在同一列
// 注：无需判断是否在同一行，因为 i 自增依次表示第 i + 1 行
if (array[i] == array[queenNum]) {
return false;
}
// 判断是否在同一斜线上
if (Math.abs(queenNum - i) == Math.abs(array[queenNum] - array[i])) {
return false;
}
}
return true;
}
private void print() {
for (int location : array) {
System.out.print(location + " ");
}
System.out.println();
}
public static void main(String[] args) {
EightQueens eightQueens = new EightQueens();
eightQueens.place(0);
System.out.println("皇后摆放方式共有 " + eightQueens.getSolution() + " 种.");
}
}
四、深度优先
五、广度优先
六、分治算法
七、动态规划
八、KMP
九、贪心算法
十、Prim
十一、Kruskal
十二、Dijkstra
十三、Floyd
十四、骑士周游问题
