重庆城乡建设子网站,网站备案撤销原因,河南关键词seo,江苏省建设厅网站首页文章目录Google的一道经典面试题 - 767. 重构字符串767. 重构字符串1054. 距离相等的条形码结论Google的一道经典面试题 - 767. 重构字符串
767. 重构字符串
题目链接#xff1a;767. 重构字符串 题目大意#xff1a;给定一个字符串 s #xff0c;检查是否能重新排布其中的…
文章目录Google的一道经典面试题 - 767. 重构字符串767. 重构字符串1054. 距离相等的条形码结论Google的一道经典面试题 - 767. 重构字符串
767. 重构字符串
题目链接767. 重构字符串 题目大意给定一个字符串 s 检查是否能重新排布其中的字母使得两相邻的字符不同。 返回 s 的任意可能的重新排列。若不可行返回空字符串 “” 。
注意11 s.length 5002s 只包含小写字母。
示例
输入: s aab
输出: aba输入: s aaab
输出: 参考代码
class Solution:def reorganizeString(self, s: str) - str:cnt Counter(s)st sorted(cnt,keylambda k:0-cnt[k])if cnt[st[0]] (len(s)1)//2: return res []for i in st:res [i]*cnt[i]ans [None for _ in range(len(res))]ans[::2] res[:len(ans[::2])]ans[1::2] res[len(ans[::2]):]return .join(ans)时间复杂度O(n∣Σ∣)O(n|\Sigma|)O(n∣Σ∣)其中 nnn 是字符串的长度Σ\SigmaΣ 是字符集在本题中字符集为所有小写字母∣Σ∣26|\Sigma|26∣Σ∣26。遍历字符串并统计每个字母的出现次数时间复杂度是 O(n)O(n)O(n)。重构字符串需要进行 nnn 次放置字母的操作并遍历每个字母得到出现次数时间复杂度是 O(n∣Σ∣)O(n|\Sigma|)O(n∣Σ∣)。空间复杂度O(∣Σ∣)O(|\Sigma|)O(∣Σ∣)其中 nnn 是字符串的长度Σ\SigmaΣ 是字符集在本题中字符集为所有小写字母∣Σ∣26|\Sigma|26∣Σ∣26。
1054. 距离相等的条形码
相似题型1054. 距离相等的条形码 题目大意在一个仓库里有一排条形码其中第 i 个条形码为 barcodes[i]。 请你重新排列这些条形码使其中任意两个相邻的条形码不能相等。 你可以返回任何满足该要求的答案此题保证存在答案。
注意11 barcodes.length 1000021 barcodes[i] 10000。
示例
输入barcodes [1,1,1,2,2,2]
输出[2,1,2,1,2,1]输入barcodes [1,1,1,1,2,2,3,3]
输出[1,3,1,3,2,1,2,1]参考代码
class Solution:def rearrangeBarcodes(self, barcodes: List[int]) - List[int]:cnt Counter(barcodes)st sorted(cnt,keylambda k:0-cnt[k])res []for i in st:res [i]*cnt[i]ans [None for _ in range(len(res))]ans[::2] res[:len(ans[::2])]ans[1::2] res[len(ans[::2]):]return ans复杂度分析和上面差不多不过Σ10000\Sigma10000Σ10000
结论
排序这一块的题目还是比较难的关于 .sort()和sorted()函数的应用非常广泛且灵活多变很有意思的加油吧努力学习。
