特斯拉一面算法原题

来自太空的 X 帖子

埃隆·马斯克(Elon Musk)旗下太空探索技术公司 SpaceX 于 2 月 26 号,从太空往社交平台 X(前身为推特,已被马斯克全资收购并改名)发布帖子。

alt

这是 SpaceX 官号首次通过星链来发送 X 帖子,马斯克对此表示祝贺和肯定。

对于此事,马斯克多次强调:"该帖子是由 SpaceX 从一部普通手机直接发到卫星上的,中间没有任何特殊设备!"

...

回到主线。

来做一道和「特斯拉」相关的面试算法题。

题目描述

平台:LeetCode

题号:777

在一个由 'L' ,'R''X' 三个字符组成的字符串(例如 "RXXLRXRXL")中进行移动操作。

一次移动操作指用一个 "LX" 替换一个 "XL",或者用一个 "XR" 替换一个 "RX"

现给定起始字符串 start 和结束字符串 end,请编写代码,当且仅当存在一系列移动操作使得 start 可以转换成 end 时, 返回 True

示例 :

输入: start = "RXXLRXRXL", end = "XRLXXRRLX"

输出: True

解释:
我们可以通过以下几步将start转换成end:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

提示:

  • startend 中的字符串仅限于 'L', 'R''X'

双指针

根据题意,我们每次移动要么是将 XL 变为 LX,要么是将 RX 变为 XR,而该两者操作可分别看做将 L 越过多个 X 向左移动,将 R 越过多个 X 向右移动。

因此在 startend 中序号相同的 LR 必然满足坐标性质:

  1. 序号相同的 L : start 的下标不小于 end 的下标(即 L 不能往右移动)
  2. 序号相同的 R : start 的下标不大于 end 的下标(即 R 不能往左移动)

其中「序号」是指在 LR 字符串中出现的相对顺序。

Java 代码:

class Solution {
    public boolean canTransform(String start, String end) {
        int n = start.length(), i = 0, j = 0;
        while (i < n || j < n) {
            while (i < n && start.charAt(i) == 'X') i++;
            while (j < n && end.charAt(j) == 'X') j++;
            if (i == n || j == n) return i == j;
            if (start.charAt(i) != end.charAt(j)) return false;
            if (start.charAt(i) == 'L' && i < j) return false;
            if (start.charAt(i) == 'R' && i > j) return false;
            i++; j++;
        }
        return i == j;
    }
}

C++ 代码:

class Solution {
public:
    bool canTransform(string start, string end) {
        int n = start.size();
        int i = 0, j = 0;
        while (i < n || j < n) {
            while (i < n && start[i] == 'X') i++;
            while (j < n && end[j] == 'X') j++;
            if (i == n || j == n) return i == j;
            if (start[i] != end[j]) return false;
            if (start[i] == 'L' && i < j) return false;
            if (start[i] == 'R' && i > j) return false;
            i++; j++;
        }
        return i == j;
    }
};

Python 代码:

class Solution:
    def canTransform(self, start: str, end: str) -> bool:
        i, j, n = 00, len(start)
        while i < n or j < n:
            while i < n and start[i] == 'X': i += 1
            while j < n and end[j] == 'X': j += 1
            if i == n or j == n: return i == j
            if start[i] != end[j]: return False
            if start[i] == 'L' and i < j: return False
            if start[i] == 'R' and i > j: return False
            i, j = i + 1, j + 1
        return i == j

TypeScript 代码:

function canTransform(start: string, end: string): boolean {
    let n = start.length;
    let i = 0, j = 0;
    while (i < n || j < n) {
        while (i < n && start.charAt(i) === 'X') i++;
        while (j < n && end.charAt(j) === 'X') j++;
        if (i === n || j === n) return i === j;
        if (start.charAt(i) !== end.charAt(j)) return false;
        if (start.charAt(i) === 'L' && i < j) return false;
        if (start.charAt(i) === 'R' && i > j) return false;
        i++; j++;
    }
    return i === j;
};
  • 时间复杂度:
  • 空间复杂度:

我是宫水三叶,每天都会分享算法知识,并和大家聊聊近期的所见所闻。

欢迎关注,明天见。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/420477.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

即插即用篇 | YOLOv8 引入 MHSA 注意力机制 | 《Bottleneck Transformers for Visual Recognition》

论文名称:《Bottleneck Transformers for Visual Recognition》 论文地址:https://arxiv.org/pdf/2101.11605.pdf 文章目录 1 原理2 源代码3 添加方式4 模型 yaml 文件template-backbone.yamltemplate-small.yamltemplate-large.yamltemplate-neck.yaml

(介绍与使用)物联网NodeMCUESP8266(ESP-12F)连接新版onenet mqtt协议实现上传数据(温湿度)和下发指令(控制LED灯)

前言 本文详细介绍了如何利用物联网技术,通过NodeMCU ESP8266(ESP-12F)模块连接到新版的OneNet平台,使用MQTT协议实现数据的上传与指令的下发。文中首先对NodeMCU ESP8266模块及其特性进行了简介,随后详细阐述了如何配置和使用MQTT协议连接到OneNet平台,实现温湿度数据的…

Linux 系统安装/卸载 Nginx教程

优质博文&#xff1a;IT-BLOG-CN 一、安装Nginx 【1】首先通过Nginx官网确定需要安装的版本&#xff0c;如果Linux联网则直接在Linux服务上使用wget命令将Nginx安装包下载到/usr/local/目录下&#xff1a; [rootxxx local]# wget -c http://nginx.org/download/nginx-1.22.1.…

XSS中级漏洞(靶场)

目录 一、环境 二、正式开始闯关 0x01 0x02 0x03 0x04 0x05 0x06 0x07 0x08 0x0B 0x0C 0x0D 0x0E ​ 0x0F 0x10 0x11 0x12 一、环境 在线环境&#xff08;gethub上面的&#xff09; alert(1) 二、正式开始闯关 0x01 源码&#xff1a; 思路&#xff1a;闭…

【Javascript编程实操02】1、判断一个年份是闰年还是平年 2、找到三个数中最小的数

目录 前言 1、判断一个年份是闰年还是平年 原理&#xff1a; 代码&#xff1a; 实现效果&#xff1a; 2、找到三个数中最小的数 流程图&#xff1a; 代码&#xff1a; 实现效果&#xff1a; 总结 前言 本次继续针对Javascript阶段的if...else...的实操练习&#xff0…

《读写算》杂志社读写算杂志社2024年第2期目录

教育资讯 教育部印发通知部署&#xff1a;做好2024年寒假期间校外培训治理工作 1《读写算》投稿&#xff1a;cn7kantougao163.com 北京提升学校心理健康工作水平——每校至少配备一名专职心理健康教育教师 1 湖北孝感&#xff1a;2026年达成小学毕业时人人会游泳 2…

【Qt】Sqlite数据库加密

1. 加密方式 对数据库文件加密。既不会暴露表结构&#xff0c;也不会暴露数据细节。 2. 加密工具&#xff08;QtCipherSqlitePlugin&#xff09; 用于密码 SQLite 的 Qt 插件&#xff0c;它基于 SQLite 源和 wxWidget 中的 wxSQLite3插件github地址&#xff1a;https://gith…

【力扣hot100】刷题笔记Day17

前言 今天竟然不用开组会&#xff01;天大的好消息&#xff0c;安心刷题了 46. 全排列 - 力扣&#xff08;LeetCode&#xff09; 回溯&#xff08;排列&#xff09; class Solution:def permute(self, nums: List[int]) -> List[List[int]]:# 回溯def backtrack():if len(…

【InternLM 实战营笔记】浦语·灵笔的图文理解及创作部署、 Lagent 工具调用 Demo

浦语灵笔的图文理解及创作部署 浦语灵笔是基于书生浦语大语言模型研发的视觉-语言大模型&#xff0c;提供出色的图文理解和创作能力&#xff0c;结合了视觉和语言的先进技术&#xff0c;能够实现图像到文本、文本到图像的双向转换。使用浦语灵笔大模型可以轻松的创作一篇图文推…

【办公类-18-03】(Python)中班米罗可儿证书批量生成打印(班级、姓名)

作品展示——米罗可儿证书打印幼儿姓名 背景需求 2024年3月1日&#xff0c;中4班孩子一起整理美术操作材料《米罗可儿》的操作本——将每一页纸撕下来&#xff0c;分类摆放、确保纸张上下位置正确。每位孩子们都非常厉害&#xff0c;不仅完成了自己的一本&#xff0c;还将没有…

nginx如何配置命令启动

我安装好nginx后&#xff0c;发现不能使用systemctl start nginx或者systemctl stop nginx来控制启停 解决方法如下 首先要建一个nginx.pid的文件 一般是建在 /var/run/这个路径下面 sudo touch /var/run/nginx.pid 添加权限 sudo chmod 644 /var/run/nginx.pid可以进入到…

C#,双向链表(Doubly Linked List)归并排序(Merge Sort)算法与源代码

1 双向链表 双向链表也叫双链表&#xff0c;是链表的一种&#xff0c;它的每个数据结点中都有两个指针&#xff0c;分别指向直接后继和直接前驱。所以&#xff0c;从双向链表中的任意一个结点开始&#xff0c;都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循…

数学学习与研究杂志社《数学学习与研究》杂志社编辑部2023年第29期目录

考试研究 提高高三数学二轮复习质量的思考与实践 佘淮青; 2-4 提升高三数学复习质量的策略探究 王飞; 5-7 核心素养背景下的高中数学命题策略研究 陈明发; 8-10 提升中考数学复习课的有效性研讨 韩兴宏; 11-13 中学教学方法《数学学习与研究》投稿&#xff1a;…

【前端素材】推荐优质后台管理系统DAdmin平台模板(附源码)

一、需求分析 1、系统定义 后台管理系统是一种用于管理网站、应用程序或系统的管理界面&#xff0c;通常由管理员和工作人员使用。它提供了访问和控制网站或应用程序后台功能的工具和界面&#xff0c;使其能够管理用户、内容、数据和其他各种功能。 2、功能需求 后台管理系…

微信小程序手势冲突?不存在的!

原生的应用经常会有页面嵌套列表&#xff0c;滚动列表能够改变列表大小&#xff0c;然后还能支持列表内下拉刷新等功能。看了很多的小程序好像都没有这个功能&#xff0c;难道这个算是原生独享的吗&#xff0c;难道是由于手势冲突无法实现吗&#xff0c;冷静的思考了一下&#…

软考-计算题

1.二维矩阵转换成一维矩阵 2.算术表达式&#xff1a; 3.计算完成项目的最少时间&#xff1a;之前和的max&#xff08;必须之前的所有环节都完成&#xff09; 松弛时间&#xff1a;最晚开始时间-最早开始时间 最早&#xff1a;之前环节都完成的和的max 最晚&#xff1a;总时间…

LTX Studio开放测试,用户可以通过输入文本来生成超过25秒的微电影视频;人工智能的崛起和局限

&#x1f989; AI新闻 &#x1f680; LTX Studio开放测试&#xff0c;用户可以通过输入文本来生成超过25秒的微电影视频 摘要&#xff1a;LTX Studio是由著名AI平台Lightricks推出的生成式AI电影制作平台。用户可以通过输入文本来生成超过25秒的微电影视频&#xff0c;并且可…

K8s安全一

Kubernetes是一个开源的&#xff0c;用于编排云平台中多个主机上的容器化的应用&#xff0c;目标是让部署容器化的应用能简单并且高效的使用, 提供了应用部署&#xff0c;规划&#xff0c;更新&#xff0c;维护的一种机制。其核心的特点就是能够自主的管理容器来保证云平台中的…

雷达新研社丨宏电雷达水位计化身“智慧管家”,守护滁州城市生命线

城市生命线是维系城市正常运行、满足群众生产生活需要的重要基础设施。为大力推进城市生命线安全工程建设&#xff0c;加快韧性城市建设&#xff0c;滁州市实施了城市生命线安全工程建设项目。 项目包含对全市1650.5公里排水安全监测感知网的建设&#xff0c;宏电股份作为智慧…

第四十七回 一丈青单捉王矮虎 宋公明二打祝家庄-强大而灵活的python装饰器

四面全是埋伏&#xff0c;宋江和众人一直绕圈跑不出去。正在慌乱之时&#xff0c;石秀及时赶到&#xff0c;教大家碰到白杨树就转弯走。走了一段时间&#xff0c;发现围的人越来越多&#xff0c;原来祝家庄以灯笼指挥号令。花荣一箭射下来红灯龙&#xff0c;伏兵自己就乱起来了…