Вопрос об алгоритме Java

Question

Постановка задачи :: В Java, учитывая массив целых чисел, можно выбрать группу из нескольких целых чисел, такую, чтобы эта сумма суммировалась с заданной целью, с этим дополнительным ограничением: если в числах есть числа массив, который является смежным и идентичным значением, они должны или все быть выбраны, или ни один из них не выбран. Например, с массивом {1, 2, 2, 2, 5, 2} должны быть выбраны либо все три 2 в середине, либо нет, все как группа. (один цикл можно использовать для определения степени одинаковых значений).

 groupSumClump(0, {2, 4, 8}, 10) → true      
 groupSumClump(0, {1, 2, 4, 8, 1}, 14) → true                   
 groupSumClump(0, {2, 4, 4, 8}, 14) → false --> Failing Test Case               
 groupSumClump(0, {8, 2, 2, 1}, 9) → true   --> Failing Test Case      
 groupSumClump(0, {8, 2, 2, 1}, 11) → false --> NegativeArraySizeException 

Я провел некоторый начальный анализ, а частичный код такой, как показано ниже.

  public boolean groupSumClump(int start, int[] nums, int target) {
    start = 0;
    boolean flag = false;

    // get the highest int from the list of array we have
    int highestInteger = getTheBiggest(nums);
    if (highestInteger > target) {
        flag = false;
    } else {
        int variable = 0;
        for (int i = 0; i < nums.length; i++) {
            variable += nums[i];
        }
        if (variable == target) {
            flag = true;
        } else {
            if (variable < target) {
                flag = false;
            } else {
                // here goes ur grouping logic here
                flag = summate(highestInteger, target, nums);
            }
        }
    }

    return flag;
}

private  boolean summate(int highestInteger, int target, int[] nums) {
    boolean val = false;
    if (highestInteger == target) {
        val = true;
    } else {
        int[] temp = new int[nums.length - 1];
        int var = 0;            

        if ((target - highestInteger) > 0) {
                 for (int j = 0; j < nums.length-1; j++) {
                   if (nums[j] != highestInteger) {
                     temp[var] = nums[j];
                     if (temp[var] == (target - highestInteger)) {
                        val = true;
                        return val;
                     }
                     var++;
                   }
                 }
             val = summate(getTheBiggest(temp), target - highestInteger,
                     temp);  

         }                                      
     }      
    return val;
}

private int getTheBiggest(int[] nums) {
    int biggestInteger = 0;
    for (int i = 0; i < nums.length; i++) {
        if (biggestInteger < nums[i]) {
            biggestInteger = nums[i];
        }
    }
    return biggestInteger;
}

Обратите внимание: я не знаю, как обращаться с логикой для постановки задачи ниже: Существует проблема Additional Constraint, заключающаяся в том, что если в массиве есть соседние числа и одинаковое значение, все они должны быть либо выбраны, либо ни один из них не выбран. Например, с массивом {1, 2, 2, 2, 5, 2} должны быть выбраны либо все три 2 в середине, либо нет, все как группа. (один цикл можно использовать для определения экстента одинаковых значений).

как мне справиться с этой частью логики в вышеуказанной проблеме. Я изо всех сил пытался получить это право без понятия. Предложения будут оценены. Не могли бы вы сообщить мне, в чем проблема с кодом / как справиться с дополнительным ограничением в этой проблеме: - ((

Дополнительное ограничение говорит, что либо вы выбираете в качестве группы, но не выбираете в качестве группы. Поэтому я не знаю, как поступить. Если вы можете ПОЖАЛУЙСТА, помогите мне. Это будет оценено.

РЕДАКТИРОВАТЬ ДЛЯ ПОЛЬЗОВАТЕЛЯ-> MISSINGNO: Я добавил приведенную ниже конструкцию кода к приведенному выше основному коду, и она выводит мне неправильные значения. Где я ошибся.

groupSumClump (0, {2, 4, 4, 8}, 14) → false снова не работает 2 8 4 Флаг -> true, что неверно.

      for(int number=0;number<nums.length-1;number++){
      if(nums[number]==nums[number+1]){
          nums[number]=nums[number]+nums[number+1];                                
      }        
    }

Answer 1

Я бы преобразовал массив в более простой массив, который можно решить с помощью предыдущего метода, скомбинировав соседние значения:

{1, 2, 2, 2, 5, 2} --> {1, 6, 5, 2}

Возможно, вы захотите сохранить некоторую дополнительную бухгалтерскую информацию, чтобынайти оригинальное решение из решения измененной проблемы.

Answer 2

Эта проблема похожа на поиск группы целых чисел в массиве, которые суммируют до заданной цели.

Подсказка для этой проблемы:

Базовый случай - это когда start> = nums.length. В этом случае верните true, если target == 0. В противном случае рассмотрим элемент в nums [start]. Основная идея заключается в том, что существует только 2 возможности - nums [start] выбран или нет. Сделайте один рекурсивный вызов, чтобы увидеть, возможно ли решение, если выбрано nums [start] (вычтите nums [start] из цели в этом вызове). Сделайте еще один рекурсивный вызов, чтобы увидеть, возможно ли решение, если nums [start] не выбран. Верните true, если один из двух рекурсивных вызовов вернет true.

Вы можете использовать ту же подсказку, но с циклом в ней, чтобы найти сумму повторяющихся чисел в массиве. Сделайте вызов, чтобы увидеть, возможно ли решение, если сумма выбрана, и сделайте еще один вызов, если сумма не выбрана. Верните true, если любой из двух рекурсивных вызовов вернет true.

Думаю, это поможет.

public boolean groupSumClump(int start, int[] nums, int target)
{   
if(start >= nums.length) return target == 0;

int count = 1;
while(start+count < nums.length && nums[start] == nums[start+count])
count++;

if(groupSumClump(start+count, nums, target-count*nums[start])) return true;
if(groupSumClump(start+count, nums, target)) return true;

return false;
}

Answer 3

Мое решение с HasMap.

public boolean groupSumClump(int start, int[] nums, int target) {
  Map<Integer, Integer> map = new HashMap<Integer, Integer>();

  Arrays.sort(nums);

  for (int i : nums) {
    if (!map.containsKey(i)) {
      map.put(i, 1);
    }

    else {
      map.put(i, map.get(i) + 1);
    }
  }

  return groupSumClumpHelper(start, nums, target, map);
}

private boolean groupSumClumpHelper(int start, int[] nums, int target, Map map) {
  if (start >= nums.length) {
    return target == 0;
  }

  if (!map.get(nums[start]).equals(1)) {
    return groupSumClumpHelper(start + Integer.parseInt(map.get(nums[start]).toString()), nums, target - Integer.parseInt(map.get(nums[start]).toString()) * nums[start], map) ||
           groupSumClumpHelper(start + Integer.parseInt(map.get(nums[start]).toString()), nums, target, map);
  }

  return groupSumClumpHelper(start + 1, nums, target - nums[start], map) || groupSumClumpHelper(start + 1, nums, target, map);
}

Answer 4

Ваш публичный список параметров метода для метода groupSumClump не должен предоставлять параметр start, особенно если у вас есть внутренняя переменная, которая переопределяет его.

Посмотрите на эту реализацию. Сложность по времени для метода solve равна O(2^N), поскольку в худшем случае вы обязаны проверить все возможные подмножества nums. Ну, если кто-то не докажет, что NP = P.

Надеюсь, это поможет.

import java.util.*;

public class SubsetSumSolver {

    public boolean solve(int[] nums, int target) {
        return solve(0, 0, target, mergeSameNumbers(nums));
    }

    private boolean solve(int start, int tempSum, int sum, ArrayList<Integer> nums) {
        if (start == nums.size())
            return sum == tempSum;
        return solve(start + 1, tempSum + nums.get(start),sum, nums) || solve(start + 1, tempSum, sum, nums);
    }

    private ArrayList<Integer> mergeSameNumbers(int[] nums) {
        if (nums.length == 0)
            return toArrayList(nums);
        LinkedList<Integer> merged = new LinkedList<>();
        int tempSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i - 1] == nums[i])
                tempSum += nums[i];
            else {
                merged.add(tempSum);
                tempSum = nums[i];
            }
        }
        merged.add(tempSum);
        return new ArrayList(merged);
    }

    private ArrayList<Integer> toArrayList(int[] nums) {
        ArrayList<Integer> result = new ArrayList();
        for (int index = 0; index < nums.length; index++)
            result.add(nums[index]);
        return result;
    }

}

Answer 5

постановка задачи неоднозначна и неясна:

с этим дополнительным ограничением: если в массиве есть числа которые являются смежными и имеют одинаковое значение, они должны быть либо выбран, или ни один из них не выбран. Например, с массивом {1, 2, 2, 2, 5, 2}, либо все три 2 в середине должны быть выбраны, либо нет, все как группа

как насчет выбора одной цифры, если «полосы» не сработали? тот же пример: {1,2,2,2,5,2}

в одном рекурсивном вызове мы выбираем полосу 2 2 2 (из ответа выше) * if (groupSumClump (start + count, nums, target-count * nums [start])) возвращает true *

в следующей записи Позвоните, почему мы не можем вычесть первую цифру в числах [начало]: if (groupSumClump (start + count, nums, target)) возвращает true;

Могу ли я сделать это:

if (groupSumClump (start + 1 , nums, target - nums [start] )) возвращает true;

Означает ли это, что мы никогда не сможем выбрать одну цифру?

Answer 6

После того, как вы выполнили шаг предварительной обработки missingno (в линейном времени), у вас есть, по сути, проблема суммы подмножеств .Это довольно сложная проблема, но существуют приблизительные алгоритмы, которые также могут оказаться практичными в зависимости от длины вашей последовательности.