所有分类
  • 所有分类
  • 未分类

Java笔试题编程题大全(有详细答案)

简介

本文介绍Java常见的笔试题中的编程题。 

排序

冒泡排序写法

见:排序算法–Java实例/原理 – 自学精灵

合并n个有序集合

方案:外排

将n个有序数集合并成一个新的有序集合,外排方式,时间复杂度list1.size()+…+listn.size()

import java.util.*;

public class Main {

	public static void main(String[] args) {
		
		List<List<Integer>> lists = new ArrayList<>();

		List<Integer> list1 = new ArrayList<>();
		list1.add(1);
		list1.add(2);
		list1.add(4);
		list1.add(8);
		List<Integer> list2 = new ArrayList<>();
		list2.add(1);
		list2.add(3);
		list2.add(5);
		list2.add(7);
		List<Integer> list3 = new ArrayList<>();
		list3.add(1);
		list3.add(6);
		list3.add(25);
		list3.add(56);
		List<Integer> list4 = new ArrayList<>();
		list4.add(9);
		list4.add(16);
		list4.add(25);
		list4.add(37);


		lists.add(list1);
		lists.add(list2);
		lists.add(list3);
		lists.add(list4);

		mergeNSort(lists);
	}


	public static void mergeNSort(List<List<Integer>> lists) {
		List<Integer> result = lists.get(0);

		for (int i = 1; i < lists.size(); i++) {
			result = mergeTwoSort(result, lists.get(i));
		}

		for (int x : result) {
			System.out.print(x + " ");
		}
	}


	public static List<Integer> mergeTwoSort(List<Integer> list1, List<Integer> list2) {
		int p1 = 0, p2 = 0;
		List<Integer> list3 = new ArrayList<>();

		while (p1 < list1.size() && p2 < list2.size()) {
			if (list1.get(p1) < list2.get(p2))
				list3.add(list1.get(p1++));
			else
				list3.add(list2.get(p2++));
		}

		while (p1 < list1.size())
			list3.add(list1.get(p1++));

		while (p2 < list2.size())
			list3.add(list2.get(p2++));

		return list3;
	}
}

查找

两个数的和等于给定的数字

题目

有序的数组 找出两个数的和等于给定的数字。要求时间O(n) 空间O(1)。

分析

1,暴力查找法
就是使用两个for循环,这种效率很差

public int[] twoSum(int[] nums, int target) {
    int length = nums.length;
    for (int i = 0; i < length - 1; i++) {
        for (int j = i + 1; j < length; j++)
            if (nums[i] + nums[j] == target)
                return new int[]{i+1, j+1};
    }
    return new int[]{-1, -1};
}

2,使用HashMap解决

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> m = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (m.get(target - nums[i]) != null) {
            return new int[]{m.get(target - nums[i])+1, i+1};
        }
        m.put(nums[i], i);
    }
    return new int[]{0, 0};
}

递归与迭代

f(0)=0;f(1)=1;f(n)=f(n-1)+f(n-2)。求f(n)   (用递归和迭代两种方法)

程序

package org.example.a;

public class Demo {
    public static void main(String[] args) {
        System.out.println("recursion: " + f1(6));
        System.out.println("iteration: " + f2(6));
    }

    //递归
    public static int f1(int n){
        if(n == 0 || n == 1){
            return n;
        }else{
            return (f1(n - 1) + f1(n - 2));
        }
    }

    //迭代
    public static int f2(int n){
        int a0, a1, a2;
        a0 = 0;
        a1 = 1;
        a2 = 0;
        for(int i = 2; i <= n; i++){
            a2 = a0 + a1;
            a0 = a1;
            a1 = a2;
        }
        return a2;
    }
}

运行结果

recursion: 8
iteration: 8

路径

走台阶

题目

总共100级台阶(任意级都行),小明每次可选择走1步、2步或者3步,问走完这100级台阶总共有多少种走法?

分析

这个问题本质上是斐波那契数列,

假设只有一个台阶,那么只有一种跳法,那就是一次跳一级,f(1)=1;

如果有两个台阶,那么有两种跳法,第一种跳法是一次跳一级,第二种跳法是一次跳两级,f(2)=2。

如果有大于2级的n级台阶,那么假如第一次跳一级台阶,剩下还有n-1级台阶,有f(n-1)种跳法,假如第一次跳2级台阶,剩下n-2级台阶,有f(n-2)种跳法。这就表示f(n)=f(n-1)+f(n-2)。

编码

public class Test {
    static final int s = 100; //自定义的台阶数
 
    static int compute(int stair){
        if ( stair <= 0){
            return 0;
        }
        if (stair == 1){
            return 1;
        }
        if (stair == 2){
            return 2;
        }
        return compute(stair-1) + compute(stair-2);
    }
 
    public static void main(String args[]) {
        System.out.println("共有" + compute(s) + "种走法");
    }
}

x*y的方格

题目

有x*y的方格,从左上角走到右下角,每次只能向右或者向下走一格,不能后退,问一共多少种走法?

方案1:递归

分析

这个问题跟上边的走台阶很像。思路是一样的:

确定退出的条件:如果是x * 1 或者 1 * y,则只有一种走法

对于一个起点,若向右走一格,则还剩f(x – 1, y)种走法;若向下走一格,则还剩f(x, y – 1)种走法,那么将这两者加起来即可:f(x – 1, y) + f(x, y – 1)

代码

package org.example.a;

public class Demo {
    public static void main(String[] args) {
        System.out.println(f(3,2));
    }

    private static int f(int x, int y) {
        if (x == 1 || y == 1) {
            return 1;
        }

        return f(x - 1, y) + f(x, y - 1);
    }
}

方案2:迭代

分析:将上边的代码用迭代写法修改

方案3:组合

分析

组合问题,从左上角各自到右下角各自总共要走m+n-2步,每次可以向下或是向右走,向下走共需n-1步,所以从n+m-2步中选择n-1步(表示选哪个地方下来)。

组合的公式:

代码

数字

奇数偶数

题目

给出一个数字n,如果n是偶数就除以2,如果是奇数就选择+1或者-1,求最少几次能够使n变成1。

分析

乍一看,这题不是很简单么?奇数-1,偶数除以2,不就是最快的吗?

但是,以15为例,如下所示,可以发现,刚开始+1比刚开始-1更快。

如果刚开始-1:15 14 7 6 3 2 1

如果刚开始+1:15 16 8 4 2 1

总结规律:我们在遇到奇数的时候,尽量让操作后的结果(偶数)除以2之后仍然是偶数,这样下一次直接除就可以,可以省一步,可以达到最快。

即:遇到奇数的时候,尽量让操作后的结果是4的倍数。

代码

package org.example.a;

public class Demo {
    public static void main(String[] args) {
        System.out.println(f(31));
    }

    private static int f(int n) {
        int number = 0;
        int tmp = n;

        while (tmp != 1) {
            if (tmp % 2 == 0) {
                tmp = tmp / 2;
            } else {
                if ((tmp + 1) % 4 == 0) {
                    tmp += 1;
                } else {
                    tmp -= 1;
                }
            }
            number++;
        }
        return number;
    }
}

斐波那契数列 3的倍数

题目

F(0) = 7,F(1) = 11,F(n) = F(n-1) + F(n-2) (n≥2),数列中第n个数是否是3的倍数。 

分析

这个题其实挺没意思的,就是个找规律题目:

f(0)=7, f(0)%3=1
f(1)=11,f(1)%3=2
f(2)=18,f(2)%3=0
f(3)=29,f(3)%3=2
f(4)=47,f(4)%3=2
f(5)=76,f(5)%3=1
f(6)=123,f(6)%3=0
f(7)=199,f(7)%3=1
f(8)=322,f(8)%3=1
f(9)=521,f(9)%3=2
……

可以发现,8为周期,则对8取余,余数为2, 6则为3的倍数。

二叉树

二叉树的镜像

找到搜索二叉树两个错误节点

栈与队列

两个栈实现队列

字符串

判断字符串有无重复字符

字符串最长的无重复字符的子字符串 

代码

package org.example.a;

public class Demo {
    public static void main(String[] args) {
        String str = "abcdaefa";
        System.out.println(longestSubString(str));
    }

    private static String longestSubString(String str) {
        int start = 0;
        int end = 0;
        int resultStart = 0;
        int resultEnd = 0;

        for (int i = 0; i < str.length(); i++) {
            start = i;
            for (int j = i + 1; j < str.length(); j++) {
                if (str.charAt(j) == str.charAt(i)) {
                    break;
                } else {
                    end = j;
                }
            }
            // 保留更长的字符串的始末位置
            if (end - start > (resultEnd - resultStart)) {
                resultStart = start;
                resultEnd = end;
            }
        }
        return str.substring(resultStart, resultEnd);
    }
}

执行结果

bcdaef
0

评论0

请先

显示验证码
没有账号?注册  忘记密码?

社交账号快速登录