首页 > 其他分享 >[LeetCode] 1664. Ways to Make a Fair Array

[LeetCode] 1664. Ways to Make a Fair Array

时间:2023-01-28 12:55:54浏览次数:64  
标签:even index Fair nums Ways Make int 数组 sum

You are given an integer array nums. You can choose exactly one index (0-indexed) and remove the element. Notice that the index of the elements may change after the removal.

For example, if nums = [6,1,7,4,1]:

  • Choosing to remove index 1 results in nums = [6,7,4,1].
  • Choosing to remove index 2 results in nums = [6,1,4,1].
  • Choosing to remove index 4 results in nums = [6,1,7,4].

An array is fair if the sum of the odd-indexed values equals the sum of the even-indexed values.

Return the number of indices that you could choose such that after the removal, nums is fair.

Example 1:

Input: nums = [2,1,6,4]
Output: 1
Explanation:
Remove index 0: [1,6,4] -> Even sum: 1 + 4 = 5. Odd sum: 6. Not fair.
Remove index 1: [2,6,4] -> Even sum: 2 + 4 = 6. Odd sum: 6. Fair.
Remove index 2: [2,1,4] -> Even sum: 2 + 4 = 6. Odd sum: 1. Not fair.
Remove index 3: [2,1,6] -> Even sum: 2 + 6 = 8. Odd sum: 1. Not fair.
There is 1 index that you can remove to make nums fair.

Example 2:

Input: nums = [1,1,1]
Output: 3
Explanation: You can remove any index and the remaining array is fair.

Example 3:

Input: nums = [1,2,3]
Output: 0
Explanation: You cannot make a fair array after removing any index.

Constraints:

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

生成平衡数组的方案数。

给你一个整数数组 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 是 平衡数组 的 方案数 。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/ways-to-make-a-fair-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题目的 tag 给的是动态规划,但是动态规划的思路不是很好想到。我这里提供一个前缀和的思路。我们创建两个和 input 数组等长的数组,分别存储奇数 index 和偶数 index 的前缀和。存好之后我们再次遍历 input 数组,对于每个 index,因为去掉的数字是在 index 位置上,在 index 左边的数字的 index 是不变的,所以 index 左边所有数字的前缀和也不变。接着我们看 index 右边的数字,无论 index 本身是奇数还是偶数,删掉 nums[index] 之后,右半边所有奇数 index 的和会变为原来右半边所有偶数 index 的和,反之也是一样。最后判断的方法是如果 leftOdd + rightEven == leftEven + rightOdd,则说明找到一个解。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public int waysToMakeFair(int[] nums) {
 3         int n = nums.length;
 4         int[] odd = new int[n];
 5         int[] even = new int[n];
 6         even[0] = nums[0];
 7         for (int i = 1; i < n; i++) {
 8             if (i % 2 == 0) {
 9                 odd[i] = odd[i - 1];
10                 even[i] = even[i - 1] + nums[i];
11             } else {
12                 odd[i] = odd[i - 1] + nums[i];
13                 even[i] = even[i - 1];
14             }
15         }
16 
17         int res = 0;
18         for (int i = 0; i < n; i++) {
19             int leftOdd = i >= 1 ? odd[i - 1] : 0;
20             int leftEven = i >= 1 ? even[i - 1] : 0;
21             int rightOdd = odd[n - 1] - odd[i];
22             int rightEven = even[n - 1] - even[i];
23             if (leftOdd + rightEven == leftEven + rightOdd) {
24                 res++;
25             }
26         }
27         return res;
28     }
29 }

 

LeetCode 题目总结

标签:even,index,Fair,nums,Ways,Make,int,数组,sum
From: https://www.cnblogs.com/cnoodle/p/17070109.html

相关文章

  • arc139 B - Make N
    题意:三种物品,<重量,费用>分别为\(<1,X>,<A,Y>,<B,Z>\),求恰凑出重量\(n\)的最小费用\(T\le100,1\len,A,B,X,Y,Z\le1e9\)思路:https://blog.csdn.net/qq_45863710......
  • Xmake v2.7.6 发布,新增 Verilog 和 C++ Modules 分发支持
    Xmake是一个基于Lua的轻量级跨平台构建工具。它非常的轻量,没有任何依赖,因为它内置了Lua运行时。它使用xmake.lua维护项目构建,相比makefile/CMakeLists.txt,配置语......
  • abc217 F - Make Pair
    题意:\(2n\)个人从小到大标号排成一行,有\(m\)对关系\(<x,y>\)。每次可删除相邻且有关系的两人,并移动旁边的位置使队伍恢复紧凑问把所有人删完的方案数\(n\le200\)......
  • makefile是什么,它是如何工作的?
    概述当某些文件发生改变时想要执行一个执行一个任务时,make可以排上用场。Make需要一个文件名为makefile或MakeFile的文件来定义一系列将要运行的任务集。你可以使用make来......
  • Makefile 和 CMake
    Makefilehttps://makefiletutorial.com/make精髓  1,如果target存在,将不会执行;反之,则执行2,如果依赖改变,即使target存在也会重新执行makeclean注意clean不是ma......
  • 【记那些年我们链不明白的青春】Cmake常用函数一文总结
    前言以一个简短且好理解的方式记录一下常用Cmake的函数,区别于网上的那些抄来抄去。废话少,全精华。link_directorieslink_directories(${PROJECT_SOURCES_DIR}/lib)是......
  • CMake 快速入门教程 All In One
    CMake快速入门教程AllInOneCMakeCMakeisanopen-source,cross-platformfamilyoftoolsdesignedtobuild,testandpackagesoftware.CMakeisusedtocont......
  • VScode和cmake的组合拳
    cmake的基本使用1.cmake的常用指令cmake是一个跨平台的安装编译软件,可以用简单的语法规则描述所有平台的安装编译过程,下面介绍cmake的常用指令cmake_minimum_requir......
  • 准备学习 make
    make-h用法:make[选项][目标]...选项:-b,-m为兼容性而忽略。-B,--always-make无条件制作(make)所有目标。-C目录,--direc......
  • https://github.com/Abraham423/CenterPointTensorRT 的cmake
    ​​link​​cmake_minimum_required(VERSION2.8.3)project(centerpoint)set(USE_CUDATrue)#ForTensorRTsamplelib#set(TRT_ROOT/home/wanghao/Desktop/projects/T......