刚刚,百度和苹果宣布联名

百度 × Apple

就在刚刚,财联社报道,百度将为苹果今年发布的 iPhone16、Mac 系统和 iOS18 提供 AI 功能。

苹果曾与阿里以及另外一家国产大模型公司进行过洽谈,最后确定由百度提供这项服务,苹果预计采取 API 接口的方式计费。

苹果将国行 iPhone 等设备采用国产大模型 AI 功能主要出于合规需求,因为苹果自身短期内还无法解决合规问题,但国外版 iPhone 等设备 AI 功能均来自苹果自己的大模型。

不是黑百度(我们要正视客观差距),相信大多数国行用户心理多少有点不是滋味,国产苹果味 🤣

为什么说大多数,而不是所有国行用户,剩下的小部分是什么人。

是持有「百度」股票的国行用户:

alt

蹭上了果链,百度盘中上涨 6 个点。

本文发出的时候,H 股那边还没收盘,但基本可以断定结局。

中国公司,不管你是 A 股、H 股还是美股,都自带「出利好 = 高开低走」的传统艺能。

关于「百度」和「Apple」本次联名,你怎么看?是否会考虑放弃保修买入海外版?

...

回归主线。

来做一道和「百度」社招相关的算法面试题。

题目描述

平台:LeetCode

题号:649

Dota2 的世界里有两个阵营:Radiant(天辉)和 Dire(夜魇)。

Dota2 参议院由来自两派的参议员组成,现在参议院希望对一个 Dota2 游戏里的改变作出决定,他们以一个基于轮为过程的投票进行。

在每一轮中,每一位参议员都可以行使两项权利中的一项:

  • 禁止一名参议员的权利:参议员可以让另一位参议员在这一轮和随后的几轮中丧失所有的权利 。
  • 宣布胜利:如果参议员发现有权利投票的参议员都是同一个阵营的,他可以宣布胜利并决定在游戏中的有关变化。

给你一个字符串 s 代表每个参议员的阵营。字母 'R''D'分别代表了 Radiant(天辉)和 Dire(夜魇)。

然后,如果有 n 个参议员,给定字符串的大小将是 n

以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束,这一过程将持续到投票结束,所有失去权利的参议员将在过程中被跳过。

假设每一位参议员都足够聪明,会为自己的政党做出最好的策略,你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。

输出应该是 "Radiant""Dire"

示例 1:

输入:s = "RD"

输出:"Radiant"

解释:
第 1 轮时,第一个参议员来自 Radiant 阵营,他可以使用第一项权利让第二个参议员失去所有权利。
这一轮中,第二个参议员将会被跳过,因为他的权利被禁止了。
第 2 轮时,第一个参议员可以宣布胜利,因为他是唯一一个有投票权的人。

示例 2:

输入:s = "RDD"

输出:"Dire"

解释:
第 1 轮时,第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利。
这一轮中,第二个来自 Dire 阵营的参议员会将被跳过,因为他的权利被禁止了。
这一轮中,第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利。
因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利

提示:

  • senate[i]'R''D'

基本分析

整理题意:每次选择对方的一个成员进行消除,直到所有剩余成员均为我方时,宣布胜利。

由于每个对方成员执行权利都意味着我方损失一名成员,因此最佳方式是 「尽量让对方的权利不执行,或延迟执行(意味着我方有更多执行权利的机会)」。因此,最优决策为 「每次都选择对方的下一个行权成员进行消除」

贪心

这个找“最近一个”对方行权成员的操作既可以使用「有序集合」来做,也可以使用「循环队列」来做。

先说使用「有序集合」的做法。

起始我们先将 s 中的 RadiantDire 分别存入有序集合 rsds 当中,然后从前往后模拟消除过程,过程中使用 idx 代表当前处理到的成员下标,使用 set 记录当前哪些成员已被消除。

当轮到 s[idx] 行权时(若 s[idx] 已被消除,则跳过本轮),从对方的有序队列中取出 「首个大于等于 idx 的下标」(取出代表移除);若对方的有序序列不存在该下标,而行权过程又是循环进行的,说明此时下一个行权的对方成员是 「首个大于等于 的下标,我们对其进行取出消除,随后往后继续决策。

Java 代码:

class Solution {
    public String predictPartyVictory(String s) {
        TreeSet<Integer> rs = new TreeSet<>(), ds = new TreeSet<>();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'R') rs.add(i);
            else ds.add(i);
        }
        Set<Integer> set = new HashSet<>();
        int idx = 0;
        while (rs.size() != 0 && ds.size() != 0) {
            if (!set.contains(idx)) {
                TreeSet<Integer> temp = null;
                if (s.charAt(idx) == 'R') temp = ds;
                else temp = rs;
                Integer t = temp.ceiling(idx);
                if (t == null) t = temp.ceiling(0);
                set.add(t);
                temp.remove(t);
            }
            idx = (idx + 1) % n;
        }
        return rs.size() != 0 ? "Radiant" : "Dire";
    }
}

不难发现,虽然将所有成员存入有序集合和取出的复杂度均为 ,但整体复杂度仍是大于

因为我们在每一轮的消除中,从 idx 位置找到下一个决策者,总是需要遍历那些已被消除的位置,而该无效遍历操作可使用「循环队列」优化。

优化

使用循环队列 rddd 来取代有序集合 rsds。起始将各个成员分类依次入队,每次从两队列队头中取出成员,假设从 rs 中取出成员下标为 a,从 dd 中取出成员下标为 b,对两者进行比较:

  • 若有 a < b,说明 a 先行权,且其消除对象为 ba 行权后需等到下一轮,对其进行大小为 的偏移后重新添加到 rd 尾部(含义为本次行权后需要等到下一轮);
  • 若有 b < a,同理,将 a 消除后,对 b 进行大小为 的偏移后重新添加到 dd 尾部。

Java 代码:

class Solution {
    public String predictPartyVictory(String s) {
        Deque<Integer> rd = new ArrayDeque<>(), dd = new ArrayDeque<>();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'R') rd.addLast(i);
            else dd.addLast(i);
        }
        while (rd.size() != 0 && dd.size() != 0) {
            int a = rd.pollFirst(), b = dd.pollFirst();
            if (a < b) rd.addLast(a + n);
            else dd.addLast(b + n);
        }
        return rd.size() != 0 ? "Radiant" : "Dire";
    }
}

C++ 代码:

class Solution {
public:
    string predictPartyVictory(string s) {
        deque<int> rd, dd;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            if (s[i] == 'R') rd.push_back(i);
            else dd.push_back(i);
        }
        while (!rd.empty() && !dd.empty()) {
            int a = rd.front(), b = dd.front();
            rd.pop_front();
            dd.pop_front();
            if (a < b) rd.push_back(a + n);
            else dd.push_back(b + n);
        }
        return !rd.empty() ? "Radiant" : "Dire";
    }
};

Python 代码:

from collections import deque

class Solution:
    def predictPartyVictory(self, s: str) -> str:
        rd, dd = deque(), deque()
        n = len(s)
        for i in range(n):
            if s[i] == 'R':
                rd.append(i)
            else:
                dd.append(i)
        while rd and dd:
            a, b = rd.popleft(), dd.popleft()
            if a < b:
                rd.append(a + n)
            else:
                dd.append(b + n)
        return "Radiant" if rd else "Dire"

TypeScript 代码:

function predictPartyVictory(s: string): string {
    let rd: Array<number> = [], dd: Array<number> = [];
    let n: number = s.length;
    for (let i = 0; i < n; i++) {
        if (s.charAt(i) == 'R') rd.push(i);
        else dd.push(i);
    }
    while (rd.length != 0 && dd.length != 0) {
        let a: number = rd.shift()!, b: number = dd.shift()!;
        if (a < b) rd.push(a + n);
        else dd.push(b + n);
    }
    return rd.length != 0 ? "Radiant" : "Dire";  
};
  • 时间复杂度:将所有成员进行分队,复杂度为 ;每个回合会有一名成员被消除,最多有 个成员,复杂度为 。整体复杂度为
  • 空间复杂度:

最后

给大伙通知一下 📢 :

全网最低价 LeetCode 会员目前仍可用!!!

📅 年度会员:有效期加赠两个月!!; 季度会员:有效期加赠两周!!

🧧 年度会员:获 66.66 现金红包!!; 季度会员:获 22.22 现金红包!!

🎁 年度会员:参与当月丰厚专属实物抽奖(中奖率 > 30%)!!

专属链接:https://leetcode.cn/premium/?promoChannel=acoier

更多详情请戳 这里 。

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

欢迎关注,明天见。

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

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【AI漏洞】人工而后智能

注&#xff1a;公众号暂时不再使用了 本文主要内容&#xff1a; 1、主题&#xff1a;AI漏洞 2、过程&#xff1a;测试步骤 3、笔者&#xff1a;寄语 &#xff08;重点&#xff1a;本文只做技术研究&#xff0c;请遵守相关法律法规&#xff0c;发现自身单位有漏洞请及时修复&…

C语言指针详解(上)

一.什么是指针 指针是一种类型&#xff0c;用来存储变量的地址的类型 有哪些类型呢 字符指针&#xff1a;char* 整型指针&#xff1a;int* 浮点型指针&#xff1a;float* 双精度浮点型指针&#xff1a;double* 空指针&#xff1a;void* &#xff08;每一个类型的指针&a…

搜维尔科技:【应急演练】【工业仿真】救援模拟演练可视化仿真项目实施

安全救援综合演练系统是一套面向公共安全事故、预案管理、应急救援模拟演练的虚拟仿真解决方案&#xff0c;它为警察、消防以及专门的应急救援保障部门提供一个综合的应急救援培训和仿真演练平台。平台主要通过设计不同的事故模型和特定的灾难场景&#xff0c;定制不同的应急救…

Phoenix伪分布安装

引言 Phoenix是构建在HBase上的一个SQL层&#xff0c;能让我们用标准的JDBC APIs而不是HBase客户端APIs来创建表&#xff0c;插入数据和对HBase数据进行查询。Phoenix完全使用Java编写&#xff0c;作为HBase内嵌的JDBC驱动。Phoenix查询引擎会将SQL查询转换为一个或多个HBase扫…

大话设计模式之模板方法模式

模板方法模式&#xff08;Template Method Pattern&#xff09;是一种行为设计模式&#xff0c;它定义了一个算法的框架&#xff0c;将特定步骤的实现延迟到子类中。模板方法模式通过在父类中定义算法的骨架&#xff0c;而将具体步骤的实现留给子类来完成&#xff0c;从而使子类…

Python学习之-正则表达式

目录 前言&#xff1a;1.re.serach1.1例子&#xff1a; 2.re.match2.1示例1&#xff1a;2.2 示例2&#xff1a; 3.re.findall3.1 示例 4.re.fullmatch4.1 示例1&#xff1a;4.2 示例2: 5.re.split5.1 示例1:5.2 示例2&#xff1a;5.3 示例3&#xff1a; 6.re.sub6.1 示例&#…

都2024年了,还不知道怎么学习网络安全?来看看吧,很难找全的

前言 最近收到不少关注朋友的私信和留言&#xff0c;大多数都是零基础小友入门网络安全&#xff0c;需要相关资源学习。其实看过的铁粉都知道&#xff0c;之前的文里是有过推荐过的。新来的小友可能不太清楚&#xff0c;这里就系统地叙述一遍。 01.简单了解一下网络安全 说白…

阿里云ubuntu服务器搭建可视化界面

连接终端 最好初始化服务器的时候 不要以root权限创建 否则会出错 1更新软件: sudo apt-get update2安装ubuntu desktop : sudo apt-get install ubuntu-desktop3 配置ubuntu desktop并重启: sudo apt-get -f install sudo dpkg-reconfigure ubuntu-desktop sudo reboot4 su…

QT文件读写操作和内容提取

访问IO设备&#xff0c;需要先调用open()来设置正确的OpenMode(例如ReadOnly或ReadWrite) 打开设备后后&#xff0c;使用write() 或putChar() 写入数据到文件和设备&#xff0c;并通过调用read()&#xff0c;readLine() 或readAll() 进行读取&#xff1b;使用完设备后&#xf…

把本地文件上传到HDFS上操作步骤

因为条件有限&#xff0c;我这里以虚拟机centos为例 实验条件&#xff1a;我在虚拟机上创建了三台节点&#xff0c;部署了hadoop&#xff0c;把笔记本上的数据上传到hdfs中 数据打包上传到虚拟机节点上 采用的是rz命令&#xff0c;可以帮我们上传数据 没有的话可以使用命令安装…

JetBrains全家桶激活,分享 WebStorm 2024 激活的方案

大家好&#xff0c;欢迎来到金榜探云手&#xff01; WebStorm公司简介 JetBrains 是一家专注于开发工具的软件公司&#xff0c;总部位于捷克。他们以提供强大的集成开发环境&#xff08;IDE&#xff09;而闻名&#xff0c;如 IntelliJ IDEA、PyCharm、和 WebStorm等。这些工具…

使用Qt生成图片

Qt之生成png/jpg/bmp格式图片_qt生成图片-CSDN博客 (1)使用QPainter 示例关键代码&#xff1a; QImage image(QSize(this->width(),this->height()),QImage::Format_ARGB32);image.fill("white");QPainter *painter new QPainter(&image);painter->…

PCL点云处理之M估计样本一致性(MSAC)平面拟合(二百三十六)

PCL点云处理之M估计样本一致性(MSAC)平面拟合(二百三十五六) 一、算法介绍二、使用步骤1.代码2.效果一、算法介绍 写论文当然用RANSAC的优化变种算法MSAC啊,RANSAC太土太LOW了哈哈 MSAC算法(M-estimator Sample Consensus)是RANSAC(Random Sample Consensus)的一种…

【计算机网络】启程

&#x1f4dd;本文介绍 本文为计算机网路系列的开始篇&#xff0c;会介绍一下使用的书籍和自己做的思维导图。 &#x1f44b;作者简介&#xff1a;一个正在积极探索的本科生 &#x1f4f1;联系方式&#xff1a;943641266(QQ) &#x1f6aa;Github地址&#xff1a;https://githu…

【蓝桥杯省赛真题34】python积木搭建 中小学青少年组蓝桥杯比赛 算法思维python编程省赛真题解析

python积木搭建 第十三届蓝桥杯青少年组python比赛省赛真题 一、题目要求 &#xff08;注&#xff1a;input&#xff08;&#xff09;输入函数的括号中不允许添加任何信息&#xff09; 1、编程实现 小蓝和小青在玩积木搭建游戏&#xff0c;具体玩法如下: 小蓝报一个数字N&…

Python 从0开始 一步步基于Django创建项目(12)使用装饰器login_required()限制对页面的访问

本文实现功能&#xff1a; 除‘主页’和‘注册’页之外的所有页面&#xff0c;都只有在用户登录后才能访问。 实施方法&#xff1a;在city_infos的views.py文件中&#xff0c;引入装饰器&#xff0c;并在所有视图函数前应用装饰器。 步骤如下&#xff1a; 1、使用import引入…

阿里云-零基础入门NLP【基于深度学习的文本分类3-BERT】

文章目录 学习过程赛题理解学习目标赛题数据数据标签评测指标解题思路BERT代码 学习过程 20年当时自身功底是比较零基础(会写些基础的Python[三个科学计算包]数据分析)&#xff0c;一开始看这块其实挺懵的&#xff0c;不会就去问百度或其他人&#xff0c;当时遇见困难挺害怕的…

android 11 SystemUI 状态栏打开之后的界面层级关系说明之一

比如WiFi 图标的父layout为&#xff1a; Class Name: ButtonRelativeLayout Class Name: QSTileView Class Name: TilePage Class Name: PagedTileLayout Class Name: QSPanel Class Name: NonInterceptingScrollView Class Name: QSContainerImpl Class Name: FrameLayout Cl…

C语言数据结构易错知识点(5)(插入排序、选择排序)

插入排序&#xff1a;直接插入排序、希尔排序 选择排序&#xff1a;直接选择排序、堆排序 上述排序都是需要掌握的&#xff0c;但原理不会讲解&#xff0c;网上有很多详尽地解释&#xff0c;本文章主要分享一下代码实现上应当注意的事项 1.直接插入排序&#xff1a; 代码实…

RK3568驱动指南|第十四篇 单总线-第155章 单总线简介

瑞芯微RK3568芯片是一款定位中高端的通用型SOC&#xff0c;采用22nm制程工艺&#xff0c;搭载一颗四核Cortex-A55处理器和Mali G52 2EE 图形处理器。RK3568 支持4K 解码和 1080P 编码&#xff0c;支持SATA/PCIE/USB3.0 外围接口。RK3568内置独立NPU&#xff0c;可用于轻量级人工…