文档章节

[EAZY] - TapeEquilibrium

dkf_genius
 dkf_genius
发布于 2015/06/11 17:21
字数 358
阅读 5
收藏 0
点赞 0
评论 0
Task description

A non-empty zero-indexed array A consisting of N integers is given. Array A represents numbers on a tape.

Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].

The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|

In other words, it is the absolute difference between the sum of the first part and the sum of the second part.

For example, consider array A such that:

A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3

We can split this tape in four places:

  • P = 1, difference = |3 − 10| = 7 
  • P = 2, difference = |4 − 9| = 5 
  • P = 3, difference = |6 − 7| = 1 
  • P = 4, difference = |10 − 3| = 7 

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty zero-indexed array A of N integers, returns the minimal difference that can be achieved.

For example, given:

A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3

the function should return 1, as explained above.

Assume that:

  • N is an integer within the range [2..100,000];
  • each element of array A is an integer within the range [−1,000..1,000].

Complexity:

  • expected worst-case time complexity is O(N);
  • expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modifie

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        
        if (A == null || A.length < 2 || A.length > 100000) {
		return 0;
	}

	if (A.length == 2) {
	        return Math.abs(A[0] - A[1]);
	}

	int leftSum = A[0];
	int rightSum = 0;

	for (int j=1; j<A.length; j++) {
		rightSum += A[j];
	}

	int minDiff = Math.abs(leftSum - rightSum);

	for (int i=1; i<A.length-1; i++) {
		leftSum += A[i];
		rightSum -= A[i];
		int diff = Math.abs(leftSum - rightSum);
		if (diff < minDiff) {
			minDiff = diff;
		}
	}

	return minDiff;        
    }
}

© 著作权归作者所有

共有 人打赏支持
dkf_genius
粉丝 4
博文 1
码字总数 358
作品 0
荆州
高级程序员
亿简浏览器招募开源志愿者

亿简浏览器招募开源志愿者 可以是纯用户(提建议) 可以是coder 可以是designer 可以是team leader 可以协助制作图片 …… http://eazy.uueasy.com (eazy user distribution, from google) h...

okgo2010 ⋅ 2011/03/04 ⋅ 21

win7 64位 scrapy安装

scrapy的安装不难 就是挺麻烦的,需要安装scrapy的一些依赖包,我以我的机子环境为例说明一些安装过程 系统:win7 64bit 安装步骤: 1.先安装Python,机子是64位的,所以Python最好安装64位的...

Airship ⋅ 2015/12/13 ⋅ 0

亿简浏览器 0.4.8 正式版发布了

亿简浏览器是一款跨平台的开源“超光速”浏览器,现已经发布0.4.8正式版(有deb包) 更新记录: +增加了拖动模式,看小说、看漫画、看大图,可以自由拖动,细细品阅(目前chrome、firefox均不...

okgo2010 ⋅ 2011/09/13 ⋅ 7

亿简浏览器Eazy 0.4.7预览版发布

亿简浏览器Eazy 0.4.7预览版发布 新增微博集成插件 新增意外恢复 新增扩展机制 修正了一些小缺陷 源码: svn checkout http://okgo.googlecode.com/svn/trunk/Eazy 安装包: http://code.go...

okgo2010 ⋅ 2011/04/13 ⋅ 0

R语言,python接口rpy2安装的问题

想使用R语言的python接口,查看文档,http://rpy.sourceforge.net/rpy2.html使用下列方法 eazy_install rpy2 下载压缩包,python setup.py install 我的环境centos6.0,python2.6,R 2.13, ...

司徒春运 ⋅ 2012/03/16 ⋅ 5

亿简浏览器源码正式放出

目前,亿简浏览器源代码在其项目网站上正式以开放许可证放出,提供zip压缩包下载,也支持svn取出。 源码下载页面: http://code.google.com/p/okgo/downloads/list svn命令: svn checkout h...

okgo2010 ⋅ 2011/02/22 ⋅ 14

Wubi 安装的ubuntu 空间不够了怎么办?

用wubi在虚拟的分区中安装ubuntu可以不影响现有的硬盘分区, 但如果最初设定的空间太小,可能在安装了很多程序之后,系统提示你空间不够用了。 我是这样解决的: (1)个人home目录下的一些个...

阿睦瓦 ⋅ 2011/11/06 ⋅ 0

亿简浏览器0.4.7正式版发布

亿简浏览器0.4.7正式版发布 * 增加了媒体嗅探功能,可保存页面的媒体数据 * 增加了部分广告过滤功能 * 改进了页面加载逻辑,增强了稳定性 Ubuntu deb包也放出了: http://okgo.googlecode.c...

okgo2010 ⋅ 2011/05/12 ⋅ 8

亿简浏览器 0.4.7 updated 2 Fedora 15 版 发布

亿简浏览器,基于webkit的开源浏览器,主要用来 cross over the wall, 你懂的。 changelog: +内置加速器,紧急时不用慌乱 +增强了窗口管理,更方便 下载页面: http://code.google.com/p/o...

阿睦瓦 ⋅ 2011/09/03 ⋅ 8

亿简浏览器 0.4.8 beta 版本放出

亿简浏览器,基于Qt和Webkit,轻巧,快速,cross over something,(你懂的) *修正了弹窗控制 *增加了自带加速器 *修正了窗口操作; *修正了加速设置; *修正了cookie操作; *修正了标签操作...

okgo2010 ⋅ 2011/09/05 ⋅ 9

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Java 后台判断是否为ajax请求

/** * 是否是Ajax请求 * @param request * @return */public static boolean isAjax(ServletRequest request){return "XMLHttpRequest".equalsIgnoreCase(((HttpServletReques......

JavaSon712 ⋅ 28分钟前 ⋅ 0

Redis 单线程 为何却需要事务处理并发问题

Redis是单线程处理,也就是命令会顺序执行。那么为什么会存在并发问题呢? 个人理解是,虽然redis是单线程,但是可以同时有多个客户端访问,每个客户端会有 一个线程。客户端访问之间存在竞争...

码代码的小司机 ⋅ 59分钟前 ⋅ 0

到底会改名吗?微软GVFS 改名之争

微软去年透露了 Git Virtual File System(GVFS)项目,GVFS 是 Git 版本控制系统的一个开源插件,允许 Git 处理 TB 规模的代码库,比如 270 GB 的 Windows 代码库。该项目公布之初就引发了争...

linux-tao ⋅ 今天 ⋅ 0

笔试题之Java基础部分【简】【二】

1.静态变量和实例变量的区别 在语法定义上的区别:静态变量前要加static关键字,而实例变量前则不加。在程序运行时的区别:实例变量属于某个对象的属性,必须创建了实例对象,其中的实例变...

anlve ⋅ 今天 ⋅ 0

Lombok简单介绍及使用

官网 通过简单注解来精简代码达到消除冗长代码的目的 优点 提高编程效率 使代码更简洁 消除冗长代码 避免修改字段名字时忘记修改方法名 4.idea中安装lombnok pom.xml引入 <dependency> <grou...

to_ln ⋅ 今天 ⋅ 0

【转】JS浮点数运算Bug的解决办法

37.5*5.5=206.08 (JS算出来是这样的一个结果,我四舍五入取两位小数) 我先怀疑是四舍五入的问题,就直接用JS算了一个结果为:206.08499999999998 怎么会这样,两个只有一位小数的数字相乘,怎...

NickSoki ⋅ 今天 ⋅ 0

table eg

user_id user_name full_name 1 zhangsan 张三 2 lisi 李四 `` ™ [========] 2018-06-18 09:42:06 星期一½ gdsgagagagdsgasgagadsgdasgagsa...

qwfys ⋅ 今天 ⋅ 0

一个有趣的Java问题

先来看看源码: public class TestDemo { public static void main(String[] args) { Integer a = 10; Integer b = 20; swap(a, b); System.out......

linxyz ⋅ 今天 ⋅ 0

十五周二次课

十五周二次课 17.1mysql主从介绍 17.2准备工作 17.3配置主 17.4配置从 17.5测试主从同步 17.1mysql主从介绍 MySQL主从介绍 MySQL主从又叫做Replication、AB复制。简单讲就是A和B两台机器做主...

河图再现 ⋅ 今天 ⋅ 0

docker安装snmp rrdtool环境

以Ubuntu16:04作为基础版本 docker pull ubuntu:16.04 启动一个容器 docker run -d -i -t --name flow_mete ubuntu:16.04 bash 进入容器 docker exec -it flow_mete bash cd ~ 安装基本软件 ......

messud4312 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部