不同子串的连接
concatenation of distinct substrings
问题 - 按字典顺序排列给定字符串的所有不同子字符串并将它们连接起来。打印连接字符串的第 K 个字符。确保给定的 K 值是有效的,即会有第 K 个字符
输入格式
第一行将包含一个数字 T,即测试用例的数量。
每个测试用例的第一行将包含一个包含字符 (a−z) 的字符串,第二行将包含一个数字 K.
输出格式
打印第 K 个字符(字符串为 1 索引)
约束条件
1≤T≤5
1≤长度≤105
K 将是一个合适的整数。
示例输入#00
1
dbac
3
示例输出 #00
c
解释#00
子串按字典顺序排列如下
a, ac, b, ba, bac, c, d, db, dba, dbac
将它们连接起来,我们得到
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)
您 运行 内存不足。您可以通过使用 -Xms256m -Xmx1024 启动 JVM 来增加 JVM 使用的内存,您可以尝试一些优化。
public static void gen(String str, int k) {
int i, c;
//Adding directly to the Set prevents a larger list because you remove the duplicates
Set<String> set = new TreeSet<String>();
for (c = 0; c < str.length(); c++) {
for (i = 1; i <= str.length() - c; i++) {
String sub = str.substring(c, c + i);
set.add(sub);
}
}
//TreeSet already orders by the String comparator
StringBuilder sb = new StringBuilder();
for (String temp : set) {
sb.append(temp);
if(sb.length()>k){
break;
}
}
String s = sb.toString();
System.out.println(s.charAt(k - 1));
}
[编辑] 添加了小的性能提升。试试看它是否变快,我没有看 StringBuilder.length() 的性能,看它是否会提高或降低。
根据给定的限制(最多 105 个字符),您应该不会遇到内存不足的问题。也许您正在使用非常大的字符串进行测试。
所以如果你有,这里有一些你在浪费内存的地方:
- 填满集合后,将其复制到列表中。这意味着子字符串集合的两个副本,而您将不再使用该集合。
- 将列表复制到数组后,您现在拥有子字符串集合的三个副本,尽管您不会再使用该列表。
- 现在您创建一个
StringBuilder
并将所有子字符串放入其中。但是知道整个连接的字符串并不是很有趣。我们只需要其中一个字符,那么为什么要把连接放在内存中呢?此外,在上面所有浪费的副本中,至少你没有复制子字符串本身。但是现在您将它们附加到 StringBuilder
,您正在创建它们的副本。这将是一个很长的字符串。
- 然后使用
toString()
将 StringBuilder
的内容复制到新字符串。这将创建一个非常大的连接字符串的副本(我们已经说过我们实际上并不需要)。
您已经得到了使用 TreeSet
并直接填充它而不是创建列表、集合和排序列表的合理建议。下一步是从该集合中提取正确的字符 而实际上不保留连接字符串 .
因此,假设您的集合名为 set
:
Iterator<String> iter = set.iterator();
int lengthSoFar = 0;
String str = null;
while ( lengthSoFar < k && iter.hasNext() ) {
str = iter.next(); // Got the next substring;
lengthSoFar += str.length();
}
// At this point we have the substring where we expect the k'th
// character to be.
System.out.println( str.charAt( k - lengthSoFar + str.length() - 1 );
请注意,程序获得 k
的高值比获得低值需要更长的时间,但通常它会比构建整个连接字符串更快,因为一旦你找到正确的子字符串。
问题 - 按字典顺序排列给定字符串的所有不同子字符串并将它们连接起来。打印连接字符串的第 K 个字符。确保给定的 K 值是有效的,即会有第 K 个字符
输入格式 第一行将包含一个数字 T,即测试用例的数量。 每个测试用例的第一行将包含一个包含字符 (a−z) 的字符串,第二行将包含一个数字 K.
输出格式 打印第 K 个字符(字符串为 1 索引)
约束条件 1≤T≤5 1≤长度≤105 K 将是一个合适的整数。
示例输入#00
1
dbac
3
示例输出 #00
c
解释#00
子串按字典顺序排列如下
a, ac, b, ba, bac, c, d, db, dba, dbac 将它们连接起来,我们得到
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)
您 运行 内存不足。您可以通过使用 -Xms256m -Xmx1024 启动 JVM 来增加 JVM 使用的内存,您可以尝试一些优化。
public static void gen(String str, int k) {
int i, c;
//Adding directly to the Set prevents a larger list because you remove the duplicates
Set<String> set = new TreeSet<String>();
for (c = 0; c < str.length(); c++) {
for (i = 1; i <= str.length() - c; i++) {
String sub = str.substring(c, c + i);
set.add(sub);
}
}
//TreeSet already orders by the String comparator
StringBuilder sb = new StringBuilder();
for (String temp : set) {
sb.append(temp);
if(sb.length()>k){
break;
}
}
String s = sb.toString();
System.out.println(s.charAt(k - 1));
}
[编辑] 添加了小的性能提升。试试看它是否变快,我没有看 StringBuilder.length() 的性能,看它是否会提高或降低。
根据给定的限制(最多 105 个字符),您应该不会遇到内存不足的问题。也许您正在使用非常大的字符串进行测试。
所以如果你有,这里有一些你在浪费内存的地方:
- 填满集合后,将其复制到列表中。这意味着子字符串集合的两个副本,而您将不再使用该集合。
- 将列表复制到数组后,您现在拥有子字符串集合的三个副本,尽管您不会再使用该列表。
- 现在您创建一个
StringBuilder
并将所有子字符串放入其中。但是知道整个连接的字符串并不是很有趣。我们只需要其中一个字符,那么为什么要把连接放在内存中呢?此外,在上面所有浪费的副本中,至少你没有复制子字符串本身。但是现在您将它们附加到StringBuilder
,您正在创建它们的副本。这将是一个很长的字符串。 - 然后使用
toString()
将StringBuilder
的内容复制到新字符串。这将创建一个非常大的连接字符串的副本(我们已经说过我们实际上并不需要)。
您已经得到了使用 TreeSet
并直接填充它而不是创建列表、集合和排序列表的合理建议。下一步是从该集合中提取正确的字符 而实际上不保留连接字符串 .
因此,假设您的集合名为 set
:
Iterator<String> iter = set.iterator();
int lengthSoFar = 0;
String str = null;
while ( lengthSoFar < k && iter.hasNext() ) {
str = iter.next(); // Got the next substring;
lengthSoFar += str.length();
}
// At this point we have the substring where we expect the k'th
// character to be.
System.out.println( str.charAt( k - lengthSoFar + str.length() - 1 );
请注意,程序获得 k
的高值比获得低值需要更长的时间,但通常它会比构建整个连接字符串更快,因为一旦你找到正确的子字符串。