Java编程题汇总备忘

1.从键盘输入一组数（用，分割），排序后输出

【分析】使用Scanner类获取键盘输入。以下代码都放在main函数中

  System.out.println("请输入一串数字，用，隔开:");
		Scanner scan = new Scanner(System.in);
		String str = scan.nextLine();
		String[] strarr = str.split(",");
		int len = strarr.length;
		int[] num = new int[len];
		for(int i=0;i<len;i++){
			num[i]=Integer.parseInt(strarr[i]);
		}		
		for(int i=0;i<len-1;i++){
			for(int j=i+1;j<len;j++){
				if(num[i]>num[j]){
					int tem  = num[i];
					num[i]=num[j];
					num[j]=tem;
				}
			}
		}
  for(int k : num){
			System.out.print(k+" ");
		}

  方法二：使用ArrayList，纯为了练习

  System.out.println("请输入一串数字，用，隔开:");
		Scanner scan = new Scanner(System.in);
		String str = scan.nextLine();
		ArrayList<Integer> list = new ArrayList<Integer>();
		for(String s : strarr){
			list.add(Integer.parseInt(s));
		}
		int len = list.size();
		for(int i=0;i<len-1;i++){
			for(int j=i+1;j<len;j++){
				if(list.get(i)>list.get(j)){
					int tem = list.get(i);
					list.set(i, list.get(j));
					list.set(j, tem);
				}
			}
		}
		
		for(int k : list){
			System.out.print(k+" ");
		}

 

2. 编程实现：从字符中获取连续数组序列，如字符串"a1dl2iad9j3la5kudp7u9pn4blj8ap5u3e6ml9a"中可以得到的连续数字序列为1234556.【注】：只考虑一位，因此最长的数字序列为：0123456789

 

【方法一】

  String str = "a1dl2iad9j3la5kudp7u9pn4blj8ap5u3e6ml9a";		
		int len = str.length();		
		ArrayList<Integer> array = new ArrayList<Integer>();
		ArrayList<Integer> result = new ArrayList<Integer>();
	
		for(int i = 0;i<len; i++){
			char tem = str.charAt(i);
			if(tem>='0'&&tem<='9'){
				array.add(Integer.parseInt(String.valueOf(tem)));
			}
		}
		int size = array.size();
		int first = array.get(0);
		result.add(first);
		for(int i =1,j=0;i<size;i++){
			
			if(array.get(i)-result.get(j) == 1){
				result.add(array.get(i));
				j++;
			}
		}
		for(int k : result){
			System.out.print(k+" ");
		}

  【方法er】使用正则匹配，纯为练手

  String str = "a1dl2iad9j3la5kudp7u9pn4blj8ap5u3e6ml9a";
//		String[] num = Pattern.compile("[\\D]").split(str,-1); // \d表示数字，\D表示非数字（等价于^0-9）
		String[] num = Pattern.compile("[^0-9]").split(str,-1);
		int k = 0;
		ArrayList<Integer> result = new ArrayList<Integer>();
		for(int i = 0;i<num.length;i++){
			if(num[i]!=null&&!num[i].equals("")){
				result.add(Integer.parseInt(String.valueOf(num[i])));
				k = i;
				break;
			}
		}
		for(int i = k,j=0;i<num.length;i++){
			if(num[i]!=null&&!num[i].equals("")){
				int tem =Integer.parseInt(String.valueOf(num[i]));
				if(tem-result.get(j)==1){
					result.add(tem);
					j++;
				}
			}
			
		}
		for(int n : result){
			System.out.print(n+" ");
		}

 

 

 

 

 

 

 

3.编程实现单链表逆转

 

 

4.用递归方法实现斐波那契数列的前10项之和。

（可参考：http://jerrygao.iteye.com/blog/101283）

 

 

 

5. 500人围成一圈报数，数到3的人出列，下面的人继续从1开始报数，求最后一个出列的人的编号（用数组模拟链表实现）。这实际上是一个约瑟夫出圈问题： n个人围成一个圈，一个个首尾相连的圈报数，从第一个开始报数，报到m的人出圈，剩下的人继续从1开始报数，直到所有人都出圈为止。 两种方法实现，数据和链表。

 

 

 

 

6.

算法程序题：
    该公司笔试题就1个，要求在10分钟内作完。
    题目如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。

 

 

 

 

 

  基本思路：
1 把问题归结为图结构的遍历问题。实际上6个数字就是六个结点，把六个结点连接成无向连通图，对于每一个结点求这个图形的遍历路径，所有结点的遍历路径就是最后对这6个数字的排列组合结果集。
2 显然这个结果集还未达到题目的要求。从以下几个方面考虑：
  1. 3，5不能相连：实际要求这个连通图的结点3，5之间不能连通, 可在构造图结构时就满足改条件，然后再遍历图。
  2. 不能有重复: 考虑到有两个2，明显会存在重复结果，可以把结果集放在TreeSet中过滤重复结果
  3. 4不能在第三位: 仍旧在结果集中去除满足此条件的结果。

 

 

我采用二维数组定义图结构，最后的代码是：

 

 

 

import
 java.util.Iterator;
import
 java.util.TreeSet;
public
 
class
 TestQuestion {
private
 String[] b = 
new
 String[]{
"1"
, 
"2"
, 
"2"
, 
"3"
, 
"4"
, 
"5"
};
private
 
int
 n = b.length;
private
 
boolean
[] visited = 
new
 
boolean
[n];
visited =falsh;
private
 
int
[][] a = 
new
 
int
[n][n];
private
 String result = 
""
;
private
 TreeSet TreeSet = 
new
 TreeSet();
public
 
static
 
void
 main(String[] args) {
new
 TestQuestion().start();
}
private
 
void
 start() {
for
 (
int
 i = 
0
; i < n; i++) {
for
 (
int
 j = 
0
; j < n; j++) {
if
 (i == j) {
a[i][j] = 0
;
} else
 {
    a[i][j] = 1
;
}
}
}a[3
][
5
] = 
0
;
a[5
][
3
] = 
0
;
for
 (
int
 i = 
0
; i < n; i++) {
    this
.depthFirstSearch(i);
}
Iterator it = set.iterator();
while
 (it.hasNext()) {
String string = (String) it.next();

if
 (string.indexOf(
"4"
) != 
2
) {
System.out.println(string);
}
}
}
private
 
void
 depthFirstSearch(
int
 startIndex) {
visited[startIndex] = true
;
result = result + b[startIndex];
if
 (result.length() == n) {
TreeSet .add(result);
}
for
(
int
 j = 
0
; j < n; j++) {
if
 (a[startIndex][j] == 
1
 && visited[j] == 
false
) {
depthFirstSearch(j);
} else
 {
continue
;
}
}
    result = result.substring(0
, result.length() -
1
);
    visited[startIndex] = false
;
}
}

import java.util.Iterator;
import java.util.TreeSet;
public class TestQuestion {
private String[] b = new String[]{"1", "2", "2", "3", "4", "5"};
private int n = b.length;
private boolean[] visited = new boolean[n];
visited =falsh;
private int[][] a = new int[n][n];
private String result = "";
private TreeSet TreeSet = new TreeSet();
public static void main(String[] args) {
new TestQuestion().start();
}
private void start() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
a[i][j] = 0;
} else {
    a[i][j] = 1;
}
}
}a[3][5] = 0;
a[5][3] = 0;
for (int i = 0; i < n; i++) {
    this.depthFirstSearch(i);
}
Iterator it = set.iterator();
while (it.hasNext()) {
String string = (String) it.next();

if (string.indexOf("4") != 2) {
System.out.println(string);
}
}
}
private void depthFirstSearch(int startIndex) {
visited[startIndex] = true;
result = result + b[startIndex];
if (result.length() == n) {
TreeSet .add(result);
}
for(int j = 0; j < n; j++) {
if (a[startIndex][j] == 1 && visited[j] == false) {
depthFirstSearch(j);
} else {
continue;
}
}
    result = result.substring(0, result.length() -1);
    visited[startIndex] = false;
}
}