海南海口网站建设,logo设计网站哪个好一些,合肥网站建设报价,苏州建站方法常见递归算法题目整理 一、单路递归1、阶乘计算2、翻转字符串3、二分查找 二、多路递归1、斐波那契1#xff09;基础版2#xff09;缓存版 2、汉诺塔3、杨辉三角1#xff09;基础版2#xff09;缓存版3#xff09;优化缓存版 ) 一、单路递归
1、阶乘计算
public class … 常见递归算法题目整理 一、单路递归1、阶乘计算2、翻转字符串3、二分查找 二、多路递归1、斐波那契1基础版2缓存版 2、汉诺塔3、杨辉三角1基础版2缓存版3优化缓存版 ) 一、单路递归
1、阶乘计算
public class 阶乘计算 {// 1*2*3....*100public static void main(String[] args) {System.out.println(num(10));}private static int num(int i) {if (i 1 || i 0) {return i;}return i * num(--i);}
}2、翻转字符串
public class 翻转字符串 {public static void main(String[] args) {String str wrewtyu;f(str,0);}private static void f(String str, int index) {if (index str.length()) {return;}f(str, index 1);System.out.println(str.charAt(index));}
}3、二分查找
public class 二分查找 {public static void main(String[] args) {int[] arr {1, 2, 3, 5, 6, 7, 9, 22, 33, 66, 78, 81, 99, 100};int targetNum 3;System.out.println(binarySearch(arr, targetNum, 0, arr.length));}private static int binarySearch(int[] arr, int targetNum, int left, int right) {if (left right) {return -1;}int mid (left right) 1;if (arr[mid] targetNum) {return binarySearch(arr, targetNum, mid 1, right);} else if (arr[mid] targetNum) {return binarySearch(arr, targetNum, left, mid - 1);} else {return mid;}}
}二、多路递归
1、斐波那契
1基础版
public class FeiBoNaQieTest {public static void main(String[] args) {System.out.println(f(10));}private static int f(int n) {if (n 1) {return 1;}if (n 0) {return 0;}return f(n - 1) f(n - 2);}
}2缓存版 基础版已经能够完成我们的目的但是在计算每一项的时候会重复计算比如在计算第8项和第9项的时候都需要借助第7项继而导致第7项重复计算。此处添加一个缓存数组cache用于存放已经计算过的项避免重复进行计算 public class FeiBoNaQieCacheTest {public static void main(String[] args) {int length 18;// 1、将所有计算过的值缓存在数组中避免重复计算int[] cache new int[length 1];// 2、默认都赋值为-1Arrays.fill(cache, -1);// 3、赋值前两项cache[0] 0;cache[1] 1;System.out.println(f(length, cache));}private static int f(int n, int[] cache) {if (cache[n] ! -1) {// 曾经计算过return cache[n];}int i f(n - 1, cache);int j f(n - 2, cache);// 返回数据的同时将数据进行缓存cache[n] i j;return i j;}
}2、汉诺塔
public class HanNuotaTest {private static ListInteger a new LinkedList();private static ListInteger b new LinkedList();private static ListInteger c new LinkedList();public static void main(String[] args) {int n 5;init(n);print();f(n, a, b, c);print();}/*** param n 圆盘个数* param a 源* param b 借* param c 目*/private static void f(int n, ListInteger a,ListInteger b,ListInteger c) {if (n 0) {return;}// 1、n个圆盘将顶部n-1个圆盘借助c由a移动到bf(n - 1, a, c, b);// 2、将a移动到cInteger remove a.remove(a.size() - 1);c.add(remove);// 如果是LinkedList可以直接使用removeLast// c.add(a.removeLast());// 3、n个圆盘将顶部n-1个圆盘借助a由b移动到cf(n - 1, b, a, c);}/*** 初始化汉诺塔集合** param n 圆盘个数*/private static void init(int n) {for (int i n; i 0; i--) {a.add(i);}}/*** 打印哈诺塔内容*/private static void print() {System.out.println(---);System.out.println(a: a.toString());System.out.println(b: b.toString());System.out.println(c: c.toString());}
}3、杨辉三角
1基础版
public class YangHuiTest {public static void main(String[] args) {f(30);}/*** param length 杨辉三角高度*/private static void f(int length) {if (length 0) {return;}for (int i 0; i length; i) {printSpace(length, i);for (int j 0; j i; j) {// 格式化打印元素占用位置宽度System.out.printf(%-4d, getElement(i, j));}System.out.println();}}/*** 打印每一行前面的空格空格数与杨辉三角高度和元素位置有关系高度-1-位置下标*2** param length 杨辉三角高度* param i 元素位置*/private static void printSpace(int length, int i) {int spaceNum (length - 1 - i) * 2;for (int k 0; k spaceNum; k) {// 这里与元素占用位置大小有关系本demo为占用4个位置System.out.print( );}}/*** 获取元素(3,2)(2,2)(2,1)两边元素i,j、(0,j)都是1** param i 横坐标* param j 纵坐标* return (i, j)坐标元素*/private static int getElement(int i, int j) {if (j 0 || i j) {return 1;}return getElement(i - 1, j - 1) getElement(i - 1, j);}
}2缓存版 此处的缓存做法与斐波那契做法相同使用一个二维数组存储杨辉三角的各个元素我们在使用getElement方法获取元素的时候可以直接去二维数组中获取继而减少递归计算的次数 public class YangHuiCacheTest {public static void main(String[] args) {f(30);}/*** param length 杨辉三角高度*/private static void f(int length) {if (length 0) {return;}// 初始化一个二维数组 用于缓存集合直接length,length太浪费空间int[][] cache new int[length][];for (int i 0; i length; i) {// 二维数组的每一行长度为i1cache[i] new int[i 1];printSpace(length, i);for (int j 0; j i; j) {// 格式化打印元素占用位置宽度System.out.printf(%-4d, getElement(cache, i, j));}System.out.println();}}/*** 打印每一行前面的空格空格数与杨辉三角高度和元素位置有关系高度-1-位置下标*2** param length 杨辉三角高度* param i 元素位置*/private static void printSpace(int length, int i) {int spaceNum (length - 1 - i) * 2;for (int k 0; k spaceNum; k) {// 这里与元素占用位置大小有关系本demo为占用4个位置System.out.print( );}}/*** 获取元素(3,2)(2,2)(2,1)两边元素i,j、(0,j)都是1** param i 横坐标* param j 纵坐标* return (i, j)坐标元素*/private static int getElement(int[][] cache, int i, int j) {if (cache[i][j] ! 0) {return cache[i][j];}if (j 0 || i j) {cache[i][j] 1;return 1;}cache[i][j] getElement(cache, i - 1, j) getElement(cache, i - 1, j - 1);return cache[i][j];}
}3优化缓存版 缓存版本将整个杨辉三角都进行了缓存但是真实在计算的时候我们会发现其实只需要缓存计算行的上一行数据即可即以空间换时间的空间可以进行优化。此版本使用一个一级缓存进行缓存上一行的数据。 public class YangHuiCachePlusTest {public static void main(String[] args) {f(5);}/*** param length 杨辉三角高度*/private static void f(int length) {if (length 0) {return;}int[] row new int[length];for (int i 0; i length; i) {// 获取当前行。// 当前行的数据需要依赖row集合的数据row集合的数据来源于上一次for循环赋值的结果createRow(row, i);// 二维数组的每一行长度为i1printSpace(length, i);for (int j 0; j i; j) {// 格式化打印元素占用位置宽度System.out.printf(%-4d, row[j]);}System.out.println();}}/*** 打印每一行前面的空格空格数与杨辉三角高度和元素位置有关系高度-1-位置下标*2** param length 杨辉三角高度* param i 元素位置*/private static void printSpace(int length, int i) {int spaceNum (length - 1 - i) * 2;for (int k 0; k spaceNum; k) {// 这里与元素占用位置大小有关系本demo为占用4个位置System.out.print( );}}/*** 创建杨辉三角一行的数据*/private static void createRow(int[] row, int n) {if (n 0) {row[0] 1;return;}// 集合赋值只能由右往左赋值从左往右i位置的值会被计算出来的新值覆盖for (int i n; i 0; i--) {row[i] row[i] row[i - 1];}}
}
