实习与工作

微软笔试

jxtxzzw · 4月3日 · 2019年 · · · 118次已读

今天晚上是微软的笔试,有点难,做出 2 题(第 1 题和第 3 题),估计不是太好,但是和身边的同学问了一圈,有做出 1.9 题的(第 3 题用树状数组做,复杂度测试超时),有做出 1.5 题的(第 1 题过了,第 3 题通过一半,又 WA 又 T,或者第 1 题没想出来随便搞了几个部分分,加第 3 题一个 9/10)。


动态规划,bead 只可以从自己的倍数或者因数手上拿来。

dp[i][j] 表示传 i 次能传到 j 这个人有多少种可能,边界数据是传 1 次只能传给 p 的倍数或者因数。

状态转移方程是双重循环计算所有的 i、j,每次用倍数和因数分别计算:传 i – 1 次能传给 j 有多少种可能,就意味着 j 可以花 1 次的时间把东西传给 j 所有的因数或者倍数,于是,dp[i][j / k] 和 dp[i][j * k] 就应该是所有对应的(符合条件的)dp[i – 1][j] 的累加。

最后的答案是不超过 k 次的(for int i = 1; i <= K; i++)的 dp[i][p] 的累加,p 表示回到 p 这个人手上。

import java.io.*;
import  java.util.*;

// Read only region start
class UserMainCode
{

	public int maxCircles(int input1,int input2,int input3){
		// Read only region end
		// Write code here...
		int n = input1;
		int p = input2;
		int x = input3;
		int[][] dp = new int[x + 1][n + 1];
        
		for (int k = p; k > 1; k--)
			if (p / k > 0 && p % k == 0)
				dp[1][p / k] = 1;
        for (int k = 2; p * k <= n; k++)
        	dp[1][p * k] = 1;
        
        for (int i = 2; i <= x; i++) {
        	for (int j = 1; j <= n; j++) {
        		for (int k = j; k > 1; k--)
                	if (j / k > 0 && j % k == 0)
                		dp[i][j / k] += dp[i - 1][j];
                for (int k = 2; j * k <= n; k++)
                	dp[i][j * k] += dp[i - 1][j];
        	}
        }
        int ans = 0;
        for (int i = 1; i <= x; i++)
        	ans += dp[i][p];
		return ans;
	}
}

第 2 题,不会。

第 3 题,裸的队列。

直接模拟,实现一个队列。

搞不懂这题为什么会有人做错。

TLE 还情有可原。用了树状数组还 T 就有点奇怪。用二分思路好像没问题,但是又 WA 又 T 应该是边界数据没考虑对。

其实实现裸的队列就 OK 了。

如果使用 java.util.LinkedList 就非常简单,代码很短。

唯一需要注意,也是特别需要注意的地方是,remove(int index) 和 remove(Object o) 是两个重载了的方法,前一个方法是删除队列中第 index 个元素(下标从 0 开始),后者是删除队列中值为 o 的那个对象。

例如队列 1 2 3 4 5,如果做 remove(int 3),删掉的是 4,变成 1 2 3 5;如果做 remove(Object 3),删掉的是 3,变成 1 2 4 5。

由于链表保存的是 Integer,如果不能确定到底 remove(Integer i) 会被自动拆箱,变成 remove(int i),还是 Integer 被变成父类 Object,那就 explicit 一下。

import java.io.*;
import  java.util.*;

// Read only region start
class UserMainCode
{

	public int findPosition(int input1,int input2,int[][] input3){
		// Read only region end

		int ans = 0;
		int n = input1;
		int q = input2;
		int[][] A = input3;
		LinkedList<Integer> list = new LinkedList<>();
    	for (int i = 1; i <= n; i++)
    		list.add(i);
    	for (int i = 0; i < A.length; i++) {
    		switch(A[i][0]) {
    		case 1:
    			list.pollFirst();
    			break;
    		case 2:
    			list.remove((Object) A[i][1]);
    			// should be "remove(Object o)", not "remove(int index)"
    			break;
    		case 3:
    			ans += list.indexOf(A[i][1]) + 1;
    			break;  			
    		}
    	}
		return ans;
		
	}
}

第 4 题,不会。

0 条回应