[数据结构与算法]LeetCode每日一题(Sum Game)

Alice and Bob take turns playing a game, with Alice starting first.

You are given a string num of even length consisting of digits and ‘?’ characters. On each turn, a player will do the following if there is still at least one ‘?’ in num:

Choose an index i where num[i] == ‘?’.
Replace num[i] with any digit between ‘0’ and ‘9’.
The game ends when there are no more ‘?’ characters in num.

For Bob to win, the sum of the digits in the first half of num must be equal to the sum of the digits in the second half. For Alice to win, the sums must not be equal.

For example, if the game ended with num = “243801”, then Bob wins because 2+4+3 = 8+0+1. If the game ended with num = “243803”, then Alice wins because 2+4+3 != 8+0+3.
Assuming Alice and Bob play optimally, return true if Alice will win and false if Bob will win.

Example 1:

Input: num = “5023”
Output: false

Explanation: There are no moves to be made.
The sum of the first half is equal to the sum of the second half: 5 + 0 = 2 + 3.

Example 2:

Input: num = “25??”
Output: true

Explanation: Alice can replace one of the '?'s with ‘9’ and it will be impossible for Bob to make the sums equal.

Example 3:

Input: num = “?3295???”
Output: false

Explanation: It can be proven that Bob will always win. One possible outcome is:

• Alice replaces the first ‘?’ with ‘9’. num = “93295???”.
• Bob replaces one of the ‘?’ in the right half with ‘9’. num = “932959??”.
• Alice replaces one of the ‘?’ in the right half with ‘2’. num = “9329592?”.
• Bob replaces the last ‘?’ in the right half with ‘7’. num = “93295927”.
  Bob wins because 9 + 3 + 2 + 9 = 5 + 9 + 2 + 7.

Constraints:

• 2 <= num.length <= 105
• num.length is even.
• num consists of only digits and ‘?’.

假设
first_half_sum是前半段的已知数字的和
second_half_sum是后半段已知数字的和
first_half_chance_count是前半段’?‘的数量
second_half_chance_count是后半段’?'的数量

可得到
diff = first_half_sum - second_half_sum
chances = first_half_chance_count - second_half_chance_count

如果chances是奇数则一定是Alice胜出， 我也不会推导，但是试过几种情况后我确信这一点， 有能力的大神可以严谨的证明一下。

如果chances是偶数则只有diff + chances / 2 * 9 == 0的情况下才会是Bob胜出

代码实现(Rust):

impl Solution {
    pub fn sum_game(num: String) -> bool {
        let mut diff = 0;
        let mut chances = 0;
        let half_index = num.len() / 2 - 1;
        for (i, c) in num.chars().enumerate() {
            if c == '?' {
                if i > half_index {
                    chances -= 1;
                } else {
                    chances += 1;
                }
            } else {
                if i > half_index {
                    diff -= c.to_string().parse::<i32>().unwrap();
                } else {
                    diff += c.to_string().parse::<i32>().unwrap();
                }
            }
        }
        if (chances as i32).abs() % 2 == 1 {
            return true;
        }
        return !(diff + chances / 2 * 9 == 0);
    }
}