一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 4329|回复: 30
收起左侧

facebook 电面

[复制链接] |试试Instant~ |关注本帖
andy198423 发表于 2014-10-29 23:31:52 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Fail

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
一道很简单的题,结果自己脑抽,绕进去了. Waral 鍗氬鏈夋洿澶氭枃绔,
string 有多少palindrome substring。
exp: 'aba' 返回4 , 'abba' 返回6

评分

5

查看全部评分

本帖被以下淘专辑推荐:

  • · fb|主题: 33, 订阅: 16
干.什么 发表于 2015-3-25 07:13:32 | 显示全部楼层
干.什么 发表于 2015-3-25 07:12
public static int partition(String s) {
        int count = 0;
        // single char is palin ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
哎呀忘记格式啦!
  1.     public static int partition(String s) {
  2.         int count = 0;
  3.         // single char is palindrome. visit 1point3acres.com for more.
  4.         for (int i = 0; i < s.length(); i++) count++;
  5.         for (int i = 1; i < s.length(); i++) {.1point3acres缃
  6.             // even position
  7.             for (int l = i - 1, r = i; l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r); l--, r++) {
  8.                 count++;
  9.             }
  10.             // odd
  11.             for (int l = i - 1, r = i + 1; l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r); l--, r++) {
  12.                 count++;
  13.             }
  14.         }
  15.         return count;
  16.     }
复制代码
回复 支持 2 反对 0

使用道具 举报

francisyang 发表于 2014-10-30 03:08:05 | 显示全部楼层
这个题我以前自己做过,不过只有O(n^2)的方法,不过代码很少,想法也比较直接。:check所有的连续substring 是否是palindrome ,  存进hashmap,最后输出map的key的数量。
代码就不贴了。
回复 支持 0 反对 1

使用道具 举报

e5399014 发表于 2014-10-31 01:49:14 | 显示全部楼层
根据输入输出,是不需要检查重复的, 'abba' 返回6。 所以用dp来做,代码如下:
public class Solution{

public int palindrome(String s) {
    if (s.length()==0) return 0;. 1point 3acres 璁哄潧
    if (s.length()==1) return 1;. 1point3acres.com/bbs

    int num=0;. 1point3acres.com/bbs
    //initialize the table
    int[][] table= new int[s.length()][s.length()];
    for (int i=0; i<s.length(); i++) {. 鍥磋鎴戜滑@1point 3 acres
        table[i][i]=1;
        num+=1;
    }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    for (int i=0; i<s.length()-1; i++) {
        if (s.charAt(i)==s.charAt(i+1)){
            table[i][i+1]=1;. 鍥磋鎴戜滑@1point 3 acres
            num+=1;
        }else{
            table[i][i+1]=0;
        }

    }

    // looping

    for (int len=3; len<=s.length(); len++) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        for (int i=0; i<=s.length()-len; i++) {
            if (s.charAt(i)==s.charAt(i+len-1) && table[i+1][i+len-2]==1){
                table[i][i+len-1]=1;. From 1point 3acres bbs
                num+=1;
            }else{
                table[i][i+len-1]=0;  
            }
        }
.鏈枃鍘熷垱鑷1point3acres璁哄潧    }

    return num;

}
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
}

评分

2

查看全部评分

回复 支持 1 反对 0

使用道具 举报

byrlhb 发表于 2014-10-30 00:13:40 | 显示全部楼层
谢楼主分享,继续加油了!
回复 支持 反对

使用道具 举报

rengokantai 发表于 2014-10-30 00:25:32 | 显示全部楼层
这是lc原题。一个月前我面f全职遇到的也是lc原题,做出来了,但是面试官让我优化,我不会,所以fail。他家的面试题lc里的不少。
回复 支持 反对

使用道具 举报

byrlhb 发表于 2014-10-30 00:36:29 | 显示全部楼层
rengokantai 发表于 2014-10-30 00:25.鐣欏璁哄潧-涓浜-涓夊垎鍦
这是lc原题。一个月前我面f全职遇到的也是lc原题,做出来了,但是面试官让我优化,我不会,所以fail。他家 ...

跟leetcode还是不一样的
回复 支持 反对

使用道具 举报

 楼主| andy198423 发表于 2014-10-30 01:00:23 | 显示全部楼层
rengokantai 发表于 2014-10-30 00:25
这是lc原题。一个月前我面f全职遇到的也是lc原题,做出来了,但是面试官让我优化,我不会,所以fail。他家 ...

这个不是原题,我开始也觉得像原题,所以一边扯一边找,然后自己就乱了
其实还不如直接自己分析,自己解,题也不难
所以我觉得大家还是别太依赖原题,思路最重要
回复 支持 反对

使用道具 举报

frozenplay 发表于 2014-10-30 23:33:37 | 显示全部楼层
francisyang 发表于 2014-10-30 03:08.1point3acres缃
这个题我以前自己做过,不过只有O(n^2)的方法,不过代码很少,想法也比较直接。:check所有的连续substring ...
. 1point3acres.com/bbs
lc原题不是可以dp优化么,因为一个长的String是palindrome,那就暗示start+1, end-1也是
最变态的是一种Manacher's algorithm,不过面试应该写不出来
回复 支持 反对

使用道具 举报

clfhaha1234 发表于 2014-10-30 23:48:04 | 显示全部楼层
恩,感觉和ON回文方法类似,这题应该还是ON的最优解吧,只是判重的话多个hashtable罢了
回复 支持 反对

使用道具 举报

Neal_kks 发表于 2014-11-24 17:31:44 | 显示全部楼层
我一开始理解错题目了,居然YY成跟子序列差不多的那种情况,感觉好复杂。。原题还是挺好写的,贴一下我的c++代码,大家看看有没有bug。
  1. #include <iostream>
  2. #include <string>
  3. using namespace std;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  4. . 鍥磋鎴戜滑@1point 3 acres
  5. const int MAX = 1002;
  6. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  7. int dp[MAX][MAX];.1point3acres缃

  8. void solve(string &s){
  9.     int len = s.length();
  10.     for(int i=0;i<len;++i){
    . visit 1point3acres.com for more.
  11.         for(int j=0;j<len;++j){
  12.             dp[i][j] = i>=j?1:0;
  13.         }
  14.     }
  15.     int res = len;
  16.     for(int k=2;k<=len;++k){
  17.         for(int i=0;i<len;++i){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  18.             int j = i+k-1;
  19.             if(j>=len)  break;
  20.             if(s[i] == s[j] && dp[i+1][j-1] == 1){. 鍥磋鎴戜滑@1point 3 acres
  21.                 dp[i][j] = 1;
  22.                 ++res;
  23.             }
  24.             
  25.         }
  26.     }
  27.     printf("%d\n", res);
  28. }

  29. int main(){. 1point 3acres 璁哄潧
  30.     string s;
  31.     while(cin>>s){
  32.         solve(s);
  33.     }
  34. }
复制代码
回复 支持 反对

使用道具 举报

GLambda 发表于 2014-11-24 18:58:42 | 显示全部楼层
直接枚举对称中点O(n),然后枚举长度O(n),计数就行,也是O(n^2)的。
回复 支持 反对

使用道具 举报

头像被屏蔽
whuwangyi 发表于 2014-11-24 22:20:59 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

njuprincerain 发表于 2014-11-24 22:48:08 | 显示全部楼层
最近也有同学被问这题, 要求o(1)空间复杂度
回复 支持 反对

使用道具 举报

还来得及吗 发表于 2014-11-25 00:27:38 | 显示全部楼层
njuprincerain 发表于 2014-11-24 22:48
最近也有同学被问这题, 要求o(1)空间复杂度
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
O(1)空间就是楼上说的枚举吧?不用DP的那种O(N^2)的算法
回复 支持 反对

使用道具 举报

njuprincerain 发表于 2014-11-25 00:30:38 | 显示全部楼层
是的, 因为用了dp然后悲剧
回复 支持 反对

使用道具 举报

pyemma 发表于 2014-11-25 08:11:51 | 显示全部楼层
这道题你用DP还不如不用,使用DP的话是严格O(n^2)的复杂度,而使用枚举的话严格复杂度是O(nk),其中k是最长回文的回文半径。这样可以达到O(1)空间
回复 支持 反对

使用道具 举报

lilihao2014 发表于 2014-11-26 02:36:20 | 显示全部楼层
为什么aba是4,abba是6????能枚举一下吗
回复 支持 反对

使用道具 举报

dragonmigo 发表于 2014-11-26 04:23:10 | 显示全部楼层
lilihao2014 发表于 2014-11-26 02:36
为什么aba是4,abba是6????能枚举一下吗

aba:.1point3acres缃
{a, b, a, aba}

abba:. 1point 3acres 璁哄潧
{a, b, b, a, bb, abba}

每一个single character 也是一个 palindrome string
回复 支持 反对

使用道具 举报

lilihao2014 发表于 2014-11-26 23:13:35 | 显示全部楼层
dragonmigo 发表于 2014-11-26 04:23.鐣欏璁哄潧-涓浜-涓夊垎鍦
aba:. From 1point 3acres bbs
{a, b, a, aba}

懂了懂了!O(∩_∩)O谢谢
回复 支持 反对

使用道具 举报

北航小涵 发表于 2015-3-18 07:36:08 | 显示全部楼层
这叫做DP么?。。。
很直接的思想做一下。这个题目的变形题https://leetcode.com/problems/longest-palindromic-substring/
设定一个boolean[j]代表i~j是否是一个回文。最后数一下boolean数组里面的true的个数就ok了。
快速的方法是 如果我们已经知道 i-1, j-1是一个回文,并s.charAt(i) == s.charAt(j)的话 那么i j 就是一个回文了。
举个栗子,abba, 已经处理了bb了,存在了flag[1][2], 那么flag[0][3] = flag[1][2] && ('a' == 'a') = true;
所以第一步初始化1和相邻位置. 鍥磋鎴戜滑@1point 3 acres
然后枚举长度,依次递推。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 19:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表