本文主要是介绍拼多多(PDD)社招一面原题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
未成年游戏退费
5 月 28 日,中国互联网协会发布《未成年人网络游戏服务消费管理要求(征求意见稿)》团体标准。
该标准是游戏行业首个完整的消费管理规范,可用于未成年人游戏消费退费纠纷解决,也可为相关行政部门、司法机关提供参考。
根据各自过错情况,该标准明确划分了网络游戏服务提供者、监护人等责任方的担责比例。
该标准针对常见的场景,给出了具体的责任划分。
举个 🌰,若游戏服务商已依法采取了「防沉迷措施」,但监护人帮助未成年人"绕过"防沉迷限制,或监护人未充分履行监护职责,该标准建议过错方承担责任比例 30%-70%,若存在多次过错行为,可能承担全部责任。
近几年,关于未成年在网络平台巨额消费(游戏充值 or 直播打赏)的新闻屡见不鲜。
一些舆论到位的案例,虽都得到了全额退款。但新闻的发生,往往少不了监护人的责任,新标准的出台一定程度上弥补这一缺失。
对于「首个未成年人游戏退费标准发布」,你怎么看?
...
回归主题。
来一道近期读者投稿的,在「拼多多(社招一面)」遇到的算法原题。
题目描述
平台:LeetCode
题号:139
给你一个字符串 s
和一个字符串列表 wordDict
作为字典。
请你判断是否可以利用字典中出现的单词拼接出 s
。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
示例 1:
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2:
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
注意,你可以重复使用字典中的单词。
示例 3:
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
提示:
-
-
-
-
s
和wordDict[i]
仅有小写英文字母组成 -
wordDict
中的所有字符串 互不相同
序列 DP
将字符串 s
长度记为 n
,wordDict
长度记为 m
。
为了方便,我们调整字符串 s
以及将要用到的动规数组的下标从 1
开始。
定义 为考虑前 i
个字符,能否使用 wordDict
拼凑出来:当 代表 能够使用 wordDict
所拼凑,反之则不能。
不失一般性考虑 该如何转移:由于 需要考虑 范围内的字符,若 为 True
说明整个 都能够使用 wordDict
拼凑,自然也包括最后一个字符 所在字符串 sub
。
「我们可以枚举最后一个字符所在字符串的左端点 ,若 在 wordDict
中出现过,并且 ,说明 能够被拼凑,并且子串 sub
也在 wordDict
,可得 f[i] = True
。」
为了快速判断某个字符是否在 wordDict
中出现,我们可以使用 Set
结构对 进行转存。
Java 代码:
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>();
for (String word : wordDict) set.add(word);
int n = s.length();
boolean[] f = new boolean[n + 10];
f[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i && !f[i]; j++) {
String sub = s.substring(j - 1, i);
if (set.contains(sub)) f[i] = f[j - 1];
}
}
return f[n];
}
}
C++ 代码:
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> set;
for (const string& word : wordDict) {
set.insert(word);
}
int n = s.length();
vector<bool> f(n + 10, false);
f[0] = true;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i && !f[i]; ++j) {
string sub = s.substr(j - 1, i - j + 1);
if (set.find(sub) != set.end()) f[i] = f[j - 1] || f[i];
}
}
return f[n];
}
};
Python 代码:
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
ss = set(wordDict)
n = len(s)
f = [False] * (n + 10)
f[0] = True
for i in range(1, n + 1):
j = i
while j >= 1 and not f[i]:
sub = s[j - 1:i]
if sub in ss:
f[i] = f[j - 1]
j -= 1
return f[n]
TypeScript 代码:
function wordBreak(s: string, wordDict: string[]): boolean {
const ss = new Set<string>(wordDict)
const n = s.length
const f = new Array<boolean>(n + 10).fill(false)
f[0] = true
for (let i = 1; i <= n; i++) {
for (let j = i; j >= 1 && !f[i]; j--) {
const sub = s.substring(j - 1, i)
if (ss.has(sub)) f[i] = f[j - 1]
}
}
return f[n]
}
-
时间复杂度:将 wordDict
转存在Set
复杂度为 ;DP
过程复忽裁剪子串和查询Set
结构的常数,复杂度为 -
空间复杂度:
总结
这里简单说下「线性 DP」和「序列 DP」的区别。
线性 DP 通常强调「状态转移所依赖的前驱状态」是由给定数组所提供的,即拓扑序是由原数组直接给出。更大白话来说就是通常有 依赖于 。
这就限定了线性 DP 的复杂度是简单由「状态数量(或者说是维度数)」所决定。
序列 DP 通常需要结合题意来寻找前驱状态,即需要自身寻找拓扑序关系(例如本题,需要自己通过枚举的方式来找左端点,从而找到可转移的前驱状态 )。
这就限定了序列 DP 的复杂度是由「状态数 + 找前驱」的复杂度所共同决定。也直接导致了序列 DP 有很多玩法,往往能够结合其他知识点出题,来优化找前驱这一操作,通常是利用某些性质,或是利用数据结构进行优化。
最后
给大伙通知一下 📢 :
全网最低价 LeetCode 会员目前仍可用 ~
📅 年度会员:有效期加赠两个月!!; 季度会员:有效期加赠两周!!
🧧 年度会员:获 66.66 现金红包!!; 季度会员:获 22.22 现金红包!!
🎁 年度会员:参与当月丰厚专属实物抽奖(中奖率 > 30%)!!
专属链接:leetcode.cn/premium/?promoChannel=acoier
我是宫水三叶,每天都会分享算法知识,并和大家聊聊近期的所见所闻。
欢迎关注,明天见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
这篇关于拼多多(PDD)社招一面原题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!