首页 > 美团3.13后端开发笔试Java
头像
木有offer
编辑于 2021-03-14 10:41
+ 关注

美团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;
		}
	}
}
整体大概就是这样,不知道写完的能跑通多少测试用例。。。

全部评论

(9) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐