问：完成包含逗号的String和点分隔的整数

给定的输入字符串，如“1,2,3..6..8,9..11”，我们必须把它转换成“1,2,3,4,5,6,7,8,9,10,11”。所以基本上我们必须填充由点提到的范围。以下是我的解决方案。有没有更好的方法来解决这个问题？我们可以进一步优化吗？

public class FlattenAString { 

    public static String flattenAString(String input) { 
     StringBuilder sbr = new StringBuilder(""); 
     StringBuilder current = new StringBuilder(""); 
     StringBuilder next = new StringBuilder(""); 
     int i = 0; 
     while (i < input.length()) { 
      if (input.charAt(i) == '.') { 
       i = i + 2; 
       while (i != input.length() && input.charAt(i) != '.' && input.charAt(i) != ',') { 
        next.append(input.charAt(i)); 
        i++; 
       } 
       int currentInt = Integer.parseInt(current.toString()); 
       int nextInt = Integer.parseInt(next.toString()); 
       appendFromCurrentTillPrevToNextInt(currentInt, nextInt, sbr); 
       current = next; 
       next = new StringBuilder(""); 
      } else if (input.charAt(i) == ',') { 
       sbr.append(current); 
       sbr.append(','); 
       current = new StringBuilder(""); 
       i++; 
      } else { 
       current.append(input.charAt(i)); 
       i++; 
      } 
     } 
     sbr.append(current); 
     return sbr.toString(); 
    } 

    private static void appendFromCurrentTillPrevToNextInt(int current, int val, StringBuilder sbr) { 
     for (int i = current; i < val; i++) { 
      sbr.append(i); 
      sbr.append(','); 
     } 
    } 
}

来源

2017-06-06 Sahil Gupta

对Code Review（https://codereview.stackexchange.com）来说这似乎是一个很好的问题。 –

如果给出'[1..n]'的所有数字都存在，那么我们不能只取第一个和最后一个数字，并填充它们之间的所有其他数字？ – Oswald

@Oswald：这确实是最好的解决方案，因为没有缺失整数。谢谢 –

我会通过分割你的输入字符串两次来解决这个问题。首先，用逗号分隔以得到单个数字或带省略号的范围。对于单个数字，只需将它们添加到列表中即可。对于范围，请在..上进行第二次分割以获取另一个数字列表。然后遍历每个这些对的范围以填充缺失的值。

注意这里一个棘手的问题是我们需要避免重复计算范围内的数字位置。这是最好的例子来解释：

3..6..8

对于这个范围内，我们首先添加3, 4, 5, 6。但是对于第二个省略号，我们从开始，然后继续，直到打到8。

String input = "1,2,3..6..8,9..11"; 
String[] parts = input.split(","); 
List<Integer> list = new ArrayList<>(); 

for (String part : parts) { 
    if (!part.contains("..")) { 
     list.add(Integer.parseInt(part)); 
    } 
    else { 
     String[] ranges = part.split("\\.\\."); 
     for (int i=0; i < ranges.length-1; ++i) { 
      int start = Integer.parseInt(ranges[i]) + (i == 0 ? 0 : 1); 
      int end = Integer.parseInt(ranges[i+1]); 
      for (int j=start; j <= end; ++j) list.add(j); 
     } 
    } 
} 

// print list of numbers 
for (int i=0; i < list.size(); ++i) { 
    System.out.print((i > 0 ? ", " : "") + list.get(i)); 
}

输出：

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11

演示在这里：

Rextester

来源

2017-06-06 04:01:32

你不觉得你的解决方案增加了空间复杂性吗？由于您正在使用数组（部分）来保存令牌。 –

是的，阵列占用空间，但你的方法似乎也是这样做的。我的方法使用的空间与输入字符串的大小/最终范围中的数字数量成正比。在任何情况下，利用'String＃split（）'大大降低了整体问题的复杂性，而且使用一点空间也没有问题。 –

如果字符串的大小非常大？你还会一次将n个物体放入记忆中吗？我的解决方案一次不会在内存中占用额外的空间，它的行为就像一个缓冲区，它正在刷新数据以输出StringBuilder。 –

试试这个。

static final Pattern RANGE = Pattern.compile("(\\d+)(\\.\\.(\\d+))+"); 

static String flattenString(String input) { 
    StringBuffer sb = new StringBuffer(); 
    StringBuilder temp = new StringBuilder(); 
    Matcher m = RANGE.matcher(input); 
    while (m.find()) { 
     int begin = Integer.parseInt(m.group(1)); 
     int end = Integer.parseInt(m.group(3)); 
     temp.setLength(0); 
     for (int i = begin; i <= end; ++i) 
      temp.append(",").append(i); 
     m.appendReplacement(sb, temp.substring(1)); 
    } 
    m.appendTail(sb); 
    return sb.toString(); 
}

来源

2017-06-06 04:24:51 saka1029

完成包含逗号的String和点分隔的整数

回答

Rextester

相关问题