沈阳市和平区建设局网站,网站优化排名易下拉霸屏,建一个app和网站那个比较好,做网站的像素是多少钱数据结构与算法--其他算法 1 汉诺塔问题 2 字符串的全部子序列 3 字符串的全排列 4 纸牌问题 5 逆序栈问题 6 数字和字符串转换问题 7 背包问题 8 N皇后问题 暴力递归就是尝试 1#xff0c;把问题转化为规模缩小了的同类问题的子问题 2#xff0c;有明确的不需要继续… 数据结构与算法--其他算法 1 汉诺塔问题 2 字符串的全部子序列 3 字符串的全排列 4 纸牌问题 5 逆序栈问题 6 数字和字符串转换问题 7 背包问题 8 N皇后问题 暴力递归就是尝试 1把问题转化为规模缩小了的同类问题的子问题 2有明确的不需要继续进行递归的条件(base case) 3有当得到了子问题的结果之后的决策过程 4不记录每一个子问题的解 1 汉诺塔问题 打印n层汉诺塔从最左边移动到最右边的全部过程
如下图所示,把 A 上的方块从移动到 C 上,要求 在移动的过程中 ,小的块在大的块上面 假设有三个点 : from to other,有 i 个方块 问题可以转换成 将 1 ~ i个圆盘从from点移动到to 点,过程如下 :
将 1 ~ (i - 1)个方块从 from 点移动到 other点将 第i个方块从 from点移动到 to点将 i - 1个方块从 other点移动到 to点
如下所示
1)
2) 3)
coding
public class HanoiTest {public static void main(String[] args) {hanoi(20);System.out.println(iCount);}public static int iCount 0;public static void hanoi(int n) {if (n 0) {func(n, A, B, C);}}public static void func(int i, String start, String end, String other) {if (i 1) {System.out.println(move 1 from start to end);iCount ;} else {func(i - 1, start, other, end);iCount ;System.out.println(move i from start to end);func(i - 1, other, end, start);}}
}2 字符串的全部子序列 假设有字符串 abc ,要求打印出 abc的全部子序列
可根据包不包含每个字符 构建如图所示的二叉树
coding
public class PrintAllSubSequenceTest {public static void main(String[] args) {ListString list processIteration(abc.toCharArray());for (String s : list) {System.out.println(s);}}public static ListString characterList new ArrayList();public static ListString getAllSubSequence(String parentStr) {characterList.clear();process(parentStr.toCharArray(), 0);return characterList;}/*** 当前来到了 i 位置 子序列中要和不要改字符走两条路** param chars* param i*/public static void process(char[] chars, int i) {// 到了最后一个位置if (i chars.length) {characterList.add(String.valueOf(chars));return;}process(chars, i 1);// 要 i 位置字符的路char temp chars[i];chars[i] 0;process(chars, i 1);// 要 i 位置字符的路chars[i] temp; //把字符串还原}/*** 使用迭代的方法** param chars*/public static ListString processIteration(char[] chars) {ListString retList new ArrayList();for (int i 0; i chars.length;i) {String str ;for (int j i ; j chars.length;j){str chars[j];retList.add(str);}}return retList;}
}3 字符串的全排列 打印一个字符串的全部排列
public class StringPermutationTest {public static void main(String[] args) {ListString strings getAllSubPermutation(abc);for (String s : strings) {System.out.println(s);}}public static ListString getAllSubPermutation(String str){ListString subPermutationList new ArrayList();if (str null || str.length() 0){return subPermutationList;}process(0,str.toCharArray(),subPermutationList);return subPermutationList;}/*** 当前来到的是 i 位置* str[0..i-1]是之前做的选择* param i* param str* param retList*/public static void process(int i,char[] str,ListString retList){if (i str.length){retList.add(String.valueOf(str));}for (int j i; j str.length;j){swap(str,i,j);process(i 1,str,retList);// 交换回来swap(str,i,j);}}public static void swap(char[] chars,int i,int j){char temp chars[i];chars[i] chars[j];chars[j] temp;}
}打印一个字符串的全部排列,要求不能出现重复的排列
public class StringPermutationTest {public static void main(String[] args) {ListString strings getAllSubPermutation(abc);for (String s : strings) {System.out.println(s);}}public static ListString getAllSubPermutation(String str){ListString subPermutationList new ArrayList();if (str null || str.length() 0){return subPermutationList;}process(0,str.toCharArray(),subPermutationList);return subPermutationList;}/*** 当前来到的是 i 位置* str[0..i-1]是之前做的选择* param i* param str* param retList*/public static void process(int i,char[] str,ListString retList){if (i str.length){retList.add(String.valueOf(str));}boolean[] bVisited new boolean[26];for (int j i; j str.length;j){//字符串没有被试过 才进行处理 if (!bVisited[str[j] - a]) {bVisited[str[j] - a] true;swap(str,i,j);process(i 1,str,retList);// 交换回来swap(str,i,j);}}}public static void swap(char[] chars,int i,int j){char temp chars[i];chars[i] chars[j];chars[j] temp;}
}4 纸牌问题 给定一个整型数组arr代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌规定玩家A先拿玩家B后拿但是每个玩家每次只能拿走最左或最右的纸牌玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数
例如 : arr[1,2,100,4]。 开始时玩家A只能拿走1或4。如果开始时玩家A拿走1则排列变为[2,100,4]接下来玩家 B可以拿走2或4然后继续轮到玩家A… 如果开始时玩家A拿走4则排列变为[1,2,100]接下来玩家B可以拿走1或100然后继续轮到玩家A… 玩家A作为绝顶聪明的人不会先拿4因为拿4之后玩家B将拿走100。所以玩家A会先拿1 让排列变为[2,100,4]接下来玩家B不管怎么选100都会被玩家 A拿走。玩家A会获胜分数为101。所以返回101。
arr[1,100,2]。 开始时玩家A不管拿1还是2玩家B作为绝顶聪明的人都会把100拿走。玩家B会获胜,分数为100。所以返回100。
ooding
public class CardInLineTest {public static void main(String[] args) {int[] arr {1,2,100,4};int iWinScore win(arr);System.out.println(iWinScore);}/*** 先手函数* 在 L..R范围上先手拿牌 返回最大值* param arr* param L* param R* return*/public static int first(int[] arr, int L, int R) {// 如果只有一个数 直接拿走if (L R) {return arr[L];}// 返回一个最大值return Math.max(arr[L] second(arr, L 1, R), // 先手拿走最左侧的数 后手在 (L 1)..R范围上arr[R] second(arr, L, R - 1)// 先手拿走最右侧的数 后手在 L..(R - 1)范围上);}/*** 后手函数** param arr* param L* param R* return*/public static int second(int[] arr, int L, int R) {// 因为是后手 L R时 被别人拿走 因此直接返回if (L R){return 0;}// 因为是别人决定的 因此会别人会把最小的留给自己return Math.min(first(arr,L 1,R),// 别人拿走了L上 先手在 (L 1)..R范围上first(arr,L,R -1));}public static int win(int[] arr){if (arr null || arr.length 0){return 0;}return Math.max(first(arr,0,arr.length - 1),second(arr,0,arr.length -1));}
}5 逆序栈问题 给你一个栈请你逆序这个栈不能申请额外的数据结构只能使用递归函数。 如何实现?
coding
public class ReverseStackNoRecurTest {public static void main(String[] args) {StackInteger stack new Stack();stack.push(3);stack.push(2);stack.push(1);reverseStack(stack);while (!stack.isEmpty()){System.out.println(stack.pop());}}/*** 反转栈* param stack*/public static void reverseStack(StackInteger stack){if (stack.isEmpty()){return;}// 每次调用都从栈中移除栈底元素int bottomEle getBottomEle(stack);// 继续反转栈reverseStack(stack);stack.push(bottomEle);}/*** 从栈中移除栈底的元素* param stack* return*/public static int getBottomEle(StackInteger stack){int ret stack.pop();if (stack.isEmpty()){return ret;} else {int last getBottomEle(stack);stack.push(ret);return last;}}
}6 数字和字符串转换问题 规定1和A对应、2和B对应、3和C对应… 那么一个数字字符串比如111就可以转化为AAA、“KA和AK”。 给定一个只有数字字符组成的字符串str返回有多少种转化结果
public class ConvertToLetterStringTest {public static void main(String[] args) {String str 111;int count convertToLetterString(str);System.out.println(count);}public static int convertToLetterString(String str){if (str null || str.length() 0){return 0;}return process(str.toCharArray(),0);}/*** [0..index-1]位置的字符已经做过决定* 当前来到 index位置* param chr* param index* return*/public static int process(char[] chr,int index){if (index chr.length){ //来到字符串的最后位置return 1;}if (chr[index] 0) { // 出现 0 则无效 返回 0return 0;}if (chr[index] 1){int ret process(chr,index 1);// index 位置自己作为单独的部分 后续有多少种if (index 1 chr.length){ret process(chr,index 2);// (index 和 index 1)作为单独的部分 后续有多少种}return ret;}if (chr[index] 2){int ret process(chr,index 1); // index 位置自己作为单独的部分 后续有多少种if (index 1 chr.length (chr[index 1] 6 chr[index] 0)) {ret process(chr,index 2);// (index 和 index 1)作为单独的部分 后续有多少种}return ret;}// index位置的字符为 3..9的情况return process(chr,index 1);}
}7 背包问题 给定两个长度都为N的数组weights和valuesweights[i]和values[i]分别代表 i号物品的重量和价值。给定一个正数bag表示一个载重bag的袋子你装的物 品不能超过这个重量。返回你能装下最多的价值是多少
coding
public class KnapsackQuesTest {/*** index... 之后的货物随意选择,形成的最大价值返回* 重量不能超过 bagWeight* param weights index号货物的价值* param values index 号货物的重量* param index* param alreadyWeight 之前做的决定 所达到的重量* param bagWeight 背包载重* return*/public static int process(int[] weights,int[] values,int index,int alreadyWeight,int bagWeight){if (alreadyWeight bagWeight){return 0;}if (index weights.length){return 0;}return Math.max(// 不要index位置的货物process(weights, values, index 1, alreadyWeight, bagWeight),// 要index位置的货物values[index] process(weights, values, index 1, weights[index] alreadyWeight,bagWeight));}
}8 N皇后问题 N皇后问题是指在N*N的棋盘上要摆N个皇后要求任何两个皇后不同行、不同列也不在同一条斜线上。 给定一个整数n返回n皇后的摆法有多少种。
n1返回1。
n2或32皇后和3皇后问题无论怎么摆都不行返回0。
n8返回92。
coding
public class NQueuesQues {public static void main(String[] args) {System.out.println(num(8));}/**** param n 皇后的个数* return*/public static int num(int n){if (n 1){return 0;}int[] rec new int[n]; // rec[index] index行的皇后放在了第几列return process(0,rec,n);}/**** param index 当前来到的行* param rec index 行放在了哪一列* param n 行数* return*/public static int process(int index,int[] rec,int n){if (index n){ // 到最后一行的下一行 则说明之前有一种选择是正确的 找到了一种摆放的方法return 1;}int ret 0;// 每一列进行尝试for (int col 0; col n;col){if (isValid(rec,index,col)){// 有效 则将 index 行的皇后放在 col列rec[index] col;//继续处理 下一行ret process(index 1,rec,n);}}return ret;}/*** 判断 r 行的皇后 放在 c 列 是否有效 只需要判断 rec[0..r-1]即可* param rec rec[]* param r* param c* return*/public static boolean isValid(int[] rec,int r,int c){for (int k 0; k r;k){// 共列if (rec[k] c){return false;}// 共斜线// Math.abs(r - k) 竖直方向 r行到 k行的距离// rec[k] - c 水平方向 c行到 rec[k]列的距离if (Math.abs(r - k) Math.abs(rec[k] - c)) {return false;}}return true;}
}
