华为3.31机试AK题解

第三题leetcode有类似题：https://leetcode-cn.com/problems/freedom-trail/

然而贪心(75)过的比暴力回溯(65)还多

求题目呜呜呜

复习一下，防止复试被问到 class Solution { public:     int findRotateSteps(string ring, string key) {         int m = key.size(), n = ring.size();         vector<vector<int>> pos(26, vector<int>(0, 0));         for (int i = 0; i < n; i++) {             pos[ring[i] - 'a&(417)#39;].push_back(i);         }         vector<vector<int>> dp(m, vector<int>(n, 0x3f3f3f3f));         for (auto j:pos[key[0] - 'a&(417)#39;]) {             dp[0][j] = min(j, n - j);         }         for (int i = 1; i < m; i++) {             for (auto j:pos[key[i] - 'a&(417)#39;]) {                 for (auto k:pos[key[i - 1] - 'a&(417)#39;]) {                     dp[i][j] = min(dp[i][j], dp[i - 1][k] + min(abs(k - j), n - abs(k - j)));                 }             }         }         int min = INT_MAX;         for (auto item:dp[m - 1]) {             if (item < min) {                 min = item;             }         }         return min + m;     } };

第三题确实不会用dp😂坐等大佬更新😁

等大佬更新

坐等大佬解第三题，dp真的好难

蹲

感觉回溯剪枝了有可能过 `int traceback(int cur , int bushu , int now){// 当前所在点， 已经走了多少步 ，即将要匹配pat中的哪一个` 1. 如果准备匹配的字符是唯一的，毋庸置疑往左或者往右找最短的就是唯一路径 2.如果匹配的字符不是唯一的，不能所有点都开回溯(极端例子，主串abbbbbbbbbbbq, 目标串abq)，只需要开2个点的回溯就可以了，一个向右走一个向左走。(这里剪枝了很多) 但是硬算时间复杂度还是过不了的(指数级别)，似乎华为样例没有很严格 白给白给

第1题知道怎么做，但是样例2没看懂，求个解答 a-b 3:0 a-c 2:1 b-a 1:1 c-a 0:1 b-c 4:3 c-b 2:2 输出是：a 10,b 5,c 1 搞不明白，

第二题跟楼主一个思路，没过，其他ac了

好厉害啊，你是华工计院/软院大佬吗

最后一题对i和i-1取模是什么意思？