亚麻OA

两题：
１　给一个单向链表，要求每次从头尾node各取一个数后相加，再delete这两node。求所有pair的最大值。要求Ｏ（１）space。
２　给定一个字符串

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

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

(2021-09-29 10:08 +8:00):
第二题跟八而八类似

写了下第二题，思路是按照楼上大哥说的dp写的

1. public static int helper(String str) {
   
2.     if (str == null || str.length() == 0) {
   
3.         return 0;
   
4.     }
   
5.     int n = str.length();
   
6.     int res = 0;
   
7. 
   
8.     int[] lastChar = new int[26];
   
9.     int[] dp = new int[n];
   
10.     Arrays.fill(lastChar, -1);
    
11.     dp[0] = 1;
    
12.     res += dp[0];
    
13.     lastChar[str.charAt(0) - 'a'] = 0;
    
14. 
    
15.     for (int i = 1; i < str.length(); i++) {
    
16.         char currChar = str.charAt(i);
    
17.         int idxOfLastChar = lastChar[currChar - 'a'];
    
18.         dp[i] += dp[i - 1] + i + 1 - (idxOfLastChar + 1);
    
19.         res += dp[i];
    
20.         lastChar[currChar - 'a'] = i;
    
21.     }
    
22.     return res;
    
23. }

复制代码

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

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

对2题确实就是828

1. class Solution:
   
2.     def uniqueLetterString(self, s: str) -> int:
   
3.         contributions = [0]*26
   
4.         lastPosition = [0]*26
   
5.         res = 0
   
6.         cur = 0
   
7.         for i,c in enumerate(s):
   
8.             charIndex = ord(c) - ord('A')
   
9.             substringsHere = i+1
   
10.             cur -=contributions[charIndex]
    
11.             contributions[charIndex] = substringsHere - lastPosition[charIndex]
    
12.             
    
13.             cur +=contributions[charIndex]
    
14.             res +=cur
    
15.             lastPosition[charIndex] = i+1
    
16.             
    
17.         return res

复制代码

请问第二题 19 是怎么算的呢？
[t, e, s, t, te, es, st, tes, est] -> 【1 1 1 1 2 2 2 3 3】16?

MJ-cr 发表于 2021-9-20 22:29
请问第二题 19 是怎么算的呢？
[t, e, s, t, te, es, st, tes, est] -> 【1 1 1 1 2 2 2 3 3】16?

test自己是自己的子串，所以还要加3

求一个海投timeline, 谢谢

第二题感觉用一个list 然后加一个 set避免重复字符

redeye1 发表于 2021-9-20 20:33
test自己是自己的子串，所以还要加3

请问为什么加上“test”只是 +3 而不是 +4 呢？

滑动窗口？fixed size, size从1到length of whole string.

感觉第二题可以用dp. dp[i ] = 以i为结尾的所有substring的sum, dp[i ] = dp[i-1] + i - count(s[i ]) + 1

aoliaochen 发表于 2021-9-22 12:54
求一个海投timeline, 谢谢

09/13　投
09/14  收到OA

vlieng 发表于 2021-9-23 00:34
请问为什么加上“test”只是 +3 而不是 +4 呢？

不重复字符，test里只有e，s，t三个