招工网站店面和昂塞特

店面是高频 short word distance(不记得是1还是2）   和 nested integer求和那题（有权重的）  都是原题  店面三哥很nice全程好好好然后昂塞特
1.HM聊天 不记得问什么了
2.LC 其艺留
3.吃饭（小哥带我吃了沙拉，哭泣）
4.

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

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

lendge我一下他都说我觉得挺好的啊。。。。为什么就被三哥下黑手了哭泣
面试真的：天时地利人和缺一不可。。。
求大米作为安慰， 和好吃的食堂再见了

thanks for sharing, 请问第四题是 print 出来 回文subsequence 还是回文substring？ 谢谢

同问。这题不是传说中的挂人题吗

iamwds 发表于 2019-1-26 10:47
thanks for sharing, 请问第四题是 print 出来 回文subsequence 还是回文substring？ 谢谢

subsequence

好吃的食堂

第四题按照memoization的方法改写了一下。欢迎指正。但是实际上这种求set的题目只能针对length比较小的输入，如果太大了的话，output也太多了吧。

1. public class Solution {
   
2.     public Set<String> countPalindromicSubsequences(String S) {
   
3.         int len = S.length();
   
4.         TreeSet[] positions = new TreeSet[26];
   
5.         char[] arr = S.toCharArray();
   
6.         for (int i = 0; i < 26; i++) {
   
7.             positions[i] = new TreeSet<Integer>();
   
8.         }
   
9.         for (int i = 0; i < len; i++) {
   
10.             positions[arr[i]-'a'].add(i);
    
11.         }
    
12. 
    
13.         Set<String>[][] dp = new Set[len+1][len+1];
    
14.         for (int i = 0; i <= len; i++) {
    
15.             for (int j = 0; j <= len; j++) {
    
16.                 dp[i][j] = new HashSet<>();
    
17.             }
    
18.         }
    
19.         return helper(dp, 0, len, positions, S);
    
20.     }
    
21. 
    
22.     public Set<String> helper(Set[][] dp, int start, int end, TreeSet<Integer>[] positions, String s) {
    
23.         if (start >= end) {
    
24.             return new HashSet<>();
    
25.         }
    
26.         if (!dp[start][end].isEmpty()) {
    
27.             return dp[start][end];
    
28.         }
    
29. 
    
30.         Set<String> res = new HashSet<>();
    
31.         for (int i = 0; i < 26; i++) {
    
32.             // 当前字符串没有该字符
    
33.             if (positions[i].isEmpty()) {
    
34.                 continue;
    
35.             }
    
36.             Integer newStart = positions[i].ceiling(start);
    
37.             Integer newEnd = positions[i].lower(end);
    
38.             // string.substring(start, end)没有该字符
    
39.             if (newStart == null || newStart >= end) {
    
40.                 continue;
    
41.             }
    
42.             // 只有当前字符，作为single char palindrome
    
43.             String cur = Character.toString(s.charAt(newStart));
    
44.             res.add(cur);
    
45.             // 在不同的index，有相同的字符，这两个字符可以组成一个palindrome
    
46.             if (newStart != newEnd) {
    
47.                 res.add(cur+cur);
    
48.                 Set<String> subsets = helper(dp, newStart + 1, newEnd, positions, s);
    
49.                 for (String sub : subsets) {
    
50.                     res.add(cur + sub + cur);
    
51.                 }
    
52.             }
    
53.         }
    
54.         dp[start][end] = res;
    
55.         return dp[start][end];
    
56.     }
    
57. }

复制代码