问题 - 按照字典顺序排列给定字符串的所有不同子字符串并连接它们。打印连接字符串的第K个字符。可以肯定的是,给定的K值将是有效的,即将有第K个字符不同子串的拼接
输入格式 第一行将包含数字T即测试用例的数量。 每个测试用例的第一行包含一个包含字符串的字符(A-Z)和第二线将包含许多K.
输出格式 打印第K个字符(串1索引)
约束 1≤T≤5 1≤length≤105 K将是一个适当的整数。
采样输入#00
1
dbac
3
样本输出#00
c
说明#00
的子串布置在词典顺序时如下
一个,交流,b,ba,bac,c,d,db,dba,dbac 关于concate给他们,我们得到
aacbbabaccddbdbadbac 这个字符串中的第三个字符是c,因此答案。
这是我的代码:
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution
{
public static void gen(String str,int k)
{
int i,c;ArrayList<String>al=new ArrayList<String>();
for(c=0;c<str.length();c++)
{
for(i=1;i<=str.length()-c;i++)
{
String sub = str.substring(c,c+i);
al.add(sub);
}
}
HashSet hs = new HashSet();
hs.addAll(al);
al.clear();
al.addAll(hs);
String[] res = al.toArray(new String[al.size()]);
Arrays.sort(res);
StringBuilder sb= new StringBuilder();
for(String temp:res)
{
sb.append(temp);
}
String s = sb.toString();
System.out.println(s.charAt(k-1));
}
public static void main(String[] args)
{
Scanner sc = new Scanner (System.in);
int t = Integer.parseInt(sc.nextLine());
while((t--)>0)
{
String str = sc.nextLine();
int k = Integer.parseInt(sc.nextLine());
gen(str,k);
}
}
}
此代码工作的很好像上面的测试情况下投入较小,但对大输入的其超时或显示这样的事情我明白这个问题是与记忆,任何替代方法来做这个问题或反正重复使用相同的内存?
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.Arrays.copyOfRange(Arrays.java:2694)
at java.lang.String.<init>(String.java:203)
at java.lang.String.substring(String.java:1913)
at Solution.gen(Solution.java:19)
at Solution.main(Solution.java:54)
即使在使用此代码之后,它也需要超过4秒的时间才能编译,所以测试用例没有通过,但仍然为此代码添加坦克,我不需要将它们添加到列表和哈希集合中,并且不需要排序... i可以直接使用:) – coder101
所以我的回答是正确的。如果你使用的是正确的编程比赛,可能还不够。对? – gfelisberto
是的,但不幸的是,它无法帮助我通过测试用例 – coder101