Facabook Intern 2.17面经

adrianliu729 发表于 2017-2-19 09:40
longest increasing subsequence 也是不连续的

你指的longest palindromic substring是lc上的吗？lc上的是连续的

英伦十六世纪 发表于 2017-2-19 09:43
你指的longest palindromic substring是lc上的吗？lc上的是连续的

subsequence 不是 substring. 子序列不等于子串。。。。

adrianliu729 发表于 2017-2-19 10:17
subsequence 不是 substring. 子序列不等于子串。。。。

直接报个lc题号吧，可能我找的lc的题目不是层主所指的那题

英伦十六世纪 发表于 2017-2-19 10:24
直接报个lc题号吧，可能我找的lc的题目不是层主所指的那题

300. Longest Increasing Subsequence

adrianliu729 发表于 2017-2-19 06:35
public class Solution {
   //given a sorted array with no dups
   //O(n^2) time, O(n^2) space

方法不错。。。。

我也分享一个dp的思路，可以用int[] dp保存当前的最大subsequence长度，set[] diffs保存当前最大长度的差值。每步更新的时候（假设第i），初始化最大长度max为1，遍历i之前的dp，若有与max相等的，把新的diff加入。若有大于max的，清空diffs，加入新的diff，更新max。复杂度也是o(n^2)

这题leetcode上有类似的吗？

lz 是一面还是二面啊？

这题好像用不着这么麻烦吧，LC446变种？

1. public class Solution {
   
2.     public int maxLenArithmeticSeq(int[] nums) {
   
3.         int n = nums.length;
   
4.         HashMap<Integer, Integer>[] map = new HashMap[n];
   
5.         int max = 0;
   
6.         for (int i = 0; i < nums.length; i++) {
   
7.             map[i] = new HashMap<>();
   
8.             for (int j = 0; j < i; j++) {
   
9.                 int diff = nums[i] - nums[j];
   
10.                 int count1 = map[i].getOrDefault(diff, 1);
    
11.                 int count2 = map[j].getOrDefault(diff, 1);
    
12.                 int len = Math.max(count2 + 1, count1);
    
13.                 max = Math.max(max, len);
    
14.                 map[i].put(diff, len);
    
15.             }
    
16.         }
    
17.         return max;
    
18.     }
    
19. }

复制代码