📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2125| 回复: 7
跳转到指定楼层
上一主题 下一主题
收起左侧

[Leetcode] 面试外企,这道题难度怎么样

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
写一个方法,两个参数,一个是字符串长度,一个是sum,当这两个参数确定,求最小的字符串,字符串由小写字母组成,a等于1,b等于2,z等于26

比如字符串长度2,sum是3,则有ab和ba两个结果,但排序后ab最小,所以返回ab

上一篇:给大家推荐一个自己认为刷题/复习很有用的工具
下一篇:请问把neetcode的简单跟中等刷了是不是够投那些不知名的小厂了?
推荐
66j 2024-12-16 17:27:29 | 只看该作者
全局:
本帖最后由 66j 于 2024-12-16 04:31 编辑
notturno 发表于 2024-12-16 02:37
说一下我的直觉,基本算法是backtracking然后用greedy去剪枝,最优解应该是纯math问题。
难度大概medium。

这个能压缩所以不需要backtrack可以直接dp。但是这题可以直接贪心O(n),先全部fill 成a,因为你要最小,所以直接从最后一个往上加。 例如n = 3 b = 10, 先aaa, 然后最后一个加7 aah。最后一个加到z就倒数第二个以此类推。 难度medium 偏简单。
求加个米!

评分

参与人数 2大米 +2 收起 理由
keluotete + 1 赞一个
BZH + 1 赞一个

查看全部评分

回复

使用道具 举报

推荐
notturno 2024-12-16 15:37:49 | 只看该作者
全局:
说一下我的直觉,基本算法是backtracking然后用greedy去剪枝,最优解应该是纯math问题。
难度大概medium。
回复

使用道具 举报

🔗
Bailuo 2024-12-16 23:50:36 来自APP | 只看该作者
全局:
66j 发表于 2024-12-16 01:27:29
这个能压缩所以不需要backtrack可以直接dp。但是这题可以直接贪心O(n),先全部fill 成a,因为你要最小,所以直接从最后一个往上加。 例如n = 3
看了你这个算法觉得深受启发,然后又再想了想最后的结果应该是中间有一个a-z之间的字母,然后前面全是a(可能0个),后面全是z(可能0个),那么可以用公式直接算,不用一个个加,floor((sum-len)/25)就是z的个数mod+1就是中间的那个数,len-z的个数-1就是a的个数,比如len=2,sum=3,sum-len=1。z个数0,中间字母是1+1=b,前面有2-0-1=1个a,最后结果是ab😀。
回复

使用道具 举报

🔗
66j 2024-12-17 02:32:20 | 只看该作者
全局:
Bailuo 发表于 2024-12-16 10:50
看了你这个算法觉得深受启发,然后又再想了想最后的结果应该是中间有一个a-z之间的字母,然后前面全是a( ...

一样的。但就是这个意思,你建立string 也还是O(n)
回复

使用道具 举报

🔗
Bailuo 2024-12-17 03:15:51 来自APP | 只看该作者
全局:
66j 发表于 2024-12-16 10:32:20
一样的。但就是这个意思,你建立string 也还是O(n)
空间复杂度要小一些,建立字符串是n,直接算是1
回复

使用道具 举报

全局:
这不就是算25进制吗?
回复

使用道具 举报

全局:
初始值所有的都是1,然后优先从后加,加满往前走继续加
回复

使用道具 举报

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

本版积分规则

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