首页 > 其他分享 >[补][leetcode每日一题]1.28

[补][leetcode每日一题]1.28

时间:2023-04-08 11:35:14浏览次数:43  
标签:下标 删除 nums 每日 元素 1.28 数组 平衡 leetcode

1664. 生成平衡数组的方案数

提示

中等

107

相关企业

给你一个整数数组 nums 。你需要选择 恰好 一个下标(下标从 0 开始)并删除对应的元素。请注意剩下元素的下标可能会因为删除操作而发生改变。

比方说,如果 nums = [6,1,7,4,1] ,那么:

  • 选择删除下标 1 ,剩下的数组为 nums = [6,7,4,1] 。
  • 选择删除下标 2 ,剩下的数组为 nums = [6,1,4,1] 。
  • 选择删除下标 4 ,剩下的数组为 nums = [6,1,7,4] 。

如果一个数组满足奇数下标元素的和与偶数下标元素的和相等,该数组就是一个 平衡数组 。

请你返回删除操作后,剩下的数组 nums 是 平衡数组 的 方案数 。

 

示例 1:

输入:nums = [2,1,6,4]
输出:1
解释:
删除下标 0 :[1,6,4] -> 偶数元素下标为:1 + 4 = 5 。奇数元素下标为:6 。不平衡。
删除下标 1 :[2,6,4] -> 偶数元素下标为:2 + 4 = 6 。奇数元素下标为:6 。平衡。
删除下标 2 :[2,1,4] -> 偶数元素下标为:2 + 4 = 6 。奇数元素下标为:1 。不平衡。
删除下标 3 :[2,1,6] -> 偶数元素下标为:2 + 6 = 8 。奇数元素下标为:1 。不平衡。
只有一种让剩余数组成为平衡数组的方案。

示例 2:

输入:nums = [1,1,1]
输出:3
解释:你可以删除任意元素,剩余数组都是平衡数组。

示例 3:

输入:nums = [1,2,3]
输出:0
解释:不管删除哪个元素,剩下数组都不是平衡数组。

 

提示:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104

Solution

class Solution:
    def waysToMakeFair(self, nums: List[int]) -> int:
        n = len(nums)
        s = [0 for _ in range(n+1)]
        for i in range(n - 1, -1, -1):
            s[i] = s[i + 1] + (-1) ** (i & 1) * nums[i]
        acc = 0
        res = 0
        for i in range(n):
            if acc == s[i + 1]:
                res += 1
            acc += (-1) ** (i & 1) * nums[i]
        return res

更进一步,其实后缀和数组没有必要,只需要记录整个数组的差,之后在正序遍历的时候每遍历到一个元素就加或减即可。代码可进一步优化。

标签:下标,删除,nums,每日,元素,1.28,数组,平衡,leetcode
From: https://blog.51cto.com/u_15763108/6177475

相关文章

  • LeetCode习题——在排序数组中查找元素的第一个和最后一个位置(二分查找)
    在排序数组中查找元素的第一个和最后一个位置力扣链接:在排序数组中查找元素的第一个和最后一个位置题目给你一个按照非递减顺序排列的整数数组nums,和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target,返回[-1,-1]。你......
  • 每日总结2023-04-07
    今天对前几天的的界面做了优化packagecom.example.math;/**注册界面*/importandroidx.annotation.NonNull;importandroidx.appcompat.app.AppCompatActivity;importandroid.content.Intent;importandroid.os.Build;importandroid.os.Bundle;importandroid.os......
  • 每日总结 4.7
    今天上了一天的课,晚上看了会c++;然后写了会代码。#include<iostream>usingnamespacestd;intmain(){//请在此输入您的代码intsu[26]={0};strings;cin>>s;for(inti=0;i<s.length();i++){su[s[i]-'a']++;}intmax=0;for(intj=0;j<26;j++){if(su......
  • 4.07每日总结
    MySQLNULL值处理我们已经知道MySQL使用SQLSELECT命令及WHERE子句来读取数据表中的数据,但是当提供的查询条件字段为NULL时,该命令可能就无法正常工作。为了处理这种情况,MySQL提供了三大运算符:ISNULL: 当列的值是NULL,此运算符返回true。不是空:当列的值不为NULL,......
  • 2023.4.7每日总结
    <%@pageimport="java.util.Calendar"%><%@pagelanguage="java"contentType="text/html;charset=UTF-8"pageEncoding="UTF-8"%><!DOCTYPEhtmlPUBLIC"-//W3C//DTDHTML4.01Transitional//EN&......
  • 每日总结-23.4.7
    字符流入文件(解决中文乱码问题)Filefile=newFile(road);try{FileWriterfileWriter=newFileWriter(file,true);//true代表写入文件不覆盖原文件BufferedWriterbufferedWriter=newBufferedWriter(fileWriter);String......
  • leetcode-1109-差分
    classSolution{publicint[]corpFlightBookings(int[][]bookings,intn){int[]diff=newint[n];for(int[]booking:bookings){intfirst=booking[0],last=booking[1],seats=booking[2];diff[first-1]......
  • 4月7日leetcode随笔,异或的灵活运用
    给你一个非空整数数组nums,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。来源:力扣(LeetCode)链接:https://leetcode.cn/problems/single-number著作权归领扣......
  • 每日总结2023/4/2
    使用bjango创建一个web项目,新建views.py文件fromdjango.httpimportHttpResponsedefhello(request):returnHttpResponse("赵文哲天天开心!")修改urls.py文件为fromdjango.conf.urlsimporturlfrom.importviewsurlpatterns=[url(r'^$',vi......
  • 每日总结2023.4.1(djanggo)
    Python快速搭建一个Web项目-知乎(zhihu.com)在PyCharm专业版中,PyCharm安装完成后,自动就集成关于Django开发环境,我们可以方便快捷地创建一个DjangoWeb项目,省去了中间安装和配置Django的多个环节。  点击Create就开始创建,第一次创建DjangoWeb项目可能会......