一些笔试面试题

最近有些网友给我QQ上或者在群里问了一些面试题，有些很简单，有些网友觉得较难的或者出现的频率较高的我就总结下，现在把我个人的一些看法给写出来，由于本人水平有限，肯定有不妥之处，请各位大虾批评指正。

package com.myclover.exam;

import java.io.File;
import java.io.FileOutputStream;
import java.math.BigDecimal;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

/**
 * <pre>
 * java程序员面试笔试的常见编程试题
 * 最近很多网友给我QQ上问一些他们被面到的面试题，下面把一些常见的
 * 频率比较高的给总结出来，通过该类来完成，因为本人水平有限，代码
 * 有什么不妥之处请谅解并指出
 * Blog: http://myclover.iteye.com
 * @author myclover
 * </pre>
 */
@SuppressWarnings("all")
public class ExamArray {
	
	
	/**
	 * 功能描述：
	 *         统计一串字符中每个字符出现的次数，并且进行排序
	 *         比如输入 abbcccddd ，则输出 a(1)b(2)c(3)d(3)
	 *         假如参数是 ddcccbAa 输出格式为:   a(1)b(1)c(3)d(2)A(1)
	 * @param str  字符串
	 * @return  返回值：返回排序并且统计之后的新字符串
	 */
	public static String calStringCounts(String str){
		//对字符串先进行排序
		str = sortString(str);
		int count = 1;
		StringBuffer sb = new StringBuffer();
		int length = str.length();
		for(int i = 0 ; i < length ; i++){
			if(i < (length - 1) && (str.charAt(i) == str.charAt(i+1))){
				count++;
			}else{
				sb.append(str.charAt(i)).append("(").append(count).append(")");
				count = 1;
				continue;
			}
		}
		return sb.toString();
	}
	
	
	/**
	 * 功能描述：
	 *         对一串无序的字符串进行排序，小写字母在大写字母之前
	 * @param str 无序的字符串
	 * @return    返回值：返回排序后的新字符串
	 */
	private static String sortString(String str){
		StringBuffer sb1 = new StringBuffer();
		StringBuffer sb2 = new StringBuffer();
		for(int i = 0 ; i < str.length() ; i++){
			//小写字母
			if((int)str.charAt(i) >= 97){
				sb1.append(str.charAt(i));
			}else{
				//大写字母
				sb2.append(str.charAt(i));
			}
		}
		//把字符串转换成字符数组
		char[] ch1 = sb1.toString().toCharArray();
		char[] ch2 = sb2.toString().toCharArray();
		//对字符数组排序
		Arrays.sort(ch1);
		Arrays.sort(ch2);
		
		return new String(ch1) + new String(ch2);
	}
	
	
	/**
	 * 功能描述：
	 *          判断两个整型数组是否相同，两个整型数组是无序的，可以有重复的
	 *          要求两个数组中重复的元素一致，并且重复的次数一致才算是相同
	 *          使用Arrays类来实现
	 * @param a 整型数组
	 * @param b 整型数组
	 * @return  返回值：如果两个数组相同，则返回true，否则返回false
	 */
	public static boolean isEqualArrayUseArrays(int[] a , int[] b){
		//如果长度不相同，则两个数组肯定不相同
		if(a.length != b.length){
			return false;
		}
		//对两个数组进行排序
		Arrays.sort(a);
		Arrays.sort(b);
		return Arrays.equals(a, b);
	}

	/**
	 * 功能描述：
	 *          判断两个整型数组是否相同，两个整型数组是无序的，可以有重复的
	 *          要求两个数组中重复的元素一致，并且重复的次数一致才算是相同
	 *          并且不能使用javaAPI中的Arrays辅助类实现
	 * @param a 整型数组
	 * @param b 整型数组
	 * @return  返回值：如果两个数组相同，则返回true，否则返回false
	 */
	public static boolean isEqualArray(int[] a , int[] b){
		//如果长度不相同，则两个数组肯定不相同
		if(a.length != b.length){
			return false;
		}
		//这里使用双端队列Deque，ArrayDeque不是线程安全的，jdk1.6版本之后才有
		Deque<Integer> list = initDeque(a);
//		List<Integer> list = initList(a);
		for(Integer s : b){
			if(list.contains((Object)s)){//如果队列中存在，则删除，继续下一次遍历
				 //这里删除指定的元素，如果是整数的话则需要转成Object类型，因为该方法支持按照索引删除
				list.remove((Object)s); 
				continue;
			}else{
				return false;
			}
		}
		//如果最后集合为空，则表示两个数组相同
		if(list.size() <= 0){
			return true;
		}
		return false;
	}
	
	
	/**
	 * 功能描述：
	 *          通过一个整型数组组装到一个Deque集合中，本方法仅适合jdk1.6+版本的
	 * @param a 一个整型数组
	 * @return  返回值：返回组装之后的集合列表
	 */
	private static Deque<Integer> initDeque(int[] a){
		Deque<Integer> deque = new ArrayDeque<Integer>();
		for(Integer ds : a){
			deque.add(ds);
		}
		return deque;
	}
	
	
	/**
	 * 功能描述：
	 *          通过一个整型数组组装到一个List集合中，该方法适合jdk1.5+
	 * @param a 一个整型数组
	 * @return  返回值：返回组装之后的集合列表
	 */
	private static List<Integer> initList(int[] a){
		//LinkedList在检索时速度要比ArrayList快，只是在装载时需要消耗更大的内存
		//如果内存允许，换取时间的话可以考虑使用LinkedList，但是如果为了内存的话那么
		//就使用ArrayList
		List<Integer> list = new LinkedList<Integer>();
//		List<Integer> list = new ArrayList<Integer>();
		for(Integer ds : a){
			list.add(ds);
		}
		return list;
	}
	
	
	/**
	 * 功能描述：
	 *         构建一个无序并且可以重复的整型数组
	 * @param length    数组的长度
	 * @param maxValue  数组中元素的最大值
	 * @return  返回值：返回一个整型数组
	 */
	public static int[] buildArray(int length , int maxValue){
		int[] a = new int[length];
		for(int i = 0 ; i < length ; i++){
			Random r = new Random();
			a[i] = r.nextInt(maxValue);
		}
		return a;
	}
	
	
	/**
	 * 功能描述：
	 *         有一种积分机制，首先是不同的等级送了一个总积分，然后每消费三个积分
	 *         时又可以赠送一个积分，请设计一个方法计算出每个等级可以享受的总积分
	 * @param sum  第一次赠送的总积分
	 * @return  返回值：返回某积分下最终可以享受的总积分数
	 */
	public static int getTotalCounts(int sum){
		int count = 0;
		while(sum > 0){
			sum-- ;
			count++;
			if(count % 3 == 0){
				sum += 1;
			}
		}
		return count;
	}
	
	
	/**
	 * 功能描述：
	 *         采用进位方式求大整数(n)的阶乘
	 * @param n 阶乘参数
	 */
	public static void bigNumFactorial(int n) throws Exception
	{
		 long[] arr = new long[1000000];   //通过arr数组装阶乘结果
		    int high ,j ;   //high控制进位 ，j控制循环
		    int digit = 1 ;  // 位数   
		    int temp , i ;   
		    arr[0] = 1 ;   
		    for(i = 2 ; i <= n ; i++){   
		        for(high = 0 , j = 1 ; j <= digit ; ++j){   // 循环计算  
		            temp=(int)(arr[j-1]*i + high);// 计算乘积   
		            arr[j-1] = temp % 10;    // 保存每一位   
		            high = temp / 10;     // 进位   
		        }   
		        while(high > 0){   
		            arr[++digit-1] = high % 10;// 保存高位   
		            high /= 10;   
		        }   
		    } 
		    File file = new File("D:/result.txt");
			FileOutputStream fouts = new FileOutputStream(file , true);
		    //循环输出结果
		    for(int k = digit ; k >= 1 ; --k){   
		    	//把结果输出到文件中，这里使用了追加模式，所以每次测试时先把文件删除再进行测试
		    	fouts.write(String.valueOf(arr[k-1]).getBytes());
		    	//以下是在控制台直接输出
//		        System.out.print(arr[k-1]);  
//		        if(k % 100 == 0){//每输出100位换行
//		        	System.out.println();
//		        }
		    }   
		    fouts.close();
	}
	
	
	
	/**
	 * 功能描述：
	 *          使用java.math.BigDecimal类进行计算大整数阶乘
	 * @param n 阶乘参数
	 */
	public static void bigDecimalFactorial(int n) throws Exception{
		BigDecimal result = new BigDecimal("1");   
        for(int i = 2 ; i <= n ; i++){   
        	result = result.multiply(new BigDecimal(String.valueOf(i)));   
        } 
//        System.out.println(result.toString());  
        //把结果保存到文件之中，这里每次会覆盖原文件
        saveResult("D:/result1.txt" , result.toString() , false);
	}
	
	
	/**
	 * 功能描述：
	 *         保存指定内容到文件中
	 * @param filePath   文件所在的路径
	 * @param content    文件内容
	 * @param isAppend   是否追加
	 * @throws Exception
	 */
	private static void saveResult(String filePath , String content , boolean isAppend) throws Exception{
		File file = new File(filePath);
		FileOutputStream fouts = new FileOutputStream(file , isAppend);
		fouts.write(content.getBytes());
		fouts.flush();
		fouts.close();
	}
	
}

package com.myclover.exam.test;

import com.myclover.exam.ExamArray;

public class TestExamArray {

	public static void main(String[] args) {

		int[] a = ExamArray.buildArray(500000, 10000);
		int[] b = ExamArray.buildArray(500000, 10000);
		
		long st = System.currentTimeMillis();
		long sf = Runtime.getRuntime().freeMemory();
//		System.out.println(ExamArray.isEqualArray(a, b));
		System.out.println(ExamArray.isEqualArrayUseArrays(a, b));
		long et = System.currentTimeMillis();
		long ef = Runtime.getRuntime().freeMemory();
		System.out.println("执行时间：" + (et - st) + "  消耗的内存：" + (sf - ef));
		
		String  str = "DAsfsdddcdsfdsfwSDSARECCXASerw";
		System.out.println(ExamArray.calStringCounts(str));
		System.out.println(ExamArray.getTotalCounts(100));
//		try {
//			ExamArray.bigNumFactorial(20);
//			ExamArray.bigDecimalFactorial(20);
//		} catch (Exception e) {
//			e.printStackTrace();
//		}
	}

}