概述
前缀和的分析及应用
- 何为前缀和
- 前缀和代码实现
- 前缀和的妙处
- 看leetcode的一道题
- 暴力解法
- 前缀和求解
何为前缀和
前缀和sums[i]表示nums[0]到nums[i-1]的和。
前缀和代码实现
public int[] Sum(int[] nums){
int sum=0;
int[] sums=new int[nums.length+1];
sums[0]=0;
//使用一次遍历求出数组nums的前缀和其中sums[i]表示nums[0]到nums[i-1]的和
for(int i=0;i<nums.length;i++){
sum+=nums[i];
sums[i+1]=sum;
}
return sums;
}
前缀和的妙处
1. 1. 1. 前缀和能够在一次遍历数组元素时统计各个子数组的和，避免了嵌套遍历；
看leetcode的一道题
给你一个下标从 0 开始的二进制数组 nums ，数组长度为 n 。nums 可以按下标 i（ 0 <= i <= n ）拆分成两个数组（可能为空）：numsleft 和 numsright 。
numsleft 包含 nums 中从下标 0 到 i - 1 的所有元素（包括 0 和 i - 1 ），而 numsright 包含 nums 中从下标 i 到 n - 1 的所有元素（包括 i 和 n - 1 ）。
如果 i == 0 ，numsleft 为 空 ，而 numsright 将包含 nums 中的所有元素。
如果 i == n ，numsleft 将包含 nums 中的所有元素，而 numsright 为 空 。
下标 i 的 分组得分 为 numsleft 中 0 的个数和 numsright 中 1 的个数之 和 。
返回 分组得分 最高 的 所有不同下标 。你可以按 任意顺序 返回答案。
示例 1：
输入：nums = [0,0,1,0]
输出：[2,4]
解释：按下标分组
- 0 ：numsleft 为 [] 。numsright 为 [0,0,1,0] 。得分为 0 + 1 = 1 。
- 1 ：numsleft 为 [0] 。numsright 为 [0,1,0] 。得分为 1 + 1 = 2 。
- 2 ：numsleft 为 [0,0] 。numsright 为 [1,0] 。得分为 2 + 1 = 3 。
- 3 ：numsleft 为 [0,0,1] 。numsright 为 [0] 。得分为 2 + 0 = 2 。
- 4 ：numsleft 为 [0,0,1,0] 。numsright 为 [] 。得分为 3 + 0 = 3 。
下标 2 和 4 都可以得到最高的分组得分 3 。
注意，答案 [4,2] 也被视为正确答案。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/all-divisions-with-the-highest-score-of-a-binary-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
暴力解法
嵌套循环+HashMap统计，很暴力，因此没有通过提交…
public class MaxScoreSolution {
public static void main(String[] args) {
MaxScoreSolution maxScoreSolution = new MaxScoreSolution();
int[] nums = new int[]{1};
List<Integer> list;
list= maxScoreSolution.maxScoreIndices(nums);
System.out.println(list);
}
public List<Integer> maxScoreIndices(int[] nums) {
HashMap<Integer,Integer> map3=new HashMap<>();
List<Integer> list=new ArrayList<>();
int[] res=new int[nums.length+1];
int res0=0;
int res1=0;
for(int i=0;i<nums.length+1;i++){
HashMap<Integer,Integer> map1=new HashMap<>();
HashMap<Integer,Integer> map2=new HashMap<>();
int part=0;
for(;part<i;part++){
map1.put(nums[part], map1.getOrDefault(nums[part], 0) + 1);
}
int j=i;
for(;j<nums.length;j++){
map2.put(nums[j], map2.getOrDefault(nums[j], 0) + 1);
}
//统计左数组中0的个数
if(map1.get(0)==null){
res0=0;
}else{
res0=map1.get(0);
}
//统计右数组中1的个数
if(map2.get(1)==null){
res1=0;
}else{
res1=map2.get(1);
}
//储存（下标，得分）
map3.put(i,res0+res1);
}
//将得分最高的下标存入list数组
for (Map.Entry<Integer, Integer> entry : map3.entrySet()) {
int num = entry.getKey();
int count = entry.getValue();
if(list.size()!=0){
if(count==map3.get(list.get(0))){
list.add(num);
}
if(count>map3.get(list.get(0))){
list.clear();
list.add(num);
}
}
else{
list.add(num);
}
}
return list;
}
}
前缀和求解
1.
1.
1. 将一个数组作为整体来遍历，通过两次遍历分别得到该数组0元素的个数以及该数组1元素的个数；这两个数组是一个竞争状态，我有你无，因此在第二次遍历时，即可得到各个下标的得分；
2.
2.
2. 设置两个变量：left, right，分别表示左数组0的个数，右数组1的个数；
3.
3.
3. 第一次遍历，记录右边的最高得分；
第二次遍历，遇到0则left+1，反之遇到1则right-1。注意题目中给定数组是二进制数组。
同时进行得到右值 与 左值 之后与max值进行判定 如果当前的最大左右值之和小于此时左右值之和，清空列表中数据，重新设置坐标位置为最大左右值之和的位置下标。
class Solution {
public List<Integer> maxScoreIndices(int[] nums) {
//用于记录当前的最大左右值之和
int max = 0;
int left=0, right=0;
//第一次遍历获取得到 左数组为空 右数组全值的情况
for (int i: nums) {
if (i== 1) {
right++;
}
}
List<Integer> res = new ArrayList<>();
//此时得到的右边全值的值为最大左右值之和的初始值
max = right;
//此时对应的结果下标为0
res.add(0);
//第二次遍历
for (int i = 0; i <nums.length; i++) {
//记录当前下标i+1的左数组0的个数与右数组1的个数
if (nums[i] == 0) {
left++;
} else {
right--;
}
//将得分最高的下标存入res数组中
if (max < left + right) {
res.clear();
res.add(i + 1);
max = left + right;
} else if (max == left + right) {
res.add(i + 1);
}
}
return res;
}
}
最后
以上就是英俊树叶为你收集整理的前缀和的分析及应用何为前缀和前缀和代码实现前缀和的妙处看leetcode的一道题的全部内容，希望文章能够帮你解决前缀和的分析及应用何为前缀和前缀和代码实现前缀和的妙处看leetcode的一道题所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复