Java递归电话号码信件
如何使用递归方法编写java程序,该方法接受类似“234”的int并将其转换为电话簿上的相应字母(2 = ABC,3 = DEF等),并打印出这个的排列? 例如:
输入= 234
输出= ADG ADH ADI AEG AEH AEI AFG AFH AFI BDG BDH BDI BEG BEH BEI BFG BFH BFI CDG CDH CDI CEG CEH CEI CFG CFH CFI
输入= 89
输出= TW TX TY TZ UW UX UY UZ VW VX VY VZ
这是一个没有数组或arraylist的版本。 根据您的要求将结果打印到标准输出。
String[] allLetters = new String[] { "0", "1", "ABC", "DEF", "GHI", "JKL", // etc... }; public static void convert(String phoneNumber) { convertSubstring(phoneNumber,""); } private static void convertSubstring(String phoneNumber, String convertedLetters) { int digit = Integer.parseInt(phoneNumber.substring(0, 1)); String letters=allLetters[digit]; String remainingString=phoneNumber.substring(1); for (int i = 0; i < letters.length(); ++i) { char letter = letters.charAt(i); String result=convertedLetters+letter; if (remainingString.length()==0) System.out.println(result); else convertSubstring(remainingString, result); } }
单独生成排列将构成良好的家庭作业,更不用说强制递归和电话号码分心。
通过类似于排序网络的方法可以有效地生成少量排列。 n个元素的序列有n! 排列(假设完全平局 ,每个排列也由n个元素组成)。 观察到对于两元素序列,有两种排列:
- 原始序列,和
- 交换了两个元素。
对于三元素序列,有六种排列:
- 那么,底部两个元素的排列
- 将序列旋转一个单元格(或左),然后
- 那么,底部两个元素的排列
- 将序列旋转一个单元格左侧(或右侧,与上方相对),和
- 底部两个元素的排列。
也就是说,它是两个元素版本执行三次,有两个干预转换。 现在,一个四元素序列有二十四个排列:
- 那么,底部三个元素的排列
- 保存位置1,分配0到1,3到0,并将保存的值分配给3,和
- 那么,底部三个元素的排列
- 交换位置0和2,交换位置1和3(或向右旋转2),和
- 那么,底部三个元素的排列
- 保存位置3,分配2到3,0到2,并将保存的值分配给0,和
- 底部三个元素的排列。
你是否开始看到一种模式? 注意解决方案的递归性质?
在四个元素之上,图案更难以发现。 您可以迭代序列,使用最后一个元素交换所选元素,反转序列,每次扩展底部24个排列。
尝试在纸上写出来,记录你为洗牌元素所采取的步骤,你会发现你已经编写了所需的程序。
另请注意,此处发布的大多数解决方案都使用String
类型并保持切碎并重新组装。 String
是一个糟糕的选择,因为它是不可变的,当生成排列最好通过交换和旋转向量中的元素(实际上是一个环 )来完成。
实际上,您必须将字母写入目标流,这是极少数情况,因此请针对该操作偏向您的解决方案。 使用一个字符数组,并在发出特定排列时逐个将字符写入流中。 形成一个字符串只是为了将条目转储到流中涉及不必要的分配和复制。
-
接受输入,转换为字符串
-
调用函数generate(String prefix,String suffix),前缀为空,转换后的输入为后缀
-
在generate()中,从后缀中删除第一个数字,将其映射到相应字母的数组,并递归调用数组中每个字母的generate(),并将其附加到前缀。
import java.util.ArrayList; class PhoneNumbers { public static void main(String[] args) { for (String result: convert(args[0])) System.out.println(result); } public static ArrayList convert(String phoneNumber) { int digit = Integer.parseInt(phoneNumber.substring(0, 1)); String letters = new String[] { "0", "1", "ABC", "DEF", "GHI", "JKL", // etc... }[digit]; ArrayList result = new ArrayList (); for (int i = 0; i < letters.length(); ++i) { char letter = letters.charAt(i); if (phoneNumber.length() > 1) { for (String rest: convert(phoneNumber.substring(1))) result.add(letter + rest); } else { result.add("" + letter); } } return result; } }
java PhoneNumbers 234
ADG ADH ADI AEG AEH AEI AFG AFH AFI ...