1049. Last Stone Weight II Medium

1/**
2 * [1049] Last Stone Weight II
3 *
4 * You are given an array of integers stones where stones[i] is the weight of the i^th stone.
5 * We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:
6 * 
7 * 	If x == y, both stones are destroyed, and
8 * 	If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.
9 * 
10 * At the end of the game, there is at most one stone left.
11 * Return the smallest possible weight of the left stone. If there are no stones left, return 0.
12 *  
13 * Example 1:
14 * 
15 * Input: stones = [2,7,4,1,8,1]
16 * Output: 1
17 * Explanation:
18 * We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then,
19 * we can combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then,
20 * we can combine 2 and 1 to get 1, so the array converts to [1,1,1] then,
21 * we can combine 1 and 1 to get 0, so the array converts to [1], then that's the optimal value.
22 * 
23 * Example 2:
24 * 
25 * Input: stones = [31,26,33,21,40]
26 * Output: 5
27 * 
28 *  
29 * Constraints:
30 * 
31 * 	1 <= stones.length <= 30
32 * 	1 <= stones[i] <= 100
33 * 
34 */
35pub struct Solution {}
36
37// problem: https://leetcode.com/problems/last-stone-weight-ii/
38// discuss: https://leetcode.com/problems/last-stone-weight-ii/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41
42impl Solution {
43    pub fn last_stone_weight_ii(stones: Vec<i32>) -> i32 {
44        0
45    }
46}
47
48// submission codes end
49
50#[cfg(test)]
51mod tests {
52    use super::*;
53
54    #[test]
55    fn test_1049() {
56    }
57}
58