考虑一个字母整数的编码系统，其中“A”表示为1，“B”为2，…z’as 26。给定一个数字数组（1到9）作为输入，编写一个函数来打印输入数组的所有有效解释。 例子
null
Input: {1, 1}Output: ("aa", 'k") [2 interpretations: aa(1, 1), k(11)]Input: {1, 2, 1}Output: ("aba", "au", "la") [3 interpretations: aba(1,2,1), au(1,21), la(12,1)]Input: {9, 1, 8}Output: {"iah", "ir"} [2 interpretations: iah(9,1,8), ir(9,18)]
请注意，我们无法更改数组的顺序。这意味着{1,2,1}不能变成{2,1,1} 乍一看，这似乎是一个排列/组合的问题。但仔细观察，你会发现这是一个有趣的树问题。 这里的想法是字符串最多可以有两条路径： 1.处理单个数字 2.处理两个数字 这意味着我们可以在这里使用二叉树。使用一位数的处理将是左子代，两位数的处理将是右子代。如果两位数的值大于26，那么我们的右子代将为空，因为我们没有大于26的字母表。 让我们用一个例子来理解。数组a={1,2,1}。下图显示了我们的树是如何生长的。
“” {1,2,1} Codes used in tree / "a" --> 1 / "b" --> 2 "a"{2,1} "l"{1} "l" --> 12 / / / / "ab"{1} "au" "la" null / / "aba" null
大括号{}包含仍在等待处理的数组。请注意，随着级别的增加，我们的数组大小会减小。如果你仔细观察，不难发现树的高度总是n（数组大小） 如何打印所有字符串（解释）？输出字符串是树的叶节点。i、 对于{1,2,1}，输出为{aba au la}。 我们可以得出结论，打印给定整数数组的所有解释主要有两个步骤。 第一步： 创建一个二叉树，其中包含叶节点中所有可能的解释。 第二步： 打印步骤1中创建的二叉树中的所有叶节点。 下面是上述算法的Java实现。
JAVA
// A Java program to print all interpretations of an integer array import java.util.Arrays; // A Binary Tree node class Node { String dataString; Node left; Node right; Node(String dataString) { this .dataString = dataString; //Be default left and right child are null. } public String getDataString() { return dataString; } } public class arrayToAllInterpretations { // Method to create a binary tree which stores all interpretations // of arr[] in lead nodes public static Node createTree( int data, String pString, int [] arr) { // Invalid input as alphabets maps from 1 to 26 if (data > 26 ) return null ; // Parent String + String for this node String dataToStr = pString + alphabet[data]; Node root = new Node(dataToStr); // if arr.length is 0 means we are done if (arr.length != 0 ) { data = arr[ 0 ]; // new array will be from index 1 to end as we are consuming // first index with this node int newArr[] = Arrays.copyOfRange(arr, 1 , arr.length); // left child root.left = createTree(data, dataToStr, newArr); // right child will be null if size of array is 0 or 1 if (arr.length > 1 ) { data = arr[ 0 ] * 10 + arr[ 1 ]; // new array will be from index 2 to end as we // are consuming first two index with this node newArr = Arrays.copyOfRange(arr, 2 , arr.length); root.right = createTree(data, dataToStr, newArr); } } return root; } // To print out leaf nodes public static void printleaf(Node root) { if (root == null ) return ; if (root.left == null && root.right == null ) System.out.print(root.getDataString() + " "); printleaf(root.left); printleaf(root.right); } // The main function that prints all interpretations of array static void printAllInterpretations( int [] arr) { // Step 1: Create Tree Node root = createTree( 0 , "", arr); // Step 2: Print Leaf nodes printleaf(root); System.out.println(); // Print new line } // For simplicity I am taking it as string array. Char Array will save space private static final String[] alphabet = {"", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "v", "z"}; // Driver method to test above methods public static void main(String args[]) { // aacd(1,1,3,4) amd(1,13,4) kcd(11,3,4) // Note : 1,1,34 is not valid as we don't have values corresponding // to 34 in alphabet int [] arr = { 1 , 1 , 3 , 4 }; printAllInterpretations(arr); // aaa(1,1,1) ak(1,11) ka(11,1) int [] arr2 = { 1 , 1 , 1 }; printAllInterpretations(arr2); // bf(2,6) z(26) int [] arr3 = { 2 , 6 }; printAllInterpretations(arr3); // ab(1,2), l(12) int [] arr4 = { 1 , 2 }; printAllInterpretations(arr4); // a(1,0} j(10) int [] arr5 = { 1 , 0 }; printAllInterpretations(arr5); // "" empty string output as array is empty int [] arr6 = {}; printAllInterpretations(arr6); // abba abu ava lba lu int [] arr7 = { 1 , 2 , 2 , 1 }; printAllInterpretations(arr7); } } |
输出：
aacd amd kcd aaa ak ka bf z ab l a j abba abu ava lba lu
练习： 1.此解决方案的时间复杂度是多少？[提示：树的大小+查找叶节点] 2.我们是否可以在创建树时存储叶节点，以便无需再次运行循环来获取叶节点？ 3.我们如何减少额外的空间？ 本文由 瓦伦·詹 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
方法2： （使用回溯）
这个问题可以通过回溯来解决。一个基本的直觉是，我们将使用输入数组的数字生成的所有数字都必须在[1,26]的范围内，两者都包括在内。因此，以一种粗暴的方式，我们尝试所有可能的组合，如果迄今为止生成的数字在[1,26]的范围内，我们附加相应的字母表，并重复剩余的字符串，我们弹出附加字符（回溯），以找到所有有效的解释。在这个过程中，如果我们到达字符串的末尾，这意味着我们找到了1种可能的解释。但在任何时候，如果我们发现迄今为止生成的数字大于26，我们不需要进一步进行，因为这不是一个可以解释的有效数字，所以在这种情况下，我们回溯并尝试其余的组合。
下面是C++实现
C++
#include<bits/stdc++.h> using namespace std; string dup; // function which returns all the valid interpretations void compute( int arr[], int n,vector<string> &vect, int s) { //cout << "ex" << endl; /* if we reach the end of the string than we have found 1 valid interpretation */ if (s == n) { // store it in the vector vect.push_back(dup); /* since we have reached the end of the string there is no string to recur so return */ return ; } // initialize the num with zero int num = 0; for ( int i=s;i<n;i++) { // generate the number num = num*10 + arr[i]; /* validate the number generated so far */ if (num >= 1 and num <= 26) { // append the corresponding alphabet dup += ( 'a' + (num - 1)); // recur for the remaining string compute(arr,n,vect,i+1); // backtrack to find rest of the combinations dup.pop_back(); } // if the number generated so far if greater // than 26 we need not to proceed further // as it cannot be used to make a valid // interpretation else break ; } return ; } vector<string> findAllInterpretations( int n, int arr[]) { // vector to store all the valid interpretations vector<string> vect; dup = "" ; compute(arr,n,vect,0); // return all valid interpretations return vect; } int main() { int n; cin >> n; int *arr = new int [n]; for ( int i=0;i<n;i++) { cin >> arr[i]; } vector<string> res; res = findAllInterpretations(n,arr); int m = res.size(); for ( int i=0;i<m;i++) { cout << res[i] << " " ; } return 0; } |
Input : 51 1 2 1 2
Output : aabab aabl aaub alab all kbab kbl kub
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
