📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: redeye1
跳转到指定楼层
上一主题 下一主题
收起左侧

亚麻OA

🔗
 楼主| redeye1 2021-9-24 12:17:15 | 只看该作者
全局:
wjxtank2010 发表于 2021-9-23 23:05
感觉第二题可以用dp. dp = 以i为结尾的所有substring的sum, dp = dp + i - count(s) + 1

count(s)是不是也得O(n)
回复

使用道具 举报

🔗
 楼主| redeye1 2021-9-24 12:19:33 | 只看该作者
全局:
匿名者 发表于 2021-9-23 01:23
滑动窗口?fixed size, size从1到length of whole string.

这样还是O(n^2)吧
回复

使用道具 举报

🔗
wjxtank2010 2021-9-24 12:27:48 | 只看该作者
全局:
redeye1 发表于 2021-9-23 20:17
count(s)是不是也得O(n)

循环从左往右顺便记录每个char的count就可以是O(1)。
回复

使用道具 举报

🔗
Smilingon 2021-9-26 16:46:41 | 只看该作者
全局:
第一题是要把单向链表改成双向链表来做吗?
回复

使用道具 举报

🔗
tl2k3 2021-9-29 02:18:28 | 只看该作者
全局:
写了下第二题,思路是按照楼上大哥说的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.     int[] lastChar = new int[26];
  8.     int[] dp = new int[n];
  9.     Arrays.fill(lastChar, -1);
  10.     dp[0] = 1;
  11.     res += dp[0];
  12.     lastChar[str.charAt(0) - 'a'] = 0;

  13.     for (int i = 1; i < str.length(); i++) {
  14.         char currChar = str.charAt(i);
  15.         int idxOfLastChar = lastChar[currChar - 'a'];
  16.         dp[i] += dp[i - 1] + i + 1 - (idxOfLastChar + 1);
  17.         res += dp[i];
  18.         lastChar[currChar - 'a'] = i;
  19.     }
  20.     return res;
  21. }
复制代码

评分

参与人数 3大米 +3 收起 理由
葡萄的奶茶 + 1
cuturdk + 1 给你点个赞!
PD1111 + 1 很有用的信息!

查看全部评分

回复

使用道具 举报

🔗
maorq08 2021-10-12 14:51:04 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
kobegao 2021-11-6 05:42:34 | 只看该作者
全局:
对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
复制代码
回复

使用道具 举报

🔗
interviewing 2021-11-22 12:58:44 | 只看该作者
全局:
redeye1 发表于 2021-9-23 20:15
不重复字符,test里只有e,s,t三个

should be +2, only count e and s
so final result for test is 18
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表