简介
本文介绍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
请先 ！