第一题(100分)

版本号排序问题,比如1.1.1版本大于1.0.0版本,每个.分割的数字范围是0-256,可以省略,比如..等价于0.0.0,可以有前导0,比如001.001.1等价于1.1.1;程序输入:需要排序的版本号个数,和各个版本号字符串,输出排序后的结果

public static List<String> dealSplit(String str){int firstIndex=str.indexOf('.');int lastIndex=str.lastIndexOf('.');List<String> list = new ArrayList<>(3);if(firstIndex==0)list.add("0");else list.add(str.substring(0,firstIndex));if(firstIndex+1==lastIndex)list.add("0");else list.add(str.substring(firstIndex+1,lastIndex));if(lastIndex==str.length()-1)list.add("0");else list.add(str.substring(lastIndex+1));return list;}public static int compare(List<String> list){int res=0;int mul=257*257;for (int i = 0; i < list.size(); i++) {String s = list.get(i);int index=0;while (index<s.length()&&s.charAt(index)=='0'){index++;}if(index!=s.length()) {res+=Integer.parseInt(s.substring(index))*mul;}mul/=257;}return res;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (scanner.hasNext()){int num=scanner.nextInt();PriorityQueue<String> queue = new PriorityQueue<String>((a,b)->{return  compare( dealSplit(b))-compare( dealSplit(a));});for (int i = 0; i < num; i++) {String s=scanner.next();queue.add(s);}while (!queue.isEmpty()){System.out.println(queue.poll());}}}

测试输出:

复盘:正则表达式在对字符串进行分割的时候并不总是分割空字符串,比如如下情况

public static void main(String[] args) {String s="..1";String s2="1..";String s3=".1.";System.out.println(Arrays.toString(s.split("\\.")));System.out.println(Arrays.toString(s2.split("\\.")));System.out.println(Arrays.toString(s3.split("\\.")));}

分割结果可以说是相当迷幻了...

[, , 1]
[1]
[, 1]

第二题(200分)

高峰用餐问题,每个进饭店用餐的人有用餐时间数组[start,end),根据数组输出最高峰的用餐时间段

输入用餐人数和每个用餐时间数组

最朴素的思路是使用一个大数组,作为一条直线段,存储每一个时间段,在[start,end)的位置+1,进一步可以优化数组的大小为(max-min+1),再进一步可以使用差分数组优化+1操作,时间复杂度变为O(1)

public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (scanner.hasNext()){int num=scanner.nextInt();int min=Integer.MAX_VALUE;int max=Integer.MIN_VALUE;int[][] matrix = new int[num][2];for (int i = 0; i < num; i++) {int start=scanner.nextInt();int end=scanner.nextInt();matrix[i][0]=start;matrix[i][1]=end;min=Math.min(start,min);max=Math.max(max,end);}//因为区间是[start,end),长度为max-min,使用差分数组,要多一个位置int[] record = new int[max - min + 1];for (int i = 0; i < matrix.length; i++) {int start=matrix[i][0]-min;int end=matrix[i][1]-min;record[start]+=1;record[end]-=1;}int maxSum=Integer.MIN_VALUE;int sum=0;for (int i = 0; i < record.length; i++) {sum+=record[i];maxSum=Math.max(sum,maxSum);}//最后呈现的数据段可能为多段boolean isStart=true;boolean isContinue=false;sum=0;ArrayList<Integer> list = new ArrayList<>();for (int i = 0; i < record.length; i++) {sum+=record[i];if(isStart&&sum==maxSum){isStart=false;isContinue=true;list.add(i);}if(isContinue&&sum!=maxSum){isContinue=false;isStart=true;list.add(i-1);}}for (Integer integer : list) {System.out.println(integer+min);}}}
}

测试输出:

 第三题(300分)

二维数组中的连连看,数组中的0代表可以经过的区域,其他数字都代表不可经过的方块,给一个输入数组和两个点的坐标(i,j),返回将两个目标点连在一起最少需要的折线数量,下图的情况是三次,路径用绿线表示,红点为两个目标点

1 2 0 0 1 3

1 4 5 0 2 0

static int targetI;static int targetJ;static int initI;static int initJ;static int m;static int n;static int[][] direction = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};static List<Integer> res = new ArrayList<>();static boolean[][] visited;//最后一个变量标识上一次是横向走还是纵向走public static void dfs(int[][] matrix, int i, int j, Boolean row, int num) {if (i == targetI && j == targetJ) {res.add(num);return;}//说明可以访问if (matrix[i][j] == 0||(i==initI&&j==initJ)) {visited[i][j] = true;for (int k = 0; k < 4; k++) {int x = i + direction[k][0];int y = j + direction[k][1];if((x>=0&&y>=0&&x<m&&y<n)&&!visited[x][y]){if (k == 0 || k == 1) {//纵向走if(row==null){dfs(matrix,x,y,false,num+1);}else if(row){//上次横向这次纵向dfs(matrix,x,y,false,num+1);}else{dfs(matrix,x,y,false,num);}}else{//横向走if(row==null){dfs(matrix,x,y,true,num+1);}else if(row){dfs(matrix,x,y,true,num);}else{//上次纵向这次横向dfs(matrix,x,y,true,num+1);}}}}visited[i][j]=false;}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);m = scanner.nextInt();n = scanner.nextInt();visited = new boolean[m][n];int[][] matrix = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {matrix[i][j] = scanner.nextInt();}}int i1 = scanner.nextInt();int j1 = scanner.nextInt();int i2 = scanner.nextInt();int j2 = scanner.nextInt();targetI = i2;targetJ = j2;initI=i1;initJ=j1;dfs(matrix,i1,j1,null,0);int min=Integer.MAX_VALUE;for (int i = 0; i < res.size(); i++) {min=Math.min(min,res.get(i));System.out.println("累计折线数"+res.get(i));}System.out.println(min);}

测试输出: