写在前面

---

有段时间没有写博客了。最近主要是在深入学习Android和准备校招。

前段时间投了不少简历出去，陆陆续续也经历了几场笔试面试。趁着这几天开学的空闲，梳理一下周六晚做的链家笔试题。

链家在房源信息方面做得确实是国内首屈一指，我在上海实习期间就已经切切实实体味到了，真的是，感觉走到哪儿都有它家的门店。所以这次就投了一波简历来尝试一下。

总的来说，链家笔试的题目中规中矩，2个小时，20道选择题+3道编程题。选择题全是Android相关的基础知识，有些Android编程经验的都能做个八九不离十。编程题则是重点考察dp，难度还是有的。我只A了2.8道，有一题多重背包，dp解的，复杂度超了，只过了82%。下面来贴一下题目和个人见解，欢迎有能力全A的大神指教~

笔试题

---

笔试时间：2017年09月02日 19:00--21:00
  考试类型：链家2018招聘京外笔试（Android研发工程师）

链家网.jpg

01.分小球问题

题目描述：

01.png

题目解析：

这题说是往杯子里倒水，实际上，就是高中数学接触的那种分小球问题，只是换了种说法。我在此就将其称为分小球问题了吧。

本题可以转化为这样的题目：有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.两端取数问题

题目描述：

03.png

题目解析：

这题描述有点长，读了好一会儿才明白题意。（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.多重背包问题

题目描述：

02.png

题目解析：

这是典型的多重背包问题。因为最后没什么时间了，用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;
    }