LeetCoding Challenge Oct. 28: Summary Ranges

LeetCode October Challenge の 28 日目。

今日の問題は Summary Ranges。

問題の概要

• ソート済みかつその要素が一意な int の配列が与えられる
• この配列のすべての数値をきっかりと覆う区間のリストを求める
• 例
  • [1,3,4,5,8,9] という配列が与えられた場合は ["1", "3->5", "8->9"] を返す

考え方

• 「数値がちょうど１ずつ増加している部分配列」ごとに分解し、それぞれの部分配列の先頭の要素と末尾の要素で区間の文字列を作ればいいだけの簡単な問題ですね 😊
  • 実際には部分配列に分解することなく、ワンパスかつオンラインで処理するけど…
• ざっと実装して submit → accept 👍、ではあったが、runtime 5ms で Your runtime beats 86.58 % of java submissions.
  • あれあれ？ 😳 変に凝ったこともしてないし、そんなに遅くなる要素はないと思ったんだがなんでだ…
  • "8->9" のような文字列を生成する処理が重いのかな？
• 一つの StringBuilder を使いまわす処理に変更しつつ、実装をよりシンプルにして submit → 0ms 達成 🎉

コード

最初に submit したコード

class Solution {
    public List<String> summaryRanges(int[] nums) {
        if (nums.length == 0) {
            return Collections.emptyList();
        }

        List<String> result = new ArrayList<>(nums.length);

        int beginIndex = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i-1] + 1) {
                int endIndex = i-1;
                if (beginIndex < endIndex) {
                    result.add(nums[beginIndex] + "->" + nums[endIndex]);
                } else {
                    result.add(Integer.toString(nums[beginIndex]));
                }
                beginIndex = i;
            }
        }

        if (beginIndex < nums.length - 1) {
            result.add(nums[beginIndex] + "->" + nums[nums.length - 1]);
        } else {
            result.add(Integer.toString(nums[beginIndex]));
        }

        return result;
    }
}

0ms 達成したコード

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> result = new ArrayList<>(nums.length);
        StringBuilder buf = new StringBuilder(30);

        int beginIndex = 0;
        for (int i = 1; i <= nums.length; i++) {
            if (i == nums.length || nums[i] > nums[i - 1] + 1) {
                int endIndex = i - 1;
                if (beginIndex < endIndex) {
                    buf.setLength(0);
                    result.add(buf
                            .append(nums[beginIndex])
                            .append("->")
                            .append(nums[endIndex])
                            .toString());
                } else {
                    result.add(Integer.toString(nums[beginIndex]));
                }
                beginIndex = i;
            }
        }

        return result;
    }
}