e***a
发帖数: 1661 | 1 1. Set Matrix Zeroes
Given a m x n matrix, if an element is 0, set its entire row and
column to 0. Do it in place.
How to devise a constant space solution?
2. Scramble String
Given a string s1, we may represent it as a binary tree by partitioning
it to two non-empty substrings recursively. To scramble the string,
we may choose any non-leaf node and swap its two children. Given two
strings s1 and s2 of the same length, determine if s2 is a scrambled string
of s1. |
e***a
发帖数: 1661 | 2 Nobody can solve these 2 leetcode questions? |
p*****2
发帖数: 21240 | |
Z*****Z
发帖数: 723 | 4 贴第二题：
import java.util.*;
public class Solution {
static Hashtable ht = new Hashtable();
static public boolean isScramble(String s1, String s2) {
if (s1.equals(s2)) {
return true;
}
if (s1.length() != s2.length()) {
return false;
}
String key = s1 + s2;
if(s1.compareTo(s2) > 0){
key = s2 + s1;
}
if(ht.containsKey(key)){
return ht.get(key);
}
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)) {
ht.put(key, true);
return true;
}
s21 = s2.substring(s2.length() - i);
s22 = s2.substring(0, s2.length() - i);
if (isScramble(s11, s21) && isScramble(s12, s22)) {
ht.put(key, true);
return true;
}
}
ht.put(key, false);
return false;
}
}
【在 p*****2 的大作中提到】
: 第二题太难了。我也每座
|
p*****2
发帖数: 21240 | 5
);
你太牛了。我还没心情想这题呢。
【在 Z*****Z 的大作中提到】
: 贴第二题：
: import java.util.*;
: public class Solution {
: static Hashtable ht = new Hashtable();
:
: static public boolean isScramble(String s1, String s2) {
: if (s1.equals(s2)) {
: return true;
: }
: if (s1.length() != s2.length()) {
|
p*****2
发帖数: 21240 | 6
我当时参与过讨论。大概知道怎么回事。recursion的应该不难，但是bottom up的当时
感觉还是有一定难度的。我就没继续想下去。
【在 Z*****Z 的大作中提到】
: 贴第二题：
: import java.util.*;
: public class Solution {
: static Hashtable ht = new Hashtable();
:
: static public boolean isScramble(String s1, String s2) {
: if (s1.equals(s2)) {
: return true;
: }
: if (s1.length() != s2.length()) {
|
Z*****Z
发帖数: 723 | 7 我不觉得这种题他们会让写了递归再写迭代或者写了迭代再写递归。搞一个自己舒服的
写法就行了吧。
【在 p*****2 的大作中提到】
:
: 我当时参与过讨论。大概知道怎么回事。recursion的应该不难，但是bottom up的当时
: 感觉还是有一定难度的。我就没继续想下去。
|
p*****2
发帖数: 21240 | 8
我觉得这题面试的时候递归应该就不错了。不过没有霸气了。像viisa, zhangchi肯定
是霸气十足的bottom up。 这题leetcode 仔细研究过bottom up说还可以。不过我还没
想过。现在没有G和F的面试，也没动力搞难题了。
【在 Z*****Z 的大作中提到】
: 我不觉得这种题他们会让写了递归再写迭代或者写了迭代再写递归。搞一个自己舒服的
: 写法就行了吧。
|
P***t
发帖数: 1006 | 9 递归的COMPLEXITY多少？我有个解法是O(N^3)，on character comparison level. 不
知道有没有更好的？
);
【在 Z*****Z 的大作中提到】
: 贴第二题：
: import java.util.*;
: public class Solution {
: static Hashtable ht = new Hashtable();
:
: static public boolean isScramble(String s1, String s2) {
: if (s1.equals(s2)) {
: return true;
: }
: if (s1.length() != s2.length()) {
|
o****o
发帖数: 1398 | |
|
|
P***t
发帖数: 1006 | 11 可以把两个字符串拆成四段来看。假如原字符串是：A B C D
中间交换 B C，应该得到：A C B D
(每次个大写字母代表一段字符，A D 可以是空).
用一个二维数组 X[i][j] 记录 S1从ｉ开始，S2从ｊ开始的相同字符的最大长度。譬如：
S1＝abcd
S2=cdab
then
X[0][0]=0
X[0][1]=0
X[0][2]=2 (ab -> ab)
X[0][2]=0
...
同时记录两头最大相同字串的长度。譬如：
S1=abxyz
S2=abyxz
那么 A 最大长度是2, D 最大长度是１.
Now,
for i = 1 to Length-1 // i is start of segment C in S1
for j = 0 to CommonPrefixLength // j is start of segment of C in S2 (
length of A)
for LenC = X[i][j] to 1 // LenC as the length of segment C
&& (i+LenC >= Length - CommonSuffixLength) // end of C must reside
in CommonSuffix.
LenA = j
LenB = i - LenA
if X[LenA][LenA+LenC] >= LenB // Common substring must be long
enough for B
return true
Not strictly checked for boundaries. But that's the idea.
【在 Z*****Z 的大作中提到】
: 我不觉得这种题他们会让写了递归再写迭代或者写了迭代再写递归。搞一个自己舒服的
: 写法就行了吧。
|
p*****2
发帖数: 21240 | 12
);
哈哈。我写了一个。跟你几乎一模一样。
HashMap hm = new HashMap();
public boolean isScramble(String s1, String s2)
{
if (s1 == null || s2 == null)
return false;
if (s1.length() != s2.length())
return false;
if (s1.equals(s2))
return true;
String key1 = s1 + ":" + s2;
String key2 = s2 + ":" + s1;
if (hm.containsKey(key1))
return hm.get(key1);
if (hm.containsKey(key2))
return hm.get(key2);
int n = s1.length();
boolean ret = false;
for (int i = 1; i < n; i++)
{
if (isScramble(s1.substring(0, i), s2.substring(0, i))
&& isScramble(s1.substring(i, n), s2.substring(i, n)))
{
ret = true;
break;
}
if (isScramble(s1.substring(0, i), s2.substring(n - i, n))
&& isScramble(s1.substring(i, n), s2.substring(0, n - i)
))
{
ret = true;
break;
}
}
hm.put(key1, ret);
return ret;
}
【在 Z*****Z 的大作中提到】
: 贴第二题：
: import java.util.*;
: public class Solution {
: static Hashtable ht = new Hashtable();
:
: static public boolean isScramble(String s1, String s2) {
: if (s1.equals(s2)) {
: return true;
: }
: if (s1.length() != s2.length()) {
|
p*****2
发帖数: 21240 | 13
为什么是N^4呢？
【在 Z*****Z 的大作中提到】
: 我不觉得这种题他们会让写了递归再写迭代或者写了迭代再写递归。搞一个自己舒服的
: 写法就行了吧。
|
Z*****Z
发帖数: 723 | 14 我错了，是N^3的
一共有N^2个子问题，用hashtable的话，每个子问题在第一次计算的时候会产生N个子子
问题，后来计算的时候是常数。所以总共是N^3的。
【在 p*****2 的大作中提到】
:
: 为什么是N^4呢？
|
S*******e
发帖数: 379 | 15 第一题有const space的solution吗？
string
【在 e***a 的大作中提到】
: 1. Set Matrix Zeroes
: Given a m x n matrix, if an element is 0, set its entire row and
: column to 0. Do it in place.
: How to devise a constant space solution?
: 2. Scramble String
: Given a string s1, we may represent it as a binary tree by partitioning
: it to two non-empty substrings recursively. To scramble the string,
: we may choose any non-leaf node and swap its two children. Given two
: strings s1 and s2 of the same length, determine if s2 is a scrambled string
: of s1.
|
r********g
发帖数: 1351 | 16 写了一个，可能有点罗嗦。。
class Solution {
public:
void setZeroes(vector > &M) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int nRow = M.size();
if(nRow <= 0) return;
int nCol = M[0].size();
if(nCol <= 0) return;
bool rowZero = false;
bool colZero = false;
for(int i = 0; i < nRow; i++) if(!M[i][0]) colZero = true;
for(int j = 0; j < nCol; j++) if(!M[0][j]) rowZero = true;
for(int i = 1; i < nRow; i++) {
for(int j = 1; j < nCol; j++){
if(M[i][j] == 0) {
M[i][0] = 0;
M[0][j] = 0;
}
}
}
for(int i = 1; i < nRow; i++) {
for(int j = 1; j < nCol; j++){
if(M[i][0] == 0 || M[0][j] == 0) M[i][j] = 0;
}
}
if(rowZero) for(int j = 0; j < nCol; j++) M[0][j] = 0;
if(colZero) for(int i = 0; i < nRow; i++) M[i][0] = 0;
}
}; |
S*******e
发帖数: 379 | 17 cool, thanks!
【在 r********g 的大作中提到】
: 写了一个，可能有点罗嗦。。
: class Solution {
: public:
: void setZeroes(vector > &M) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
:
: int nRow = M.size();
: if(nRow <= 0) return;
: int nCol = M[0].size();
|
e***a
发帖数: 1661 | 18 1. Set Matrix Zeroes
Given a m x n matrix, if an element is 0, set its entire row and
column to 0. Do it in place.
How to devise a constant space solution?
2. Scramble String
Given a string s1, we may represent it as a binary tree by partitioning
it to two non-empty substrings recursively. To scramble the string,
we may choose any non-leaf node and swap its two children. Given two
strings s1 and s2 of the same length, determine if s2 is a scrambled string
of s1. |
e***a
发帖数: 1661 | 19 Nobody can solve these 2 leetcode questions? |
p*****2
发帖数: 21240 | |
|
|
Z*****Z
发帖数: 723 | 21 贴第二题：
import java.util.*;
public class Solution {
static Hashtable ht = new Hashtable();
static public boolean isScramble(String s1, String s2) {
if (s1.equals(s2)) {
return true;
}
if (s1.length() != s2.length()) {
return false;
}
String key = s1 + s2;
if(s1.compareTo(s2) > 0){
key = s2 + s1;
}
if(ht.containsKey(key)){
return ht.get(key);
}
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)) {
ht.put(key, true);
return true;
}
s21 = s2.substring(s2.length() - i);
s22 = s2.substring(0, s2.length() - i);
if (isScramble(s11, s21) && isScramble(s12, s22)) {
ht.put(key, true);
return true;
}
}
ht.put(key, false);
return false;
}
}
【在 p*****2 的大作中提到】
: 第二题太难了。我也每座
|
p*****2
发帖数: 21240 | 22
);
你太牛了。我还没心情想这题呢。
【在 Z*****Z 的大作中提到】
: 贴第二题：
: import java.util.*;
: public class Solution {
: static Hashtable ht = new Hashtable();
:
: static public boolean isScramble(String s1, String s2) {
: if (s1.equals(s2)) {
: return true;
: }
: if (s1.length() != s2.length()) {
|
p*****2
发帖数: 21240 | 23
我当时参与过讨论。大概知道怎么回事。recursion的应该不难，但是bottom up的当时
感觉还是有一定难度的。我就没继续想下去。
【在 Z*****Z 的大作中提到】
: 贴第二题：
: import java.util.*;
: public class Solution {
: static Hashtable ht = new Hashtable();
:
: static public boolean isScramble(String s1, String s2) {
: if (s1.equals(s2)) {
: return true;
: }
: if (s1.length() != s2.length()) {
|
Z*****Z
发帖数: 723 | 24 我不觉得这种题他们会让写了递归再写迭代或者写了迭代再写递归。搞一个自己舒服的
写法就行了吧。
【在 p*****2 的大作中提到】
:
: 我当时参与过讨论。大概知道怎么回事。recursion的应该不难，但是bottom up的当时
: 感觉还是有一定难度的。我就没继续想下去。
|
p*****2
发帖数: 21240 | 25
我觉得这题面试的时候递归应该就不错了。不过没有霸气了。像viisa, zhangchi肯定
是霸气十足的bottom up。 这题leetcode 仔细研究过bottom up说还可以。不过我还没
想过。现在没有G和F的面试，也没动力搞难题了。
【在 Z*****Z 的大作中提到】
: 我不觉得这种题他们会让写了递归再写迭代或者写了迭代再写递归。搞一个自己舒服的
: 写法就行了吧。
|
P***t
发帖数: 1006 | 26 递归的COMPLEXITY多少？我有个解法是O(N^3)，on character comparison level. 不
知道有没有更好的？
);
【在 Z*****Z 的大作中提到】
: 贴第二题：
: import java.util.*;
: public class Solution {
: static Hashtable ht = new Hashtable();
:
: static public boolean isScramble(String s1, String s2) {
: if (s1.equals(s2)) {
: return true;
: }
: if (s1.length() != s2.length()) {
|
o****o
发帖数: 1398 | |
P***t
发帖数: 1006 | 28 可以把两个字符串拆成四段来看。假如原字符串是：A B C D
中间交换 B C，应该得到：A C B D
(每次个大写字母代表一段字符，A D 可以是空).
用一个二维数组 X[i][j] 记录 S1从ｉ开始，S2从ｊ开始的相同字符的最大长度。譬如：
S1＝abcd
S2=cdab
then
X[0][0]=0
X[0][1]=0
X[0][2]=2 (ab -> ab)
X[0][2]=0
...
同时记录两头最大相同字串的长度。譬如：
S1=abxyz
S2=abyxz
那么 A 最大长度是2, D 最大长度是１.
Now,
for i = 1 to Length-1 // i is start of segment C in S1
for j = 0 to CommonPrefixLength // j is start of segment of C in S2 (
length of A)
for LenC = X[i][j] to 1 // LenC as the length of segment C
&& (i+LenC >= Length - CommonSuffixLength) // end of C must reside
in CommonSuffix.
LenA = j
LenB = i - LenA
if X[LenA][LenA+LenC] >= LenB // Common substring must be long
enough for B
return true
Not strictly checked for boundaries. But that's the idea.
【在 Z*****Z 的大作中提到】
: 我不觉得这种题他们会让写了递归再写迭代或者写了迭代再写递归。搞一个自己舒服的
: 写法就行了吧。
|
p*****2
发帖数: 21240 | 29
);
哈哈。我写了一个。跟你几乎一模一样。
HashMap hm = new HashMap();
public boolean isScramble(String s1, String s2)
{
if (s1 == null || s2 == null)
return false;
if (s1.length() != s2.length())
return false;
if (s1.equals(s2))
return true;
String key1 = s1 + ":" + s2;
String key2 = s2 + ":" + s1;
if (hm.containsKey(key1))
return hm.get(key1);
if (hm.containsKey(key2))
return hm.get(key2);
int n = s1.length();
boolean ret = false;
for (int i = 1; i < n; i++)
{
if (isScramble(s1.substring(0, i), s2.substring(0, i))
&& isScramble(s1.substring(i, n), s2.substring(i, n)))
{
ret = true;
break;
}
if (isScramble(s1.substring(0, i), s2.substring(n - i, n))
&& isScramble(s1.substring(i, n), s2.substring(0, n - i)
))
{
ret = true;
break;
}
}
hm.put(key1, ret);
return ret;
}
【在 Z*****Z 的大作中提到】
: 贴第二题：
: import java.util.*;
: public class Solution {
: static Hashtable ht = new Hashtable();
:
: static public boolean isScramble(String s1, String s2) {
: if (s1.equals(s2)) {
: return true;
: }
: if (s1.length() != s2.length()) {
|
p*****2
发帖数: 21240 | 30
为什么是N^4呢？
【在 Z*****Z 的大作中提到】
: 我不觉得这种题他们会让写了递归再写迭代或者写了迭代再写递归。搞一个自己舒服的
: 写法就行了吧。
|
|
|
Z*****Z
发帖数: 723 | 31 我错了，是N^3的
一共有N^2个子问题，用hashtable的话，每个子问题在第一次计算的时候会产生N个子子
问题，后来计算的时候是常数。所以总共是N^3的。
【在 p*****2 的大作中提到】
:
: 为什么是N^4呢？
|
S*******e
发帖数: 379 | 32 第一题有const space的solution吗？
string
【在 e***a 的大作中提到】
: 1. Set Matrix Zeroes
: Given a m x n matrix, if an element is 0, set its entire row and
: column to 0. Do it in place.
: How to devise a constant space solution?
: 2. Scramble String
: Given a string s1, we may represent it as a binary tree by partitioning
: it to two non-empty substrings recursively. To scramble the string,
: we may choose any non-leaf node and swap its two children. Given two
: strings s1 and s2 of the same length, determine if s2 is a scrambled string
: of s1.
|
r********g
发帖数: 1351 | 33 写了一个，可能有点罗嗦。。
class Solution {
public:
void setZeroes(vector > &M) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int nRow = M.size();
if(nRow <= 0) return;
int nCol = M[0].size();
if(nCol <= 0) return;
bool rowZero = false;
bool colZero = false;
for(int i = 0; i < nRow; i++) if(!M[i][0]) colZero = true;
for(int j = 0; j < nCol; j++) if(!M[0][j]) rowZero = true;
for(int i = 1; i < nRow; i++) {
for(int j = 1; j < nCol; j++){
if(M[i][j] == 0) {
M[i][0] = 0;
M[0][j] = 0;
}
}
}
for(int i = 1; i < nRow; i++) {
for(int j = 1; j < nCol; j++){
if(M[i][0] == 0 || M[0][j] == 0) M[i][j] = 0;
}
}
if(rowZero) for(int j = 0; j < nCol; j++) M[0][j] = 0;
if(colZero) for(int i = 0; i < nRow; i++) M[i][0] = 0;
}
}; |
S*******e
发帖数: 379 | 34 cool, thanks!
【在 r********g 的大作中提到】
: 写了一个，可能有点罗嗦。。
: class Solution {
: public:
: void setZeroes(vector > &M) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
:
: int nRow = M.size();
: if(nRow <= 0) return;
: int nCol = M[0].size();
|
x*******6
发帖数: 262 | 35 挖个坟，试了试柏芝大牛的code，xiao和xaio返回是true，想半天也没发现怎么
scramble的，求大牛解答一下 |
l*****a
发帖数: 559 | 36 xiao
x iao
x ia o
x ai o
【在 x*******6 的大作中提到】
: 挖个坟，试了试柏芝大牛的code，xiao和xaio返回是true，想半天也没发现怎么
: scramble的，求大牛解答一下
|
H****s
发帖数: 247 | 37 给你点提示: 第一题就利用matrix的第一行和第一列做flag, 细节你自己就可以figure
out 啦！
Scramble string 昨天还是前天就有个技术含量十足的帖子在讨论！
http://www.mitbbs.com/article_t/JobHunting/32307045.html
【在 S*******e 的大作中提到】
: 第一题有const space的solution吗？
:
: string
|
