虾皮9.14笔试

三道都是简化的板子题

第一题

给出每个位置的过路费，求从左上角到右下角的最小花费是多少。
只允许往下或者往右走。
数据范围只有100直接暴力搜索即可。

int minPathSum(vector<vector<int> >& grid) {  
    int m = grid.size();  
    int n = grid[0].size();  
    int res = 1e8 + 5;  
    vector<vector<int>> dir = {{0,1},{1,0}};  
    function<void(int, int, int)> dfs = [&](int x, int y, int now) {  
        if (x == m - 1 && y == n - 1) {  
            res = min(res, now);  
            return ;  
        }  
        for (int i = 0; i < 2; i++) {  
            int xx = x + dir[i][0];  
            int yy = y + dir[i][1];  
            if (xx < 0 || xx >= m || yy < 0 || yy >= n) continue;  
            dfs(xx, yy, now + grid[xx][yy]);  
        }  
    };  
    dfs(0,0,grid[0][0]);  
    return res;  
}

第二题

给出零钱和对应的商品列表，如何尽量花掉这些零钱
也就是体积和价值相同的01背包问题。

int pickGoods(vector<int>& goods_list, int balance) {  
    //体积与价值相同  
    int n = goods_list.size();  
    vector<vector<int>> dp(n + 1, vector<int>(balance + 1, 0));  
    for (int i = 0; i < n; i++) {  
        //dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - goods_list[i]]);  
        //由于对应只选择一次，需要倒序获取  
        for (int j = balance; j >= goods_list[i]; j--) {  
            dp[i + 1][j] = max(dp[i][j], dp[i][j - goods_list[i]] + goods_list[i]);  
        }  
    }  
    return dp[n][balance];  
}

第三题

给出摆动队列的定义是数组中数字大小变化是波浪形。要求数组中能获得的最长摆动子数组长度为多少。
给出的数据范围是1000，直接使用两个数组分别维护以i为开始往上摆动或者往下摆动的长度。
遍历i之后的所有位置进行状态转移，时间复杂度为\(O(n^2)\)

int wiggleMaxLength(vector<int> nums, int numsLen) {  
    // 维护每个数字后面第一个比它大的数字或者比它小的下标  
    int n = numsLen;  
    vector<int> dp1(n + 1, 1);//后面更大  
    vector<int> dp2(n + 1, 1);  
    for (int i = n - 1; i >= 0; i--) {  
        for (int j = i + 1; j < n; j++) {  
            if (nums[j] > nums[i]) dp1[i] = max(dp1[i], dp2[j] + 1);  
            else if (nums[j] < nums[i]) dp2[i] = max(dp2[i], dp1[j] + 1);  
            else {  
                dp1[i] = max(dp1[i], dp1[j]);  
                dp2[i] = max(dp2[i], dp2[j]);  
            }  
        }  
    }  
    int ans = 0;  
    for (int i = 0; i < n; i++) {  
        ans = max(ans, dp1[i]);  
        ans = max(ans, dp2[i]);  
    }  
    return ans;  
}