个人练习- Leetcode1664-Ways to Make a Fair Array

题目链接https://leetcode.cn/problems/ways-to-make-a-fair-array/

题目大意：给出一个数组，如果删去其中一个元素后，奇偶下标的元素和相等，那么数组就是Fair的。求能使删除后数组Fair的下标的个数。

思路：在被删除下标左边奇偶性不变，右边奇偶性相反，这是需要注意的第一点。一开始用了两个数组记录累加和：

• up[i]表示从左往右直到i，和i奇偶性相同的元素累加和，即up[i]=nums[i]+nums[i-2]+...
• down[i]表示从右往左直到i，和i奇偶性相同的元素累加和,即up[i]=nums[i]+nums[i+2]+...

随后遍历，如果删除rm下标的元素，那么删除后数组中，与rm奇偶性相同的两个相邻下标为
same_left = rm-2; same_right = rm+1;
同理与rm奇偶性相反的两个相邻下标为
diff_left = rm-1; diff_right = rm+2;

那么只需计算【与rm相同奇偶性】以及【与rm相异奇偶性】两个和，判断是否相等即可。这里就用到了之前计算的两个数组up和down，注意数组下标不要越界即可。

        if (same_left >= 0)
            same_sum += up[same_left];
        if (same_right < nums.size())
            same_sum += down[same_right];
        if (diff_left >= 0)
            diff_sum += up[diff_left];
        if (diff_right < nums.size())
            diff_sum += down[diff_right];

        if (diff_sum == same_sum)
            ret++;
1
2
3
4
5
6
7
8
9
10
11

完整代码

int Solution::waysToMakeFair(vector<int>& nums) {
    int ret = 0;

    vector<int> up(nums.size(), 0);
    vector<int> down(nums.size(), 0);

    // cal up
    for (int i = 0; i < nums.size(); i++) {
        if (i != 0 && i != 1)
            up[i] = up[i-2] + nums[i];
        else
            up[i] = nums[i];
    }

    // cal down
    for (int i = nums.size()-1; i >= 0; i--) {
        if (i != nums.size()-1 && i != nums.size()-2)
            down[i] = down[i+2] + nums[i];
        else
            down[i] = nums[i];
    }

    for (int rm = 0; rm < nums.size(); rm++) {
        int same_sum = 0, diff_sum = 0;

        int same_left, same_right, diff_left, diff_right;
        same_left = rm-2;
        same_right = rm+1;
        diff_left = rm-1;
        diff_right = rm+2;

        if (same_left >= 0)
            same_sum += up[same_left];
        if (same_right < nums.size())
            same_sum += down[same_right];
        if (diff_left >= 0)
            diff_sum += up[diff_left];
        if (diff_right < nums.size())
            diff_sum += down[diff_right];

        if (diff_sum == same_sum)
            ret++;
    }


    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

虽然通过了，但速度不尽人意，于是看了靠前的题解，发现了一个巧妙的做法。

首先最重要的还是：在被删除下标左边奇偶性不变，右边奇偶性相反

首先计算原数组奇数下标和偶数下标的和，odd_sum和even_sum。

然后我们从最右边开始遍历，因为删除最后一个元素时，所有奇偶性都没有发生改变，此时若rm为奇数，odd_sum -= nums[rm]后判断是否相等即可，反之亦然。

最重要的是【更新】这一步：在遍历rm-1之前，rm的奇偶性已经改变了！于是若rm为奇数，就给even_sum += nums[rm]。之后再遍历移除rm-1下标元素的步骤！

由于每次循环都在更新，因此保证了【左边是原来的奇偶性，右边奇偶性相反】，这个算法在线地解决了这个问题！由此也可以看出【从最右边开始遍历】是非常巧妙的点。

 for (int rm = nums.size()-1; rm >= 0; rm--) {
      if (rm % 2 == 0) {
         even_sum -= nums[rm];
         if (even_sum == odd_sum)
             ret++;
         odd_sum += nums[rm];
     }
     else {
         odd_sum -= nums[rm];
         if (even_sum == odd_sum)
             ret++;
         even_sum += nums[rm];
     }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

完整代码

class Solution {
public:
    int waysToMakeFair(vector<int>& nums) {
        int ret = 0;
        int odd_sum = 0, even_sum = 0;

        for (int i = 0; i < nums.size(); i++) {
            if (i % 2)
                odd_sum += nums[i];
            else
                even_sum += nums[i];
        }

        for (int rm = nums.size()-1; rm >= 0; rm--) {
            if (rm % 2 == 0) {
                even_sum -= nums[rm];
                if (even_sum == odd_sum)
                    ret++;
                odd_sum += nums[rm];
            }
            else {
                odd_sum -= nums[rm];
                if (even_sum == odd_sum)
                    ret++;
                even_sum += nums[rm];
            }
        }
        

        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32