这是悦乐书的第370次更新,第398篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第232题(顺位题号是985)。有一个整数数组A和一个查询数组queries。

对于第i个查询val = queries[i][0]index = queries[i][1],我们将val添加到A[index]。然后,第i个查询的答案是A的偶数值的总和。(这里给定的index = queries[i][1]是一个基于0的索引,每个查询都会修改数组A。)

返回所有查询的答案。你的答案数组answer应该是answer[i]作为第i个查询的答案。例如:

输入:A = [1,2,3,4],queries = [[1,0],[-3,1],[-4,0],[2,3]]
输出:[8,6,2,4]
说明:一开始,数组是[1,2,3,4]。
在向A[0]加1后,数组为[2,2,3,4],偶数值之和为2 + 2 + 4 = 8。
在向A[1]加-3后,数组为[2,-1,3,4],偶数值之和为2 + 4 = 6。
在向A[0]加上-4后,数组为[-2,-1,3,4],偶数值之和为-2 + 4 = 2。
在向A[3]加2后,数组为[-2,-1,3,6],偶数值之和为-2 + 6 = 4。

注意

  • 1 <= A.length <= 10000

  • -10000 <= A[i] <= 10000

  • 1 <= queries.length <= 10000

  • -10000 <= queries[i][0] <= 10000

  • 0 <= queries[i][1] <A.length

02 第一种解法

直接翻译题目,找出queries中对应的索引和val,改变A中对应元素的的值,接着利用循环求A中偶数元素的总和,赋值给结果数组result

此解法的时间复杂度为O(M*N)Mqueries的长度,NA的长度,空间复杂度为O(M)Mqueries的长度。

public int[] sumEvenAfterQueries(int[] A, int[][] queries) {
    int len = queries.length;
    int[] result = new int[len];
    for (int i=0; i<len; i++) {
        A[queries[i][1]] += queries[i][0];
        result[i] = evenSum(A);
    }
    return result;
}

public int evenSum(int[] A){
    int sum = 0;
    for (int num : A) {
        if (num%2==0) {
            sum += num;    
        }
    }
    return sum;
}


03 第二种解法

第一种解法的时间复杂度太高了,还可以再优化下。

结果数组中的值,后一位是在前一位的基础上产生的,主要判断A中的当前位元素值、queries中的值的奇偶性。拿题目给的示例来看,在第二次操作后,A变成了[2,-1,3,4],将第一次操作后的数组A=[2,2,3,4]中的第二个元素变成了-1,而第一次操作的偶数元素和是8,现在第二个元素变成了奇数,就需要将第一次加的2给减掉,所以第二次操作后的偶数和变成了8-2=6,剩下的几步操作都可以这样理解。

因此,我们就需要判断当前要操作的的A[i]奇偶queries[i][0]奇偶,可以分为四种情况:

第一种情况queries[i][0]为偶数、A[i]也为偶数,即前一次的求和中有A[i],只需加上queries[i][0]的值即可,即sum = sum + queries[i][0]

第二种情况queries[i][0]为偶数、A[i]为奇数,即前一次的求和中没有A[i],并且A[i]加上queries[i][0]后也是奇数,所以不用更新sum的值。

第三种情况queries[i][0]为奇数、A[i]为偶数,即前一次的求和中有A[i],现在A[i]加上queries[i][0]后变成了奇数,需要将前一次求和中的A[i]减掉,即sum = sum - A[i]

第四种情况queries[i][0]为奇数、A[i]也为奇数,即前一次的求和中没有A[i],但是A[i]加上queries[i][0]后变成了偶数,需要把这个新的偶数加到sum上,即sum = sum + queries[i][0] + A[i]

在计算完sum的值后,将sum赋值给新数组对应位置元素,将ueries[i][0] + A[i]的值赋值给A[i],最后返回结果数组。

此解法的时间复杂度为O(M)Mqueries的长度,空间复杂度为O(M)Mqueries的长度。

public int[] sumEvenAfterQueries2(int[] A, int[][] queries) {
    int sum = 0, i = 0;
    for (int num : A) {
        if (num%2 == 0) {
            sum += num;
        }
    }
    int[] result = new int[queries.length];
    for (int[] arr : queries) {
        int curval = arr[0];
        int preval = A[arr[1]];
        // 做奇偶判断
        if (curval%2 == 0) {
            if (preval%2 == 0) {
                sum = sum + curval;
            } 
        } else {
            if (preval%2 == 0) {
                sum = sum - preval;
            } else {
                sum = sum + curval + preval;
            }
        }
        A[arr[1]] += curval;
        result[i++] = sum;
    }
    return result;
}


04小结

算法专题目前已连续日更超过七个月,算法题文章238+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

内容来源于网络如有侵权请私信删除
你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!