学校校园网站,wordpress数据库安装,想学网站建设 如何开始,wordpress 添加统计代码字典序的一个生成算法。最近在LeetCode刷题#xff0c;刷到一个题#xff0c;链接#xff1a;https://leetcode-cn.com/problems/permutation-sequence/这个题要求得长度为n的字典序列的第k个排列。我们知道#xff0c;字典序列是一个长度为n(n1)#xff0c;元素为1~n…字典序的一个生成算法。最近在LeetCode刷题刷到一个题链接https://leetcode-cn.com/problems/permutation-sequence/这个题要求得长度为n的字典序列的第k个排列。我们知道字典序列是一个长度为n(n1)元素为1~n的无重复整数序列。之前还真没仔细了解过如何按照顺序从小到大生成这个序列。这次就探究一下。我先在纸上枚举了n3、4、5这几种简单的序列的生成从中找到规律然后推理出一般方法。以n4为例字典序从小到大生成如下1234 → 1243 → 1324 → 1342 → 1423 → 1432 → 2134 → 2143 → 2314 → 2341 → 2413 → 2431 → 3124 → 3142 → 3214 → 3241 → 3412 → 3421 → 4123 → 4132 → 4213 → 4231 → 4312 → 4321当我们拥有了从第m个排列到m1个排列的生成方法时就可以写一个算法findNext()通过k-1次生成排列就可以求出第k次的排列。那么接下来就是寻找字典序的规律我们能够知道 如果当前字典序排列为M假设M的下一个字典序为NN也有下一个字典序O那么有以下推论1. N findNext(M)2. O findNext(N)3. M N O所以可得N是大于M的最小的排列既然我们要生成这样的一个排列那么就要尽可能变动位数更低的数去增大序列以 findNext(1243)为例为了尽可能变动位数更低的数去增大序列由于“43”已经是降序排列的子序列无法通过变动“4”这个位及更低的位去增大序列那么只能从上一位“2”去增大序列所以我们要从“43”这个降序序列中找到一个最的数“3”换到“2”的位置把“2”放入降序序列中然后重新按照升序排序这样就生成了“1324”即1324 findNext(1243)所以我们有以下思路1. 从最低位开始寻找最长的递减序列L的最高位i2. 如果i是最高位证明已经是最大的字典序算法结束如果不是取i的上一位j从L中找到大于j的最小值k然后交换jk位置3. 对L进行升序排序把L变为最小序列Java代码如下public class GetPermutation {public static String getPermutation(int n, int k) {if(n 0 || k 0){return ;}int[] array new int[n];for (int i 0; i n; i) {array[i] i 1;}for (int i 1; i k; i) {findNext(array);}return intArrayToString(array);}public static void findNext(int[] array){if(array ! null array.length 1){int left_exchange_index -1;//找到最长逆序的上一位for (int i array.length - 1; i 0; i--) {if(array[i - 1] array[i]){left_exchange_index i - 1;break;}}//如果还有更大的序列if(left_exchange_index ! -1){//找到交换点的位置int right_exchange_index findExchangeIndex(array, left_exchange_index);//交换exchange(array, left_exchange_index, right_exchange_index);//对交换后的序列升序排序sortRight(array, left_exchange_index 1);}}}public static int findExchangeIndex(int[] array, int left_exchange_index){int left left_exchange_index 1;int right array.length - 1;int temp array[left_exchange_index];int middle (left right) / 2;while(left right){//找到逆序内大于目标值的最小值if(array[middle] temp array[middle 1] temp){return middle;}else if(array[middle] temp){right middle - 1;middle (left right) / 2;}else {//array[middle 1] templeft middle 1;middle (left right) / 2;}}//就剩一个只能和它换了if(left right){return left;}return -1;}public static void exchange(int[] array, int left, int right){int temp array[left];array[left] array[right];array[right] temp;}public static void sortRight(int[] array, int left){Arrays.sort(array, left, array.length);}public static String intArrayToString(int[] array){StringBuffer temp new StringBuffer();for(int value : array){temp.append(value);}return temp.toString();}public static void main(String[] args) {System.out.println(getPermutation(4, 9));}}该算法能够计算出长度为n的字典序的第k个排列。后来啊我想了想这个方法有些慢毕竟k次移动只有最后一次是有意义的之前的k-1次移动都是白白浪费了运算。于是打算优化一下算法。从优化生成字典序的方法开始吧上面的算法移动次数很多这次优化可以采用回溯法处理。思路如下图所示(本图来自Leetcode该题优秀题解自己不想画图了借用一哈)生成字典序的优化思路如下1. 构造一个1~n的升序序列N2. 从小到大逐个取N中的数递归放入空序列M中3. 当该序列的数全部用光时记录该序列拿走M中尾数字回溯4. 来到上一层证明该层刚才递归用的数字已经用过了从M尾部拿出从N中取更大的一个数递归放入M回到步骤25. 当最外层使用了N中最大的数并且回溯之后证明所有序列已经生成算法结束。Java代码如下class Solution {public List permute(int[] nums) {List res new ArrayList();List temp new ArrayList();boolean[] used new boolean[nums.length];arrange(res, used, nums, temp);return res;}public static void arrange(List res, boolean[] used, int[] nums, List temp){if(temp.size() nums.length){res.add(new ArrayList(temp));return;}for(int i 0; i used.length; i){if(used[i] false){used[i] true;temp.add(nums[i]);arrange(res, used, nums, temp);used[i] false;temp.remove(temp.size() - 1);}}return;}}使用的used数组是为了记录该位置的数字是否使用过。有了这个递归思路之后通过剪枝的操作就可以快速定位第k个字典序所在的分支直接找到并返回。以n 4, k 9为例 所求序列为 L以1开头的序列一共有 3*2 6个因为k 9 6所以L肯定不以1开头。以2开头的序列也有 3*2 6 个以2为开头的序列应该是第7个至第12个因为 7 k 12所以L以2开头。以21开头的序列一共有 2*1 2个以21开头的序列应该是第7个至第8个因为 8 k所以L不以21开头以23开头的序列一共有 2*1 2个以23开头的序列应该是第9个至第10个因为 k 9所以L以23开头且是23开头的第一个数就是2314求解完毕。将剪枝操作放在递归之前即可求解Java代码如下public class GetPermutation_better {public static String getPermutation(int n, int k) {int[] list new int[]{1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};int k_inner k;Map used new HashMap(16);for (int i 1; i n; i) {used.put(i, false);}List array new ArrayList();arrange(array, used, k_inner, list);StringBuffer buffer new StringBuffer();for(int temp : array){buffer.append(temp);}return buffer.toString();}public static void arrange(List array, Map used, int k, int[] list){if(array.size() used.size()) {return;}int inner_k k;for (int i 1; i used.size(); i) {if(used.get(i)){continue;}else {int num used.size() - array.size() - 1;//判断当前的这个值是否在这个分支内if(inner_k list[num]){array.add(i);used.put(i, true);arrange(array, used, inner_k, list);}else {//不在就切换到下一个分支去掉之前的个数inner_k inner_k - list[num];}}}}public static void main(String[] args) {System.out.println(getPermutation(3, 2));}}为了不再多构造一个int数组来存递增数列将boolean数组升级为HashMap兼具int数组与used数组的功能。由于每层遍历从1开始可能会遇到已经用过的数这种情况下不能剪枝因为剪枝只针对还没有用过的数的分支所以要先判断该数是否用过再判断是否需要剪枝。该算法不使用递归public class GetPermutation_best {public static String getPermutation(int n, int k) {int[] list new int[]{1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};int k_inner k;Map used new HashMap(16);for (int i 1; i n; i) {used.put(i, false);}List array new ArrayList();arrange(array, used, k_inner, list);StringBuffer buffer new StringBuffer();for(int temp : array){buffer.append(temp);}return buffer.toString();}public static void arrange(List array, Map used, int k, int[] list){int inner_k k;for (int i 1; i used.size(); i) {int num used.size() - array.size() - 1;int integer inner_k / list[num];int rest inner_k % list[num];int index;if(rest 0){index integer;inner_k list[num];}else {index integer 1;inner_k rest;}array.add(getNum(index, used));}array.add(getNum(1, used));}public static int getNum(int index, Map used){int counter 0;for (int i 1; i used.size(); i) {if(!used.get(i)){counter;}if(index counter){used.put(i, true);return i;}}return -1;}public static void main(String[] args) {System.out.println(getPermutation(3, 3));}}两种优化算法均为O(n^2)时间复杂度。
