`
peijunlin2008
  • 浏览: 170741 次
  • 性别: Icon_minigender_1
  • 来自: 河北省
社区版块
存档分类
最新评论

两个关于算法的题目

阅读更多
1、         从一个数组中找出一个平衡点,即这个点的左边的和与右边的和相等。这个数组可能非常大。
2、         找出数组中出现次数超过一次的数,数组长度可能超过100万。


import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;

/**
*
* @author peijunlin

*/
public class BalanceNum1 {

/**
* @param args
*/
public static void main(String[] args) {
int[]   nums = {2,3,2,-2,-3,2,3};
List list = getBalanceIndex(nums);

for(int i=0;i<list.size();i++){
System.out.print(list.get(i)+"  ");
}
}


/**
*  本方法用BigDecimal类来保存数组之和
*  确保int[] 数组之和不会发生越界而产生错误
*
* @param nums  int[]数组
* @return  List所有平衡点下标集合
*/
public static List getBalanceIndex(int[] nums){

List list = new ArrayList();

int n_length = nums.length;
BigDecimal sumBig = new BigDecimal(0);
BigDecimal leftBig = new BigDecimal(0);
BigDecimal rightBig = new BigDecimal(0);

for(int i=0;i<n_length;i++){
BigDecimal bigi = new BigDecimal(nums[i]);
sumBig = bigi.add(sumBig);
}

for(int i=0;i<n_length;i++){
rightBig = leftBig.negate().add(sumBig).add(new BigDecimal(nums[i]).negate());
System.out.println("nums["+i + "]" + leftBig); 
System.out.println("nums["+i + "]" + rightBig);
if(leftBig == rightBig)
list.add(i);
leftBig = new BigDecimal(nums[i]).add(leftBig);
}
return list;
}

}

/* 运行结果:
nums[0]0
nums[0]5
nums[1]2
nums[1]2
nums[2]5
nums[2]0
nums[3]7
nums[3]2
nums[4]5
nums[4]5
nums[5]2
nums[5]3
nums[6]4
nums[6]0
1  4
即下标为 :1 和  4 的位置的数为平衡数
*/



import java.util.HashMap;
import java.util.Map;

/**
* 采用将原数组进行分段存取的策略
* 本类将原数据分为三段进行存取,当然可以分的更多一些;
*
* @author peijunlin
*
*/
public class ReData1 {

//存放1000以下的数据
Map<Integer,Integer > map1000 = new HashMap<Integer,Integer>();

//存放1000-10000之间的数据
Map<Integer,Integer> map10000 = new HashMap<Integer,Integer >();

//存放10000以上的数据
Map<Integer,Integer> mapOther = new HashMap<Integer,Integer >();


/**
*
* @param args
*/
public static void main(String[] args) {

ReData1 redata = new ReData1();

//假如有数组长度有一百万
int[] bigints = new int[1000000];

//把大数组阶段成较小的数组,每段10000
for(int i=0;i<bigints.length;i+=10000){
int[] small = new int[10000];
System.arraycopy(bigints, i, small, 0, 10000);
redata.dataAdd2Map(small);
}

}



/**
* 循环遍历一个数组将其中的数据加到Map中去
*
* @param nums
*/
public  void dataAdd2Map(int[] nums){
int nums_length = nums.length;

for(int i=0;i<nums_length;i++){
add2Map(nums[i]);
}

}

/**
* 根据int参数值的范围选择对应的Map进行存放
* @param num
*/
public  void add2Map(int num){
Map<Integer ,Integer> map = new HashMap<Integer,Integer>();
if(num<1000){
map = map1000;
}else if(num>1000 && num<10000) {
map = map10000;
}else {
map = mapOther;
}

Integer key = map.get(num);
if(key == null){
map.put(num, 1);
}else{
Integer n = map.get(num);
map.put(num, n+1);
}
}

}

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
* 百万级的数据一般存放在数据文件或数据库中,
* 本Demo设计针对数据存放在数据文件中的情况。
*
* 用读取IO流的方式读取大数据文件,让后再去将重复
* 数据存到另一个数据文件中,但是同样在JVM中使用分段
* Map保存数据。
*
*/
public class ReData2 {



//存放1000以下的数据
static Map<Integer,Integer > map1000 = new HashMap<Integer,Integer>();

//存放1000-10000之间的数据
static Map<Integer,Integer> map10000 = new HashMap<Integer,Integer >();

//存放10000以上的数据
static Map<Integer,Integer> mapOther = new HashMap<Integer,Integer >();



public static void main(String[] args) throws Exception {

ReData2 rd = new ReData2();
rd.readData();

Set<Integer> set = map1000.keySet();
Iterator it = set.iterator();
while(it.hasNext()){
Integer key = (Integer)it.next();
Integer value = map1000.get(key);

System.out.println("map1000 ["+key+","+value+"]");
}

rd.writeData(map1000,"redata.txt");



}



/**
* 将数据文件中的数据读取到Map中去
* @throws Exception
*/
public  void readData() throws Exception {

InputStreamReader is = new InputStreamReader(new FileInputStream("datafile.txt"));
BufferedReader reader = new BufferedReader(is);
String s;
while((s=reader.readLine())!=null){
List<Integer> list = str2int(s);
list2Map(list);
}
reader.close();

}

/**
* 将指定的Map中的数据存放到指定的文件中
* @param map
* @param file 存放数据的文件名(包括路径)
* @throws Exception
*/
public  void writeData(Map<Integer,Integer> map,String file) throws Exception {

FileOutputStream fos=new FileOutputStream(file);
OutputStreamWriter out = new OutputStreamWriter(fos);
PrintWriter writer=new PrintWriter(out);

Map<Integer,Integer > maps = new HashMap<Integer,Integer>();
maps = map;
Set<Integer> set = map.keySet();
Iterator it = set.iterator();
int number=0;
while(it.hasNext()){

Integer data = (Integer)it.next();
Integer nums = map.get(data);

if(nums>1 ){
number++;
writer.write(data+",");
}


if(number >= 1000){
writer.flush();
number = 0;
}
}

writer.close();
}

/**
* 一个字符串数据分割之后,将有效数据保存到List中
* @param s  String字符串
* @return List<Integer>
*/
public  List<Integer> str2int(String s){
List<Integer> list = new ArrayList<Integer>();

String[] ss = s.split(",");
int ss_length = ss.length;
for(int i=0;i<ss_length;i++){
String str = ss[i];
if(!"".equals(str))
list.add(Integer.parseInt(str));
}
return list;
}

/**
* 将List中的数据存放到指定的Map中
* @param list
*/
public  void list2Map(List list){
int size = list.size();
for(int i=0;i<size;i++){
Integer num = (Integer) list.get(i);
add2Map(num);
}

}

/**
* 根据int参数值的范围选择对应的Map进行存放
* @param num
*/
public  void add2Map(int num){
Map<Integer ,Integer> map = new HashMap<Integer,Integer>();
if(num<1000){
map = map1000;
}else if(num>1000 && num<10000) {
map = map10000;
}else {
map = mapOther;
}

Integer key = map.get(num);
// System.out.println("key:"+key);
if(key == null){
map.put(num, 1);
}else {
Integer n = map.get(num);
// System.out.println("n:"+n);
map.put(num, n+1);
}
}

}

1
2
分享到:
评论

相关推荐

    工程实践 第一部分 题目一 求两个集合的合并运算 题目二 求两个有序表合并算法.zip

    在本压缩包文件中,包含了两个编程题目,均与数据结构和算法相关,适用于C语言的编程实践。这些练习旨在帮助学生掌握集合合并运算以及两个有序表的高效合并方法。成都信息工程大学的学生们可以通过完成这些题目来...

    基础算法题目精简集合

    ### 基础算法题目精简集合解析 #### 第一章 循环控制 ##### 题目1:输出特定格式的菱形 - **题目描述**:输入一个奇数`n`,输出一个对角线长度为`n`的实心或空心菱形图案。 - **解题思路**: - 使用双重循环结构...

    c++ 经典算法题目

    C++经典算法题目 本资源是一个C++经典算法题目集,涵盖了多种算法类型,包括基本算法、数字算法、字符串算法等。该资源来自学校内部的资料,是学习C++编程的非常有价值的参考资料。 算法1:A+B Problem 该算法的...

    python算法趣味题目

    本文将介绍并解析两道有趣的Python算法题目,旨在帮助读者更好地理解Python语言的特点及其在处理字符串方面的优势。通过具体的示例代码,我们将深入探讨Python如何以简洁而高效的方式解决实际问题。 #### 题目1:...

    经典算法题目与答案-含代码

    本书《经典算法题目与答案-含代码》是一本集成了多种编程语言的算法题目的资料书籍,覆盖了基础数据结构、排序算法、基础算法、数学问题解决以及编码相关问题。其中,数据结构部分包括字符串、链表、二叉树、哈夫曼...

    动态规划算法经典题目

    1. 最长公共子序列:给定两个序列,求它们的最长公共子序列。 2. 最长上升子序列:给定一个序列,求其中的最长上升子序列。 3. 最优二分检索树:给定一个序列,求其中的最优二分检索树。 4. 最优矩阵链乘:给定多个...

    算法题目集锦.pdf

    《算法题目集锦》是一本深入探讨算法设计与程序设计的资料,对于学习和提升算法能力有着极高的价值。本书主要分为两大部分:算法初步和程序设计。 在算法初步部分,书中强调了算法的重要性,指出算法是解决问题的...

    PTA习题:数据结构与算法题目集1

    对于这个问题,可以使用一次遍历来解决,维护两个变量:当前子序列的和以及迄今为止找到的最大子序列和。每次遍历到一个新元素时,可以选择将其加入当前子序列或开始一个新的子序列(即当前元素)。通过比较当前元素...

    2017年华为算法比赛题目

    在《HUAWEI_Code_Craft_2017_Preliminary_Contest_Question_en_v1.3.zip》和《HUAWEI_Code_Craft_2017_Preliminary_Contest_Question_zh_v1.3.zip》这两个压缩包中,包含了比赛的初步竞赛题目。这些题目可能涵盖数据...

    一个关于Dijkstra算法的题目

    Dijkstra算法在许多领域都有应用,如路由协议中的最短路径优先(Shortest Path First, SPF)算法,网络流量优化,旅行商问题的近似解,以及各种图形算法中计算两点间的最短路径等。值得注意的是,当图中存在负权重边...

    判别两个广义表是否相等的递归算法

    判别两个广义表是否相等的递归算法

    POJ算法题目分类

    POJ 算法题目分类 POJ 算法题目分类是指分类所有 POJ 题目的算法思想和解决方案,本文将对算法分类进行详细的介绍。 一、基本算法 基本算法是指最基础的算法思想,如枚举、贪心、递归和分治法、递推、构造法、...

    acm算法题目

    代码中需要填充的地方包括两个条件判断:第一个是在外层循环中判断是否跳过当前分数,第二个是在内层循环中累加有效分数。完整的代码如下: ```c if(i != j) sum += x[j]; ``` 这样可以确保不包括当前正在检查的...

    LeetCode每日一题高频面试算法题目1

    本资源是一个 LeetCode 高频面试算法题目集合,包括队列实现栈、反转单链表、合并两个排序数组等多个算法题目。 1. 队列实现栈: 在该题目中,我们使用了两个队列来实现栈的功能。队列是 First-In-First-Out(FIFO...

    数据结构算法复杂度题目答案

    以下是给定题目中涉及的一些知识点。 1. 大O符号(Big-Oh)表示法:大O符号是用来描述算法运行时间或空间需求的渐进上界。在这些程序片段中,我们使用大O符号来表示每个循环结构的时间复杂度。 - (1) O(N):一个...

    扫描算法介绍及题目1

    本文主要讨论了两种常用的算法:节约算法和扫描算法,以及在扫描算法实施中应用的最近插入法,用于解决车辆路线问题(Vehicle Routing Problem, VRP)。 节约算法由Carke和Wight在1964年提出,适用于解决车辆数量不...

    JAVA算法题目集合.pdf

    这个文件中的Java算法题目集合涵盖了多个经典算法和编程问题,适合用来提升编程能力和算法理解。以下是对这些题目知识点的详细解释: 1. **最大公约数与最小公倍数**:求两个数的最大公约数(GCD)和最小公倍数...

    Java程序设计算法竞赛题目

    算法思路:使用冒泡排序算法,扫描数组 R,从下往上比较每个气泡的权重,如果发现轻气泡在重气泡之下,则将其向上"飘浮",直到最后任何两个气泡都是轻者在上,重者在下为止。 输出结果:比较次数和交换次数 ...

    算法分析与设计题目

    7. **快速排序算法**:快速排序是一种采用分治策略的递归排序算法,其核心是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后分别对这两部分记录继续进行排序,以...

Global site tag (gtag.js) - Google Analytics