用友笔试 - 20200818 - Java后台开发工程师

发表于 | 分类于 |

10道单选，多考察设计模式。

10道多选，Java基础为主。

3道编程题，总体不难。

1. 字符串压缩

算是经典题目了，印象里做过好多次了。

题目描述

压缩字符串。

要求：如果压缩后字符串长于原字符串，则返回原字符串。

1
2
3
4
5
Input:
"abbcccaadddd"

Output:
"a1b2c3a2d4"

解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Main{
    public String compress (String str) {
        int N = str.length();
        int i = 0;
        StringBuilder sb = new StringBuilder();
        while (i < N) {
            int j = i;
            while (j < N && str.charAt(j) == str.charAt(i)) {
                j++;
            }
            sb.append(str.charAt(i));
            sb.append(j - i);
            i = j;
        }
        
        String res = sb.toString();
        if (res.length() < str.length()) {
            return res;
        } else {
            return str;
        }
    }
}

2. 将矩阵上下翻转（二维数组）

不太清楚这道题目考察什么。

题目描述

1
2
3
4
5
6
7
8
9
Input:
[[1,2,3],
 [4,5,6],
 [7,8,9]]

Output:
[[7,8,9],
 [4,5,6],
 [1,2,3]]

解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Main{  
    public int[][] convert (int[][] matrix) {
        int i = 0;
        int j = matrix.length - 1;
        int[] temp;
        
        while (i < j){
            temp = matrix[i];
            matrix[i] = matrix[j];
            matrix[j] = temp;
            i++;
            j--;
        }
        return matrix;
    }
}

3. 城市到其他城市的最短距离

得分要求不一样，用Dijkstra得分最高，但实在想不起来怎么写了，最近刷题也没遇到啊。最后用动规做的，算是暴力法。

787.K 站中转内最便宜的航班[Medium]【这里用K限制了中转的数量】

LeetCode

题目描述

有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到其他所有城市的最便宜的价格。 如果没有这样的路线，则输出 -1；两个城市间机票价格不超过Integer.MAX_VALUE。

1
2
3
4
5
Input:
n = 3, flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500]] ,src = 0

Output:
[0, 100, 200]

解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Main{
	public int[] findAllCheapestPrice(int n, int[][] flights, int src) {
        int K = flights.length; // 不限制中转
        int[][] dp = new int[n][K+2];
        for(int i = 0; i < n; ++i){
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        for(int k = 0; k <= K+1; ++k){
            dp[src][k] = 0;
        }
        for(int k = 1; k <= K+1; ++k){
            for(int[] flight : flights){
                if(dp[flight[0]][k-1] != Integer.MAX_VALUE)
                    dp[flight[1]][k] = Math.min(dp[flight[1]][k], 
                                                dp[flight[0]][k-1] + flight[2]);
            }
        }
        int[] res = new int[n];
        for(int i=0; i< n; i++)
            res[i] = dp[i][K+1] == Integer.MAX_VALUE ? -1 : dp[i][K+1];
        return res;
    }
}