j*********6 发帖数: 407 | 1 Q1:
给你一个n * n 的二维char数组 内部存的是 'X' 和 'O',形式如下
X X X X X
X O O O X
X X O O X
X X X O X
X O X X X
学要编写一个函数将被'X'包围的'O'统统变成'X'
比如下标为 (1,1) (1,2) (1,3) (2,2) (2,3) (3,3)的'O'需要被变成'X'
而下标为(4,1)的'O' 不需要变成'X'
Q2:
给定一个String str, 切n刀,使得每个substr都是回文的,求最小的n, 然后保存切
法,最后计算时间复杂度
例如: abbab 切一刀 变成 abba, b
第一次发帖 有什么问题请大家多多包涵~ |
l***i 发帖数: 1309 | 2 1. DFS, if a component can reach border, no change needed
2. try each prefix from length=1 to n, if prefix is palindrome, solve the
rest recursively. You need to use either recursion+memorization or bottom-up
dp for this.
【在 j*********6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Q1: : 给你一个n * n 的二维char数组 内部存的是 'X' 和 'O',形式如下 : X X X X X : X O O O X : X X O O X : X X X O X : X O X X X : 学要编写一个函数将被'X'包围的'O'统统变成'X' : 比如下标为 (1,1) (1,2) (1,3) (2,2) (2,3) (3,3)的'O'需要被变成'X' : 而下标为(4,1)的'O' 不需要变成'X'
|
p*****2 发帖数: 21240 | |
j*********6 发帖数: 407 | 4 请二爷明示~ BFS从哪里开始呢~ 刚刷题不久,基础知识还是不行啊~
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不错的题目。第一题BFS,第二题DP
|
p*****2 发帖数: 21240 | 5
都走一遍就可以了。如果已经走过的标记一下,不会重复走。
【在 j*********6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请二爷明示~ BFS从哪里开始呢~ 刚刷题不久,基础知识还是不行啊~
|
r*********n 发帖数: 4553 | 6 第二题 DP是O(N^2)吧,不知道会不会有更好的方法。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不错的题目。第一题BFS,第二题DP
|
w****a 发帖数: 710 | 7 第二题
int minpalin(string str){
int leng = str.size();
vector dp(leng+1);
for(int i = 0; i <= leng; i++)
dp[i] = leng-i;
for(int i = leng-1; i >= 0; i--){
for(int j = i; j < leng; j++){
if(isPalindrome(str.substr(i,j-i+1))){
if((j == leng-1 || dp[j+1]!=0) &&
dp[i] > dp[j]+1){
dp[i] = dp[j+1]+1;
}
}
}
}
return dp[0]-1;
} |
p*****2 发帖数: 21240 | 8
是N^2
【在 r*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第二题 DP是O(N^2)吧,不知道会不会有更好的方法。
|
f*******t 发帖数: 7549 | |
d******e 发帖数: 164 | 10 贴个第二题:
def palindrome(s):
dp = range(-1, len(s))
for i in xrange(1, len(s)+1):
for j in xrange(i):
if is_palindrome(s[j:i]):
dp[i] = min(dp[i], dp[j]+1)
return dp[-1]
【在 j*********6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Q1: : 给你一个n * n 的二维char数组 内部存的是 'X' 和 'O',形式如下 : X X X X X : X O O O X : X X O O X : X X X O X : X O X X X : 学要编写一个函数将被'X'包围的'O'统统变成'X' : 比如下标为 (1,1) (1,2) (1,3) (2,2) (2,3) (3,3)的'O'需要被变成'X' : 而下标为(4,1)的'O' 不需要变成'X'
|
|
|
g*****o 发帖数: 1637 | 11 不是N^3吗?
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 是N^2
|
B********t 发帖数: 147 | 12 第二题:
int minPalindrom(sting &s)
{
vector dp(s.size(), INT_MAX);
for(int i = 0; i < s.size(); i++)
if(isPalindrom(s.substr(0, i+1)))
{
dp[i] = 0;
continue;
}
else
for(int j = 1; j <= i; j++)
if(isPalindrom(s.substr(j, i-j+1)) && dp[j-1] != INT_MAX)
dp[i] = min(dp[i], dp[j-1]+1);
return dp[s.size()-1];
}
第一题怎么个DFS法啊,为啥我只能想到从border上的O出发DFS,找到所有不能变的O..
....
【在 j*********6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Q1: : 给你一个n * n 的二维char数组 内部存的是 'X' 和 'O',形式如下 : X X X X X : X O O O X : X X O O X : X X X O X : X O X X X : 学要编写一个函数将被'X'包围的'O'统统变成'X' : 比如下标为 (1,1) (1,2) (1,3) (2,2) (2,3) (3,3)的'O'需要被变成'X' : 而下标为(4,1)的'O' 不需要变成'X'
|
p*****2 发帖数: 21240 | 13
可以优化
【在 g*****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不是N^3吗?
|
g**e 发帖数: 6127 | 14 大牛写个看看,我不会
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 可以优化
|
p*****2 发帖数: 21240 | 15
用scala吗?
【在 g**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 大牛写个看看,我不会
|
p*****2 发帖数: 21240 | 16 def solve(s:String):Int={
val n=s.length
val pos=Array.ofDim[Boolean](n,n)
val dp=Array.tabulate(n+1)(i=>n-i)
for(i<-n-1 to 0 by -1; j<-i until n if(s(i)==s(j) && (j-i<2 || pos(i
+1)(j-1)))){
pos(i)(j)=true
dp(i)=math.min(dp(i), 1+dp(j+1))
}
return dp(0)-1
} |
B********t 发帖数: 147 | 17 2爷,你的这个是在扫的过程中就isPalindrom()了么
(i
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : def solve(s:String):Int={ : val n=s.length : val pos=Array.ofDim[Boolean](n,n) : val dp=Array.tabulate(n+1)(i=>n-i) : : for(i<-n-1 to 0 by -1; j<-i until n if(s(i)==s(j) && (j-i<2 || pos(i : +1)(j-1)))){ : pos(i)(j)=true : dp(i)=math.min(dp(i), 1+dp(j+1)) : }
|
j*********6 发帖数: 407 | 18 多谢以上各位大牛们的精彩解答~
有没有大牛可以提供一下第一题的代码?
先谢过啦~ |
p*****2 发帖数: 21240 | 19
是
【在 B********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 2爷,你的这个是在扫的过程中就isPalindrom()了么 : : (i
|
B********t 发帖数: 147 | 20 和KMP求next[]是不是有点类似
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 是
|
|
|
p*****2 发帖数: 21240 | 21
感觉比KMP要简单呀。next[]是啥东西。
【在 B********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 和KMP求next[]是不是有点类似
|
p*****2 发帖数: 21240 | 22
我一会儿有时间写一个吧。
【在 j*********6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 多谢以上各位大牛们的精彩解答~ : 有没有大牛可以提供一下第一题的代码? : 先谢过啦~
|
c********t 发帖数: 5706 | 23 二爷这个解法牛,不过为啥要反着来走?
(i
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我一会儿有时间写一个吧。
|
B********t 发帖数: 147 | 24 第一题写了一个很蠢的,不要笑我。。。。。。测了几个case好像是work的。。。。。
O(n^2)
void DFS(vector &matrix, vector > &visited, int x, int
y, int size)
{
visited[x][y] = true;
matrix[x][y] = '#';
if(y-1 >= 0 && matrix[x][y-1] == 'O' && !visited[x][y-1])
DFS(matrix, visited, x, y-1, size);
if(x+1 < size && matrix[x+1][y] == 'O' && !visited[x+1][y])
DFS(matrix, visited, x+1, y, size);
if(y+1 < size && matrix[x][y+1] == 'O' && !visited[x][y+1])
DFS(matrix, visited, x, y+1, size);
if(x-1 >= 0 && matrix[x-1][y] == 'O' && !visited[x-1][y])
DFS(matrix, visited, x-1, y, size);
}
void OOOO_XXXX(vector &matrix)
{
vector > visited(matrix.size(), vector(matrix.size(),
false));
for(int i = 0; i < matrix.size(); i++)
{
if(matrix[0][i] == 'O')
DFS(matrix, visited, 0, i, matrix.size());
if(matrix[i][0] == 'O')
DFS(matrix, visited, i, 0, matrix.size());
if(matrix[i][matrix.size()-1] == 'O')
DFS(matrix, visited, i, matrix.size()-1, matrix.size());
if(matrix[matrix.size()-1][i] == 'O')
DFS(matrix, visited, matrix.size()-1, i, matrix.size());
}
for(int i = 0; i < matrix.size(); i++)
for(int j = 0; j < matrix.size(); j++)
if(matrix[i][j] == '#')
matrix[i][j] = 'O';
else
if(matrix[i][j] == 'O')
matrix[i][j] = 'X';
}
【在 B********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第二题: : int minPalindrom(sting &s) : { : vector dp(s.size(), INT_MAX); : for(int i = 0; i < s.size(); i++) : if(isPalindrom(s.substr(0, i+1))) : { : dp[i] = 0; : continue; : }
|
B********t 发帖数: 147 | 25 next[]就是那个记录不匹配时下一个开始匹配位置的数组。
和KMP那个不一样。。是我弄错了。。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我一会儿有时间写一个吧。
|
c********t 发帖数: 5706 | 26 看完大家第二题精彩的回答,俺又扫了一眼题
保存切法!!!
【在 j*********6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Q1: : 给你一个n * n 的二维char数组 内部存的是 'X' 和 'O',形式如下 : X X X X X : X O O O X : X X O O X : X X X O X : X O X X X : 学要编写一个函数将被'X'包围的'O'统统变成'X' : 比如下标为 (1,1) (1,2) (1,3) (2,2) (2,3) (3,3)的'O'需要被变成'X' : 而下标为(4,1)的'O' 不需要变成'X'
|
B********t 发帖数: 147 | 27 好吧。保存切法。
map > cut;
int minPalindrom(sting &s)
{
vector dp(s.size(), INT_MAX);
for(int i = 0; i < s.size(); i++)
if(isPalindrom(s.substr(0, i+1)))
{
dp[i] = 0;
continue;
}
else
for(int j = 1; j <= i; j++)
{
if(isPalindrom(s.substr(j, i-j+1)) && dp[j-1] != INT_MAX)
{
if(dp[j-1]+1 < dp[i])
{
cut[i] = cut[j-1];
cut[i].push_back(j);
dp[i] = dp[j-1]+1;
}
}
}
return dp[s.size()-1];
}
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 看完大家第二题精彩的回答,俺又扫了一眼题 : 保存切法!!!
|
f*******t 发帖数: 7549 | 28 看不懂前面第二题的解法,自己写了个O(n^3)的
public class MinPalindromeSplits {
private int[][] dp;
private boolean isPalindrome(String s) {
if (s.length() < 2)
return true;
for (int i = 0; i <= s.length() / 2; i++) {
if (s.charAt(i) != s.charAt(s.length() - i - 1))
return false;
}
return true;
}
public int minSplits(String s) {
dp = new int[s.length() + 1][s.length() + 1];
for (int len = 1; len <= s.length(); len++) {
for (int start = 0; start + len <= s.length(); start++)
dp[start][start + len] =
isPalindrome(s.substring(start, start + len)) ? 0 :
Math.min((dp[start][start + len - 1] + 1), dp[start
+ 1][start + len] + 1);
}
return dp[0][s.length()];
}
public static void main(String[] args) {
MinPalindromeSplits m = new MinPalindromeSplits();
System.out.println(m.minSplits("abcba"));
System.out.println(m.minSplits("acbbc"));
}
} |
p*****2 发帖数: 21240 | 29
这个不是关键。
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 看完大家第二题精彩的回答,俺又扫了一眼题 : 保存切法!!!
|
p*****2 发帖数: 21240 | 30 第一题
def solve(mat:Array[Array[Int]]):Unit={
val n=mat.length
val m=mat(0).length
val v=Array.ofDim[Boolean](n,m)
def check(i:Int, j:Int):Unit={
val isOK=(x:Int,y:Int)=>{
x>=0 && x=0 && y
}
var fill=true
if(isOK(i,j)){
val set=collection.mutable.Set[Int]()
val queue=collection.mutable.Queue[Int]()
queue+=i*m+j
v(i)(j)=true
while(queue.nonEmpty){
val curr=queue.dequeue
set+=curr
val x=curr/m
val y=curr%m
if(x==0 || x==n-1 || y==0 || y==m-1) fill=false
for(ii<- -1 to 1; jj<- -1 to 1 if isOK(x+ii,y+jj)){
queue+=(x+ii)*m+(y+jj)
v(x+ii)(y+jj)=true
}
}
if(fill) set.foreach{v=>mat(v/m)(v%m)=1}
}
}
for(i<-0 until n; j<-0 until m) check(i,j)
} |
|
|
c********t 发帖数: 5706 | 31 你这个比我自己写的简洁,值得借鉴,试试改成O(N^2)的吧
【在 B********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好吧。保存切法。 : map > cut; : int minPalindrom(sting &s) : { : vector dp(s.size(), INT_MAX); : for(int i = 0; i < s.size(); i++) : if(isPalindrom(s.substr(0, i+1))) : { : dp[i] = 0; : continue;
|
B********t 发帖数: 147 | 32 2爷可不可以写个c++或java的 n^2的版本啊。。scala那个看不明白。。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一题 : def solve(mat:Array[Array[Int]]):Unit={ : val n=mat.length : val m=mat(0).length : val v=Array.ofDim[Boolean](n,m) : : def check(i:Int, j:Int):Unit={ : val isOK=(x:Int,y:Int)=>{ : x>=0 && x=0 && y: }
|
p*****2 发帖数: 21240 | 33
习惯了。
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 二爷这个解法牛,不过为啥要反着来走? : : (i
|
p*****2 发帖数: 21240 | 34
scala又被鄙视了。:(
【在 B********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 2爷可不可以写个c++或java的 n^2的版本啊。。scala那个看不明白。。
|
Y********f 发帖数: 410 | 35 全部走一遍要一个visit数组吧,只需要对是O的边缘元素做bfs/dfs就可以了。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : scala又被鄙视了。:(
|
p*****2 发帖数: 21240 | 36
边缘元素是不需要变色的。那些需要变色的怎么办?
【在 Y********f 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 全部走一遍要一个visit数组吧,只需要对是O的边缘元素做bfs/dfs就可以了。
|
Y********f 发帖数: 410 | 37 恩,我弄反了。不过可以在这些bfs/dfs中标记一下,比如标记成*, 然后所有O变为X,
*变O,好像也挺麻烦的。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 边缘元素是不需要变色的。那些需要变色的怎么办?
|
p*****2 发帖数: 21240 | 38
可以这么做。coding更麻烦一些。我用visited就是想让code简单点。
【在 Y********f 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 恩,我弄反了。不过可以在这些bfs/dfs中标记一下,比如标记成*, 然后所有O变为X, : *变O,好像也挺麻烦的。
|
b***e 发帖数: 1419 | 39 I finally realized that's Martin Odersky. That's why it looks familiar.
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 可以这么做。coding更麻烦一些。我用visited就是想让code简单点。
|
p*****2 发帖数: 21240 | 40
lol. 我刚在twitter上follow他,感觉像在follow我自己。
【在 b***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : I finally realized that's Martin Odersky. That's why it looks familiar.
|
|
|
B********t 发帖数: 147 | 41 啊。。我上面的代码就是这么搞的。。
【在 Y********f 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 恩,我弄反了。不过可以在这些bfs/dfs中标记一下,比如标记成*, 然后所有O变为X, : *变O,好像也挺麻烦的。
|
z******t 发帖数: 59 | 42 就第二题写了篇博客,供参考:
http://codercareer.blogspot.com/2013/02/no-43-minimal-number-of
第一题和我之前写的一篇博客中的题目类似:
http://codercareer.blogspot.com/2013/02/no-41-group-of-1s-in-ma
只是这里的题目要稍微麻烦一点:每遍历到一个'O'时,找出和它同组的所有'O'。如果
所有'O'都不在边界上(即该组被'X'包围),那么再把这个组的所有'O'都变成'X'。
解决这个问题可能需要定义一个大小和原矩阵相同的bool矩阵,用来标记原矩阵中的字
符是否已经被访问。
【在 j*********6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Q1: : 给你一个n * n 的二维char数组 内部存的是 'X' 和 'O',形式如下 : X X X X X : X O O O X : X X O O X : X X X O X : X O X X X : 学要编写一个函数将被'X'包围的'O'统统变成'X' : 比如下标为 (1,1) (1,2) (1,3) (2,2) (2,3) (3,3)的'O'需要被变成'X' : 而下标为(4,1)的'O' 不需要变成'X'
|
d**********x 发帖数: 4083 | 43 第一题直接就是union-find的基本应用
遇到O就Union便是,和边界有接触的O和一个特殊的点Union
最后走一遍isConnected就有结果。
【在 z******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 就第二题写了篇博客,供参考: : http://codercareer.blogspot.com/2013/02/no-43-minimal-number-of : 第一题和我之前写的一篇博客中的题目类似: : http://codercareer.blogspot.com/2013/02/no-41-group-of-1s-in-ma : 只是这里的题目要稍微麻烦一点:每遍历到一个'O'时,找出和它同组的所有'O'。如果 : 所有'O'都不在边界上(即该组被'X'包围),那么再把这个组的所有'O'都变成'X'。 : 解决这个问题可能需要定义一个大小和原矩阵相同的bool矩阵,用来标记原矩阵中的字 : 符是否已经被访问。
|