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