Range Extraction

kata programming

یک فرمت برای بیان کردن یک لیست مرتب شده از اعداد صحیح که با استفاده از کاما از هریک، مجزا شده اند به صورت زیر است:

  • اعداد صحیح منفرد
  • یا یک سری از اعداد صحیح که شروع عدد صحیح با آخرین عدد صحیح با استفاده از ‘-‘ مجزا می شود، نشان داده می شود. این سری شامل تمام اعداد صحیح می شود که بین دو نقطه ابتدایی و انتهایی است. این سری حتما باید حداقل 3 عدد را در بر بگیرد. برای مثال “12و13و15-17”.

مساله را طوری حل کنید که لیست اعداد صحیح را با افزایش ترتیب به دست آورد و یک رشته فرمت شده صحیح در فرمت سری برگرداند.

مثال:

Solution.rangeExtraction(new int[] {-6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20})
# returns "-6,-3-1,3-5,7-11,14,15,17-20"

Description:

A format for expressing an ordered list of integers is to use a comma separated list of either

– individual integers

– or a range of integers denoted by the starting integer separated from the end integer in the range by a dash, ‘-‘. The range includes all integers in the interval including both endpoints. It is not considered a range unless it spans at least 3 numbers. For example “12,13,15-17”

Complete the solution so that it takes a list of integers in increasing order and returns a correctly formatted string in the range format.

Example:

Solution.rangeExtraction(new int[] {-6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20})
# returns "-6,-3-1,3-5,7-11,14,15,17-20"

راه حل ها:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.apache.commons.lang3.StringUtils;

public class Solution {

  public static String rangeExtraction(int[] arr) {
    Arrays.parallelSort(arr);
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i=0; i<arr.length; i++) {
      Integer key = arr[i];
      Integer value = arr[i];
      for (int j=i+1; j<arr.length; j++) {
        if (value.equals(arr[j] - 1)) {
          value = arr[j];
          i=j;
        }
      }
      map.put(key, value);
    }
    
    List<String> result = new ArrayList<String>();
    List<Integer> keyList = new ArrayList<Integer>(map.keySet());
    Collections.sort(keyList);
    for (int key : keyList) {
      Integer value = map.get(key);
      if (value.equals(key))
        result.add("" + key);
      else if (value.equals(key + 1))
        result.add(key + "," + value);
      else
        result.add(key + "-" + value);
    }
    
    return StringUtils.join(result, ",");
  }

}
class Solution {
    public static String rangeExtraction(int[] arr) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]);
            int j = i;
            while (j < arr.length - 1 && arr[j] + 1 == arr[j + 1]) j++;
            if (i + 1 < j) {
                i = j;
                sb.append("-");
                sb.append(arr[i]);
            }
            sb.append(",");
        }
        sb.setLength(sb.length() - 1);
        return sb.toString();
    }
}
import java.util.*;
class Solution {
    public static String rangeExtraction(int[] arr) {
        String res = "";
        boolean isStart = true;
        for (int i = 0; i < arr.length - 1; i++) {
            boolean isDiapason = (arr[i] + 1 != arr[i + 1]);
            res += isDiapason ? arr[i] + "," : isStart ? arr[i] + "~" : "~";
            isStart = isDiapason;
        }
        return res.replaceAll("([~]{2,})","-").replace("~", ",") + arr[arr.length - 1];
    }
}
class Solution {
    static String rangeExtraction(final int[] array) {
        final StringBuilder sb = new StringBuilder();
        for (int i = 0; i < array.length; i++) {
            int rangeStart = array[i];
            sb.append(rangeStart);
            for (int j = i + 1; j <= array.length; j++) {
                if (j == array.length || array[j] != rangeStart + (j - i)) {
                    if (j - i >= 3) {
                        sb.append('-').append(array[j - 1]);
                        i = j - 1;
                    }
                    sb.append(',');
                    break;
                }
            }
        }
        return sb.deleteCharAt(sb.length() - 1).toString();
    }
}
import java.util.*;

class Solution {

  private static void addSequence(LinkedList<Integer> sequence, StringBuilder result) {
    result.append(sequence.getFirst());
    
    if (sequence.size() > 2) {
      result.append("-");
    } else if (sequence.size() == 2) {
      result.append(",");
    }
    
    if (sequence.size() > 1) {
      result.append(sequence.getLast());
    }
  }

    public static String rangeExtraction(int[] arr) {
        LinkedList<Integer> sequence = new LinkedList<>();
        
        StringBuilder result = new StringBuilder();
        
        for (int i = 0; i < arr.length; i++) {
          int element = arr[i];
          
          if (sequence.isEmpty() || element == sequence.getLast()+1) {
            sequence.add(element);
          } else {
            addSequence(sequence, result);
            result.append(",");
            sequence.clear();
            sequence.add(element);
          }
        }
        
        if (!sequence.isEmpty()) {
          addSequence(sequence, result);
        }
          
        return result.toString();
    }
}
class Solution {
    public static String rangeExtraction(int[] arr) {
        String str = String.valueOf(arr[0]);
        for (int i = 1; i < arr.length; i++)
            str += (arr[i-1] == arr[i]-1 ? "<":",") + String.valueOf(arr[i]);
        return str.replaceAll("<([^,]*<)+","-").replaceAll("<",",");
    }
}
class Solution {
    public static String rangeExtraction(int[] arr) {
        
        StringBuilder sb = new StringBuilder();
        boolean deltaPrevious = false;
        
        for (int i = 1; i < arr.length; i++) {
            boolean deltaCurrent = (arr[i] - arr[i-1] == 1);

            if (deltaCurrent && deltaPrevious) {
                sb.setCharAt(sb.length()-1,'-');
            } else {
                sb.append(arr[i-1]).append(",");
            }

            deltaPrevious = deltaCurrent;
        }
        
        sb.append(arr[arr.length-1]);
        
        return sb.toString();
    }
}

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *