`
zhouYunan2010
  • 浏览: 206130 次
  • 性别: Icon_minigender_1
  • 来自: 湖南
社区版块
存档分类

基本算法题目汇总(不断追加中..)

算法 
阅读更多
1.一道简单16进制加密算法 
/**
 * 简单加密解密算法
 * 任意十六进制字符ascii转换，转换规则：
 * 当前index位置的数加上index，如果结果超出F则从0重新开始循环
 * 比如： "3A4E"应该被转换为"3B61"
 *   3在0位置，所以保持不变,
 *   A在1位置，转化为B,
 *   4在2位置，转化为6,
 *   E在3位置，转化为1,
 * 然后倒转字符，比如"3B61"转换为"16B3"
 */
public class Encryption {
	public static void main(String[] args) {
		System.out.println(Decrypt2(encrypt2("3A4E46ABAE829")));  
        System.out.println(encrypt2("3A4E"));  
        System.out.println(Decrypt2("16B3"));
	}
	
	//encrypt 加密
	public static String encrypt2(String hexStr){
		String template = "0123456789ABCDEF";
		int len = hexStr.length();
		char[] result = new char[len];
		int index = 0;
		int ch = 0;
		for(int i=0;i<len;i++){
			ch = hexStr.charAt(i);
			index = (i + template.indexOf(ch))%16;
			result[i] = template.charAt(index);
		}
		result = reverse(result);
		return new String(result);
	}
	
	//Decrypt 解密
	public static String Decrypt2(String hexStr){
		String template = "FEDCBA9876543210";
		char[] argStr = hexStr.toCharArray();
		argStr = reverse(argStr);

		char[] result = new char[argStr.length];
		int index = 0;
		for(int i=0;i<argStr.length;i++){
			index = (i + template.indexOf(argStr[i]))%16;
			result[i] = template.charAt(index);
		}
		return new String(result);
	}
	
	//reverse the char array
	public static char[] reverse(char[] chs){
		char temp;
		for(int i=0;i<chs.length/2;i++){
			temp = chs[i];
			chs[i] = chs[chs.length-1-i];
			chs[chs.length-1-i] = temp;
		}
		return chs;
	}
}



2.上机试题三则 
public class HaweiQuestion {
	public static void main(String[] args) {
		HaweiQuestion q = new HaweiQuestion();
		int[] input = {3, 6, 1, 9, 7, 8}; 
		int[] output = new int[input.length];
		q.sort(input, input.length, output);
		for(int i=0;i<input.length;i++){
			System.out.print(output[i]+" ");
		}
		System.out.println();
		int[] task = {0, 30, 155, 1, 80, 300, 170, 40, 99};
		int[] system_task = new int[task.length];
		int[] user_task = new int[task.length];
		q.scheduler(task, task.length, system_task, user_task);
		
	}
	
	/**
	 * 选秀节目打分，分为专家评委和大众评委，score[] 数组里面存储每个评委打的分数，
	 * judge_type[] 里存储与 score[] 数组对应的评委类别，judge_type[i] == 1，表示专家评委，
	 * judge_type[i] == 2，表示大众评委，n表示评委总数。
	 * 打分规则如下：专家评委和大众评委的分数先分别取一个平均分（平均分取整），
	 * 然后，总分 = 专家评委平均分 * 0.6 + 大众评委 * 0.4，总分取整。如果没有大众评委，
	 * 则 总分 = 专家评委平均分，总分取整。函数最终返回选手得分。
	 */
	public int cal_score(int score[], int judge_type[], int n)  {
		int proNum=0;
		int peoNum=0;
		int total=0;
		int peoCount=0;
		for(int i=0;i<n;i++){
			if(judge_type[i]==1){
				proNum += score[i];
			}else{
				peoNum += score[i];
				peoCount++;
			}
		}
		if(peoCount!=0)
			total = (int)(proNum * 0.6 + peoNum * 0.4);
		else
			total = proNum / n ;
		return total;
	}
	
	
	/**
	 * 给定一个数组input[] ，如果数组长度n为奇数，
	 * 则将数组中最大的元素放到 output[] 数组最中间的位置，
	 * 如果数组长度n为偶数，则将数组中最大的元素放到 output[] 数组中间两个位置偏右的那个位置上，
	 * 然后再按从大到小的顺序，依次在第一个位置的两边，按照一左一右的顺序，依次存放剩下的数。
     * 例如：input[] = {3, 6, 1, 9, 7} output[] = {3, 7, 9, 6, 1}; 
     * input[] = {3, 6, 1, 9, 7, 8} output[] = {1, 6, 8, 9, 7, 3}
	 */
	 public void sort(int input[], int n, int output[]){
		 //首先按从大到小的顺序排列input
		 for(int i=0; i < n;i++){
			 for(int j = i;j > 0;j--){
				 if(input[j] > input[j-1]){	//大数上浮
					 swap(input,j,j-1);
				 }
			 }
		 }

		int count = 0;
		for (int i = n / 2, j = n / 2; i >= 0 && j < n; i--, j++) {
			if (i == j) {
				output[i] = input[count++];
			} else {
				output[i] = input[count++];
				output[j] = input[count++];
			}
		}
		if(n%2 == 0){	//偶数还有一个值
			output[0] = input[count];
		}
		 
	 }

	private void swap(int[] input, int j, int i) {
		int temp = input[j];
		input[j] = input[j-1];
		input[j-1] = temp;
		
	}
	
	
	/**
	 * 操作系统任务调度问题。操作系统任务分为系统任务和用户任务两种。
	 * 其中，系统任务的优先级 < 50，用户任务的优先级 >= 50且 <= 255。
	 * 优先级大于255的为非法任务，应予以剔除。
	 * 现有一任务队列task[]，长度为n，task中的元素值表示任务的优先级，数值越小，优先级越高。
	 * 函数scheduler实现如下功能，将task[] 中的任务按照系统任务、用户任务依次存放到 system_task[]数组和 
	 * user_task[] 数组中（数组中元素的值是任务在task[] 数组中的下标），
	 * 并且优先级高的任务排在前面，优先级相同的任务按照入队顺序排列（即先入队的任务排在前面），
	 * 数组元素为-1表示结束。
     * 例如：task[] = {0, 30, 155, 1, 80, 300, 170, 40, 99} 
     * system_task[] = {0, 3, 1, 7, -1} user_task[] = {4, 8, 2, 6, -1}
	 */
	public void scheduler(int task[], int n, int system_task[], int user_task[]){
		int[] indexs = new int[n];	//用来保存下标
		for(int i=0;i<n;i++){	//初始化
			indexs[i] = i ;
		}
		//按从小到大的顺序排列task
		 for(int i=0; i < n;i++){
			 for(int j = i;j > 0;j--){
				 if(task[j] < task[j-1]){	//小数上浮，相等不交换
					 swap(task,j,j-1);
					 swap(indexs,j,j-1);	//同时交换下标
				 }
			 }
		 }
		 int sysPoint = 0;
		 int userPoint = 0;
		 for(int i=0;i<n;i++){
			 if(task[i] < 50){
				 system_task[sysPoint++] = indexs[i];
			 }else if(task[i]<=255){
				 user_task[userPoint++] = indexs[i];
			 }else{
				 //do nothing
			 }
		 }
	}
}



3.将1-9组成三个特殊三位数 
/*
 *  将1-9九个数字组合成三个三位数。
 *  要求1-9每个数字只使用一次，且第二个数是第一个数的两倍，第三个数是第一个数的三倍。
 *  符合条件的数有几组？将他们打印出来。
 * */
public class FindGroup {
	public static void main(String[] args) {
		int maxNumber = 987/3;   //不重复最大数为987
		int count = 0;
		for(int i=123;i<maxNumber;i++){
			if(isRepeat(i+""+i*2+""+i*3)){   //无重复
				count++;
				System.out.println(i+" "+i*2+" "+i*3);
			}
		}
	}
	
	public static boolean isRepeat(String str){       //判断是否有重复数字
		char[] chs = str.toCharArray();
		String reserve = "";
		for(int i=0;i<chs.length;i++){
			if(reserve.indexOf(chs[i])==-1){
				reserve+=chs[i];
			}
		}
		return chs.length==reserve.length()?true:false;
	}
}



4.超大数相加 
public class AddBigNumber {
	public static void main(String[] args) {
		String data1 = "123456";
        String data2 = "22";
        String result = add(data1,data2);
        System.out.println(result);

	}

	public static String add(String data1, String data2) {
		int store = 0;
		int len1 = data1.length();
		int len2 = data2.length();
		StringBuffer sb = new StringBuffer();
		for(int i=0;i<(len1>len2?len1:len2);i++){
			int d1 = getLowerNumber(i,data1);
			int d2 = getLowerNumber(i,data2);
			int sum = d1 + d2 + store;
			
			store = sum/10;       //有进位就存下来
			sb.append(sum%10);
		}
		if(store!=0)sb.append(store);     //考虑最高位进位
		return sb.reverse().toString();
	}
	
	public static int getLowerNumber(int i,String str){
		if(i>=str.length())return 0;
		String s = str.charAt(str.length()-1-i)+"";
		return Integer.parseInt(s);
	}
}



5.求喝饮料数与求日期 
package com.algorithm;

/**
 * @author 
 * http://topic.csdn.net/u/20111012/20/1c402221-028c-4920-b2fc-0b63b839d256.html?38410
 */
public class BottleDay {
	/**
	 * 20块钱，1块钱1瓶，两个空瓶子可以换一瓶，问最多可以喝几瓶？
	 */
	public static void maxDrink(){
		int sum = 20;
		int bottle = sum;
		while (bottle > 1) {
			System.out.println(bottle+" "+bottle/2);
		    sum += bottle/2;
		    bottle = bottle%2 + bottle/2;
		}
		System.out.println(sum);
	}
	
	
	/**
	 * 有一名员工发现日历已经7天没有翻了，
	 * 于是他连着翻了7页，7天的总和刚好是138，问这一天是几号？
	 */
	public static void getSpecialDay() {
		int[] end = { 28, 29, 30, 31 };		//可能的月末最後一天
		int days = 138;
		int count = 0;
		int day; 
		int max;
		boolean found = false;	//标志位
		for (int i = 0; i < end.length; i++) {
			max = end[i] + 7;	//7号
			day = 1;
			while (max > 0) {
				count = 0;
				for (int j = day; j < day + 7; j++) {
					if (j > end[i]) {
						count += j % end[i];
					} else {
						count += j;
					}
				}
				if (count == days) {
					found = true;
					for (int j = day; j < day + 7; j++) {
						System.out.printf("%d, ", j > end[i] ? j % end[i] : j);
					}
					break;
				}
				day++;
				max--;
			}
			if (found) {
				System.out.printf("------end=%d\n", end[i]);
				break;
			}
		}
		if (!found) {
			System.out.println("error");
		}
	}
	
	public static void main(String[] args) {
		maxDrink();
		System.out.println("--------");
		getSpecialDay();
	}
}


6.正则表达式按要求切割代码
文件名：test.txt,这是要切割的代码 
#include<iostream>
int main()
{
    int c[20];
    int a=5;
    int b=a+12;
    for(int i=0;i<=10;i++)
    {
        c[i]=i;  
    }
    return 0;
}

算法如下 
package com.algorithm;


import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * author:yunan
 */
public class SpiltCode {
	//你要保留的连续的字符
	private String[] codes = {"==","++","--",">=","+=","<="};  //等等..
	ArrayList<String> saveTable = new ArrayList<String>();	//保存所有切割出来的串
	
	public static void main(String[] args) {
		new SpiltCode().spiltCode();
	}
	
	private BufferedReader getBuffreader(String path){
		File file = new File(path);
		FileInputStream in;
		BufferedReader reader=null;
		try {
			in = new FileInputStream(file);
		    reader = new BufferedReader(new InputStreamReader(in));
		} catch (Exception e) { 
			e.printStackTrace();
		}
		return reader;
	}
	
	public  void spiltCode(){
		BufferedReader reader = getBuffreader("test.txt");
		String regex = "\\w+|\\p{Punct}";	//这个可以把单词和一个一个特殊字符全切出来
		Pattern p = Pattern.compile(regex);
		Matcher m = null;
		String line = null;
		String pre = "";	//上一个匹配的串
		int index = 0;
		try {
			while((line=reader.readLine())!=null){
				m = p.matcher(line);
				while(m.find()){
					String chars = m.group();
					if(isInCodes(pre+chars)){ 
						saveTable.set(--index, pre+chars);
					}else{ 
						saveTable.add(chars);
					}
					pre = chars;
					index++;
				}
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
		printTable();	//打印
	}
	
	private boolean isInCodes(String code){
		for(int i=0;i<codes.length;i++){
			if(codes[i].equals(code)){
				return true;
			}
		}
		return false;
	}
	
	private void printTable(){
		for(String sav:saveTable){
			System.out.println(sav);
		}
	}
}
结果如下：

#
include
<
iostream
>
int
main
(
)
{
int
c
[
20
]
;
int
a
=
5
;
int
b
=
a
+
12
;
for
(
int
i
=
0
;
i
<=
10
;
i
++
)
{
c
[
i
]
=
i
;
}
return
0
;
}



7.超大数相乘的两种方法 
//方法一
public static void testMul()  {
		String p1 = "123456789012345678901234123456789012345678901234";// "123456789012345678901234";
		String p2 = "987654321098765432109876543210987654123456789012345678901234";// "987654321098765432109876543210987654";
		int ASCII = 48;
		char[] result = new char[p1.length() + p2.length()];
		for (int i = 0; i < result.length; i++) {
			result[i] = '0';
		}
		char ctemp = ' ';
		char[] pc1 = p1.toCharArray();
		for (int i = 0; i < pc1.length / 2; i++) {	//交换位置，如45689变98654
			ctemp = pc1[i];
			pc1[i] = pc1[pc1.length - 1 - i];
			pc1[pc1.length - 1 - i] = ctemp;
		}
		
		char[] pc2 = p2.toCharArray();
		for (int i = 0; i < pc2.length / 2; i++) {
			ctemp = pc2[i];
			pc2[i] = pc2[pc2.length - 1 - i];
			pc2[pc2.length - 1 - i] = ctemp;
		}
		int temp = 0;// 临时结果
		int step = 0;// 进位
		int time = 0;// 次数
		int bit = 0;// 位数
		for (char c1 : pc1) {	//021
			time = bit;
			for (char c2 : pc2) {	//654
				temp = (c1 - ASCII) * (c2 - ASCII);	//0
				temp = temp + result[time] - ASCII;	//0
				if (temp > 9) {// 进位
					int i = 0;
					do {
						result[time + i] = (char) (temp % 10 + ASCII);
						step = (temp - temp % 10) / 10;
						i++;
						temp = result[time + i] - ASCII + step;
					} while (temp > 9);
					result[time + i] = (char) (temp + ASCII);
				} else {
					result[time] = (char) (temp + ASCII); //result[0] = '0'
				}
				time++;
			}
			bit++;
		}
		System.out.println("##############################");
		System.out.print(p1 + " x " + p2 + " = ");
		for (int i = result.length - 1; i >= 0; i--) {
			System.out.print(result[i]);
		}
		System.out.println();
		System.out.println("##############################");
	}
	
	
	
	//方法二
	public static void bigNumberMulti(){
		String num1 = "123456789012345678901234123456789012345678901234";
		String num2 = "987654321098765432109876543210987654123456789012345678901234";
		
		char[] cp1 = num1.toCharArray();
		char[] cp2 = num2.toCharArray();
		
		char[] result = new char[cp1.length+cp2.length];   //用于存储每位的值
		
		//矩阵存储计算的值
		int sum = cp1.length+cp2.length;	//竖排总数
		char[][] caculate = new char[cp1.length][sum];  
		for(int i=0;i<caculate.length;i++){
			for(int j=0;j<caculate[0].length;j++){
				caculate[i][j] = ' ';
			}
		}
		
		int bit = 0;   //位数
		int level = 0;  //层数
		int temp = 0;  //临时存储的数据
		int ASIIC0 = 48;  //0的asiic码值
		int carry = 0; //进位
		for(int i=cp1.length-1;i>=0;i--){	//9
			bit = sum-1;	
			for(int j=cp2.length-1;j>=0;j--){	//6
				temp = (cp1[i]- ASIIC0) * (cp2[j]-ASIIC0) + carry;
				carry = 0;
				if(temp>9){
					carry = temp / 10;
					temp = temp % 10 ;
				}
				caculate[level][bit--] = (char) (temp + ASIIC0);
			}
			//如果最后一位还有进位
			if(carry>0){
				caculate[level][bit] =  (char)(carry + ASIIC0);
				carry=0;
			}
			sum--;
			level++;
		}
		
		int carry2 = 0;
		for(int y=caculate[0].length-1;y>=0;y--){
			int value = 0;
			for(int x=0;x<caculate.length;x++){
				if(caculate[x][y]>='0' && caculate[x][y]<='9'){
					value += caculate[x][y] - ASIIC0;
				}
			}
			value += carry2;
			carry2 = 0;
			if(value>9){
				carry2 = value / 10;
				value = value % 10;
			}
			result[y] = (char)(value + ASIIC0);
		}
		System.out.println(result);
		
		System.out.println("====================用于显示=======================");
		for(int i=0;i<caculate.length;i++){
			for(int j=0;j<caculate[0].length;j++){
				System.out.print(caculate[i][j]+" ");
			}
			System.out.println();
		}
		for(int i=0;i<caculate[0].length;i++){
			System.out.print("--");
		}
		System.out.println();
		for(char re:result){
			System.out.print(re+" ");
		}
		
	}
分享到：
| 最优二叉树（哈弗曼树）
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics