b********s
发帖数: 436 | 1 不是SDE职位，假如之前没刷过，第一次碰到这种题。如果是变种呢，有信心没？ |
s********e
发帖数: 1 | 2 我实话实说，第一次的时候10分钟，
beats 100%的solution,
那题的官解很傻逼，属于想太多的解法。 |
b********s
发帖数: 436 | 3 可否贴下你的SOLUTION？比如说INPUT是两个同样维度的LIST，每个LIST的ITEM都是存
的是数字，求ED
结果。 |
s********e
发帖数: 1 | 4 https://leetcode.com/problems/one-edit-distance/
是不是这题？
【在 b********s 的大作中提到】
: 可否贴下你的SOLUTION？比如说INPUT是两个同样维度的LIST，每个LIST的ITEM都是存
: 的是数字，求ED
: 结果。
|
A******g
发帖数: 1 | 5 这个太简单了 我以为是算两个string的edit distance
【在 s********e 的大作中提到】
: https://leetcode.com/problems/one-edit-distance/
: 是不是这题？
|
b********s
发帖数: 436 | 6 72. Edit Distance
: 这个太简单了 我以为是算两个string的edit distance
【在 A******g 的大作中提到】
: 这个太简单了 我以为是算两个string的edit distance
|
n********g
发帖数: 6504 | 7 看了几分钟。应该可以。很久没刷题。比不上年轻人了。
【在 b********s 的大作中提到】
: 72. Edit Distance
:
:
: 这个太简单了 我以为是算两个string的edit distance
:
|
s********e
发帖数: 1 | 8 刚才试了一下，第一次面试遇到的话，
过程如下：
#1， 10分钟之内写完这个，超时
int min = Math.Max(word1.Length, word2.Length);
for(int i = 0; i < word1.Length; i++)
{
for(int j = 0; j < word2.Length; j++)
{
if(word1[i] == word2[j])
{
int left = MinDistance(word1left, word2left);
int right = MinDistance(word1right, word2right);
min = Math.Min(min, left + right);
}
}
}
#2 琢磨了一下，觉得应该是记忆化，30分钟左右写完。
Dictionary dp;
public int MinDistance(string word1, string word2) {
if(dict.ContainsKey(key)) return dict[key];
int min = Math.Max(word1.Length, word2.Length);
for(int i = 0; i < word1.Length; i++)
{
for(int j = 0; j < word2.Length; j++)
{
if(word1[i] == word2[j])
{
int left = MinDistance(word1left, word2left);
int right = MinDistance(word1right, word2right);
min = Math.Min(min, left + right);
}
}
}
dict.Add(key, min);
return min;
}
#3
写完之后感觉应该用dp，看了官解果然是dp,
然后自己写了一遍dp，第一遍漏了初始化边界。。。。
int n = word1.Length;
int m = word2.Length;
int[,] dp = new int[n + 1, m + 1];
//第一遍忘了下面2行，尼玛。。。
for(int i = 0; i < n; i++) dp[i + 1, 0] = i+1;
for(int i = 0; i < m; i++) dp[0, i + 1] = i+1;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
dp[i+1, j+1] = Math.Min(dp[i, j+1], dp[i+1, j]) + 1;
dp[i+1, j+1] = Math.Min(dp[i+1, j+1], dp[i, j] + (word1[i] =
= word2[j] ? 0 : 1));
}
}
return dp[n, m];
感觉题目不难，dp里面算中等吧，但是就是没想到。
鄙视自己还是大婶，不是大神。
【在 b********s 的大作中提到】
: 72. Edit Distance
:
:
: 这个太简单了 我以为是算两个string的edit distance
:
|
y**********u
发帖数: 2839 | 9 5min bug free吧，这个是有意防水，要珍惜机会啊 |
s********e
发帖数: 1 | 10 我去，第一次做就能那么牛逼？
看来我要继续努力了。
【在 y**********u 的大作中提到】
: 5min bug free吧，这个是有意防水，要珍惜机会啊
|
l******r
发帖数: 1 | 11 凡事求maximum， minimum，optimum的问题，一般都用DP。
对DP来说，只要找到state transfer equation，问题就解决了。
state transfer equation 首先要找到state， 对这个问题来讲就是两个string的长度
l1，l2
还有action，
action作用于state，然后state的变化。
还有就是value function是state 的函数。
有些DP很难，比如merge stone和pop balloon。首先state 就难找。
这些和reinforcement learning里面的markov decision process很像。
【在 b********s 的大作中提到】
: 72. Edit Distance
:
:
: 这个太简单了 我以为是算两个string的edit distance
:
|
u******d
发帖数: 166 | 12 N年前linkedIn 面试被问到这题，当时没刷过，当场一脸懵逼。 |
