4.9美团笔试情况
5道编程题，ac了4.27
第一题，输入一个n，比如1234，1对应1，看代码中的map，2对应0，最后加起来，题目的意思用int可能会不够，我看可以就没换，很快ac。
//对于80% 的数据，n<=100000
//对于20% 的数据，n<=1000000000
public static void main(String[] args) {
int[] map = new int[]{1, 0, 0, 0, 0, 0, 1, 0, 2, 1};
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
int res = 0;
while (x != 0) {
int y = x % 10;
res += map[y];
x /= 10;
}
System.out.println(res);
} 第二题，经典排序题，给几个人，有身高和名字，身高由低到高，如果身高一样，按姓名字典序排，不知道为什么我用数组自定义排序不给我排正确，最后用了堆才ac。题目看到一半还以为往单调栈方向走，没想到就简单的排序。 public class Solution2 {
@Test
public void myTest() {
System.out.println("beta".compareTo("alpha"));
}
//remebor, how to compare tow string
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Person[] p = new Person[n];
for (int i = 0; i < n; i++) {
Person person = new Person();
person.height = sc.nextInt();
p[i] = person;
}
for (int i = 0; i < n; i++) {
p[i].name = sc.next();
}
PriorityQueue<Person> pq = new PriorityQueue<>((a, b) -> (a.height != b.height ? a.height - b.height : a.name.compareTo(b.name)));
// Arrays.sort(p, (a, b) -> (a != b ? a.height - b.height : b.name.compareTo(a.name)));
for (int i = 0; i < p.length; i++) {
pq.add(p[i]);
}
for (int i = 0; i < n; i++) {
System.out.print(pq.poll().name + " ");
}
}
static class Person {
int height;
String name;
public Person() {
}
public Person(int height, String name) {
this.height = height;
this.name = name;
}
}
}
第三题：给你一个图，判断是否u直连v，这个也很简单。 public class Solution3 {
@Test
public void myTest() {
}
//4 5
//1 2 1 3 1
//2 1 3 2 4
//4
//1 2
//2 4
//2 3
//1 4
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
int[][] graph = new int[n + 1][n + 1];
int[] u = new int[m], v = new int[m];
for (int i = 0; i < m; i++) {
u[i] = sc.nextInt();
}
for (int i = 0; i < m; i++) {
v[i] = sc.nextInt();
}
for (int i = 0; i < m; i++) {
graph[u[i]][v[i]] = 1;
graph[v[i]][u[i]] = 1;
}
int q = sc.nextInt();
for (int i = 0; i < q; i++) {
int x = sc.nextInt(), y = sc.nextInt();
if (graph[x][y] == 1) System.out.println("Yes");
else System.out.println("No");
}
}
} 第四题，2X2的矩阵，一行一列元素不能一样，问有多少种方法，这个推导一下就出来了，不过我中间出错了一部导致花了很多时间，还好最后ac了。做完这四个还剩下30min。 public class Solution4 {
@Test
public void myTest() {
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNextInt()) {
int n = sc.nextInt();
if (n < 2) System.out.println(0);
else if (n == 2) System.out.println(2);
else if (n == 3) System.out.println((int) ((2 * c(n, 2) + 12 * c(n, 3)) % Math.pow(10, 7)));
else if (n >= 4) System.out.println((int) ((2 * c(n, 2) + 12 * c(n, 3) + 24 * c(n, 4)) % Math.pow(10, 7)));
}
}
static int[] arr = new int[11];
private static int c(int n, int k) {
arr[0] = 1;
int n_j = 0, k_j = 0, n_K_j = 0;
if (arr[n] != 0) n_j = arr[n];
else {
n_j = fun(n);
arr[n] = n_j;
}
if (arr[k] != 0) k_j = arr[k];
else {
k_j = fun(k);
arr[k] = k_j;
}
if (arr[n - k] != 0) n_K_j = arr[n - k];
else {
n_K_j = fun(n - k);
arr[n - k] = n_K_j;
}
return n_j / (k_j * n_K_j);
}
private static int fun(int x) {
int res = 1;
for (int i = 1; i <= x; i++) {
res *= i;
}
return res;
}
}
第五题，给你两个队列，只能从队列的右边删除，左边插入，问使得c1[1,5,3,4,6]变成目标队列c2[2,1,5,3,4]。这个只过了27%，题看懂了但是没思路，暴力也只能暴力一点点。。。 public class Solution5 {
//5
//1 5 3 4 6
//5
//2 1 5 3 4
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
int[] c1 = new int[n];
StringBuffer sb1 = new StringBuffer(), sb2 = new StringBuffer();
for (int i = 0; i < n; i++) {
c1[i] = sc.nextInt();
sb1.append(c1[i]);
}
int m = sc.nextInt();
int[] c2 = new int[m];
for (int i = 0; i < m; i++) {
c2[i] = sc.nextInt();
sb2.append(c2[i]);
}
// System.out.println(sb1.toString() + "\t" + sb2.toString());
int i = 0;
// for (i = 0; i < sb2.length(); i++) {
// if (sb1.toString().contains(sb2.substring(i, sb2.length()))) {
// int len = sb2.length() - i;
// System.out.println(sb1.length() + sb2.length() - 2 * len);
// break;
// }
// }
// if (i == sb2.length()) {
// System.out.println(sb1.length() + sb2.length());
// }
if (sb2.charAt(sb2.length() - 1) != sb1.charAt(sb1.length() - 1))
System.out.println(sb1.length() + sb2.length());
if (sb1.toString().equals(sb2.toString())) System.out.println(0);
int lcs = fun(sb1.toString(), sb2.toString());
if (lcs < sb2.length()) System.out.println(sb1.length() + sb2.length());
System.out.println(sb1.length() + sb2.length() - 2 * lcs);
}
}
//find the lcs
public static int fun(String s1, String s2) {
int[][] dp = new int[s1.length() + 1][s2.length() + 1];
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp.length; 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[s1.length()][s2.length()];
}
} 
