美团3.13后端开发笔试Java
4道算法题，另一道非算法题，没有看，所以不清楚
1. 矩阵翻转输出
给一个矩阵A,，将这个矩阵沿A[0][0]..A[i][i]这条边对折，然后按行输出
如果矩阵行列相等，则沿对角线对折，行列不相等，则需要反转；
其实将原矩阵按列输出即可
/*
测试用例
3 4 //行和列
1 2 3 11
4 5 6 12
7 8 9 13 输出
1 4 7
2 5 8
3 6 9
11 12 13 */
public class MatrixDouble {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int rows = sc.nextInt();
int cols = sc.nextInt();
int[][] original = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
original[i][j] = sc.nextInt();
}
}
for (int i = 0; i < cols; i++) {
for (int j = 0; j < rows; j++) {
if (j < rows - 1) {
System.out.print(original[j][i] + " ");
} else {
System.out.print(original[j][i]);
}
}
System.out.println();
}
}
}
2.解析仅包含小写字母和数字的一行字符串，并将其中的数字进行排序，按行输出
/*
测试用例：he15l154lo87wor7l87d
将其中包含的数字排序，输出
7
15
87
87
154 */
public class StringNum {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
List<Integer> res = new ArrayList<>();
resolve(str, res);
int[] arr = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
arr[i] = res.get(i);
}
Arrays.sort(arr);
for (int i = 0; i < res.size(); i++) {
System.out.println(arr[i]);
}
}
private static void resolve(String s, List<Integer> res) {
if (s == null) return;
int len = s.length();
int right = 0;
String tmp = "";
while (right < len) {
tmp = "";
while (right < len && s.charAt(right) >= 'a' && s.charAt(right) <= 'y') {
right++;
}
while (right < len && s.charAt(right) >= '0' && s.charAt(right) <= '9') {
tmp += s.charAt(right);
right++;
}
if (tmp != "") {
res.add(Integer.parseInt(tmp));
}
}
}
}
3. 在数组中找出每个滑动窗口下出现次数最多的元素，出现次数相同，返回最小值
/*
7 4 //元素数目 窗口大小
2
1
1
1
4
6
7
输出：
1
1
1
1
*/
public class MostOccurence {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int len = sc.nextInt();
int k = sc.nextInt();
int[] res = new int[len];
for (int i = 0; i < len; i++) {
res[i] = sc.nextInt();
}
//也可以只使用一个HashMap保存，但移动窗口依然需要对窗口内元素遍历
for (int i = 0; i <= len -k; i++) {
System.out.println(getMost(res, i, i+k-1));
}
}
private static int getMost(int[] res, int start, int end) {
if (start == end) return res[start];
int tmp = res[start];
Map<Integer, Integer> map = new HashMap<>();
for (int i = start; i <= end ; i++) {
if (map.containsKey(res[i])) {
map.put(res[i],map.get(res[i])+1);
} else {
map.put(res[i],1);
}
if (map.get(res[i]) > map.get(tmp) ||
(map.get(res[i]).equals(map.get(tmp)) && res[i] < tmp)) {
tmp = res[i];
}
}
return tmp;
}
}
4 打家劫舍3，给定二叉树，计算非相邻节点所能抢的最大值和最小值，参见lc337. 打家劫舍 III
/*
测试用例：
依次是
节点数nodeNUm 边数edge
下标从0到nodeNum对应的节点值
相连的两个节点下标
5 4
3 2 3 3 1
1 2
1 3
2 4
3 5
结果：
最大金额
最小金额
7
3
原始的测试用例忘了
*/
public class TreeNodeSum {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int nodeNum = sc.nextInt();
int edge = sc.nextInt();
TreeNode[] nodes = new TreeNode[nodeNum + 1];
for (int i = 1; i <= nodeNum; i++) {
nodes[i] = new TreeNode(i, sc.nextInt());
}
int[] relations = new int[2];
for (int i = 0; i < edge; i++) {
for (int j = 0; j < 2; j++) {
relations[j] = sc.nextInt();
}
if (nodes[relations[0]].left == null) {
nodes[relations[0]].left = nodes[relations[1]];
} else {
nodes[relations[0]].right = nodes[relations[1]];
}
}
int[] res = dfs(nodes[1]);
System.out.println(Math.max(res[0], res[1]));
System.out.println(Math.min(res[0], res[2]));
}
private static int[] dfs(TreeNode node) {
if (node == null) return new int[]{0, 0};
int[] left = dfs(node.left);
int[] right = dfs(node.right);
int[] dp = new int[3];
dp[0] = node.val + left[0] + right[0];
dp[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
dp[2] = Math.min(left[0], left[1]) + Math.min(right[0], right[1]);
return dp;
}
static class TreeNode {
int index;
int val;
TreeNode left;
TreeNode right;
TreeNode(int index, int val) {
this.index = index;
this.val = val;
}
}
}
整体大概就是这样，不知道写完的能跑通多少测试用例。。。
