从论坛上看到一个平衡点的考题,问题如下:
引用
1.平衡点问题
平衡点:比如int[] numbers = {1,3,5,7,8,25,4,20}; 25前面的总和为24,25后面的总和也是24,25这个点就是平衡点;假如一个数组中的元素,其前面的部分等于后面的部分,那么这个点的位序就是平衡点
要求:返回任何一个平衡点
原帖地址:
http://www.iteye.com/topic/600079
跟帖中有人采用了求和,然后从头遍历的方法,马背想换种思路,采用从头尾向中间步进的方法,简单实现了一下,第一版的代码如下:
package org.eric;
/**
* 测试找出平衡点。
* 平衡点:数组中某一个元素,其前面元素的总和和后面的元素总和相等,则此元素为平衡点。
* @author 马背{eric.liu} http://mabei.iteye.com
*/
public class BalanceElement {
public static void main(String[] argc) {
//测试数据:{1, 3, 5, 7, 8, 25, 4, 20}
int[] elements = new int[]{1, 3, 5, 7, 8, 25, 4, 20};
findSomeOneBalance(elements);
}
public static void findSomeOneBalance(int[] elements) {
//判断不合理情况
if (elements == null || elements.length < 3) {
System.out.println("==bad elements ==");
return;
}
int pos = 0; //最终找到的平衡点的位置
int element = 0; //平衡点的值
int n = elements.length; //当前判断剩余的元素,初始值为元素总长度
int headPos = -1; //循环判断中头部元素位置
int tailPos = elements.length; //循环判断中尾部元素位置
int head = 0; //头部值的累加和
int tail = 0; //尾部值的累加和
boolean headStep = true; //头部累加在循环判断中下一步是否前进
boolean tailStep = true; //尾部累加在循环判断中下一步是否前进
//循环判断
do {
if (headStep) {
head += elements[++headPos];
n--;
}
if (tailStep) {
tail += elements[--tailPos];
n--;
}
if (head < tail) {
headStep = true;
tailStep = false;
} else if (head > tail) {
headStep = false;
tailStep = true;
} else {
pos = headPos + 1;
element = elements[pos];
}
} while (n > 1);
//输出结果
if (pos != 0) {
System.out.println("==find balance element pos is:" + pos
+ ",and value is:" + element);
} else {
System.out.println("==can't find balance element ==");
}
}
}
此实现马上就发现有重要的bug,当head和tail相等的时候,中间可能还有不止一个元素,即只是相等不能作为判断平衡点的唯一标准,修改之后,第二版程序如下:
if (head < tail) {
headStep = true;
tailStep = false;
} else if (head > tail) {
headStep = false;
tailStep = true;
} else if(n==1) { //注意此处n==1的判断
pos = headPos + 1;
element = elements[pos];
}
考虑到一些特殊情况,例如:数组中可能存在多个平衡点、两个平衡点相邻等,进一步修改到第三版:
if (head < tail) {
headStep = true;
tailStep = false;
} else if (head > tail) {
headStep = false;
tailStep = true;
} else if (n == 1 || n == 0) { //n=0时代表两个平衡点相邻
pos = headPos + n; //+n取代固定+1,平衡点相邻的时候,总是取靠近head的
element = elements[pos];
}
最后针对上面这个版本,马背测试了一些模拟数据,暂时没有发现问题:
- {1,1,1,1,2,1}
- {1, 1, 0, 0, 1, 1}
- {1,2,0,2,1}
附最后第三版源代码:
分享到:
相关推荐
英语音标简记法英语音标简记法英语音标简记法英语音标简记法英语音标简记法英语音标简记法
这是群主Earnest为大家出过的习题及答案,第一期共两个题~。
简记个人博客网站源码为博主现有博客网站,前端采用LayUI框架,此分享版本为asp + access。所有功能齐全,欢迎使用。 使用方法:上传至空间或服务器,通过IIS发布网站即可。 演示地址:...
497476974884240简记.apk
Programming 简记 LP)则是数学规划的一个重要分支。自从 1947 年 G. B. Dantzig 提出 求解线性规划的单纯形方法以来,线性规划在理论上趋向成熟,在实用中日益广泛与深 入。特别是在计算机能处理成千上万个约束条件...
中考知识要点简记归纳之人教版初一数学知识点总结.pdf
高中化学各简记规律.docx
提出一种改进的正弦余弦算法(简记为ISCA)。受粒子群优化(PSO)算法的启发,引入惯性权重以提高正弦余弦算法的收敛精度和加快收敛速度。此外,采取反向学习策略产生初始个体以提高种群的多样性和解的质量。采用八...
jsp标准语法中7大动作 简记(经典) jsp标准语法中7大动作 简记(经典)
七年级英语音标简记法PPT教案.pptx
简记个人博客网站源码 v2.10.01.rar
考试_上课简记&qq群消息汇总.pdf
第一章:这是 USACO 的第一篇文章,《杂题》,所谓杂题,广义上讲:就是没有任何套路的题目,通常这种题目使用的是构造法,而模拟策略又居多,文章言简意赅的叙述了
高中历史之历史百科简记美国“飞虎队”在云南素材
NULL 博文链接:https://joard.iteye.com/blog/403031
NULL 博文链接:https://chengjianxiaoxue.iteye.com/blog/2428561
针对局外k 卡车调度问题,给出了如下研究结果:给出了一种通过构造加权有向图,进而应用最小费用最大流法(MinimalCostMaximalFlow,简记为MCMF)求解该问题的方法;给出了应用动态规划(DynamicProgramming,简记为DP)以及...
title: GAMESS2013编译使用简记- 科2014-02-23 21:14:14 初稿2014-03-08 12:09:09 修订编译解压 tar -