Java算法問題

Question

問題陳述::在Java中，給定一個int數組，是否可以選擇一組int值，從而使得該組與給定的目標相加，並附加這個約束：如果存在數組中相鄰且相同值的數字，它們必須全選或全選。例如，對於數組{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必須被選擇或不被選擇，全部作爲一個組。 （一個循環可用於查找相同值的範圍）。

我應該如何處理上述問題中的這部分邏輯。 我一直在努力爭取這個權利，不知道。 提供的建議將不勝感激。 你讓我知道什麼是代碼問題/如何處理這個問題的附加約束： - （（

其他約束說，你選擇作爲一個組，而不是選擇作爲一個group.so我不知道如何proceed.if u能請幫me.it可以理解

編輯USER-> MISSINGNO：我已經添加了下面的代碼結構，以上述主要代碼，並打印我的錯values.where我錯了

groupSumClump（0，{2,4,4,8}，14）→false再次失敗該標誌是 - > 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

此問題類似於在數組中總結給定目標的整數組。

提示針對此問題是：

基礎案例是當開始> = nums.length。在這種情況下，如果目標== 0，則返回true。否則，請考慮nums [start]處的元素。關鍵的想法是隻有兩種可能性 - 選擇nums [開始]或不選擇。如果選擇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

一旦你這樣做missingno的預處理步驟（線性時間），你有什麼本質上是subset sum problem。這是一個相當困難的問題，但存在近似算法 - 最終可能取決於序列的長度。

Answer 4

問題陳述是ambigious和不明確：

與此附加約束：如果有陣列 在相鄰且相同的值的數字，它們必須要麼全部是 選擇，或無他們選擇了。例如，與陣列{1，2，2， 2，5,2}，或者所有三個2點的中間必須選擇與否， 所有作爲一組

怎麼樣如果「條紋」沒有解決，選擇單個數字？ 同樣的例子：{1,2,2,2,5,2}

在一個遞歸調用，我們選擇的2 2 2連勝（從上面的回答） *如果（groupSumClump（啓動+計數，NUMS ，target-count * nums [start]））return true *

在下一個rec。 （groupSumClump（start + count，nums，target））返回true;如果（groupSumClump（start + count，nums，target））返回true，則調用爲什麼我們不能在nums [start]處減去第一個單個數字：

我可以做到這一點：

如果（groupSumClump（開始+ ，NUMS，靶 - NUMS [開始]））返回true;

是否意味着我們不能選擇單一數字？

Answer 5

方法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; 
    } 

}