当前位置: 首页 > news >正文

拼多多(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

提示:

  • swordDict[i] 仅有小写英文字母组成
  • wordDict 中的所有字符串 互不相同

序列 DP

将字符串 s 长度记为 nwordDict 长度记为 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<stringset;
        for (const string& word : wordDict) {
            set.insert(word);
        }
        int n = s.length();
        vector<boolf(n + 10false);
        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)社招一面原题

未成年游戏退费 5 月 28 日&#xff0c;中国互联网协会发布《未成年人网络游戏服务消费管理要求&#xff08;征求意见稿&#xff09;》团体标准。 该标准是游戏行业首个完整的消费管理规范&#xff0c;可用于未成年人游戏消费退费纠纷解决&#xff0c;也可为相关行政部门、司法…...

类中使用QtConcurrent::run

在QtConcurrent::run中调用类的成员函数时&#xff0c;你需要注意几个关键点&#xff1a; 对象生命周期&#xff1a;你需要确保在QtConcurrent::run调用的整个期间&#xff0c;类对象都是有效的。如果对象在成员函数执行期间被销毁&#xff0c;将会导致未定义行为。成员函数访…...

基于深度学习的中文情感分析系统python flask

基于python的毕业设计 基于深度学习的中文情感分析系统(flask)(源码说明文档演示) 毕业设计课程设计期末大作业、课程设计、高分必看&#xff0c;下载下来&#xff0c;简单部署&#xff0c;就可以使用。 包含&#xff1a;项目源码、数据库脚本、软件工具等&#xff0c;该项目…...

Mysql联合索引

对mysql联合索引的认识 文章目录 对mysql联合索引的认识最左原则匹配一、最左匹配的原理&#xff1f;二、实战 最左原则匹配 所谓最左原则指的就是如果你的 SQL 语句中用到了联合索引中的最左边的索引&#xff0c;那么这条 SQL 语句就可以利用这个联合索引去进行匹配&#xff…...

Linux基础指令用户管理003

继Linux基础指令002我们讲了如何设置用户密码以及修改用户信息&#xff0c;我们讲一下高级用户管理。 操作系统 CentOS Stream 9 高级用户管理 visudo 用于普通用户临时提升权限执行命令&#xff0c;如下图 [yylocalhost ~]$ cp -av /etc/passwd{,_bak} /etc/passwd ->…...

java图书电子商务网站的设计与实现源码(springboot+vue+mysql)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的图书电子商务网站的设计与实现。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 项目简介&#xff1a; 图书电子商…...

全球首个多语种手语视频生成模型诞生:SignLLM

近日&#xff0c;一项名为 SignLLM 的新型 AI 技术取得了突破性进展&#xff0c;或将彻底改变听障人士的沟通方式。作为全球首个多语种手语生成模型&#xff0c;SignLLM 能够将输入的文本或语音指令&#xff0c;实时转化为对应的手语手势视频&#xff0c;为打破语言障碍、促进信…...

初学C语言100题:经典例题节选(源码分享)

1.输出10000以内所有完数 完数的概念 一个正整数的所有因子&#xff08;除了自身以外的约数&#xff09;的和恰巧等于它本身 #include <stdio.h>int main() {int i 0;for (i 2; i < 10000; i)//生成1到10000之间的数{int j 0;int sum 0;//注意这里的sum每次循环结…...

C++设计模式之策略模式、迭代器模式、适配器模式、工厂模式、超级工厂模式、享元模式、代理模式

文章目录 一、介绍1.毫无价值的使用虚函数例子 二、策略模式1.策略模式2.多重策略与迭代器模式3.不要什么东西都塞一块 三、适配器模式1.跨接口的适配器2.跨接口的适配器 四、工厂模式1.工厂模式2.超级工厂模式3.RAII 自动管理内存4.工厂模式实战 五、享元模式1.享元模式2.代理…...

18 js时间对象

时间对象是一种复杂数据类型&#xff0c;用来存储时间 创建时间对象 内置构造函数创建 语法&#xff1a;var 时间名new Date() var datenew Date()console.log(date) //Wed May 29 2024 16:03:47 GMT0800 (中国标准时间) 创建指定日期 当参数为数字——>在格林威治的时间基…...

安卓赤拳配音v1.0.2Ai配音神器+百位主播音色

Ai配音神器 本人自用版本&#xff01;超级稳定&#xff01;百位主播音色 登陆即可用 链接&#xff1a;https://pan.baidu.com/s/1WVsrYZqLaPAriHMMLMdPBg?pwdz9ru 提取码&#xff1a;z9ru...

前端面试题日常练-day40 【面试题】

题目 希望这些选择题能够帮助您进行前端面试的准备&#xff0c;答案在文末 1. Bootstrap 的栅格系统是基于&#xff08; &#xff09;进行布局的。A. 像素 B. 百分比 C. 媒体查询 2. 在 Bootstrap 中&#xff0c;要创建一个按钮&#xff0c;可以使用&#xff08; &#xff…...

UG NX二次开发(C#)-UFun函数-利用UFPart.Export导出模型中的对象并创建一个新的part

文章目录 1、前言2、UF_PART_export函数定义3、UF_PART_export_with_options函数定义4、代码1、前言 在UG NX 10.0二次开发中,需要用到将装配体中通过几何建模创建的对象独立创建一个part文件,所以查找了下UFun函数,即是UF_PART_export 和UF_PART_export_with_options两个函…...

SFOS2:组件介绍

一、前言 在sailfish os application的开发过程中&#xff0c;几乎是困难重重&#xff0c;因为我暂未找到具有完整性、指导性、易懂性的开发文档&#xff0c;特别是组件的使用&#xff0c;现决定将自己的探究结果记录下来。因此&#xff0c;这篇文章只会具有参考价值&#xff0…...

交换机的三层交换技术

现有pc1与pc2不在同一个网段之下&#xff0c;通过交换机相连接。 进人交换机1&#xff0c;创建两个vlan 10和vlan 20 &#xff0c;进入串口2设置串口模式为access&#xff0c;并且设置默认vlan为10.进入串口3设置串口模式为access&#xff0c;并且设置默认vlan为20. 进入串口1…...

探秘URL的奥义:JavaScript中轻松获取页面参数值的N种姿势【含代码示例】

探秘URL的奥义&#xff1a;JavaScript中轻松获取页面参数值的N种姿势【含代码示例】 URL基础知识补给站基础案例&#xff1a;直接解析URL案例一&#xff1a;使用URLSearchParams案例二&#xff1a;传统字符串分割法 高级策略&#xff1a;动态与安全案例三&#xff1a;封装与模块…...

VSCode小技巧,忽略不想格式化的代码行

零&#xff0e;格式化工具文档 1 . Black Ignoring sections功能 2 . autopep8 disabling-line-by-line功能&#xff1b;&#xff1b;–line-range选项 3 . Prettier prettier-ignore功能(例&#xff1a;适用于JS的// prettier-ignore&#xff0c;适用于CSS的/* prettier-igno…...

揭秘网络编程:同步与异步IO模型的实战演练

摘要 ​ 在网络编程领域&#xff0c;同步(Synchronous)、异步(Asynchronous)、阻塞(Blocking)与非阻塞(Non-blocking)IO模型是核心概念。尽管这些概念在多篇文章中被广泛讨论&#xff0c;它们的抽象性使得彻底理解并非易事。本文旨在通过具体的实验案例&#xff0c;将这些抽象…...

在Visual Studio Code和Visual Studio 2022下配置Clang-Format,格式化成Google C++ Style

项目开发要求好的编写代码格式规范&#xff0c;常用的是根据Google C Style Guide 网上查了很多博文&#xff0c;都不太一样有的也跑不起来&#xff0c;通过尝试之后&#xff0c;自己可算折腾好了&#xff0c;整理一下过程 背景&#xff1a; 编译器主要有三部分&#xff1a;前…...

民国漫画杂志《时代漫画》第32期.PDF

时代漫画32.PDF: https://url03.ctfile.com/f/1779803-1248635561-0ae98a?p9586 (访问密码: 9586) 《时代漫画》的杂志在1934年诞生了&#xff0c;截止1937年6月战争来临被迫停刊共发行了39期。 ps: 资源来源网络!...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...