[LeetCode] (#1046) Last Stone Weight

We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together.  Suppose the stones have weights x and y with x <= y.  The result of this smash is:

• If x == y, both stones are totally destroyed;
• If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left.  Return the weight of this stone (or 0 if there are no stones left.)

 

Example 1:

Input: [2,7,4,1,8,1] Output: 1 Explanation: We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then, we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then, we combine 2 and 1 to get 1 so the array converts to [1,1,1] then, we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.

 

Note:

1. 1 <= stones.length <= 30
2. 1 <= stones[i] <= 1000

#1 

import java.util.ArrayList;
import java.util.Collections;

public class Solution {
	
	public int lastStoneWeight(int[] stones) {
		
		ArrayList<Integer> list = new ArrayList<>();
		ArrayList<Integer> list_s;
		for( int i : stones )
			list.add( i );
		
		while( list.size() > 1 ) {
			list_s = new ArrayList<Integer>();
			for( int i = 0; i < list.size(); i++ ) 
				list_s.add( list.get(i) );
			Collections.sort( list_s, Collections.reverseOrder() );
			int dif = list_s.get(0) - list_s.get(1);
			if( dif == 0 ) {
				list.remove( list.indexOf( list_s.get(1) ) );
				list.remove( list.indexOf( list_s.get(0) ) );
			}
			else { 
				list.set( list.indexOf( list_s.get(0) ), dif );
				list.remove( list_s.get(1) );
			}
			list_s.remove(1);
			list_s.remove(0);
		}
        	return list.isEmpty() ? 0 : list.get(0);
    }

}

 

#2

import java.util.Arrays;

public class Solution {

	public static int lastStoneWeight(int[] stones) {
    
		int l = stones.length-1;
		for( int i = 0; i < l; i++ ) {
			Arrays.sort(stones);
			stones[l] -= stones[l-1];
			stones[l-1] = 0;
		}
		return stones[l];
	}
    
}