切棍棒：黑客熱身挑戰

Question

我一直在努力解決Hackerrank的熱身挑戰。對於這個特殊的挑戰 - https://www.hackerrank.com/challenges/cut-the-sticks - 我寫了一些代碼，儘管對我來說這在邏輯上看來是正確的，但我沒有得到正確的答案。

我的代碼 -

import java.util.*; 

public class Solution { 

    public static void main(String[] args) { 

     Scanner sc = new Scanner(System.in); 
     int n = sc.nextInt(); 

     int lengths[] = new int[n]; 
     List<Integer> output = new LinkedList<Integer>(); 

     for (int i = 0; i < n; i++) 
      lengths[i] = sc.nextInt(); 

     sc.close(); 
     Arrays.sort(lengths); 

     for (int i = 0; i < n; i++) { 
      if (lengths[i] == 0) 
       continue; 
      else { 
       output.add(n - i); 
       for (int j = i; j < n; j++) { // This loop isn't working like it should 
        lengths[j] -= lengths[i]; 
       // System.out.print(lengths[j] + " "); // For debugging purposes 
       } 
      // System.out.println(""); 
      } 
     } 

     for (int i = 0; i < output.size(); i++) 
      System.out.println(output.get(i)); 
    } 
} 

對於下面的輸入 -

6 
5 4 4 2 8 2 

我得到的輸出 -

6 
5 
4 
3 
2 
1 

正確的輸出應該是 -

6 
4 
2 
1 

我試圖在整個的用於標記中的代碼（具有評論）循環的運行顯示長度數組的值，這是我所得到的對於相同的輸入如上 -

0 2 4 4 5 8 
0 4 4 5 8 
0 4 5 8 
0 5 8 
0 8 
0 
6 
5 
4 
3 
2 
1 

我完全被難住爲什麼會發生這種情況。

Answer 1

的問題是在這裏：

lengths[j] -= lengths[i]; 

當i == j是真實的，這改變了lengths[i]值。您需要先保存該值。

final int v = lengths[i]; 
for (int j = i; j < n; j++) { 
    lengths[j] -= v; 
} 

Answer 2

已經解決了它。

這裏有答案的一個版本，使用do while循環

public static void main(String[] args) { 
    Scanner scan = new Scanner(System.in); 
    int size = scan.nextInt(); 
    int sticks [] = new int[size]; 
    for (int i = 0; i < size; i++){ 
     sticks[i] = scan.nextInt(); 
    }  
    Arrays.sort(sticks); 
    do { 
    int count =0; 
    int leastLength = sticks[0]; 
    for (int j=0; j < sticks.length; j++){ 
     sticks[j] = sticks[j] - leastLength; 
     count++; 
    } 
    System.out.println(count); 
    List<Integer> resizeArray = new LinkedList<Integer>(); 
    for (int i=0; i< sticks.length; i++){ 
     if (sticks[i] != 0){ 
      resizeArray.add(sticks[i]); 
     } 
    } 
    int temp[] = new int[resizeArray.size()]; 
     for (int i = 0; i < resizeArray.size(); i ++){ 
      temp[i] = resizeArray.get(i); 
     } 
     sticks = temp; 
    } while (sticks.length > 0); 
} 

Answer 3

package com.omt.learn.algo; 

    import java.io.BufferedReader; 
    import java.io.IOException; 
    import java.io.InputStreamReader; 
    import java.util.Arrays; 

    public class CutTheSticks2 { 
    public static void main(String s[]) throws NumberFormatException, IOException { 
     BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 

     short N = Short.parseShort(br.readLine()); 
     short[] A = new short[N]; 
     N = 0; 
     for (String str : br.readLine().split(" ")) { 
      A[N++] = Short.parseShort(str); 
     } 

     Arrays.sort(A); 

     StringBuffer sb = new StringBuffer(); 
     System.out.println(N); 
     for (int i = 1; i < N; i++) { 
      if (A[i - 1] != A[i]) { 
       sb.append((N - i) + "\n"); 
      } 
     } 

     // OUTPUT 
     System.out.print(sb); 
    } 
    } 

Answer 4

import java.io.*; 
import java.util.*; 
import java.text.*; 
import java.math.*; 
import java.util.regex.*; 

public class Solution { 

    public static void main(String[] args) { 
     Scanner in = new Scanner(System.in); 
     int n = in.nextInt(); 
     int arr[] = new int[n]; 
     for(int arr_i=0; arr_i < n; arr_i++){ 
      arr[arr_i] = in.nextInt(); 
     } 
     int count = 2; 
     int min=1000; 
     for(int arr_i=0;count !=1 ; arr_i++){ // read 
      count = 0; 
      for(int arr_j=0; arr_j < n; arr_j++)// find min 
      { if(min >arr[arr_j] && arr[arr_j]!=0) 
       min=arr[arr_j]; 
       } 

      for(int arr_k=0; arr_k < n; arr_k++)// sub 
      { 
       if(arr[arr_k]>=min) 
       { count++; 
        arr[arr_k]= arr[arr_k] - min; 
       } 


      } 

      System.out.println(count); 
     } 

    } 
} 

Answer 5

這是JavaScript的一個可行的解決方案。花了我一段時間才意識到，JavaScript中的sort()按字母順序執行字符串比較。

function sortNumbers(a, b) { 
    return a - b; 
} 

function cutSticks(arr){ 
    var smallestStick = 0; 
    arr = arr.sort(sortNumbers); 
    while(arr.length > 0) { 
     console.log(arr.length); 
     smallestStick = arr[0]; 

     var newArray = []; 
     arr.forEach(function (val) { 
      var newValue = val - smallestStick; 
      if (newValue > 0) { 
       newArray.push(newValue); 
      } 
     }); 

     arr = newArray; 
    } 
} 

function main() { 
    var n = parseInt(readLine()); 
    arr = readLine().split(' '); 
    arr = arr.map(Number); 
    cutSticks(arr); 
} 

希望它有幫助！