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

米哈游(原神)终面算法原题

恒大正式破产

准确来说,是中国恒大(恒大汽车、恒大物业已于 2024-01-30 复牌)。

恒大破产,注定成为历史的注目焦点。

作为首个宣布破产的房地产企业,恒大的破产规模也创历史新高。

房地产作为推动中国三分之一经济增长的行业,恒大是当中毫无疑问的佼佼者。

能够成就这样的巨无霸,自然是有时代和政策因素的。

在房地产行业的上升周期中,房企普遍的高杠杆率和过度扩张如今成为一种"回旋镖",对各个层面都产生了影响。

即使你和我一样,家里没有几套房,没有买恒大的LW楼,也没有持有恒大系股票,但我们都感受到了这波的消费低迷和各行业的裁员潮,这与房地产去泡沫化不无关系。

中国楼市基本对标美国股市,当一个国家的重要经济载体出现问题(失去信心),普通人不可能独善其身。

当然了,最幸福的人不会变。

仍然是那些无论房地产高歌猛进还是岌岌可危,都自诩与他无关的人(他觉得自己不考虑买房嘛,能有啥关系)。

我相信这批人,和看到《游戏意见稿》就只讨论「该不该给氪金游戏充值」是同一批人。

随他们去吧。

...

回归主线。

自上次写了米哈游的一面原题和变形题之后,又有读者来投稿了。

据说,这次是米哈游(原神)终面算法题

看着确实像,因为这是一道适合「由浅入深」的题目,适合在面试过程中有来有回。

启动!

题目描述

平台:LeetCode

题号:215

给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2

输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4

输出: 4

提示:

值域映射 + 树状数组 + 二分

除了直接对数组进行排序,取第 位的 做法以外。

对于值域大小 小于 数组长度本身时,我们还能使用「树状数组 + 二分」的 做法,其中 为值域大小。

首先值域大小为 ,为了方便,我们为每个 增加大小为 的偏移量,将值域映射到 的空间。

将每个增加偏移量后的 存入树状数组,考虑在 范围内进行二分,假设我们真实第 大的值为 ,那么在以 为分割点的数轴上,具有二段性质:

  • 范围内的数 满足「树状数组中大于等于 的数不低于 个」
  • 范围内的数 不满足「树状数组中大于等于 的数不低于 个」

二分出结果后再减去刚开始添加的偏移量即是答案。

Java 代码:

class Solution {
    int M = 100010, N = 2 * M;
    int[] tr = new int[N];
    int lowbit(int x) {
        return x & -x;
    }
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
        return ans;
    }
    void add(int x) {
        for (int i = x; i < N; i += lowbit(i)) tr[i]++;
    }
    public int findKthLargest(int[] nums, int k) {
        for (int x : nums) add(x + M);
        int l = 0, r = N - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (query(N - 1) - query(mid - 1) >= k) l = mid;
            else r = mid - 1;
        }
        return r - M;
    }
}

C++ 代码:

class Solution {
public:
    int N = 200010, M = 100010, tr[200010];
    int lowbit(int x) {
        return x & -x;
    }
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
        return ans;
    }
    void add(int x) {
        for (int i = x; i < N; i += lowbit(i)) tr[i]++;
    }
    int findKthLargest(vector<int>& nums, int k) {
        for (int x : nums) add(x + M);
        int l = 0, r = N - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (query(N - 1) - query(mid - 1) >= k) l = mid;
            else r = mid - 1;
        }
        return r - M;
    }
};

Python 代码:

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        N, M = 200010100010
        tr = [0] * N
        def lowbit(x):
            return x & -x
        def query(x):
            ans = 0
            i = x
            while i > 0:
                ans += tr[i]
                i -= lowbit(i)
            return ans
        def add(x):
            i = x
            while i < N:
                tr[i] += 1
                i += lowbit(i)
        for x in nums:
            add(x + M)
        l, r = 0, N - 1
        while l < r:
            mid = l + r + 1 >> 1
            if query(N - 1) - query(mid - 1) >= k: l = mid
            else: r = mid - 1
        return r - M

TypeScript 代码:

function findKthLargest(nums: number[], k: number): number {
    const N = 200010, M = 100010;
    const tr = new Array(N).fill(0);
    const lowbit = function(x: number): number {
        return x & -x;
    };
    const add = function(x: number): void {
        for (let i = x; i < N; i += lowbit(i)) tr[i]++;
    };
    const query = function(x: number): number {
        let ans = 0;
        for (let i = x; i > 0; i -= lowbit(i)) ans += tr[i];
        return ans;
    };
    for (const x of nums) add(x + M);
    let l = 0, r = N - 1;
    while (l < r) {
        const mid = l + r + 1 >> 1;
        if (query(N - 1) - query(mid - 1) >= k) l = mid;
        else r = mid - 1;
    }
    return r - M;
};
  • 时间复杂度:将所有数字放入树状数组复杂度为 ;二分出答案复杂度为 ,其中 为值域大小。整体复杂度为
  • 空间复杂度:

优先队列(堆)

另外一个容易想到的想法是利用优先队列(堆),由于题目要我们求的是第 大的元素,因此我们建立一个小根堆。

根据当前队列元素个数或当前元素与栈顶元素的大小关系进行分情况讨论:

  • 当优先队列元素不足 个,可将当前元素直接放入队列中;
  • 当优先队列元素达到 个,并且当前元素大于栈顶元素(栈顶元素必然不是答案),可将当前元素放入队列中。

Java 代码:

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->a-b);
        for (int x : nums) {
            if (q.size() < k || q.peek() < x) q.add(x);
            if (q.size() > k) q.poll();
        }
        return q.peek();
    }
}

C++ 代码:

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<intvector<int>, greater<int>> q;
        for (int x : nums) {
            if (q.size() < k || q.top() < x) q.push(x);
            if (q.size() > k) q.pop();
        }
        return q.top();
    }
};

Python 代码:

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        q = []
        for x in nums:
            if len(q) < k or q[0] < x:
                heapq.heappush(q, x)
            if len(q) > k:
                heapq.heappop(q)
        return q[0]
  • 时间复杂度:
  • 空间复杂度:

快速选择

对于给定数组,求解第 大元素,且要求线性复杂度,正解为使用「快速选择」做法。

基本思路与「快速排序」一致,每次敲定一个基准值 x,根据当前与 x 的大小关系,将范围在 划分为到两边。

同时利用,利用题目只要求输出第 大的值,而不需要对数组进行整体排序,我们只需要根据划分两边后,第 大数会落在哪一边,来决定对哪边进行递归处理即可。

快速排序模板为面试向重点内容,需要重要掌握。

Java 代码:

class Solution {
    int[] nums;
    int qselect(int l, int r, int k) {
        if (l == r) return nums[k];
        int x = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < x);
            do j--; while (nums[j] > x);
            if (i < j) swap(i, j);
        }
        if (k <= j) return qselect(l, j, k);
        else return qselect(j + 1, r, k);
    }
    void swap(int i, int j) {
        int c = nums[i];
        nums[i] = nums[j];
        nums[j] = c;
    }
    public int findKthLargest(int[] _nums, int k) {
        nums = _nums;
        int n = nums.length;
        return qselect(0, n - 1, n - k);
    }
}

C++ 代码:

class Solution {
public:
    vector<int> nums;
    int qselect(int l, int r, int k) {
        if (l == r) return nums[k];
        int x = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < x);
            do j--; while (nums[j] > x);
            if (i < j) swap(nums[i], nums[j]);
        }
        if (k <= j) return qselect(l, j, k);
        else return qselect(j + 1, r, k);
    }
    int findKthLargest(vector<int>& _nums, int k) {
        nums = _nums;
        int n = nums.size();
        return qselect(0, n - 1, n - k);
    }
};

Python 代码:

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def qselect(l, r, k):
            if l == r:
                return nums[k]
            x, i, j = nums[l], l - 1, r + 1
            while i < j:
                i += 1
                while nums[i] < x:
                    i += 1
                j -= 1
                while nums[j] > x:
                    j -= 1
                if i < j:
                    nums[i], nums[j] = nums[j], nums[i]
            if k <= j:
                return qselect(l, j, k)
            else:
                return qselect(j + 1, r, k)

        n = len(nums)
        return qselect(0, n - 1, n - k)

TypeScript 代码:

function findKthLargest(nums: number[], k: number): number {
    const qselect = function(l: number, r: number, k: number): number {
        if (l === r) return nums[k];
        const x = nums[l];
        let i = l - 1, j = r + 1;
        while (i < j) {
            i++;
            while (nums[i] < x) i++;
            j--;
            while (nums[j] > x) j--;
            if (i < j) [nums[i], nums[j]] = [nums[j], nums[i]];
        }
        if (k <= j) return qselect(l, j, k);
        else return qselect(j + 1, r, k);
    };
    const n = nums.length;
    return qselect(0, n - 1, n - k);
};
  • 时间复杂度:期望
  • 空间复杂度:忽略递归带来的额外空间开销,复杂度为

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

欢迎关注,明天见。

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

本文由 mdnice 多平台发布

相关文章:

米哈游(原神)终面算法原题

恒大正式破产 准确来说&#xff0c;是中国恒大&#xff08;恒大汽车、恒大物业已于 2024-01-30 复牌&#xff09;。 恒大破产&#xff0c;注定成为历史的注目焦点。 作为首个宣布破产的房地产企业&#xff0c;恒大的破产规模也创历史新高。 房地产作为曾推动中国三分之一经济增…...

机器学习如何改变缺陷检测的格局?

机器学习在缺陷检测中扮演着重要的角色&#xff0c;它能够通过自动学习和识别各种缺陷的模式和特征&#xff0c;改变缺陷检测的格局。以下是机器学习在缺陷检测中的一些应用和优势&#xff1a; 自动化检测&#xff1a;机器学习技术可以自动化处理大量的数据&#xff0c;通过学…...

【Java万花筒】图数据库 vs 多模型数据库:哪种数据库适合你的应用场景?

解密图数据库与多模型数据库&#xff1a;特性、查询语言和成功案例的全景展示 前言 图数据库和多模型数据库在当今数据处理领域扮演着重要的角色。本文将介绍四个主要的图数据库和多模型数据库&#xff1a;Neo4j、Apache TinkerPop、JGraphT和ArangoDB&#xff0c;探索它们的…...

【射影几何13 】梅氏定理和塞瓦定理探讨

梅氏定理和塞瓦定理 目录 一、说明二、梅涅劳斯&#xff08;Menelaus&#xff09;定理三、塞瓦(Giovanni Ceva&#xff09;定理四、塞瓦点的推广 一、说明 在射影几何中&#xff0c;梅涅劳斯&#xff08;Menelaus&#xff09;定理和塞瓦定理是非常重要的基本定理。通过这两个定…...

Powershell Install 一键部署Openssl+certificate证书创建

前言 Openssl 是一个方便的实用程序,用于创建自签名证书。您可以在所有操作系统(如 Windows、MAC 和 Linux 版本)上使用 OpenSSL。 Windows openssl 下载 前提条件 开启wmi,配置网卡,参考 自签名证书 创建我们自己的根 CA 证书和 CA 私钥(我们自己充当 CA)创建服务器…...

SERVLET线程模型

1. SERVLET线程模型 Servlet规范定义了两种线程模型来阐明Web容器应该如何在多线程环境中处理servlet。第一种模型称为多线程模型,默认在此模型内执行所有servlet。在此模型中,每次客户机向servlet发送请求时Web容器都启动一个新线程。这意味着可能有多个线程同时访问servle…...

【开源】基于JAVA+Vue+SpringBoot的新能源电池回收系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 用户档案模块2.2 电池品类模块2.3 回收机构模块2.4 电池订单模块2.5 客服咨询模块 三、系统设计3.1 用例设计3.2 业务流程设计3.3 E-R 图设计 四、系统展示五、核心代码5.1 增改电池类型5.2 查询电池品类5.3 查询电池回…...

【蓝桥杯冲冲冲】Prime Gift

【蓝桥杯冲冲冲】Prime Gift 蓝桥杯备赛 | 洛谷做题打卡day31 文章目录 蓝桥杯备赛 | 洛谷做题打卡day31Prime Gift题面翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 提示题解代码我的一些话 Prime Gift 题面翻译 给你 n n n 个…...

【PyQt】06-.ui文件转.py文件

文章目录 前言方法一、基本脚本查看自己的uic安装目录 方法二、添加到扩展工具里面&#xff08;失败了&#xff09;方法二的成功步骤总结 前言 方法一、基本脚本 将Qt Designer&#xff08;一种图形用户界面设计工具&#xff09;生成的.ui文件转换为Python代码的脚本。 pytho…...

λ-矩阵知识点

原文:链接 λ-矩阵 若矩阵 A \mathbf{A} A 的元素为关于 λ λ λ 的多项式&#xff0c;则称 A \mathbf{A} A 为 λ λ λ-矩阵 (表示为 A ( λ ) \mathbf{A}(λ) A(λ)). λ λ λ-矩阵也存在秩、逆、初等变换、相抵的概念, 但是有一些不同. 定义. λ λ λ-矩阵的秩是…...

cocos creator 3.x 预制体无法显示

双击预制体&#xff0c;进入详情页&#xff0c;没有显示资源 Bomb 是个预制体&#xff0c;但是当我双击进来什么都没有了&#xff0c;无法对预制体进行可视化编辑 目前我只试出来一个解决方法&#xff1a; 把预制体拖进Canvas文件中&#xff0c;这样就能展示到屏幕上&#xff…...

Tomcat之虚拟主机

1.创建存放网页的目录 mkdir -p /web/{a,b} 2.添加jsp文件 vi /web/a/index.jsp <% page language"java" import"java.util.*" pageEncoding"UTF-8"%> <html> <head><title>JSP a page</title> </head> …...

前后端数据校验

前端校验内容 前端开发中的必要校验&#xff0c;可以保证用户输入的数据的准确性、合法性和安全性。同时&#xff0c;这些校验也有助于提供良好的用户体验和防止不必要的错误提交到后端。 1、必填字段校验&#xff1a; 对于必填的字段&#xff0c;需确保用户输入了有效的数据…...

Python把png图片转成jpg图片

在Python中&#xff0c;您可以使用PIL&#xff08;Python Imaging Library&#xff0c;也被称为Pillow&#xff09;库来将PNG图片转换为JPG格式。以下是一个简单的示例&#xff1a; 首先&#xff0c;确保你已经安装了Pillow库。如果没有安装&#xff0c;可以使用pip来安装&…...

STM32搭建开发环境

常用开发工具简介 集成开发环境 MDK&#xff1a;全名RealViewMDK&#xff0c;是Keil公司&#xff08;已被ARM收购的&#xff09;一款集成开发环境&#xff0c;界面美观&#xff0c;简单易用&#xff0c;是STM32最常用的集成开发环境EWARM&#xff1a;IAR公司的一款集成开发环…...

C#入门详解_01_课程简介、C#语言简介、开发环境和学习资料的准备

文章目录 1. 课程简介2. C#语言简介3.开发环境与学习资料 1. 课程简介 开设本课程的目的 传播C#开发的知识&#xff0c;让更多的人有机会接触到软件开发行业引导有兴趣或者想转行的朋友进入软件开发行业 课程内容 完整讲述C#语言在实际软件开发中的应用采用知识讲述加实例程序…...

C++服务器端开发(2):确定服务器框架

选择C服务器框架时&#xff0c;可以考虑&#xff1a; 并发性能&#xff1a;C的强项之一是其并发性能。选择一个具有高并发处理能力的服务器框架&#xff0c;可以更好地满足大量并发请求的需求。例如&#xff0c;libevent、Boost.Asio和CppServer都是具有良好并发性能的C服务器框…...

CGAL::2D Arrangements-5

5.Arrangement无界曲线 前几章中构建和操作的所有Arrangement都只由线段引起&#xff0c;线段尤其是有界曲线。这样的Arrangement总是具有一个包含所有其他Arrangement特征的unbounded face。在本节中&#xff0c;我们将解释如何构造无界曲线的Arrangement。为了简化说明&…...

登录+JS逆向进阶【过咪咕登录】(附带源码)

JS渗透之咪咕登录 每篇前言&#xff1a;咪咕登录参数对比 captcha参数enpassword参数搜索enpassword参数搜索J_RsaPsd参数setPublic函数encrypt加密函数运行时可能会遇到的问题此部分改写的最终形态JS代码&#xff1a;运行结果python编写脚本运行此JS代码&#xff1a;运行结果&…...

CTF秀 ctfshow WEB入门 web1-10 wp精讲

目录 web1_查看源码 web3_抓包 web4-9_目录文件 web10_cookie web1_查看源码 ctrlu 查看源码 web3_抓包 查看源码&#xff0c;无果 抓包&#xff0c;找到flag web4-9_目录文件 GitHub - maurosoria/dirsearch: Web path scanner 下载dirsearch工具扫一下就都出来了 web4-…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...