AtomoVideo 问世,还在 B 端落地商用,中国版 "Sora" 来了?
AtomoVideo
近日,淘天集团旗下阿里妈妈技术团队推出高保真图片生成视频框架 AtomoVideo(阿瞳木视频)。
AtomoVideo 可将图片素材自动化转换为高质量视频动效。
据悉,AtomoVideo 采取预测帧生成技术。
直接创造一个长视频很难,需要大量的计算资源,预测帧生成技术巧妙的解决了该问题。
目前,该技术已在阿里妈妈的万相实验室、广告投放平台等应用场景上线,所有商家都可以体验"图片一键变视频"的人工智能新技术,快速生成创意短视频。
...
回归主线。
来一道和「淘天」相关的算法原题。
题目描述
平台:LeetCode
题号:1759
给你一个字符串 s
,返回 s
中 同构子字符串 的数目。
由于答案可能很大,只需返回对 109+710^9 + 7109+7 取余 后的结果。
同构字符串的定义为:如果一个字符串中的所有字符都相同,那么该字符串就是同构字符串。
子字符串是字符串中的一个连续字符序列。
示例 1:
输入:s = "abbcccaa"
输出:13
解释:同构子字符串如下所列:
"a" 出现 3 次。
"aa" 出现 1 次。
"b" 出现 2 次。
"bb" 出现 1 次。
"c" 出现 3 次。
"cc" 出现 2 次。
"ccc" 出现 1 次。
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13
示例 2:
输入:s = "xy"
输出:2
解释:同构子字符串是 "x" 和 "y" 。
示例 3:
输入:s = "zzzzz"
输出:15
提示:
- 1<=s.length<=1051 <= s.length <= 10^51<=s.length<=105
s
由小写字符串组成
双指针 + 数学
根据题意,我们需要找出 s
中所有字符相同的连续段。
假设 s[i...(j−1)]s[i...(j - 1)]s[i...(j−1)] 为某个连续段,长度为 mmm,根据「等差数列求和」可知该连续段所能提供的同构字符串数量为 (1+m)×m2\frac{(1 + m) \times m}{2}2(1+m)×m。
具体的,我们可以从前往后扫描 s
,假设当前处理到的位置为 i
,将其看作连续段的左端点,然后从 i
出发找到当前最长连续段的右端点 j - 1
,统计 s[i...(j−1)]s[i...(j - 1)]s[i...(j−1)] 所能贡献同构字符串数量,并调整下个发起点为 i=ji = ji=j 以扫描下一个连续段。
Java 代码:
class Solution {
public int countHomogenous(String s) {
int n = s.length(), MOD = (int)1e9+7;
long ans = 0;
for (int i = 0; i < n; ) {
int j = i;
while (j < n && s.charAt(j) == s.charAt(i)) j++;
long cnt = j - i;
ans += (1 + cnt) * cnt / 2;
ans %= MOD;
i = j;
}
return (int) ans;
}
}
C++ 代码:
class Solution {
public:
int countHomogenous(string s) {
int n = s.size(), MOD = 1e9+7;
long ans = 0;
for (int i = 0; i < n; ) {
int j = i;
while (j < n && s[j] == s[i]) j++;
long cnt = j - i;
ans += (1 + cnt) * cnt / 2;
ans %= MOD;
i = j;
}
return (int) ans;
}
};
Python3 代码:
class Solution:
def countHomogenous(self, s: str) -> int:
n, mod, i, ans = len(s), 1e9+7, 0, 0
while i < n:
j = i
while j < n and s[j] == s[i]:
j += 1
cnt = j - i
ans += (cnt + 1) * cnt / 2
ans %= mod
i = j
return int(ans)
TypeScript 代码:
function countHomogenous(s: string): number {
let n = s.length, mod = 1e9+7, ans = 0
for (let i = 0; i < n; ) {
let j = i
while (j < n && s.charAt(j) == s.charAt(i)) j++
const cnt = j - i
ans += (1 + cnt) * cnt / 2
ans %= mod
i = j
}
return ans
}
- 时间复杂度:O(n)O(n)O(n)
- 空间复杂度:O(1)O(1)O(1)
最后
给大伙通知一下 📢 :
全网最低价 LeetCode 会员目前仍可用,快来薅羊毛!!!
📅 年度会员:有效期加赠两个月!!; 季度会员:有效期加赠两周!!
🧧 年度会员:获 66.66 现金红包!!; 季度会员:获 22.22 现金红包!!
🎁 年度会员:参与当月丰厚专属实物抽奖(中奖率 > 30%)!!
更多详情请戳 这里 。
我是宫水三叶,每天都会分享算法知识,并和大家聊聊近期的所见所闻。
欢迎关注,明天见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉