問：完成包含逗號的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

相關問題