> For the complete documentation index, see [llms.txt](https://fantasy-jxf.gitbook.io/artificial-intelligence/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://fantasy-jxf.gitbook.io/artificial-intelligence/interview/bi-shi-shun-feng-180917.md).

# 顺丰

* 选择 30，编程 2

## Index

* [编辑距离](https://fantasy-jxf.gitbook.io/artificial-intelligence/interview/pages/-L_GZbFo9BkO5w7j5D_-#编辑距离)
* [分发糖果](https://fantasy-jxf.gitbook.io/artificial-intelligence/interview/pages/-L_GZbFo9BkO5w7j5D_-#分发糖果)

## 编辑距离

> LeetCode [72. 编辑距离](https://leetcode-cn.com/problems/edit-distance/description/)

**思路**

* 动态规划

**C++**（AC）

```cpp
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. 分发糖果](https://leetcode-cn.com/problems/candy/description/)

**思路**

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

**C++**（AC）

```cpp
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;
    }
};
```