因为4月初要参加微软的online。所以今天把微软的面试题拿出来做了，自己解答了题目。下面附上我的解答代码。
-----------16年9月校招：
第一道题：Farthest Point（最远的整数点）
题目：
#1237 : Farthest Point 时间限制:5000ms 单点时限:1000ms 内存限制:256MB 描述 Given a circle on a two-dimentional plane. Output the integral point in or on the boundary of the circle which has the largest distance from the center. 输入 One line with three floats which are all accurate to three decimal places, indicating the coordinates of the center x, y and the radius r. For 80% of the data: |x|,|y|<=1000, 1<=r<=1000 For 100% of the data: |x|,|y|<=100000, 1<=r<=100000 输出 One line with two integers separated by one space, indicating the answer. If there are multiple answers, print the one with the largest x-coordinate. If there are still multiple answers, print the one with the largest y-coordinate. 样例输入 1.000 1.000 5.000 样例输出 6 1
答案和思路：AC不了的原因是因为float是不够用的，要变成double。
其实就是x的整数范围可以求出来。然后遍历x的时候，求Y。y上最大，y下最小然后看看所产生的距离是否是最大的。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
double x = sc.nextDouble();
double y = sc.nextDouble();
double r = sc.nextDouble();
int xMax = (int)Math.floor(r + x);
int xMin = (int)Math.ceil(x - r);
int xResult = 0;
int yResult = 0;
double maxDistance = 0;
for (int i = xMax; i >= xMin;i--) {
int x1 = i;
int y1 = (int)Math.floor(y + (Math.sqrt(r * r - (x1 - x) * (x1 - x))));
if (distance(x, y, x1 * 1.0, y1 * 1.0) > maxDistance) {
xResult = x1;
yResult = y1;
maxDistance = distance(x, y, x1 * 1.0, y1 * 1.0);
}
y1 = (int)Math.ceil(y - (Math.sqrt(r * r - (x1 - x) * (x1 - x))));
if (distance(x, y, x1 * 1.0, y1 * 1.0) > maxDistance) {
xResult = x1;
yResult = y1;
maxDistance = distance(x, y, x1 * 1.0, y1 * 1.0);
}
}
System.out.println(xResult + " " + yResult);
}
private static double distance(double x, double y, double x1, double y1) {
return Math.pow(x1 - x, 2) + Math.pow(y1 - y, 2);
}
}
第二题：-----Fibonacci
答案和思路：DP。dp[i][j]表示到了序列的第i个有j个序列是fabonacci的个数。这里因为无论怎样初始化dp[i][j]都会先等于dp[i - 1][j].然后如果a[i]是fabonacci，那么在进行加上多了的个数。所以，注意i==0要作为初始化。
当a[i]不是fabonacci里面的时候，他的出现不改变任何数值。
当a[i]试的时候，要分情况，因为如果a[i] == 1，比较特殊。dp[i][0]都要++。这里是表示出现了1个。因为1可以作为单独的一个。然后dp[i][1]出现了2的要+上dp[i - 1][0]。表示的是出现2要加上i-1就出现了一个的基础上，因为1可以作为第二个构成出现两个。
a[i] != 1的时候。dp[i][pos] 要加上i-1个出现了pos-1个的，因为这个a[i]和他们能够组合成完整的了。
答案：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int[] fib = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040};
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n + 1];
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
}
int[][] dp = new int[n + 1][30];
int mod = 1000000007;
for(int i=1;i<=n;i++){
for(int j=0;j<30;j++)
dp[i][j]=dp[i-1][j];
int pos = 0;
while (fib[pos] < a[i]) {
pos++;
}
if(fib[pos]==a[i]){
if(fib[pos]==1){
dp[i][pos+1]=(dp[i][pos+1]+dp[i-1][0])%mod;
dp[i][pos]=(dp[i][pos]+1)%mod;
}
else{
dp[i][pos]=(dp[i][pos]+dp[i-1][pos-1])%mod;
}
}
}
int ans = 0;
for(int i=0;i<30;i++){
ans = (ans+dp[n][i])%mod;
}
System.out.println(ans);
}
}
--------16年微软实习4道题：
第一道题：Magic Box
题目：
题目1 : Magic Box 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 The circus clown Sunny has a magic box. When the circus is performing, Sunny puts some balls into the box one by one. The balls are in three colors: red(R), yellow(Y) and blue(B). Let Cr, Cy, Cb denote the numbers of red, yellow, blue balls in the box. Whenever the differences among Cr, Cy, Cb happen to be x, y, z, all balls in the box vanish. Given x, y, z and the sequence in which Sunny put the balls, you are to find what is the maximum number of balls in the box ever. For example, let's assume x=1, y=2, z=3 and the sequence is RRYBRBRYBRY. After Sunny puts the first 7 balls, RRYBRBR, into the box, Cr, Cy, Cb are 4, 1, 2 respectively. The differences are exactly 1, 2, 3. (|Cr-Cy|=3, |Cy-Cb|=1, |Cb-Cr|=2) Then all the 7 balls vanish. Finally there are 4 balls in the box, after Sunny puts the remaining balls. So the box contains 7 balls at most, after Sunny puts the first 7 balls and before they vanish. 输入 Line 1: x y z Line 2: the sequence consisting of only three characters 'R', 'Y' and 'B'. For 30% data, the length of the sequence is no more than 200. For 100% data, the length of the sequence is no more than 20,000, 0 <= x, y, z <= 20. 输出 The maximum number of balls in the box ever. 提示 Another Sample Sample Input Sample Output 0 0 0 RBYRRBY 4 样例输入 1 2 3 RRYBRBRYBRY 样例输出 7 EmacsNormalVim
AC答案：
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int x = in.nextInt();
int y = in.nextInt();
int z = in.nextInt();
ArrayList<Integer> flag = new ArrayList();
flag.add(x);
flag.add(y);
flag.add(z);
Collections.sort(flag);
String str = in.next();
int max = 0;
int rCount = 0;
int bCount = 0;
int yCount = 0;
int count = 0;
for (int i = 0; i < str.length(); i++) {
count++;
max = Math.max(max, count);
if (str.charAt(i) == 'R') {
rCount++;
} else if (str.charAt(i) == 'B') {
bCount++;
} else {
yCount++;
}
ArrayList<Integer> cur = new ArrayList();
cur.add(Math.abs(rCount - bCount));
cur.add(Math.abs(rCount - yCount));
cur.add(Math.abs(bCount - yCount));
Collections.sort(cur);
if (cur.equals(flag)) {
count = 0;
rCount = 0;
bCount = 0;
yCount = 0;
}
}
System.out.println(max);
}
}
第二道题：
题目：TLE（后面改进思路初步估计是建图）
10000ms 单点时限:1000ms 内存限制:256MB 描述 Professor Q develops a new software. The software consists of N modules which are numbered from 1 to N. The i-th module will be started up by signal Si. If signal Si is generated multiple times, the i-th module will also be started multiple times. Two different modules may be started up by the same signal. During its lifecircle, the i-th module will generate Ki signals: E1, E2, ..., EKi. These signals may start up other modules and so on. Fortunately the software is so carefully designed that there is no loop in the starting chain of modules, which means eventually all the modules will be stoped. Professor Q generates some initial signals and want to know how many times each module is started.signals.png 输入 The first line contains an integer T, the number of test cases. T test cases follows. For each test case, the first line contains contains two numbers N and M, indicating the number of modules and number of signals that Professor Q generates initially. The second line contains M integers, indicating the signals that Professor Q generates initially. Line 3~N + 2, each line describes an module, following the format S, K, E1, E2, ... , EK. S represents the signal that start up this module. K represents the total amount of signals that are generated during the lifecircle of this module. And E1 ... EK are these signals. For 20% data, all N, M <= 10 For 40% data, all N, M <= 103 For 100% data, all 1 <= T <= 5, N, M <= 105, 0 <= K <= 3, 0 <= S, E <= 105. Hint: HUGE input in this problem. Fast IO such as scanf and BufferedReader are recommended. 输出 For each test case, output a line with N numbers Ans1, Ans2, ... , AnsN. Ansi is the number of times that the i-th module is started. In case the answers may be too large, output the answers modulo 142857 (the remainder of division by 142857). 样例输入 3 3 2 123 256 123 2 456 256 456 3 666 111 256 256 1 90 3 1 100 100 2 200 200 200 1 300 200 0 5 1 1 1 2 2 3 2 2 3 4 3 2 4 5 4 2 5 6 5 2 6 7 样例输出 1 1 3 1 2 2 1 1 2 3 5
答案：
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String str = in.readLine();
String[] a = str.split(" ");
int T = Integer.parseInt(a[0]);
while (T-- > 0) {
str = in.readLine();
a = str.split(" ");
int N = Integer.parseInt(a[0]);
int M = Integer.parseInt(a[1]);
ArrayList<Integer> signal = new ArrayList();
Map<Integer,ArrayList<Integer>> map = new HashMap();
str = in.readLine();
a = str.split(" ");
int m = 0;
while (M-- > 0) {
signal.add(Integer.parseInt(a[m++]));
}
ArrayList<int[]> generate = new ArrayList();
int temp = N;
for(int i = 0; i < temp; i++) {
str = in.readLine();
a = str.split(" ");
int S = Integer.parseInt(a[0]);
if (map.containsKey(S)) {
ArrayList<Integer> list = map.get(S);
list.add(i);
map.put(S, list);
} else {
ArrayList<Integer> list = new ArrayList();
list.add(i);
map.put(S, list);
}
int k = Integer.parseInt(a[1]);
int[] array = new int[k];
m = 2;
for (int j = 0; j < k; j++) {
array[j] = Integer.parseInt(a[m]);
m++;
}
generate.add(array);
}
int[] result = new int[N];
while (signal.size() != 0) {
int s = signal.get(0);
signal.remove(0);
ArrayList<Integer> list= map.get(s);
if (list == null) {
continue;
}
for (int i = 0; i < list.size(); i++) {
int n = list.get(i);
result[n]++;
int[] ge = generate.get(n);
for (int t = 0; t < ge.length; t++) {
signal.add(ge[t]);
}
}
}
for (int i = 0; i < N; i++) {
System.out.print(result[i] + " ");
}
System.out.println();
}
}
}
15年：
备注：在hihocoder。需要自己接口。常用基本接口如下：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()) {
int a = in.nextInt();
int b = in.nextInt();
System.out.println(a + b);
}
}
}
1，题目：
题目1 : Beautiful String 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 We say a string is beautiful if it has the equal amount of 3 or more continuous letters (in increasing order.) Here are some example of valid beautiful strings: "abc", "cde", "aabbcc", "aaabbbccc". Here are some example of invalid beautiful strings: "abd", "cba", "aabbc", "zab". Given a string of alphabets containing only lowercase alphabets (a-z), output "YES" if the string contains a beautiful sub-string, otherwise output "NO". 输入 The first line contains an integer number between 1 and 10, indicating how many test cases are followed. For each test case: First line is the number of letters in the string; Second line is the string. String length is less than 10MB. 输出 For each test case, output a single line "YES"/"NO" to tell if the string contains a beautiful sub-string. 提示 Huge input. Slow IO method such as Scanner in Java may get TLE. 样例输入 4 3 abc 4 aaab 6 abccde 3 abb 样例输出 YES NO YES NO
答案：
-
import java.util.Scanner; import java.lang.String; import java.util.ArrayList; class MyMap { char c; int count; MyMap(char ch, int n) { c = ch; count = n; } } public class Main { public static void main(String[] args) { int num = 0; Scanner sc = new Scanner(System.in); num = sc.nextInt(); int length = 0; String str = new String(); while (num-- > 0) { length = sc.nextInt(); str = sc.next(); ArrayList<MyMap> list = new ArrayList(); for (int i = 0; i < str.length();) { char tempC = str.charAt(i); int tempN = 0; while (i < str.length() && str.charAt(i) == tempC) { tempN++; i++; } MyMap map = new MyMap(tempC, tempN); list.add(map); } boolean flag = true; for (int i = 1; i < list.size() - 1; i++) { if (list.get(i).c - list.get(i - 1).c == 1 && list.get(i + 1).c - list.get(i).c == 1) { if (list.get(i).count <= list.get(i - 1).count && list.get(i).count <= list.get(i + 1).count) { flag = false; System.out.println("YES"); break; } } } if (flag) { System.out.println("NO"); } } } }