问两道面试中碰到的题目 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问两道面试中碰到的题目

问两道面试中碰到的题目# JobHunting - 待字闺中

j*62013-02-20 08:02

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*i2013-02-20 08:02

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 的大作中提到】

: 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*22013-02-20 08:02

3 楼

不错的题目。第一题BFS，第二题DP

j*62013-02-20 08:02

4 楼

请二爷明示~ BFS从哪里开始呢~ 刚刷题不久，基础知识还是不行啊~

【在 p*****2 的大作中提到】

: 不错的题目。第一题BFS，第二题DP

p*22013-02-20 08:02

5 楼

都走一遍就可以了。如果已经走过的标记一下，不会重复走。

【在 j*********6 的大作中提到】

: 请二爷明示~ BFS从哪里开始呢~ 刚刷题不久，基础知识还是不行啊~

r*n2013-02-20 08:02

6 楼

第二题 DP是O(N^2)吧，不知道会不会有更好的方法。

【在 p*****2 的大作中提到】

: 不错的题目。第一题BFS，第二题DP

w*a2013-02-20 08:02

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*22013-02-20 08:02

8 楼

是N^2

【在 r*********n 的大作中提到】

: 第二题 DP是O(N^2)吧，不知道会不会有更好的方法。

f*t2013-02-20 08:02

9 楼

两道好题，建议加进leetcode :D

d*e2013-02-20 08:02

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 的大作中提到】

g*o2013-02-20 08:02

11 楼

不是N^3吗？

【在 p*****2 的大作中提到】

:
: 是N^2

B*t2013-02-20 08:02

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 的大作中提到】

p*22013-02-20 08:02

13 楼

可以优化

【在 g*****o 的大作中提到】

: 不是N^3吗？

g*e2013-02-20 08:02

14 楼

大牛写个看看，我不会

【在 p*****2 的大作中提到】

:
: 可以优化

p*22013-02-20 08:02

15 楼

用scala吗？

【在 g**e 的大作中提到】

: 大牛写个看看，我不会

p*22013-02-20 08:02

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+1)(j-1)))){
pos(i)(j)=true
dp(i)=math.min(dp(i), 1+dp(j+1))
}

return dp(0)-1
}

B*t2013-02-20 08:02

17 楼

2爷，你的这个是在扫的过程中就isPalindrom()了么

(i

【在 p*****2 的大作中提到】

: 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: +1)(j-1)))){
: pos(i)(j)=true
: dp(i)=math.min(dp(i), 1+dp(j+1))
: }

j*62013-02-20 08:02

18 楼

多谢以上各位大牛们的精彩解答~
有没有大牛可以提供一下第一题的代码？
先谢过啦~

p*22013-02-20 08:02

19 楼

是

【在 B********t 的大作中提到】

: 2爷，你的这个是在扫的过程中就isPalindrom()了么
:
: (i

B*t2013-02-20 08:02

20 楼

和KMP求next[]是不是有点类似

【在 p*****2 的大作中提到】

:
: 是

p*22013-02-20 08:02

21 楼

感觉比KMP要简单呀。next[]是啥东西。

【在 B********t 的大作中提到】

: 和KMP求next[]是不是有点类似

p*22013-02-20 08:02

22 楼

我一会儿有时间写一个吧。

【在 j*********6 的大作中提到】

: 多谢以上各位大牛们的精彩解答~
: 有没有大牛可以提供一下第一题的代码？
: 先谢过啦~

c*t2013-02-20 08:02

23 楼

二爷这个解法牛，不过为啥要反着来走？

(i

【在 p*****2 的大作中提到】

:
: 我一会儿有时间写一个吧。

B*t2013-02-20 08:02

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 的大作中提到】

: 第二题：
: 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*t2013-02-20 08:02

25 楼

next[]就是那个记录不匹配时下一个开始匹配位置的数组。
和KMP那个不一样。。是我弄错了。。

【在 p*****2 的大作中提到】

:
: 我一会儿有时间写一个吧。

c*t2013-02-20 08:02

26 楼

看完大家第二题精彩的回答，俺又扫了一眼题
保存切法！！！

【在 j*********6 的大作中提到】

B*t2013-02-20 08:02

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 的大作中提到】

: 看完大家第二题精彩的回答，俺又扫了一眼题
: 保存切法！！！

f*t2013-02-20 08:02

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*22013-02-20 08:02

29 楼

这个不是关键。

【在 c********t 的大作中提到】

: 看完大家第二题精彩的回答，俺又扫了一眼题
: 保存切法！！！

p*22013-02-20 08:02

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(iiqueue+=(x+ii)*m+(y+jj)
v(x+ii)(y+jj)=true
}
}
if(fill) set.foreach{v=>mat(v/m)(v%m)=1}
}
}

for(i}

c*t2013-02-20 08:02

31 楼

你这个比我自己写的简洁，值得借鉴，试试改成O(N^2)的吧

【在 B********t 的大作中提到】

: 好吧。保存切法。
: 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*t2013-02-20 08:02

32 楼

2爷可不可以写个c++或java的 n^2的版本啊。。scala那个看不明白。。

【在 p*****2 的大作中提到】

: 第一题
: 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*22013-02-20 08:02

33 楼

习惯了。

【在 c********t 的大作中提到】

: 二爷这个解法牛，不过为啥要反着来走？
:
: (i

p*22013-02-20 08:02

34 楼

scala又被鄙视了。：（

【在 B********t 的大作中提到】

: 2爷可不可以写个c++或java的 n^2的版本啊。。scala那个看不明白。。

Y*f2013-02-20 08:02

35 楼

全部走一遍要一个visit数组吧，只需要对是O的边缘元素做bfs/dfs就可以了。

【在 p*****2 的大作中提到】

:
: scala又被鄙视了。：（

p*22013-02-20 08:02

36 楼

边缘元素是不需要变色的。那些需要变色的怎么办？

【在 Y********f 的大作中提到】

: 全部走一遍要一个visit数组吧，只需要对是O的边缘元素做bfs/dfs就可以了。

Y*f2013-02-20 08:02

37 楼

恩，我弄反了。不过可以在这些bfs/dfs中标记一下，比如标记成*, 然后所有O变为X，
*变O，好像也挺麻烦的。

【在 p*****2 的大作中提到】

:
: 边缘元素是不需要变色的。那些需要变色的怎么办？

p*22013-02-20 08:02

38 楼

可以这么做。coding更麻烦一些。我用visited就是想让code简单点。

【在 Y********f 的大作中提到】

: 恩，我弄反了。不过可以在这些bfs/dfs中标记一下，比如标记成*, 然后所有O变为X，
: *变O，好像也挺麻烦的。

b*e2013-02-20 08:02

39 楼

I finally realized that's Martin Odersky. That's why it looks familiar.

【在 p*****2 的大作中提到】

:
: 可以这么做。coding更麻烦一些。我用visited就是想让code简单点。

p*22013-02-20 08:02

40 楼

lol. 我刚在twitter上follow他，感觉像在follow我自己。

【在 b***e 的大作中提到】

: I finally realized that's Martin Odersky. That's why it looks familiar.

B*t2013-02-20 08:02

41 楼

啊。。我上面的代码就是这么搞的。。

【在 Y********f 的大作中提到】

: 恩，我弄反了。不过可以在这些bfs/dfs中标记一下，比如标记成*, 然后所有O变为X，
: *变O，好像也挺麻烦的。

z*t2013-02-20 08:02

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 的大作中提到】

d*x2013-02-20 08:02

43 楼

第一题直接就是union-find的基本应用
遇到O就Union便是，和边界有接触的O和一个特殊的点Union
最后走一遍isConnected就有结果。

【在 z******t 的大作中提到】

: 就第二题写了篇博客，供参考：
: 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矩阵，用来标记原矩阵中的字
: 符是否已经被访问。