s*e
2 楼
我实话实说，第一次的时候10分钟，
beats 100%的solution,
那题的官解很傻逼，属于想太多的解法。
beats 100%的solution,
那题的官解很傻逼，属于想太多的解法。
b*s
3 楼
可否贴下你的SOLUTION？比如说INPUT是两个同样维度的LIST，每个LIST的ITEM都是存
的是数字，求ED
结果。
的是数字，求ED
结果。
s*e
4 楼
https://leetcode.com/problems/one-edit-distance/
是不是这题？
【在 b********s 的大作中提到】
: 可否贴下你的SOLUTION？比如说INPUT是两个同样维度的LIST，每个LIST的ITEM都是存
: 的是数字，求ED
: 结果。
是不是这题？
【在 b********s 的大作中提到】
: 可否贴下你的SOLUTION？比如说INPUT是两个同样维度的LIST，每个LIST的ITEM都是存
: 的是数字，求ED
: 结果。
A*g
5 楼
这个太简单了 我以为是算两个string的edit distance
【在 s********e 的大作中提到】
: https://leetcode.com/problems/one-edit-distance/
: 是不是这题？
【在 s********e 的大作中提到】
: https://leetcode.com/problems/one-edit-distance/
: 是不是这题？
b*s
6 楼
72. Edit Distance
: 这个太简单了 我以为是算两个string的edit distance
【在 A******g 的大作中提到】
: 这个太简单了 我以为是算两个string的edit distance
: 这个太简单了 我以为是算两个string的edit distance
【在 A******g 的大作中提到】
: 这个太简单了 我以为是算两个string的edit distance
n*g
7 楼
看了几分钟。应该可以。很久没刷题。比不上年轻人了。
【在 b********s 的大作中提到】
: 72. Edit Distance
:
:
: 这个太简单了 我以为是算两个string的edit distance
:
【在 b********s 的大作中提到】
: 72. Edit Distance
:
:
: 这个太简单了 我以为是算两个string的edit distance
:
s*e
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
:
过程如下：
#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
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
9 楼
5min bug free吧，这个是有意防水，要珍惜机会啊
s*e
10 楼
我去，第一次做就能那么牛逼？
看来我要继续努力了。
【在 y**********u 的大作中提到】
: 5min bug free吧，这个是有意防水，要珍惜机会啊
看来我要继续努力了。
【在 y**********u 的大作中提到】
: 5min bug free吧，这个是有意防水，要珍惜机会啊
l*r
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
:
对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
12 楼
N年前linkedIn 面试被问到这题，当时没刷过，当场一脸懵逼。
相关阅读
上次激动完还没有消息什么是Will you be providing mental health services as defined above?问一个男生面试着装问题Help! How to keep working before getting the EAD card?Bloomberg网上测试题H1b Transfer 被拒错过500强的ONSITE 面试安排，该郁闷么？感慨下，还是CS的机会多呀opt 可以在学期结束之前开始吗关于Intel一问请问Consulting是做什么呢？能这样negotiate salary 吗？怎么向USCIC要I797？renew H1B, 有效期从什么时候开始？有没有postdoc后去了工业界的朋友？～～请进问一个题目，谢谢。expert, pls help on one interview questionINTEL LAB BARCELONA 招人急问：OPT后的grace period发几个国内的猎头公布的招聘职位