本文主要是介绍抖音 UG 社招一面算法变形题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
英伟达超苹果
昨夜美股收盘，英伟达（NVDA）股价来到了 1224.4 美元，总市值突破 3 万亿美元，超越苹果（AAPL），成为仅次于微软（总市值 3.15 万亿美元）的全球第二大公司。
英伟达今年累计上涨超 147%，去年上涨 239%。
通常坐上一次火箭，就能成就一家百亿规模的独角兽公司，而英伟达是坐了三次火箭的神奇公司。
游戏 -> 虚拟货币（挖矿）-> AI。
得益于此，英伟达联合的创始人兼首席执行官，黄仁勋也因此成为《福布斯》全球富豪榜上第 16 位资产超过千亿美元的"超级富豪"之一。
...
回归主线。
来一道与之前读者投稿的「字节跳动（抖音 UG）社招一面」相关的变形题。
题目描述
平台：LeetCode
题号：828
我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。
例如：s = "LEETCODE" ，则其中 "L", "T","C","O","D" 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5。
本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。
输入用例保证返回值为 32 位整数。
注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。
示例 1：
输入: s = "ABC"
输出: 10
解释: 所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。
其中，每一个子串都由独特字符构成。
所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10
示例 2：
输入: s = "ABA"
输出: 8
解释: 除了 countUniqueChars("ABA") = 1 之外，其余与示例 1 相同。
示例 3：
输入：s = "LEETCODE"
输出：92
提示：
-
-
s只包含大写英文字符
模拟 + 乘法原理
这道题和 907. 子数组的最小值之和 如出一辙，只不过无须考虑运用「单调栈」。
原问题为求所有子数组的唯一字符数量和，其可等价为求每个 对答案的贡献，即每个 可作为多少个子数组的唯一元素。
假定我们能预处理出两数组 l 和 r 分别代表 作为子数组唯一字符时，其所能到达的最远两端：
-
l[i] = a代表下标 为 能够作为子数组唯一字符时的最远左边界，即为 左边第一个与 值相同的位置（若不存在，则为 ） -
r[i] = b代表跳表 为 能够作为子数组唯一字符时的最远右边界，即为 右边第一个与 值相同的位置（若不存在，则为 ）
子数组左端点个数为 个，右端点个数为 个，根据乘法原理可知，子数组个数为两者乘积。
预处理 l 和 r 只需要使用遍历计数即可。
Java 代码：
class Solution {
public int uniqueLetterString(String s) {
char[] cs = s.toCharArray();
int n = cs.length, ans = 0;
int[] l = new int[n], r = new int[n];
int[] idx = new int[26];
Arrays.fill(idx, -1);
for (int i = 0; i < n; i++) {
int u = cs[i] - 'A';
l[i] = idx[u];
idx[u] = i;
}
Arrays.fill(idx, n);
for (int i = n - 1; i >= 0; i--) {
int u = cs[i] - 'A';
r[i] = idx[u];
idx[u] = i;
}
for (int i = 0; i < n; i++) ans += (i - l[i]) * (r[i] - i);
return ans;
}
}
C++ 代码：
class Solution {
public:
int uniqueLetterString(string s) {
int n = s.size(), ans = 0;
vector<int> l(n, -1), r(n, n);
vector<int> idx(26, -1);
for (int i = 0; i < n; i++) {
int u = s[i] - 'A';
l[i] = idx[u];
idx[u] = i;
}
fill(idx.begin(), idx.end(), n);
for (int i = n - 1; i >= 0; i--) {
int u = s[i] - 'A';
r[i] = idx[u];
idx[u] = i;
}
for (int i = 0; i < n; i++) ans += (i - l[i]) * (r[i] - i);
return ans;
}
};
Python 代码：
class Solution:
def uniqueLetterString(self, s: str) -> int:
n = len(s)
l, r = [-1] * n, [n] * n
idx = [-1] * 26
for i in range(n):
u = ord(s[i]) - ord('A')
l[i] = idx[u]
idx[u] = i
idx = [n] * 26
for i in range(n - 1, -1, -1):
u = ord(s[i]) - ord('A')
r[i] = idx[u]
idx[u] = i
return sum((i - l[i]) * (r[i] - i) for i in range(n))
Typescript 代码：
function uniqueLetterString(s: string): number {
let n = s.length, ans = 0
const l = new Array<number>(n), r = new Array<number>(n)
const idx = new Array<number>(26).fill(-1)
for (let i = 0; i < n; i++) {
const u = s.charCodeAt(i) - 65
l[i] = idx[u]
idx[u] = i
}
idx.fill(n)
for (let i = n - 1; i >= 0; i--) {
const u = s.charCodeAt(i) - 65
r[i] = idx[u]
idx[u] = i
}
for (let i = 0; i < n; i++) ans += (i - l[i]) * (r[i] - i)
return ans
};
-
时间复杂度： -
空间复杂度：
线性 DP
另外一个实现思路是利用「动态规划」思想。
定义 为考虑以 为结尾的所有子串中的唯一字符个数。
不失一般性考虑 该如何转移：以 为结尾的子串包括在所有以 为结尾的子串结尾添加一个字符而来，以及 字符本身组成的新子串。
首先我们令 ，同时使用 记录字符 x 前一次出现的下标，使用 记录字符 x 在上上次出现的下标，然后假设当前处理的字符为 ，考虑 对 的影响（注意 始终为子串右端点）：
-
在子串左端点下标范围在 的子串中， 必然只出现一次（满足唯一字符要求），即可增加 个唯一字符 ； -
在子串左端点下标范围在 的子串中，原本位于 的字符在新子串中出现次数变为 次（不再满足唯一字符要求），即需减少 个唯一字符 。
综上，我们有状态转移方程：
实现上，由于 只依赖于 ，因此我们真的无须创建动规数组，而只需要使用单个变量 cur 来记录当前处理到的 即可，累积所有的 即是答案。
Java 代码：
class Solution {
public int uniqueLetterString(String s) {
int n = s.length(), ans = 0, cur = 0;
int[] a = new int[26], b = new int[26];
Arrays.fill(a, -1); Arrays.fill(b, -1);
for (int i = 0; i < n; i++) {
int u = s.charAt(i) - 'A';
cur += i - b[u] - (b[u] - a[u]);
ans += cur;
a[u] = b[u]; b[u] = i;
}
return ans;
}
}
C++ 代码：
class Solution {
public:
int uniqueLetterString(string s) {
int n = s.length(), ans = 0, cur = 0;
vector<int> a(26, -1), b(26, -1);
for (int i = 0; i < n; ++i) {
int u = s[i] - 'A';
cur += i - b[u] - (b[u] - a[u]);
ans += cur;
a[u] = b[u]; b[u] = i;
}
return ans;
}
};
Python 代码：
class Solution:
def uniqueLetterString(self, s: str) -> int:
n, ans, cur = len(s), 0, 0
a, b = [-1] * 26, [-1] * 26
for i in range(n):
u = ord(s[i]) - ord('A')
cur += i - b[u] - (b[u] - a[u])
ans += cur
a[u], b[u] = b[u], i
return ans
TypeScript 代码：
function uniqueLetterString(s: string): number {
let n = s.length, ans = 0, cur = 0
const a = new Array<number>(26).fill(-1), b = new Array<number>(26).fill(-1)
for (let i = 0; i < n; i++) {
const u = s.charCodeAt(i) - 65
cur += i - b[u] - (b[u] - a[u])
ans += cur
a[u] = b[u]; b[u] = i
}
return ans
};
-
时间复杂度： -
空间复杂度： ，其中 为字符集大小
最后
给大伙通知一下 📢 ：
全网最低价 LeetCode 会员目前仍可用 ~
📅 年度：有效期加赠两个月！！; 季度：有效期加赠两周！！
🧧 年度：获 66.66！！; 季度：获 22.22！！
🎁 年度：参与当月丰厚专属实物抽奖（中奖率 > 30%)！！
专属链接：leetcode.cn/premium/?promoChannel=acoier
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
这篇关于抖音 UG 社招一面算法变形题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
