facebook 电面

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

干.什么 发表于 2015-3-25 07:13
哎呀忘记格式啦！

这个解法好像不太对。。

干.什么 发表于 2015-3-25 07:13
哎呀忘记格式啦！

sorry,好像是对的。
另外感觉没必要单算单个字符的数量。
我改了一下：

1. public static int partition(String s) {
   
2.         int count = 0;
   
3.         for (int i = 0; i < s.length(); i++) {
   
4.             for (int l = i, r = i; l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r); l--, r++) {
   
5.                 count++;
   
6.             }
   
7.             for (int l = i, r = i + 1; l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r); l--, r++) {
   
8.                 count++;
   
9.             }
   
10.         }
    
11.         return count;
    
12.     }

复制代码

下面这个solution对么？

1. public static int numPalindrome(String s) {
   
2.                 int ret = s.length();
   
3.                 // 以i为中心, 以j为半径 判断
   
4.                 for (int i = 0; i < s.length(); i++) {
   
5.                         boolean pal1 = true;
   
6.                         boolean pal2 = true;
   
7.                         for (int j = 1; j + i <= s.length() && i - j >= 0; j++) {
   
8.                                 // 偶数长度case
   
9.                                 if (j + i < s.length() && s.charAt(i + j) == s.charAt(i - j)
   
10.                                                 && pal1) {
    
11.                                         ret++;
    
12.                                 } else {
    
13.                                         pal1 = false;
    
14.                                 }
    
15.                                 // 奇数长度case
    
16.                                 if (s.charAt(i + j - 1) == s.charAt(i - j) && pal2) {
    
17.                                         ret++;
    
18.                                 } else {
    
19.                                         pal2 = false;
    
20.                                 }
    
21.                         }
    
22.                 }
    
23.                 return ret;
    
24.         }

复制代码

aba 为啥返回4.。。。。。。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

pandafolk 发表于 2015-3-18 07:36
这叫做DP么？。。。
很直接的思想做一下。这个题目的变形题https://leetcode.com/problems/longest-palind ...

同意。感觉这道题是memorization而非dp

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

得到i->max palindrome length 的map后再来每个算一遍就可以了，那个map就是leetcode原题要求出来的