2018年3月22日19:00–21:20,参与了美团点评春招在线考试,前两部分的智力题和基础题均为选择题,共40分。两道编程题每题30分,共60分。现将编程题记录如下:

字符串距离

题目描述
  给出两个相同长度的由字符 aa 和 bb 构成的字符串,定义它们的距离为对应位置不同的字符的数量。如串 aabaab与 串 abaaba 的距离为
2;串baba 与串 aaaa 的距离为 1;串 baabaa 和串 baabaa 的距离为 0。
  下面给出两个字符串 SS 与 TT,其中 SS 的长度不小于 TT 的长度。我们用 |S||S| 代表 SS 的长度,|T||T| 代表 TT
的长度,那么在SS 中一共有 |S|−|T|+1|S|−|T|+1 个与 TT 长度相同的子串,现在你需要计算 TT 串与这些 |S|−|T|+1|S|−|T|
+1 个子串的距离的和。
  假设 SS 与 TT 只包含 aa 和 bb ,且 1≤|T|≤|S|≤2251≤|T|≤|S|≤225 。

输入
abbba ab
输出
4
时间限制:C/C++语言 2000MS;其他语言 4000MS
内存限制:C/C++语言 65536KB;其他语言 589824KB
import java.util.Scanner; public class Main{ public static int getDistance
(String S, String T,int len) { int distant = 0; for (int i = 0; i < len; i++) {
if (S.charAt(i) != T.charAt(i)) { distant += 1; } } return distant; } public
static void main(String[] args) { Scanner scanner = new Scanner(System.in);
String S = scanner.nextLine(); String T = scanner.nextLine(); scanner.close();
int DISTANT = 0; int sLen = S.length(); int tLen = T.length(); int n = sLen -
tLen +1; if (sLen == 1) { DISTANT = S.equals(T) ? 0 : 1; } else { if (sLen ==
tLen) { DISTANT = getDistance(S, T, tLen); }else { for (int i = 0; i < n; i++)
{ DISTANT += getDistance(S.substring(i, i + tLen), T, tLen); } } }
System.out.println(DISTANT); } }
数字字符

题目描述

  在十进制表示中,任意一个正整数都可以用字符‘0’-‘9’表示出来。但是当‘0’-‘9’这些字符每种字符的数量有限时,可能有些正整数就无法表示出来了。比如你有两个‘1’
,一个‘2’ ,那么你能表示出 11,12,121 等等,但是无法表示出 10,122,200 等数。
  现在你手上拥有一些字符,它们都是‘0’-‘9’的字符。你可以选出其中一些字符然后将它们组合成一个数字,那么你所无法组成的最小的正整数是多少?

输入
55
输出
1
时间限制:C/C++语言 2000MS;其他语言 4000MS
内存限制:C/C++语言 65536KB;其他语言 589824KB

(只有20%通过率)
import java.util.Scanner; import java.util.HashMap; import java.util.Map;
public class Main { public static void main(String[] args) { Scanner scanner =
new Scanner(System.in); String NUMS = scanner.nextLine(); scanner.close(); Map
map =new HashMap<String, Integer>(); int result = 1; int n = NUMS.length(); for
(int i = 0; i < n; i++) { String str = NUMS.substring(i, i + 1); if
(map.containsKey(str)) { map.put(str, (Integer) map.get(str) +1); } else {
map.put(str,1); } } for (int j = 1; j < Math.pow(10, n + 1); j++) { String jStr
= String.valueOf(j);if (!map.containsKey(jStr) || ((Integer) map.get(jStr)) == 0
) { result = j;break; } else { int c = (Integer) map.get(jStr); map.put(jStr, c
-1); } } System.out.println(result); } }