笔试-顺丰-180917.md

笔试-顺丰-180917

• 选择 30，编程 2

Index

• 编辑距离
• 分发糖果

编辑距离

LeetCode 72. 编辑距离

思路

• 动态规划

C++（AC）

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.length();
        int n = word2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        // 初始化 dp
        for (int i = 1; i <= m; i++)
            dp[i][0] = i;
        for (int j = 1; j <= n; j++)
            dp[0][j] = j;

        // 更新 dp
        for (int i = 1; i <=m; i++)
            for (int j = 1; j <= n; j++)
                if (word1[i - 1] == word2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = min({ dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1 });
            
        return dp[m][n];
    }
};

分发糖果

LeetCode 135. 分发糖果

思路

• 贪心：
  • 首先初始化每个人一个糖果，然后这个算法需要遍历两遍，
  • 第一遍从左向右遍历，如果右边的小盆友的等级高，等加一个糖果，这样保证了一个方向上高等级的糖果多。
  • 第二遍从右向左遍历，如果相邻两个左边的等级高，而左边的糖果又少的话，则左边糖果数为右边糖果数加一。
  • 最后再把所有小盆友的糖果数都加起来返回即可。

C++（AC）

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        
        vector<int> nums(n, 1);
        for (int i = 0; i < n - 1; ++i) {
            if (ratings[i + 1] > ratings[i]) 
                nums[i + 1] = nums[i] + 1;
        }
        
        for (int i = n - 1; i > 0; --i) {
            if (ratings[i - 1] > ratings[i]) 
                nums[i - 1] = max(nums[i - 1], nums[i] + 1);
        }
        
        int res = 0
        for (auto num : nums) 
            res += num;
        return res;
    }
};