Goldman新鲜白嫖OA

120分钟两个题
第一题地里原题，很eas

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

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

思路

匿名用户 发表于 2022-7-17 08:11
樓主 能不能發一下代碼? 感謝你

用python写的， 其实可以用一个8*n的二维数组的，为了直观点用了8个一位数组

1. def palindrome_subquence(s):
   
2.     n, ans = len(s), 0
   
3.     MOD = pow(10, 9)+7
   
4.     left_0 = [0]*n
   
5.     left_1 = [0]*n
   
6.     right_0 = [0]*n
   
7.     right_1 = [0]*n
   
8.     left_cur01 = [0]*n
   
9.     left_cur10 = [0]*n
   
10.     right_cur01 = [0]*n
    
11.     right_cur10 = [0]*n
    
12.     for i in range(n-2, -1, -1):
    
13.         if s[i+1] == '0':
    
14.             right_0[i] = right_0[i+1]+1
    
15.             right_1[i] = right_1[i+1]
    
16.         else:
    
17.             right_1[i] = right_1[i+1]+1
    
18.             right_0[i] = right_0[i+1]
    
19.         if s[i] == '1':
    
20.             right_cur10[i] = right_cur10[i+1]+right_0[i]
    
21.             right_cur01[i] = right_cur01[i+1]
    
22.         else:
    
23.             right_cur01[i] = right_cur01[i+1]+right_1[i]
    
24.             right_cur10[i] = right_cur10[i+1]
    
25.     for i in range(1,n-1):
    
26.         if s[i-1] == '0':
    
27.             left_0[i] = left_0[i-1]+1
    
28.             left_1[i] = left_1[i]
    
29.         else:
    
30.             left_1[i] = left_1[i-1]+1
    
31.             left_0[i] = left_0[i-1]
    
32.         if s[i] == '0':
    
33.             left_cur10[i] = left_cur10[i-1]+left_1[i]
    
34.             left_cur01[i] = left_cur01[i-1]
    
35.         else:
    
36.             left_cur01[i] = left_cur01[i-1]+left_0[i]
    
37.             left_cur10[i] = left_cur10[i-1]
    
38.         if 2 <= i <= n-3:
    
39.             # count 00x00
    
40.             if left_0[i] >= 1 and right_0[i] >= 1:
    
41.                 ans += (left_0[i]*(left_0[i]-1)//2)*(right_0[i]*(right_0[i]-1)//2)
    
42.             # count 11x11
    
43.             if left_1[i] >= 1 and right_1[i] >= 1:
    
44.                 ans += (left_1[i]*(left_1[i]-1)//2)*(right_1[i]*(right_1[i]-1)//2)
    
45.             # count 01x10
    
46.             ans += left_cur01[i-1]*right_cur10[i+1]
    
47.             # count 10x01
    
48.             ans += left_cur10[i-1]*right_cur01[i+1]
    
49.     return ans % MOD
    
50. 
    
51. print(palindrome_subquence('0100110'))

复制代码

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

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

第二题 先groupby 再排列组合算总的个数？其他dp或者回溯时间复杂度高了

张进 发表于 2022-07-13 13:59:04
第二题 先groupby 再排列组合算总的个数？其他dp或者回溯时间复杂度高了

请教下怎么groupby，是储存0或者1的位置吗

张进 发表于 2022-07-13 14:25:31
s =
nums = .
f =          频率，把相邻的0，1放一起

其实，你这个思路是跟我想到一起了，但我觉得两个小时内，我这么分类讨论肯定写不完，所以一直在想别的思路

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

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

张进 发表于 2022-07-13 14:29:54
以1，0 为中心，是考虑frequency数组里面的0，1，不是在原始string里慢慢移动，那样太慢了
考虑左右俩边的01，10情况，要用到前后缀和吧，还有统计每组0，1左边和右边0， 1的个数和

讲个笑话，这是ng的oa

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

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

https://stackoverflow.com/questi ... 0make%20palindromic,Hence%2C%20the%20answer%20is%202%20.

这个的数据规模也才700

https://codeforces.com/blog/entry/56448
找到非常相似的了，别人都是俩nested loop，感觉一个loop恐怕搞不定，sad