写在前面
有段时间没有写博客了。最近主要是在深入学习Android和准备校招。
前段时间投了不少简历出去，陆陆续续也经历了几场笔试面试。趁着这几天开学的空闲，梳理一下周六晚做的链家笔试题。
链家在房源信息方面做得确实是国内首屈一指，我在上海实习期间就已经切切实实体味到了，真的是，感觉走到哪儿都有它家的门店。所以这次就投了一波简历来尝试一下。
总的来说，链家笔试的题目中规中矩，2个小时，20道选择题+3道编程题。选择题全是Android相关的基础知识，有些Android编程经验的都能做个八九不离十。编程题则是重点考察dp，难度还是有的。我只A了2.8道，有一题多重背包，dp解的，复杂度超了，只过了82%。下面来贴一下题目和个人见解，欢迎有能力全A的大神指教~
笔试题
笔试时间：2017年09月02日 19:00--21:00
考试类型：链家2018招聘京外笔试（Android研发工程师）
01.分小球问题
题目描述：
题目解析：
这题说是往杯子里倒水，实际上，就是高中数学接触的那种分小球问题，只是换了种说法。我在此就将其称为分小球问题了吧。
本题可以转化为这样的题目：有n个相同的小球，m个相同的盒子，要求每个盒子里面至少有k个小球，问一共有多少种放法？（本题的k=0）
思路：使用二维数组dp[i][j]表示i个小球放入j个盒子的方法数。
因为盒子可以为空，我们分两种情况来考虑：
①球数最少的盒子为空：那么就相当于，有一个盒子不能放球，即把i个小球放入j-1个盒子里面，就是 dp[i][j-1]。
②球数最少的盒子不为空：那么就相当于每个盒子里面都至少有一个小球，我们就预先把每个盒子里面放入一个小球好了，有 dp[i-j][j]。
所以，递推公式为 dp[i][j] = dp[i][j-1] + dp[i-j][j]，这种情况在 i>=j时成立。而当 i<j时，可以知道，球没有盒子多，肯定会有盒子为空，就不存在②这种情况了，于是dp[i][j] = dp[i][j-1]。
根据以上思路，就可以解决本题了。贴上我的AC代码。关键是init()方法的实现。具体如下：
Java解答：
import java.util.Scanner;
public class Main {
public static final int maxN = 11;
public static int[][] dp = new int[maxN][maxN];
private static void init(){
for(int i=1;i<=10;i++) {
dp[0][i]=1;
dp[i][1]=1;
}
for(int i=1;i<maxN;i++)
for(int j=2;j<maxN;j++)
if(j<=i)
dp[i][j]=dp[i][j-1]+dp[i-j][j];
else
dp[i][j]=dp[i][i];
}
public static void main(String[] args) {
init();
Scanner in = new Scanner(System.in);
int num = in.nextInt();
for (int i=0; i<num; i++) {
int m = in.nextInt();
int n = in.nextInt();
System.out.println(dp[m][n]);
}
in.close();
return;
}
}
02.两端取数问题
题目描述：
题目解析：
这题描述有点长，读了好一会儿才明白题意。（PS:吐槽一句题目：食物放越久越值钱？你是想卖82年的黄焖鸡呢，还是69年的凤爪啊？）
整理一下题意：给定一个正整数的数组，表示一列货物的价值。第1天起，我们每天可以从最左或最右端取一个数，货物的售价=天数*货物价值。要求出这批货物最多可以卖多少钱？
这题和上面那题一样。满满的dp感。
假定货物总个数为 num。
我们的思路还是建立一个二维数组 dp[x][y]，表示x~y这段货物 num天的最大售卖价格。那么有：
①初始化：dp[i][i]在num天的最大售价就是在第num天将其出售，于是有dp[i][i] = arr[i] * num;
②对于每个dp[x][y]，它的值等于 max(最后卖arr[x]的最大售价，最后卖arr[y]的最大售价)。 而最后卖arr[x]的最大售价为: (num-y+x) * arr[x] + dp[x+1][y], 最后卖arr[y]的最大售价为：(num-y+x) * arr[y] + dp[x][y-1]。
即：dp[x][y] = Math.max((num-y+x) * arr[x]+dp[x+1][y], (num-y+x) * arr[y]+dp[x][y-1])。
最后，dp[0][num-1]即是题目所求的 num天所有货物的最大售价。
Java解答：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int num = in.nextInt();
int[] arr = new int[num];
for (int i=0; i<num; i++) {
arr[i] = in.nextInt();
}
in.close();
int[][] dp = new int[num][num];
for(int i=0; i<num; i++) {
dp[i][i] = arr[i] * num;
}
for (int dis=1; dis<num; dis++) {
// dis means y-x
for (int x=0; x<num-dis; x++) {
dp[x][x+dis] = Math.max((num-dis)*arr[x]+dp[x+1][x+dis], (num-dis)*arr[x+dis]+dp[x][x+dis-1]);
}
}
System.out.println(dp[0][num-1]);
}
}
03.多重背包问题
题目描述：
题目解析：
这是典型的多重背包问题。因为最后没什么时间了，用c++写的朴素dp，但是复杂度太高，只过了82%。后来在网上找了一下解法，大家可以参考：P03 多重背包问题
C++解答
给大家贴上我的c++弱鸡dp解，仅供参考，复杂度有待改进：
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <math.h>
#include <string>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#include <time.h>
#include <iomanip>
typedef unsigned int uint;
using namespace std;
/* 动态规划 */
int DPKnapsack(uint c, const uint n, uint &bestV, const vector<uint> &w, const vector<uint> &v, const vector<uint> &x)
{ // w体积 v价值 s数量
vector<vector<uint>> dp(n + 1, vector<uint>(c + 1, 0));
int i, j, cur, k;
// 动态规划
int temp;
for (i = 1; i <= n; i ++)
{
for (j = 1; j <= c; j ++)
{
for (k = 0; k <= x[i]; k ++)
{
temp = j - k * w[i];xx
if (temp >= 0)
{
cur = dp[i - 1][temp] + k * v[i];
dp[i][j] = dp[i][j] > cur ? dp[i][j] : cur;
}
else
{
break;
}
}
}
}
bestV = dp[n][c];
return 0;
}
int main()
{
// n , v
uint n, v;
while (cin >> n >> v)
{
vector<uint> ws, ss, xs;
uint m, w, s;
ws.push_back(0);
ss.push_back(0);
xs.push_back(0);
for (int i = 0; i < n; ++ i)
{
cin >> m >> w >> s;
ws.push_back(w);
ss.push_back(s);
xs.push_back(m);
}
uint bestS = 0;
DPKnapsack(v, ws.size() - 1, bestS, ws, ss, xs);
cout << bestS << endl;
}
return 0;
}
