360

admin管理员组

文章数量:1026989

360

时间：20180827      19：00~21：00

地点：远程

岗位：Java开发工程师

分两部分，第一部分选择题，共40道，没啥可说的，就是不明白为什么还有C++的代码分析题（Java岗）。

第二部分编程题，一共三道。

一、算正方形面积。

大概题目：翻修城镇，要求把所有的居民都包含到城镇里，请问城镇最小的面积。（城镇是正方形的，平行于坐标轴）输入：第一行一个整数N，表示城镇人口数；接下来N行，每一行是一个人的坐标。(-1e9<x,y<1e9)
输出：城镇的最小面积是多少。样例输入：
2
0 0
0 2样例输出：
4

调试程序，一直通不过所有测试用例。考完后看了下牛客网讨论区，才知道忽略的一个重要问题，(-1e9<x,y<1e9)，应该用long型或其他符合要求的类型。（网上有人说用BigInteger，没有试验过。）

上代码：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();long x = 0, y = 0;long x1 = 1000000000;long x2 = -x1;long y1 = x1;long y2 = x2;for (int i = 0; i < n; i++) {x = scanner.nextLong();y = scanner.nextLong();x1 = Math.min(x1, x);x2 = Math.max(x2, x);y1 = Math.min(y1, y);y2 = Math.max(y2, y);}long ans = Math.max(Math.abs(x1 - x2), Math.abs(y1 - y2));System.out.println(ans * ans);scanner.close();}
}

二、看花

输入两个数n,m;(1<=n<=2000,1<=m<=100);分别表示n次看花，m表示一共有m朵花儿。
接下来输入n个数a[1]~a[n]，a[i]表示第i次，小明看的花的种类;
输入一个数Q(1<=Q<=1000000);表示小红的问题数量。
输入Q行 每行两个数 l,r(1<=l<=r<=n); 表示小红想知道在第l次到第r次，小明一共看了多少不同的花儿。输入样例：
5 3
1 2 3 2 2
3
1 4
2 4
1 5输出样例：
3
2
3

运行程序，超时，用的是list判断是否是重复的花，应该用HashSet去重，应该就不会超时了吧。其实也想到了，但是hashset没怎么用过......还是得多练习啊！

上代码：

import java.util.HashSet;
import java.util.Scanner;public class Flower {static final int MAX = 2005;static int flower[] = new int[MAX];static int n, m, q;static int[][] kinds = new int[MAX][MAX];public static void getKindTable() {HashSet set = new HashSet();for (int i = 1; i <= n; i++) {set.clear();for (int j = i; j <= n; j++) {set.add(flower[j]);kinds[i][j] = set.size();}}}public static int getAns(int l, int r) {if (l > r) {int t = l;l = r;r = t;}return kinds[l][r];}public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();for (int i = 1; i <= n; i++) {flower[i] = sc.nextInt();}getKindTable();q = sc.nextInt();for (int i = 0; i < q; i++) {int l, r;l = sc.nextInt();r = sc.nextInt();System.out.println(getAns(l, r));}sc.close();}
}

三、最长子序列

把其中一个序列逆序，求两个序列的最长公共子序列。
上代码：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int[] a = new int[N];int[] b = new int[N];for (int i = 0; i < N; i++) {a[i] = sc.nextInt();}for (int j = 0; j < N; j++) {b[j] = sc.nextInt();}System.out.println(maxLen(a, b));sc.close();}private static int maxLen(int[] a, int[] b) {String s1 = String.valueOf(a);String s2 = String.valueOf(b);s2 = new StringBuilder(s2).reverse().toString();int lcs = Lcs(s1, s2);return lcs;}private static int Lcs(String s1, String s2) {int m = s1.length();int n = s2.length();int[][] dp = new int[m + 1][n + 1];for (int i = 0; i <= m; i++) {dp[i][0] = 0;}for (int i = 0; i <= n; i++) {dp[0][i] = 0;}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (s1.charAt(i - 1) == s2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[m][n];}
}

 

360

时间：20180827      19：00~21：00

地点：远程

岗位：Java开发工程师

分两部分，第一部分选择题，共40道，没啥可说的，就是不明白为什么还有C++的代码分析题（Java岗）。

第二部分编程题，一共三道。

一、算正方形面积。

大概题目：翻修城镇，要求把所有的居民都包含到城镇里，请问城镇最小的面积。（城镇是正方形的，平行于坐标轴）输入：第一行一个整数N，表示城镇人口数；接下来N行，每一行是一个人的坐标。(-1e9<x,y<1e9)
输出：城镇的最小面积是多少。样例输入：
2
0 0
0 2样例输出：
4

调试程序，一直通不过所有测试用例。考完后看了下牛客网讨论区，才知道忽略的一个重要问题，(-1e9<x,y<1e9)，应该用long型或其他符合要求的类型。（网上有人说用BigInteger，没有试验过。）

上代码：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();long x = 0, y = 0;long x1 = 1000000000;long x2 = -x1;long y1 = x1;long y2 = x2;for (int i = 0; i < n; i++) {x = scanner.nextLong();y = scanner.nextLong();x1 = Math.min(x1, x);x2 = Math.max(x2, x);y1 = Math.min(y1, y);y2 = Math.max(y2, y);}long ans = Math.max(Math.abs(x1 - x2), Math.abs(y1 - y2));System.out.println(ans * ans);scanner.close();}
}

二、看花

输入两个数n,m;(1<=n<=2000,1<=m<=100);分别表示n次看花，m表示一共有m朵花儿。
接下来输入n个数a[1]~a[n]，a[i]表示第i次，小明看的花的种类;
输入一个数Q(1<=Q<=1000000);表示小红的问题数量。
输入Q行 每行两个数 l,r(1<=l<=r<=n); 表示小红想知道在第l次到第r次，小明一共看了多少不同的花儿。输入样例：
5 3
1 2 3 2 2
3
1 4
2 4
1 5输出样例：
3
2
3

运行程序，超时，用的是list判断是否是重复的花，应该用HashSet去重，应该就不会超时了吧。其实也想到了，但是hashset没怎么用过......还是得多练习啊！

上代码：

import java.util.HashSet;
import java.util.Scanner;public class Flower {static final int MAX = 2005;static int flower[] = new int[MAX];static int n, m, q;static int[][] kinds = new int[MAX][MAX];public static void getKindTable() {HashSet set = new HashSet();for (int i = 1; i <= n; i++) {set.clear();for (int j = i; j <= n; j++) {set.add(flower[j]);kinds[i][j] = set.size();}}}public static int getAns(int l, int r) {if (l > r) {int t = l;l = r;r = t;}return kinds[l][r];}public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();for (int i = 1; i <= n; i++) {flower[i] = sc.nextInt();}getKindTable();q = sc.nextInt();for (int i = 0; i < q; i++) {int l, r;l = sc.nextInt();r = sc.nextInt();System.out.println(getAns(l, r));}sc.close();}
}

三、最长子序列

把其中一个序列逆序，求两个序列的最长公共子序列。
上代码：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int[] a = new int[N];int[] b = new int[N];for (int i = 0; i < N; i++) {a[i] = sc.nextInt();}for (int j = 0; j < N; j++) {b[j] = sc.nextInt();}System.out.println(maxLen(a, b));sc.close();}private static int maxLen(int[] a, int[] b) {String s1 = String.valueOf(a);String s2 = String.valueOf(b);s2 = new StringBuilder(s2).reverse().toString();int lcs = Lcs(s1, s2);return lcs;}private static int Lcs(String s1, String s2) {int m = s1.length();int n = s2.length();int[][] dp = new int[m + 1][n + 1];for (int i = 0; i <= m; i++) {dp[i][0] = 0;}for (int i = 0; i <= n; i++) {dp[0][i] = 0;}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (s1.charAt(i - 1) == s2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[m][n];}
}

 

本文标签： 360