GOOGLE ONSITE9/29

第二题可以这么dp: 求str和翻转str的longest common subsequence，然后剩下的部分就是必须要删的

第二题确实是面筋题，如果理解没错的话，第二题应该是求longest palindrome subsequence的变形。如果求出subsequence的长度，那么要删除的chars就是 total - len(longest Palindrome Subsequence)

http://www.geeksforgeeks.org/dynamic-programming-set-12-longest-palindromic-subsequence/

nothingtrouble 发表于 2015-11-13 23:21
第二题确实是面筋题，如果理解没错的话，第二题应该是求longest palindrome subsequence的变形。如果求出su ...

应该是这样的，写了下代码。

1. public class LongestPalindromicSubsequenceByDeleting {
   
2.        
   
3.         public static void main(String[] args) {
   
4.                 String s = "abcdesc";
   
5.                 System.out.println(leastCharacterDeleted(s));
   
6.         }
   
7.        
   
8.         public static int leastCharacterDeleted(String str) {
   
9.                 int len = getLongestPalindromicSubsequence(str);
   
10.                 return str.length() - len;
    
11.         }
    
12. 
    
13.         public static int getLongestPalindromicSubsequence(String str) {
    
14.                 if (str == null || str.length() == 0) {
    
15.                         return 0;
    
16.                 }
    
17.                 int len = str.length();
    
18.                 int[][] dp = new int[len][len];
    
19.                 for (int i = 0; i < len; i++) {
    
20.                         dp[i][i] = 1;
    
21.                 }
    
22.                 for (int cl = 2; cl <= len; cl++) {
    
23.                         for (int i = 0; i < len - cl + 1; i++) {
    
24.                                 int j = i + cl - 1;
    
25.                                 if (str.charAt(i) == str.charAt(j) && cl == 2) {
    
26.                                         dp[i][j] = 2;
    
27.                                 } else if (str.charAt(i) == str.charAt(j)) {
    
28.                                         dp[i][j] = dp[i + 1][j - 1] + 2;
    
29.                                 } else {
    
30.                                         dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
    
31.                                 }
    
32.                         }
    
33.                 }
    
34.                
    
35.                 return dp[0][len - 1];
    
36.         }
    
37. }
    

复制代码

面我的第一个华人面试官告诉我Java的HashMap没有remove function，别自己乱想一个乱用=。=我也是呵呵了，最后也是栽在他手上了，无话可说

bill701 发表于 2015-11-12 12:48
第四题可不可以利用数学的思想呢？char的话就把他映射到1-256上。分别对两个str算出他们各自的乘积和相加的 ...

你这个应该可以，不过直接hashmap或者array[]不就是可以了，都是O(1)space和O(n)time啊

请问第三题O(1)SPACE记录路径如何做，是改变原矩阵？

bobzhang2004 发表于 2015-12-9 11:18
请问第三题O(1)SPACE记录路径如何做，是改变原矩阵？

这么久我哪记得 。。大概是你从左边来2D ARRAY的VALUE就变成负的。。

楼主为啥没有店面呢？ CMU的？

aiwojiujiu 发表于 2016-1-23 21:51
楼主为啥没有店面呢？ CMU的？

实习有GG的OFFER 免电面的 然并卵哟

majiamajia 发表于 2016-1-24 03:05
实习有GG的OFFER 免电面的 然并卵哟

楼主遇到三哥  没办法  来年再搞！！！