a***e
发帖数: 413 | 1 刷题巨慢。。。。。
看那些DP的题看得头大，有人面试碰到这个题吗？
https://oj.leetcode.com/problems/scramble-string/
一点都不想做，不知道什么人会出这些题，要弄个三维的table，太夸张了。 |
S********0
发帖数: 5749 | 2
据说是google的，我觉得面试能用backtracking做出来就可以了。 dp好像效率也没高
太多
【在 a***e 的大作中提到】
: 刷题巨慢。。。。。
: 看那些DP的题看得头大，有人面试碰到这个题吗？
: https://oj.leetcode.com/problems/scramble-string/
: 一点都不想做，不知道什么人会出这些题，要弄个三维的table，太夸张了。
|
l*****a
发帖数: 14598 | 3 没有
skip 吧
【在 a***e 的大作中提到】
: 刷题巨慢。。。。。
: 看那些DP的题看得头大，有人面试碰到这个题吗？
: https://oj.leetcode.com/problems/scramble-string/
: 一点都不想做，不知道什么人会出这些题，要弄个三维的table，太夸张了。
|
y*****e
发帖数: 712 | 4 亲我们抱头痛哭好了，我一直都觉得有些面试题根本就是反社会反人类，碰到了就两手
一摊，直接认栽。。。这题是难在思路，我最最恨的是那个word ladder 2, 在网上找
的最简洁的答案也是5重loop， 我真的不知道为什么要出这样的题来折磨一个普通的
sde. |
l*****a
发帖数: 14598 | 5 这种题面试写的能work就可以了
谁说一定要过LC呢？
【在 y*****e 的大作中提到】
: 亲我们抱头痛哭好了，我一直都觉得有些面试题根本就是反社会反人类，碰到了就两手
: 一摊，直接认栽。。。这题是难在思路，我最最恨的是那个word ladder 2, 在网上找
: 的最简洁的答案也是5重loop， 我真的不知道为什么要出这样的题来折磨一个普通的
: sde.
|
S*******C
发帖数: 822 | 6 哈哈
【在 y*****e 的大作中提到】
: 亲我们抱头痛哭好了，我一直都觉得有些面试题根本就是反社会反人类，碰到了就两手
: 一摊，直接认栽。。。这题是难在思路，我最最恨的是那个word ladder 2, 在网上找
: 的最简洁的答案也是5重loop， 我真的不知道为什么要出这样的题来折磨一个普通的
: sde.
|
a***e
发帖数: 413 | 7 我感觉word ladder 2的思路比这道题还容易点，算法还比较出名，就是很不好写。。
。。。。。。
yuxrose (鱼香肉丝), 我倒是找到两个比较简洁的答案，但是最烦recursion。。。。
。。我觉得自己都缺乏动力搞懂这个题，也可能今天状态不佳。看答案都不清楚为啥，
都想放弃刷题啦！
但是花时间仔细琢磨，第一个答案好像也不是那么那么难，但第二个就不知道在干嘛了
，搞了3d table。晕啊！哪位大牛能解释一下呢？
如果没见过，谁能15分钟内搞懂题意，到写完代码，估计得下了狠功夫的。
这个有recursion还比没有recursion的快！
class Solution {
private:
bool isDeformation(string &s1, string &s2)
{
if(s1.size() != s2.size())return false;
int albe[26] = {0};
for(int i = 0; i < s1.size(); i ++)
albe[s1[i] - 'a'] ++;
for(int i = 0; i < s2.size(); i ++)
{
albe[s2[i] - 'a'] --;
if(albe[s2[i] - 'a'] < 0)return false;
}
return true;
}
public:
bool isScramble(string s1, string s2) {
if(isDeformation(s1, s2))
{
int len = s1.size();
if(len <= 3) return true;
for(int i = 1; i < s1.size(); i ++)
{
string s11 = s1.substr(0, i);
string s12 = s1.substr(i, len-i);
if(isScramble(s11, s2.substr(0,i)) && isScramble(s12, s2.
substr(i, len-i)))
return true;
if(isScramble(s11, s2.substr(len-i,i)) && isScramble(s12, s2
.substr(0, len-i)))
return true;
}
}
return false;
}
};
class Solution {
public:
bool isScramble(string s1, string s2) {
int len=s1.size();
if (len!=s2.size()) return false;
bool dp[100][100][100]={false};
for (int i=len-1;i>=0;i--)
for (int j=len-1;j>=0;j--) {
dp[i][j][1]=(s1[i]==s2[j]);
for (int l=2;i+l<=len && j+l<=len;l++) {
for (int n=1;n
dp[i][j][l]|=dp[i][j][n]&&dp[i+n][j+n][l-n];
dp[i][j][l]|=dp[i][j+l-n][n]&&dp[i+n][j][l-n];
}
}
}
return dp[0][0][len];
}
}; |
i*******e
发帖数: 114 | 8 千万别迷信什么leetcode，题里边很多的都不会在真正的面试里出现。基本不太可能在
45分钟内搞定，所谓的0-1 question，就是要么做出来，要么一点思路没有得0分。
比如 Google等公司更不会考leetcode原题。也就FB等公司面试官比较懒，还经常出点
原题 ;)
关键是你算法和编程得基本功。
【在 a***e 的大作中提到】
: 刷题巨慢。。。。。
: 看那些DP的题看得头大，有人面试碰到这个题吗？
: https://oj.leetcode.com/problems/scramble-string/
: 一点都不想做，不知道什么人会出这些题，要弄个三维的table，太夸张了。
|
a***e
发帖数: 413 | 9 请问大牛怎么才能在短期内提高算法和编程的基本功呢？
多谢！
【在 i*******e 的大作中提到】
: 千万别迷信什么leetcode，题里边很多的都不会在真正的面试里出现。基本不太可能在
: 45分钟内搞定，所谓的0-1 question，就是要么做出来，要么一点思路没有得0分。
: 比如 Google等公司更不会考leetcode原题。也就FB等公司面试官比较懒，还经常出点
: 原题 ;)
: 关键是你算法和编程得基本功。
|
l*****a
发帖数: 14598 | 10 你多大？
问点成熟的问题好不？
【在 a***e 的大作中提到】
: 请问大牛怎么才能在短期内提高算法和编程的基本功呢？
: 多谢！
|
|
|
p*****2
发帖数: 21240 | 11 这道题当初是f面亚洲acm金牌出的
一般人应该不会被面到
【在 a***e 的大作中提到】
: 刷题巨慢。。。。。
: 看那些DP的题看得头大，有人面试碰到这个题吗？
: https://oj.leetcode.com/problems/scramble-string/
: 一点都不想做，不知道什么人会出这些题，要弄个三维的table，太夸张了。
|
p*****2
发帖数: 21240 | 12 wl2是出名的算法吗？
【在 a***e 的大作中提到】
: 我感觉word ladder 2的思路比这道题还容易点，算法还比较出名，就是很不好写。。
: 。。。。。。
: yuxrose (鱼香肉丝), 我倒是找到两个比较简洁的答案，但是最烦recursion。。。。
: 。。我觉得自己都缺乏动力搞懂这个题，也可能今天状态不佳。看答案都不清楚为啥，
: 都想放弃刷题啦！
: 但是花时间仔细琢磨，第一个答案好像也不是那么那么难，但第二个就不知道在干嘛了
: ，搞了3d table。晕啊！哪位大牛能解释一下呢？
: 如果没见过，谁能15分钟内搞懂题意，到写完代码，估计得下了狠功夫的。
: 这个有recursion还比没有recursion的快！
: class Solution {
|
y****e
发帖数: 25 | 13 可以用recursion:
public boolean isScramble(String s1, String s2) {
if (s1.length() != s2.length()) return false;
if (s1.equals(s2)) return true;
char []c1 = s1.toCharArray();
char []c2 = s2.toCharArray();
Arrays.sort(c1);
Arrays.sort(c2);
if (!Arrays.equals(c1, c2)) return false;
for (int i = 1; i < s1.length(); i++) {
String s11 = s1.substring(0, i);
String s12 = s1.substring(i);
String s21 = s2.substring(0, i);
String s22 = s2.substring(i);
if (isScramble(s11, s21) && isScramble(s12, s22)) return true;
s21 = s2.substring(s2.length() - i);
s22 = s2.substring(0, s2.length() - i);
if (isScramble(s11, s21) && isScramble(s12, s22)) return true;
}
return false;
}
【在 a***e 的大作中提到】
: 我感觉word ladder 2的思路比这道题还容易点，算法还比较出名，就是很不好写。。
: 。。。。。。
: yuxrose (鱼香肉丝), 我倒是找到两个比较简洁的答案，但是最烦recursion。。。。
: 。。我觉得自己都缺乏动力搞懂这个题，也可能今天状态不佳。看答案都不清楚为啥，
: 都想放弃刷题啦！
: 但是花时间仔细琢磨，第一个答案好像也不是那么那么难，但第二个就不知道在干嘛了
: ，搞了3d table。晕啊！哪位大牛能解释一下呢？
: 如果没见过，谁能15分钟内搞懂题意，到写完代码，估计得下了狠功夫的。
: 这个有recursion还比没有recursion的快！
: class Solution {
|
y*****e
发帖数: 712 | 14 我今天状态也不好，尤其是长假，yy自己可以做至少20题，结果一半也没做完，特别捉
急。我觉得其实弄懂一道难题不如花时间去弄2道medium难的题，或者3-4道简单题。。
。尤其时间不够的情况下。
【在 a***e 的大作中提到】
: 我感觉word ladder 2的思路比这道题还容易点，算法还比较出名，就是很不好写。。
: 。。。。。。
: yuxrose (鱼香肉丝), 我倒是找到两个比较简洁的答案，但是最烦recursion。。。。
: 。。我觉得自己都缺乏动力搞懂这个题，也可能今天状态不佳。看答案都不清楚为啥，
: 都想放弃刷题啦！
: 但是花时间仔细琢磨，第一个答案好像也不是那么那么难，但第二个就不知道在干嘛了
: ，搞了3d table。晕啊！哪位大牛能解释一下呢？
: 如果没见过，谁能15分钟内搞懂题意，到写完代码，估计得下了狠功夫的。
: 这个有recursion还比没有recursion的快！
: class Solution {
|
a***e
发帖数: 413 | 15 同感，有时候越急越没动力做。我是在细水长流的做题。前面做过的忘了不少。
下周起又是见缝插针啦。
【在 y*****e 的大作中提到】
: 我今天状态也不好，尤其是长假，yy自己可以做至少20题，结果一半也没做完，特别捉
: 急。我觉得其实弄懂一道难题不如花时间去弄2道medium难的题，或者3-4道简单题。。
: 。尤其时间不够的情况下。
|
