0830--算法练习题

1. 内存中有一个长数组，条目数为10万，数组单元为结构体struct array，sizeof(struct array)为512字节。结构有一int型成员变量weight。现需要取得按weight值从大到小排序的前500个数组单元，请实现算法，要求效率尽可能高。

 

package org.jyjiao.test1;

//Struct 元素类
class Struct{
	private int weight;
	
	public int getWeight() {
		return weight;
	}
	
	public void setWeight(int weight) {
		this.weight = weight;
	}
	
}

//堆操作
class Heap{
	Struct[] items;
	int itemsLen;    //堆大小
	int lastIndex;   //最后一个元素的下标
	
	public Heap(Struct[] items){
		this.items=items;
		this.itemsLen=items.length;
		this.lastIndex=this.itemsLen-1;
	}
	
	//创建最大堆
	public void createHeap(){
		if(itemsLen>0){
			for(int i=itemsLen/2-1;i>=0;i--){
				siftDown(i);                              //注意参数
			}
		}else{
			System.out.println("array is null");
		}
	}
	
	//取得堆顶元素，并重新调整堆
	public Struct getMax(){
		Struct ret=items[0];
		items[0]=items[lastIndex];
		lastIndex--;
		siftDown(0);
		return ret;
	}
	
	//向下筛
	void siftDown(int i){                                //核心算法
		int childIndex;
		while((2*i+1)<=lastIndex ){
			childIndex=2*i+1;
			if((2*i+2)<=lastIndex && items[2*i+1].getWeight()<items[2*i+2].getWeight()){
				childIndex=2*i+2;
			}
			if(items[i].getWeight()<items[childIndex].getWeight()){
				Struct tmp=items[i];
				items[i]=items[childIndex];
				items[childIndex]=tmp;
				i=childIndex;
			}else{
				break;
			}
		}//while
	}
	
}

//测试代码
public class Max500 {
	public static void main(String[] args){
		Struct[] array=new Struct[10];
		for(int i=0;i<10;i++){
			array[i]=new Struct();                                      //本句不能缺少，必须初始化数组对象！
			array[i].setWeight((int)(Math.random()*50));  //注意用set，不要用赋值语句
			System.out.print(array[i].getWeight()+"  ");
		}
		System.out.println("\n");
		Heap heap=new Heap(array);
		heap.createHeap();
		for(int i=0;i<5;i++){
			Struct tmp=heap.getMax();
			System.out.print(tmp.getWeight()+"  ");
		}
	}
	
}

 

 算法效率: O(n)

 

 

2. 现有两个文件，

　　a)数据文件A，格式为：关键词、IP地址、时间，记录条数为1000万左右，该文件是无序排列的。

　　b)数据文件B是关键词ID到关键词的对应表文件，格式为：ID、关键词，记录条数在100万左右，也是无序排列的。该对应表中的记录是一一对应的，不存在ID或者关键词重复的情况。

　　要求将数据文件A对应的关键词替换为B中的ID，生成新的数据文件C，数据文件C的格式为：关键词ID、IP地址、时间。

　　请设计一个程序，实现上述功能，并分析时间复杂度和空间复杂度。运行程序所使用的服务器的内存为1G，硬盘足够大。(至少要给出关键算法和设计思路)

 

package org.jyjiao.test1;

import java.io.*;
import java.util.*;

public class ReplaceKeyWord {
	String fileA, fileB, fileC;
	HashMap<String,Integer> map;
	public ReplaceKeyWord(String fileA, String fileB, String fileC) {
		this.fileA = fileA;
		this.fileB = fileB;
		this.fileC = fileC;
		map = new HashMap<String,Integer>();
	}

	public void replace() {
		try {
			BufferedReader brA = new BufferedReader(new FileReader(fileA));
			BufferedReader brB = new BufferedReader(new FileReader(fileB));
			BufferedWriter bwC = new BufferedWriter(new FileWriter(fileC));
			// iniciate hashmap (时间复杂度：O(1M)，空间复杂度：O(1M))
			String str;
			while ((str = brB.readLine()) != null) {
				str.trim();
				String[] tmpB = new String[2];
				tmpB = str.split("、");
				map.put(tmpB[1],new Integer(tmpB[0]));
			}
			
			// input fileC (时间复杂度:O(10M), 空间复杂度：O(1))
			while ((str = brA.readLine()) != null) {
				str.trim();
				String[] tmpA=str.split("、");
				
				String key=tmpA[0];
				if(map.containsKey(key)){
					Integer id=map.get(key);
					str=id+"、"+tmpA[1]+"、"+tmpA[2];
					bwC.write(str);
					bwC.newLine();
				}
			}
			
			brA.close();
			brB.close();
			bwC.flush();
			bwC.close();
			
		} catch (IOException ex) {
			ex.printStackTrace();
		} finally {

		}
	}

	public static void main(String[] args) {
		String fileA="D:\\fileA.txt";
		String fileB="D:\\fileB.txt";
		String fileC="D:\\fileC.txt";
		ReplaceKeyWord rk=new ReplaceKeyWord(fileA,fileB,fileC);
		rk.replace();
	}

}

 时间复杂度:O(len(fileA)) ,  空间复杂度：O(len(fileB))

 

 

3. 对一个数组S，求其中满足要求的最大元素C。要求C满足等式C=A*B，其中A、B也是数组S中的元素。请用能想到的最优算法，分析时间和空间复杂度。（用语言描述算法，不用写程序）
注：这个题我当时做的方法在时间上要用o(n^3)，事后想出了个o(n^2 logn)的方法。不知有没有更好的方法。

 

 

package org.jyjiao.test1;
import java.util.*;
public class MaxProduct {
	public static void main(String[] args){
		int[] S={2,3,6,18,36,216,12,108};
		int C=0;;
		HashSet<Integer> set=new HashSet<Integer>();
		for(int i=0;i<S.length;i++){
			set.add(new Integer(S[i]));
		}
		for(int i=0;i<S.length;i++){
			for(int j=i+1;j<S.length;j++){
				int tmp=S[i]*S[j];
				if(set.contains(new Integer(tmp))){
					if(tmp>C){
						C=tmp;
					}
				}
			}
		}
		System.out.println("max product is:"+C);
	}

}

 

 

 

5. 一个整数数列，元素取值可能是1-N（N是较大的正整数）中的任意一个数，相同数值不会重复出现。设计一个算法，找出数列中符合条件的的数对的个数，满足数对中两个数的和等于N+1。

复杂度最好是O(n)

 

 

6.有个整数数列，如何求绝对数和最大的连续字符串，