13 道典型 Java 面试算法题及解答_java算法题库及答案解析

1. 人民币金额转换，阿拉伯数字的金额转换成中国传统的形式如：（￥1011）－>（一千零一拾一元整）输出
2. 判断身份证：要么是15位，要么是18位，最后一位可以为字母，并写程序提出其中的年月日。
3. 编写一个截取字符串的函数，输入为一个字符串和字节数，输出为按字节截取的字符串，但要保证汉字不被截取半个，如“我ABC”，4，应该截取“我AB”，输入“我ABC汉DEF”，6，应该输出“我ABC”，而不是“我ABC+汉的半个”。
4. 给定一个四句古诗，程序实现从每一句中随机挖去一个字，并顺序打乱生成四个选项。从而随机生成一个填字题目。
5. 统计一篇英文文章中单词个数
6. 给定任意长度的字符串，字符串中可以有任意顺序和任意个数的任意字符。要求去除重复只留下唯一的字符并升序排序。比如：aabbxxcaaccyyxxxyydddd 输出结果为：abcdxy
7. 全排列：给出五个数字 12345 的所有排列
8. 回文素数：所谓回文数就是顺着读和倒着读一样的数(例如：11，121，1991…)，回文素数就是既是回文数又是素数(只能被 1 和自身整除的数)的数。编程找出11～9999 之间的回文素数。
9. 给一个任意的字符串，如果统计出每个字符出现的次数？
10. 有一串无序的任意序列字符串，包含了一些特殊字符，现在需要去除特殊字符，只留下数字字母下划线。
11. 写一个算法判断一个英文单词的所有字母是否全都不同（不区分大小写）
12. 一个有 n 级的台阶，一次可以走 1 级、2 级或 3 级，问走完 n 级台阶有多少种走法。
13. 编写一个程序，统计文本文件中内容的总行数？

人民币转换

1. 人民币金额转换，阿拉伯数字的金额转换成中国传统的形式如：（￥1011）－>（一千零一拾一元整）输出。

思路：

人民币从阿拉伯数字转为大写中文，这就需要首先解决 0~9 到 壹~玖之间的映射。

这种映射，可以通过数组来解决即可。

而还有要考虑的问题是，元拾佰仟的转换问题。这个可以结合数组及位数来实现。每多一位则从数组中依次往后取出单位拼接到结果字符串中。

package test;

public class RenMingBi {

	private static final char[] data = new char[]{	'零','壹','贰','叁','肆','伍','陆','柒','捌','玖'	}; 
	private static final char[] units = new char[]{	'元','拾','佰','仟','万','拾','佰','仟','亿'};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(
				convert(100000003));
	}

	public static String convert(int money)
	{
		StringBuffer sbf = new StringBuffer();
		int unit = 0;
		while(money!=0)
		{
			sbf.insert(0,units[unit++]);
			int number = money%10;
			sbf.insert(0, data[number]);
			money /= 10;
		}

		return sbf.toString().replaceAll("零[拾佰仟]","零").replaceAll("零+万","万").replaceAll("零+元","元").replaceAll("零+","零");
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

字符串、正则表达式等其他问题

2. 判断身份证：要么是15位，要么是18位，最后一位可以为字母，并写程序提出其中的年月日。

思路：

首先需要了解正则表达式，\d 表示数字。{n,m}表示字符个数。

可以使用正则表达式从第6位之后开始截取 8 位即可取出年月日。

package com.demo2;

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class RegexTest {

	public static void main(String[] args) {

		// 测试是否为合法的身份证号码
		String[] strs = { "130681198712092019", "13068119871209201x", "13068119871209201", "123456789012345",
				"12345678901234x", "1234567890123" };
		Pattern p1 = Pattern.compile("(\\d{17}[0-9a-zA-Z]|\\d{14}[0-9a-zA-Z])");
		for (int i = 0; i < strs.length; i++) {
			Matcher matcher = p1.matcher(strs[i]);
			System.out.println(strs[i] + ":" + matcher.matches());
		}

		Pattern p2 = Pattern.compile("\\d{6}(\\d{8}).*"); // 用于提取出生日字符串
		Pattern p3 = Pattern.compile("(\\d{4})(\\d{2})(\\d{2})");// 用于将生日字符串进行分解为年月日
		for (int i = 0; i < strs.length; i++) {
			Matcher matcher = p2.matcher(strs[i]);
			boolean b = matcher.find();
			if (b) {
				String s = matcher.group(1);
				Matcher matcher2 = p3.matcher(s);
				if (matcher2.find()) {
					System.out.println(
							"生日为" + matcher2.group(1) + "年" + matcher2.group(2) + "月" + matcher2.group(3) + "日");
				}
			}

		}

	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

3. 编写一个截取字符串的函数，输入为一个字符串和字节数，输出为按字节截取的字符串，但要保证汉字不被截取半个，如“我ABC”，4，应该截取“我AB”，输入“我ABC汉DEF”，6，应该输出“我ABC”，而不是“我ABC+汉的半个”。

思路：

本题首先要注意一个字符中，汉字是张勇两个字节的。字母和数字为一个字节。而且如果我们把字符串转为byte数组时，会发现中文其实是两个负数来表示的。所以在做截取时，只要注意碰到负数则表示到汉字了。对于负数也必须得偶数个负数才能为一个完整的汉字。

public static void main(String[] args) throws Exception{
		String str = "我a爱中华abc我爱我的祖国def';
		String str = "我ABC汉";
		int num = trimGBK(str.getBytes("GBK"),5);
		System.out.println(str.substring(0,num) );
	}
	
	public static int  trimGBK(byte[] buf,int n){
		int num = 0;
		boolean bChineseFirstHalf = false;
		for(int i=0;i<n;i++)
		{
			if(buf[i]<0 && !bChineseFirstHalf){
				bChineseFirstHalf = true;
			}else{
				num++;
				bChineseFirstHalf = false;				
			}
		}
		return num;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4. 问题：给定一个四句古诗，程序实现从每一句中随机挖去一个字，并顺序打乱生成四个选项。从而随机生成一个填字题目。

思路：

本题主要考查对字符串的掌握。可以根据每句古诗的长度来生成一个随机数，作为要挖去的字符。并保存到变量数组中。以便作为题目选项。然后把数组的保存的字符随机打乱，作为选项。

package com;
import java.util.Random;
import java.util.Scanner;

/**
 * 问题：
 * 给定一个四句古诗，程序实现从每一句中随机挖去一个字，并顺序打乱生成四个选项。从而随机生成一个填字题目。
 *
 */
public class 填字游戏2 {

	public static void main(String[] args) {
		String content = "白日依山尽,黄河入海流,欲穷千里目,更上一层楼";
		String[] poems = content.split(",");//题目
		String[] options = new String[4];
		
		char[] answerChar = new char[4];;
		
		Random random = new Random();
		//挖去一个字
		for (int i = 0; i < poems.length; i++) {
			char ch = poems[i].charAt(random.nextInt(4));//
			poems[i] = poems[i].replace(ch, '?');//挖去的字替换成问号
			answerChar[i] =  ch; //挖去的为答案 保留起来
		}
		
		//生成正确选项 放入选项数组随机位置
		int rightPos = random.nextInt(4);
		options[rightPos] = new String(answerChar);
		
		for (int i = 0; i < options.length; i++) {
			if(i==rightPos){
				continue;
			}
			
			int s = random.nextInt(4);
			int e = random.nextInt(4);
			char temp = answerChar[s];
			answerChar[s] = answerChar[e];
			answerChar[e] = temp;
			
			boolean isRepeat = false;
			String opStr = new String(answerChar);
			//是否和已有的选项重复（已有中包含了正确的选项）
			for (int j = 0; j <options.length; j++) {
//				System.out.println(options[j]+"="+i+"="+opStr);
				if(options[j]!=null && options[j].equals(opStr)){
					isRepeat = true;
					break;
				}
			}
			if(isRepeat){
				i--;//条件变量减一 这样下次循环的i++等于没变化
//				System.out.println("===重复了：==="+Arrays.toString(options));
				continue;
			}
			options[i] = opStr;	//如果没有重复，则次		
		}

		
		System.out.println("题目如下：\n");
		//打印题目
		for (int i = 0; i < poems.length; i++) {
			System.out.println(poems[i]);
		}
		System.out.println("\n请从下面选项中选出正确答案：");
		for (int i = 0; i < options.length; i++) {
			System.out.print((char)('A'+i)+":");
			System.out.print(options[i].charAt(0)+",");
			System.out.print(options[i].charAt(1)+",");
			System.out.print(options[i].charAt(2)+",");
			System.out.println(options[i].charAt(3));
		}
		System.out.println("您选择的答案是：");
		Scanner sc = new Scanner(System.in);
		char input = sc.next().charAt(0);
		if ((input-'A')==rightPos) {
			System.out.println("恭喜您答对了！");
		} else {
			System.out.println("对不起，答错了！");
			System.out.println("正确答案是"  + (char)('A' + rightPos));
		}
		
		sc.close();
		
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

5. 统计一篇英文文章中单词个数。

思路：

本题主要是用到 IO 的字符流来读取字符文件，并根据空格，换行，制表符等进行判断单词存在的数量。

读取字符逐一分析间隔符号，然后统计结果。

import java.io.FileReader; 
public class WordCounting { 
 public static void main(String[] args) { 
 try(FileReader fr = new FileReader("a.txt")) { 
 int counter = 0; 
 boolean state = false; 
 int currentChar; 
 while((currentChar= fr.read()) != -1) { 
 if(currentChar== ' ' || currentChar == '\n' 
 || currentChar == '\t' || currentChar == '\r') { 
 state = false; 
 } 
 else if(!state) { 
 state = true; 
 counter++; 
 } 
 } 
 System.out.println(counter); 
 } 
 catch(Exceptione) { 
 e.printStackTrace(); 
 } 
 } 
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

6. 给定任意长度的字符串，字符串中可以有任意顺序和任意个数的任意字符。要求去除重复只留下唯一的字符并升序排序。比如：aabbxxcaaccyyxxxyydddd 输出结果为：abcdxy

思路：

本题关键点是两个词 ：唯一 和 排序 自然要想到 TreeSet。

所以我们把所有字符放入TreeSet 则可以自动去除重复及排序了。然后再取出来组合起来就好

package com.wdzl.demo;

import java.util.TreeSet;

public class Test {

	public static void main(String[] args) {
		String str = "aabbxxcaaccyyxxxyydddd";
		TreeSet<Character> ts = new TreeSet<>();
		for (int i = 0; i < str.length(); i++) {
			ts.add(str.charAt(i));
		}
		str = "";
		for (Character character : ts) {
			str += character;
		}
		System.out.println(str);
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

7. 全排列：给出五个数字 12345 的所有排列。

思路：

本题主要使用分区，分别递归处理

public class FullPermutation { 
 public static void perm(int[] list) { 
 	perm(list,0); 
 } 
 private static void perm(int[] list, int k) { 
 	if (k == list.length) { 
 		for (int i = 0; i < list.length; i++) { 
 			System.out.print(list[i]); 
 		} 
 		System.out.println(); 
 	}else{ 
 		for (int i = k; i < list.length; i++) { 
 			swap(list, k, i); 
 			perm(list, k + 1); 
 			swap(list, k, i); 
 		} 
 	} 
 } 
 private static void swap(int[] list, int pos1, int pos2) { 
 	int temp = list[pos1]; 
 	list[pos1] = list[pos2]; 
 	list[pos2] = temp; 
 } 
 public static void main(String[] args) { 
 	int[] x = {1, 2, 3, 4, 5}; 
 	perm(x); 
 } 
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

8. 回文素数：所谓回文数就是顺着读和倒着读一样的数(例如：11，121，1991…)，回文素数就是既是回文数又是素数(只能被 1 和自身整除的数)的数。编程找出11～9999 之间的回文素数。

思路：

本题主要有两个关键点：判断是否为素数。判断是否为回文。

素数判断可以单独方法来完成，整除从 2~本身-1， 如果全部除不尽，则为素数

回文数也是定义一个方法，分别取出首尾两个数，比较是否相等即可

public class PalindromicPrimeNumber {
        public static void main(String[] args) {
            for(int i = 11; i <= 9999; i++) {
                if(isPrime(i) && isPalindromic(i)) {
                    System.out.println(i);
                }
            }
        }

        public static boolean isPrime(int n) {
            for(int i = 2; i <= Math.sqrt(n); i++) {
                if(n % i == 0) {
                    return false;
                }
            }
            return true;
        }
        public static boolean isPalindromic(int n) {
            int temp = n;
            int sum = 0;
            while(temp > 0) {
                sum= sum * 10 + temp % 10;
                temp/= 10;
            }
            return sum == n;
        }
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

9. 给一个任意的字符串，如果统计出每个字符出现的次数？

例如：aabbxxcaaccyyxxxyydddd，统计出结果为：{a=4, b=2, c=3, d=4, x=5, y=4}

思路：

本题只需要逐一取出每个字符，放入Map，Map是键值对结构。在放入时，我们先判断是否已经放过了，如果没有放过则初始为1。如果存在，则取出加一，在放回。

package com.wdzl.demo;

import java.util.HashMap;
import java.util.TreeSet;

public class Test {

	public static void main(String[] args) {
		String str = "aabbxxcaaccyyxxxyydddd";
		HashMap<Character, Integer> s = new HashMap<>();
		for (int i = 0; i < str.length(); i++) {
			Character c = str.charAt(i);
			Integer count = s.get(c);
			if(count==null){
				count = 0;
			}
			count++;
			s.put(c, count);
		}
		System.out.println(s);
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

10. 有一串无序的任意序列字符串，包含了一些特殊字符，现在需要去除特殊字符，只留下数字字母下划线。

例如：”aabb23xx&caaccy#yxx@xyyd5_d4dd“ 处理后需要留下结果为：”aabb23xxcaaccyyxxxyyd5_d4dd“

思路：

如果使用循环判断字符类型也可以处理，但是太麻烦，所以使用正则表达式会很方便。

‘\W’ 在正则表达式中代表的是非数字字母下划线的字符。这样可以使用此表达式替换成空字符。

public class Test {

	public static void main(String[] args) {
		String str = "aabb23xx&caaccy#yxx@xyyd5_d4dd";
		str = str.replaceAll("[\\W]", "");
		System.out.println(str);
	}

}
1
2
3
4
5
6
7
8
9

11. 写一个算法判断一个英文单词的所有字母是否全都不同（不区分大小写）

思路：

循环逐一取出每个字母，并放入数组中，如果后面取出的字符在数组中存在则直接为假。

如果整个循环结束后，还是没有重复的在数组中。则认为是没有重复的。

public class AllNotTheSame {
    public static boolean judge(String str) {
        String temp = str.toLowerCase();
        int[] letterCounter = new int[26];
        for(int i = 0; i <temp.length(); i++) {
            int index = temp.charAt(i)- 'a';
            letterCounter[index]++;
            if(letterCounter[index] > 1) {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        System.out.println(judge("hello"));
        System.out.print(judge("smile"));
    }
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

12. 一个有 n 级的台阶，一次可以走 1 级、2 级或 3 级，问走完 n 级台阶有多少种走法。

思路：

本题使用递归可以很方便求出结果。台阶级数任意，但是走法只有三种，所以每次递归计算三种执行次数就可得出结果。

//可以通过递归求解。
public class GoSteps { 
 public static int countWays(int n) { 
 if(n < 0) { 
 return 0; 
 } 
 else if(n == 0) { 
 return 1; 
 } 
 else { 
 return countWays(n - 1) + countWays(n - 2) + countWays(n -3); 
 } 
 } 
 public static void main(String[] args) { 
 System.out.println(countWays(5)); // 13 
 } 
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

13. 编写一个程序，统计文本文件中内容的总行数？

思路：

这是一个 IO 流问题，而且是一个字符流，读取行数，BufferedReader 可以一次读取一行，所以直接使用这个流循环读取到文件末尾就可计算出总行数

package com.wdzl.demo;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

public class Test {

	public static void main(String[] args) {
		try {
			FileReader fw = new FileReader("ResizeImage.java");
			BufferedReader br = new BufferedReader(fw);
			int count = 0;
         	//一次读取一行
			while(br.readLine()!=null){
				count++;
			}
			System.out.println("总行数："+count);
			br.close();
			fw.close();
		} catch (IOException e) {
			
			e.printStackTrace();
		}
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29