滴滴笔试题来聊一聊

我是算法岗，第一题排列小球，过了100%，第二题没过，就不说了 第一题递归的方***超时，主要是有重复计算，使用数组保存结果就好了，避免重复计算，是动规的思想。 动规用四维数组保存状态值，用四元组表示一个状态（上一个球的颜色，P球的剩余数量，Q球的剩余数量，R球的剩余数量），上一个球颜色为-1表示初始状态，说明下一个球可以是任意球，上一个球为0表示为P球，下一个球只能为Q或者R，上一个球为Q球、R球时同理。 递归代码： #include <bits/stdc++.h> using namespace std; int total; int dfs(vector<int>& nums, int last, int len) {  if (len == total)   return 1;  int cnt = 0;  for (int i = 0; i < 3; i++)  {   if (i != last && nums[i] > 0)   {    nums[i]--;    cnt += dfs(nums, i, len + 1);    nums[i]++;   }  }  return cnt; } int main() {  vector<int> nums(3, 0);  for (int i = 0; i < 3; i++)  {   cin >> nums[i];   total += nums[i];  }  int res = dfs(nums, -1, 0);  cout << res << endl;     return 0; } 动规代码： #include <bits/stdc++.h> using namespace std; long total; long dfs(vector<long>& nums, long last, long len, vector<vector<vector<vector<long>>>>& dp) {  if (len == total)   return 1;     if(dp[last + 1][nums[0]][nums[1]][nums[2]] > 0) {         return dp[last + 1][nums[0]][nums[1]][nums[2]];     } else {         long cnt = 0;         for (int i = 0; i < 3; i++)         {             if (i != last && nums[i] > 0)             {                 nums[i]--;                 cnt += dfs(nums, i, len + 1, dp);                 nums[i]++;             }         }         dp[last + 1][nums[0]][nums[1]][nums[2]] = cnt;         return cnt;     } } int main() {  vector<long> nums(3, 0);  for (int i = 0; i < 3; i++)  {   cin >> nums[i];   total += nums[i];  }     vector<vector<vector<vector<long>>>> dp(4, vector<vector<vector<long>>>(nums[0] + 1, vector<vector<long>>(nums[1] + 1, vector<long>(nums[2] + 1, 0))));  long res = dfs(nums, -1, 0, dp);  cout << res << endl;     return 0; } 动规代码是从递归改过来的，可能不是太简洁。

第二题 https://www.geeksforgeeks.org/ways-to-arrange-balls-such-that-adjacent-balls-are-of-different-types/

写了好久只有第一道题57%。。第二个动规压根没看 哎。。

清华的大佬都直接缴械了？

劝退笔试+1😂

第一题a了71%，第二题33%，凉凉，选择题忘了好多知识，网络全忘了

最小编辑距离那道，AC class Solution:     def minDistance(self, word1, word2):         m = len(word1)         n = len(word2)         tuple_1 = "q w e r t a s d f g z x c v".split()         tuple_2 = "y u i o p h j k l b n m".split()         t = 3         dp = [i * t for i in range(n + 1)]         last_v = 0         for i in range(1, m + 1):             dp[0] = i * t             last_v = (i - 1) * t             for j in range(1, n + 1):                 tmp = dp[j]                 a = word1[i - 1]                 b = word2[j - 1]                 replace_score = 2                 if (a in tuple_1 and b in tuple_1) or (a in tuple_2 and b in tuple_2):                     replace_score = 1                 if word1[i - 1] == word2[j - 1]:                     dp[j] = last_v                 else:                     left = dp[j - 1]                     up = dp[j]                     left_up = last_v                     dp[j] = min(left + t, min(left_up + replace_score, up + t))                 last_v = tmp         return dp[-1] if __name__ == "__main__":     istr = [s for s in input().split()]     o_s = istr[0]     dict_s = istr[1:]     scores = []     solution = Solution()     for d_s in dict_s:         score = solution.minDistance(o_s, d_s)         scores.append((d_s, score))     scores.sort(key=lambda x: x[1])     print(" ".join([v[0] for v in scores[:3]]))

第二题我用的全排列，递归超时了。。。2333

想知道为啥编辑距离那道题只过了71%，有什么需要注意的点嘛？

选择感觉很变态了 编程虽然做的一般 但是算不上变态

为啥我第二题dfs是0.17啊

第二题自己测感觉还ok ，然后就0%了

第一题，检查拼写错误，没有考虑添加后还需要修改的情况A了57% 第二题，同色小球不相邻的组合数，想了半小时没有思路，最后print(0)A了17% 凉的很彻底。。。

哈哈哈0飘过

我也是0.17 用的回溯

PHP levenshtein 了解一下，求最短编辑距离，可以设置权重，不过 题目变换权重的要求满足不了（汗）

第二题不是司机行驶轨迹那个吗

第二个用递归时间复杂度高吗？我也没过，67%

字符串0.86，小球0.67（TLE）。都用的递归

两道题都没啥难度啊，两道题都可以DP一下，字符串编辑距离具体可以看我的博客： https://www.cnblogs.com/lishiyao/p/6426241.html