Java编程题.doc

Java编程篇
1. 将一个十进制数（byte类型）转化二进制数，将二进制数前后颠倒，再算出颠倒后其对应的十进制数。
public class MyByte{
private byte b;
private int a[] = {0,0,0,0,0,0,0,0};

public MyByte(byte b){
this.b = b;
}

public void tenToSecond(){
int i=0;
do{
a[i] = b%2;
b = (byte) (b/2);
i++;
}while(b != 0);
}

public byte toTen(){
int temp[] = {0,0,0,0,0,0,0,0},j=0;
for(int i=7;i>=0;i--){
temp[j]=a[i];
j++;
}
for(int i=0;i<8;i++){
b+=temp[i]*2;
}
return b;
}

public static void main(String[] args){
MyByte mb = new MyByte((byte) 7);
mb.tenToSecond();
System.out.println("转化后的字符："+mb.toTen());
}
}

2.实现简易字符串压缩算法：一个长度最大为128的字符串，由字母a-z或者A-Z组成，将其中连续出现2次以上（含2次）的字母转换为出现次数加字母，以达到压缩目的。
import java.util.*;

public class ThreadTestA {
void stringZip(char inputStr[], int len, char outputStr[]) {
int k = 0;
for (int i = 0; i < len; i++) {
int j = i + 1, n = 1;
while (j < len) { // 选取i的字符比较i后面的
if (inputStr[i] != inputStr[j]) { //若i与j不等，i向后移一位
if (n > 1) {
outputStr[k++] = (n + "").charAt(0);//数字转化成对应的数字字符
}
outputStr[k++] = inputStr[i];
break;
} else { //若i与j相等，j向后移一位，再判断
j++;
n++;
}
i = j - 1;
}
if (j == len && n == 1)
outputStr[k] = inputStr[i];
if (j == len && n > 1) {
outputStr[k++] = (n + "").charAt(0);
outputStr[k] = inputStr[i];
}
}

for (int j = 0; j <= k; j++) {
System.out.print(outputStr[j]);
}
}

public static void main(String[] agrs) {
Scanner cin = new Scanner(System.in);
String str;
while (cin.hasNext()) {
str = cin.next();
ThreadTestA t = new ThreadTestA();
int len = str.length();
char outputStr[] = new char[len];
t.stringZip(str.toCharArray(), len, outputStr);
}
}
}
3. 用java写一个字符串匹配“{”，“}”。用栈结构
//StringMatch.java
import java.util.Stack;
public class StringMatch {
private String str;

public StringMatch(String str) {
this.str=str;
}

public boolean match(){
Stack<Character> st = new Stack<Character>();
char ch[] = str.toCharArray();
int n = str.length(),flag=0;
for(int i=0;i<n;i++){
st.push(ch[i]);
}
//出栈时记录flag的变化，如果第一次出现 }，输入的串有误。若flag>0 ，flag<0都不匹配。
for(int i=0;i<n;i++){
char tempch = st.pop();
if(tempch == '}'){
flag++;
}else if(tempch == '{'){
flag--;
}

if(tempch == '{' && flag == 1){
System.out.println("输入格式有误，‘}’不能首次出现！");
return false;
}
}

if(flag==0){
return true;
}
return false;
}
}

//Test.java
public class Test {
public static void main(String[] args){
String str = "}{2*{1+3}/{3*{1+1}-3}";
StringMatch sm = new StringMatch(str);
if(sm.match()){
System.out.println("'{'和'}'匹配！");
}else{
System.out.println("'{'和'}'不匹配！");
}
}
}

4.将16进制字符串转化成10进制整数输出。例如输入0x15a，输出：346。
public class Test {
int invsert(String str){
int temp=0;
char a[] = str.toCharArray();
int m = a.length;
int[] b = new int[m-2];
/**
* 将字符数组转化成整型数组
*/
for(int i=2,j=0; i<m;i++,j++){
if(a[i]>='0' && a[i] <='9'){
b[j] = a[i]-'0'; //将数字字符变成数字
}
else if(a[i]>='a' && a[i]<='e'){
b[j]=10+97-a[i]; //将字母字符变成数字
}
}

for(int i = m-2-1,n=0;i>=0;i--){
temp += b[i]*((int)Math.pow(16, n));
n++;
}
return temp;

}
public static void main(String[] args){
Test t = new Test();
String str ="0x15a";
System.out.println(t.invsert(str));
}
}
5. 函数void CleanString（char *str）的功能是删除字符串str中的所有数字字符和非字母字符，并将字符串压缩。要求：不使用c库，不开辟新空间，复杂度好。
public class Test {
void CleanString(String str){
char ch[] = str.toCharArray();
int n = str.length(),m=0;
/*索引i和j，当j对应的是字母时先判断ch[i]！=ch[j]，再i++，最后将j赋值给i.....
* 特殊情况：i=0不是是字母时就要把j第一次的字母赋值给ch[0]
*/
for(int j=0,i=0;j<n;j++){
if((ch[j]>='a' && ch[j]<='z') || (ch[j]>='A' && ch[j]<='Z')){
if(i==0 && !(ch[0]>='a' && ch[0]<='z') || (ch[0]>='A' && ch[0]<='Z')){
ch[0] = ch[j];
}
if(ch[i] != ch[j]){
i++;
ch[i] = ch[j];
}
}
m=i+1;
}

for(int j=0;j<m;j++){
System.out.print(ch[j]);
}

}

public static void main(String[] args){
Test t = new Test();
String str1 ="0xxabb00"; //xab
String str2 ="xx00ab0bb";//xab
t.CleanString(str1);
System.out.println("");
t.CleanString(str2);
}
}
6. .已知一个整数数组A[n]，写出算法实现将奇数元素放在数组的左边，将偶数放在数组的右边。要求时间复杂度为O(n)。
void sort(int a[], int n){
int i=0,j=n-1;
while(i != j){
while(a[i]%2 ==1){
i++;
}
while(a[j]%2 ==0){
j--;
}
if(i<j){
swap(a[i],a[j]);
}
}
}

7. 创建两个线程，每个线程打印出线程名字后再睡眠，每个线程前后共睡眠5次，最后打印睡眠结束信息。使用2种方法：Thread 和 Runnable 。
方法一：Thread
public class BB extends Thread {
int time;
public BB(int time) {
super();
this.time = time;
}

public void run() {
for (int i = 1; i <= 5; i++) {
try {
synchronized (this) {
System.out.println(Thread.currentThread().getName() + "第"
+ i + "进入睡眠");
notify();
sleep(time);
wait();
if (i == 5){
System.out.println(Thread.currentThread().getName()
+ "睡觉结束");
notify();}
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
//Test.java
public class Test {
public static void main(String[] args) {
BB c = new BB(50);
Thread t1 = new Thread(c);
t1.start();
Thread t2 = new Thread(c);
t2.start();
}
}
方法二：Runnable 接口：同步代码一样
8. 两个线程交替打印。例如第一个线程打印1，接着第二个线程打印100，接着第一个线程打印2。
public class Test {

public static void main(String[] args) {
CC c = new CC(1);
Thread t1 = new Thread(c, "线程1");
t1.start();
Thread t2 = new Thread(c, "线程2");
t2.start();

}
}

// CC.java
public class CC extends Thread {
public CC(int num) {
super();
this.num = num;
}

private int num;

public void run() {
for (int i = 1; i <= 5; i++) {
try {
synchronized (this) {
notify();
if( "线程1".equals(Thread.currentThread().getName())){
System.out.println(Thread.currentThread().getName()+":"+num);
num--;
}else{
System.out.println(Thread.currentThread().getName()+":"+(num+100));
}
num++;
wait();
// if(i == 5 ) notifyAll();
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}

9. 设计4个线程，其中2个对j进行加1，其中2个对j进行减1。
public class ThreadTestA {
private int j;
public synchronized void decValue() {
for (int i = 0; i < 5; i++) {
j--;
System.out.println(Thread.currentThread().getName() + "-dec:" + j);
}
}

public synchronized void incValue() {
for (int i = 0; i < 5; i++) {
j++;
System.out.println(Thread.currentThread().getName() + "-inc:" + j);
}
}

class IncOfJ extends Thread {
public IncOfJ(String name) {
super(name);
}

public void run() {
incValue();
}
}

class DecOfJ extends Thread {
public DecOfJ(String name) {
super(name);
}

public void run() {
decValue();
}
}

public static void main(String[] agrs) {
ThreadTestA tt = new ThreadTestA();
IncOfJ inc = tt.new IncOfJ("自增线程1");
inc.start();
IncOfJ inc1 = tt.new IncOfJ("自增线程2");
inc1.start();
DecOfJ dec = tt.new DecOfJ("自减线程3");
dec.start();
DecOfJ dec1 = tt.new DecOfJ("自减线程4");
dec1.start();
}
}

10.华为机试题（java）
描述:
输入一串数字，找到其中包含的最大递增数。递增数是指相邻的数位从小到大排列的数字。如： 2895345323，递增数有：289，345，23, 那么最大的递增数为345。
运行时间限制:
无限制
内存限制:
无限制
输入:
输入一串数字，默认这串数字是正确的，即里面不含有字符/空格等情况
输出:
输出最大递增数
样例输入:
123526897215
样例输出:
2689
import java.util.*;

public class Main {
public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
String str = "";
while(cin.hasNext()){
str = cin.next();
char[] ch = str.toCharArray();
int n = ch.length,max = 0;
List<StringBuffer> list = new ArrayList<StringBuffer>();
StringBuffer sb = new StringBuffer();

for(int i=0; i< n-1; i++){

if(ch[i]<ch[i+1]){
sb.append(ch[i]);
}else{
sb.append(ch[i]);
list.add(sb);
sb = new StringBuffer();
}

if(i == n-2 && ch[i]<ch[i+1]){
sb.append(ch[n-1]);
list.add(sb);
}
}

max =Integer.parseInt(list.get(0).toString());
for(int k=1;k<list.size();k++){
int m =Integer.parseInt(list.get(k).toString());
if(max < m){
max = m;
}
}
System.out.println(max);
}
}
}
11. 通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串过滤程序，若字符串中出现多个相同的字符，将非首次出现的字符过滤掉。
比如字符串“abacacde”过滤结果为“abcde”。
要求实现函数： 
void stringFilter(const char *pInputStr, long lInputLen, char *pOutputStr);

【输入】 pInputStr：  输入字符串
         lInputLen：  输入字符串长度         
【输出】 pOutputStr： 输出字符串，空间已经开辟好，与输入字符串等长；

【注意】只需要完成该函数功能算法，中间不需要有任何IO的输入输出

示例 
输入：“deefd”        输出：“def”
输入：“afafafaf”     输出：“af”
输入：“pppppppp”     输出：“p”
import java.util.*;

public class Main {
void stringFilter(char inputStr[], int len, char outputStr[]) {
outputStr[0] = inputStr[0];
int n = 1;
for (int i = 1; i < len; i++) {
int j = 0;
for (; j < n; j++) {
if (inputStr[i] == outputStr[j]) {
break;
}
}
if (j == n) {
outputStr[n++] = inputStr[i];
}

}

for (int j = 0; j < n; j++) {
System.out.print(outputStr[j]);
}
}

public static void main(String[] agrs) {
Scanner cin = new Scanner(System.in);
String str;
while (cin.hasNext()) {
str = cin.next();
Main t = new Main();
int len = str.length();
char outputStr[] = new char[len];
t.stringFilter(str.toCharArray(), len, outputStr);
}
}

12. 通过键盘输入100以内正整数的加、减运算式，请编写一个程序输出运算结果字符串。
输入字符串的格式为：“操作数1 运算符 操作数2”，“操作数”与“运算符”之间以一个空格隔开。

补充说明：
1. 操作数为正整数，不需要考虑计算结果溢出的情况。
2. 若输入算式格式错误，输出结果为“0”。

要求实现函数： 
void arithmetic(const char *pInputStr, long lInputLen, char *pOutputStr);

【输入】 pInputStr：  输入字符串
         lInputLen：  输入字符串长度         
【输出】 pOutputStr： 输出字符串，空间已经开辟好，与输入字符串等长；

【注意】只需要完成该函数功能算法，中间不需要有任何IO的输入输出
示例 
输入：“4 + 7”  输出：“11”
输入：“4 - 7”  输出：“-3”
输入：“9 ++ 7”  输出：“0” 注：格式错误
public class Main {
private static void arithmetic(char[] inputStr, long length,
char[] outputStr) {
int num1 = 0;
int num2 = 0;
boolean first = true; //true是第一个数字，false是第二个数字
boolean oper = false; //false是减 ， true是加操作
boolean zero = false; //false表示输入格式正确，true表示格式有误
int once = 0; //=0表达式中操作符还没有，=1说明已经有一个操作符

for (int i = 0; i < length; i++) {
if (inputStr[i] == ' ') {
continue;
}
if (inputStr[i] >= '0' && inputStr[i] <= '9') {
if (first) {
num1 = num1 * 10 + (inputStr[i] - '0');

} else {
num2 = num2 * 10 + (inputStr[i] - '0');
}
} else {

if (once == 0) {
if (inputStr[i] == '-') {
oper = false;
} else {
oper = true;
}
once = 1;
first = false;
} else {
zero = true;
break;
}
}
}

if (zero) { // 输出：“0”,格式错误
outputStr[0] = '0';
} else {
int sum = 0;
if (oper) {
sum = num1 + num2;
} else {
sum = num1 - num2;
}

int i = 0;
if (sum < 0) {
outputStr[i++] = '-';
sum = 0 - sum;
}

if (sum >= 0 && sum <= 9) {
outputStr[i++] = (char) (sum + '0');
} else if (sum > 9 && sum <= 99) {
int tmp = sum / 10;
outputStr[i++] = (char) (tmp + '0');
sum = sum % 10;
outputStr[i++] = (char) (sum + '0');
} else if (sum > 99) {
int tmp = sum / 100;
outputStr[i++] = (char) (tmp + '0');
sum = sum % 100;
tmp = sum / 10;
outputStr[i++] = (char) (tmp + '0');
sum = sum % 10;
outputStr[i++] = (char) (sum + '0');
}

}
}

public static void main(String[] args) {
char[] inputStr = new char[] { '6', ' ', '-', ' ', '8' };
long n = inputStr.length;
char[] outputStr = new char[(int) n];
arithmetic(inputStr, n, outputStr);
for (int i = 0; i < outputStr.length; i++) {
System.out.print(outputStr[i]);
}
}
}
13.
Word Maze 是一个网络小游戏，你需要找到以字母标注的食物，但要求以给定单词字母的顺序吃掉。如上图，假设给定单词if，你必须先吃掉i然后才能吃掉f。

    但现在你的任务可没有这么简单，你现在处于一个迷宫Maze（n×m的矩阵）当中，里面到处都是以字母标注的食物，但你只能吃掉能连成给定单词W的食物。

如下图，指定W为“SOLO”，则在地图中红色标注了单词“SOLO”。 

注意区分英文字母大小写,你只能上下左右行走。
运行时间限制:
无限制
内存限制:
无限制
输入:
输入第一行包含两个整数n、m(0<n, m<21)分别表示n行m列的矩阵，第二行是长度不超过100的单词W，从第3行到底n+3行是只包含大小写英文字母的长度为m的字符串。
输出:
如果能在地图中连成给定的单词，则输出“YES”，否则输出“NO”。注意：每个字母只能用一次。
样例输入:
5 5
SOLO
CPUCY
EKLQH
CRSOL
EKLQO
PGRBC
样例输出:
YES
解题思路：
先找第一个字母。。。。（找到一个符合的时，定义个数组接收此时的查询位置）再找它的上下左右（注意别越界），看看是否跟第二个字母相同（有相同的继续往里加）。。。。。再找第三个字母的上下左右（注意排除已经记录入的数据）。。。。。。再找第四个。。。

import java.util.ArrayList;
import java.util.List;

public class Main {
public static void main(String args[]) {
char[] keys = "SOLO".toCharArray();
char[] tr0 = "CPUCY".toCharArray();
char[] tr1 = "EKLQH".toCharArray();
char[] tr2 = "CRSOL".toCharArray();
char[] tr3 = "EKLQO".toCharArray();
char[] tr4 = "PGRBC".toCharArray();
System.out.println(sf(new char[][] { tr0, tr1, tr2, tr3, tr4 }, keys));
}

private static String sf(char[][] map, char[] key) {
String temp = "NO";
for (int y = 0; y < map.length; y++) {
for (int x = 0; x < map[y].length; x++) {
if (key[0] == map[y][x]) {
// 如果找到第一个相同,则进行查找
if (dg(map, key, x, y)) {
temp = "Yes";
}
}
}
}
return temp;

}

//递归初始化
private static boolean dg(char[][] map, char[] key, int sx, int sy) {
List<Point> Points = new ArrayList<Point>();
return dg(map, key, sx, sy, 0, Points);
}

//递归查找
static boolean dg(char[][] map, char[] key, int px, int py, int np, List<Point> Points) {
if (np + 1 == key.length) return true;
Points.add(new Point(px, py));

//不越界,数相符,不是已存在的点
//上
if (py - 1 >= 0 && map[py - 1][px] == key[np + 1] && !exists(Points, px, py - 1)) {
return dg(map, key, px, py - 1, np + 1, new ArrayList<Point>(Points));
}
//下
if (py + 1 < map.length && map[py + 1][px] == key[np + 1] && !exists(Points, px, py + 1)) {
return dg(map, key, px, py + 1, np + 1, new ArrayList<Point>(Points));
}
//左
if (px - 1 >= 0 && map[py][px - 1] == key[np + 1] && !exists(Points, px - 1, py)) {
return dg(map, key, px - 1, py, np + 1, new ArrayList<Point>(Points));
}
//右
if (px + 1 < map[0].length && map[py][px + 1] == key[np + 1] && !exists(Points, px + 1, py)) {
return dg(map, key, px + 1, py, np + 1, Points);
}
//没有找到符合的则返回false
return false;
}

//查找数组中是否存在x,y这个位置
static Boolean exists(List<Point> list, int x, int y) {
for(Point p : list){
if (p.Equals(x, y)) {
return true;
}
}
return false;
}
}

class