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

【1237. 找出给定方程的正整数解】

来源:力扣(LeetCode)

描述:

给你一个函数 f(x, y) 和一个目标结果 z,函数公式未知,请你计算方程 f(x,y) == z 所有可能的正整数 数对 xy。满足条件的结果数对可以按任意顺序返回。

尽管函数的具体式子未知,但它是单调递增函数,也就是说:

  • f(x, y) < f(x + 1, y)
  • f(x, y) < f(x, y + 1)

函数接口定义如下:

interface CustomFunction {
public:// Returns some positive integer f(x, y) for two positive integers x and y based on a formula.int f(int x, int y);
};

你的解决方案将按如下规则进行评判:

  • 判题程序有一个由 CustomFunction9 种实现组成的列表,以及一种为特定的 z 生成所有有效数对的答案的方法。
  • 判题程序接受两个输入:function_id(决定使用哪种实现测试你的代码)以及目标结果 z 。
  • 判题程序将会调用你实现的 findSolution 并将你的结果与答案进行比较。
  • 如果你的结果与答案相符,那么解决方案将被视作正确答案,即 Accepted

示例 1:

输入:function_id = 1, z = 5
输出:[[1,4],[2,3],[3,2],[4,1]]
解释:function_id = 1 暗含的函数式子为 f(x, y) = x + y
以下 x 和 y 满足 f(x, y) 等于 5:
x=1, y=4 -> f(1, 4) = 1 + 4 = 5
x=2, y=3 -> f(2, 3) = 2 + 3 = 5
x=3, y=2 -> f(3, 2) = 3 + 2 = 5
x=4, y=1 -> f(4, 1) = 4 + 1 = 5

示例 2:

输入:function_id = 2, z = 5
输出:[[1,5],[5,1]]
解释:function_id = 2 暗含的函数式子为 f(x, y) = x * y
以下 x 和 y 满足 f(x, y) 等于 5:
x=1, y=5 -> f(1, 5) = 1 * 5 = 5
x=5, y=1 -> f(5, 1) = 5 * 1 = 5

提示:

  • 1 <= function_id <= 9
  • 1 <= z <= 100
  • 题目保证 f(x, y) == z 的解处于 1 <= x, y <= 1000 的范围内。
  • 在 1 <= x, y <= 1000 的前提下,题目保证 f(x, y) 是一个 32 位有符号整数。

方法一:枚举

根据题目给出的 x 和 y 的取值范围,枚举所有的 x, y 数对,保存满足 f(x, y) = z 的数对,最后返回结果。

代码:

class Solution {
public:vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {vector<vector<int>> res;for (int x = 1; x <= 1000; x++) {for (int y = 1; y <= 1000; y++) {if (customfunction.f(x, y) == z) {res.push_back({x, y});}}}return res;}
};

执行用时:124 ms, 在所有 C++ 提交中击败了13.98%的用户
内存消耗:6.2 MB, 在所有 C++ 提交中击败了80.64%的用户
复杂度分析
时间复杂度:O(mn),其中 m 是 x 的取值数目,n 是 y 的取值数目。
空间复杂度:O(1)。返回值不计入空间复杂度。

方法二:二分查找

我们固定 x = x0​ 时,函数 g(y) = f(x0, y) 是单调递增函数,可以通过二分查找来判断是否存在 y = y0 ,使 g(y0) = f(x0, y0) = z 成立。

代码:

class Solution {
public:vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {vector<vector<int>> res;for (int x = 1; x <= 1000; x++) {int yleft = 1, yright = 1000;while (yleft <= yright) {int ymiddle = (yleft + yright) / 2;if (customfunction.f(x, ymiddle) == z) {res.push_back({x, ymiddle});break;}if (customfunction.f(x, ymiddle) > z) {yright = ymiddle - 1;} else {yleft = ymiddle + 1;}}}return res;}
};

执行用时:4 ms, 在所有 C++ 提交中击败了51.61%的用户
内存消耗:6.1 MB, 在所有 C++ 提交中击败了96.77%的用户
复杂度分析
时间复杂度:O(mlogn),其中 m 是 x 的取值数目,n 是 y 的取值数目。
空间复杂度:O(1)。返回值不计入空间复杂度。

方法三:双指针

假设 x1 < x2,且 f(x1, y1) = f(x2, y2) = z,显然有 y1 > y2。因此我们从小到大进行枚举 x,并且从大到小枚举 y,当固定 x 时,不需要重头开始枚举所有的 y,只需要从上次结束的值开始枚举即可。

代码:

class Solution {
public:vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {vector<vector<int>> res;for (int x = 1, y = 1000; x <= 1000 && y >= 1; x++) {while (y >= 1 && customfunction.f(x, y) > z) {y--;}if (y >= 1 && customfunction.f(x, y) == z) {res.push_back({x, y});}}return res;}
};

执行用时:4 ms, 在所有 C++ 提交中击败了51.61%的用户
内存消耗:6.3 MB, 在所有 C++ 提交中击败了17.20%的用户
复杂度分析
时间复杂度:O(m+n),其中 m 是 x 的取值数目,n 是 y 的取值数目。
空间复杂度:O(1)。返回值不计入空间复杂度。
author:LeetCode-Solution

相关文章:

【1237. 找出给定方程的正整数解】

来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 给你一个函数 f(x, y) 和一个目标结果 z&#xff0c;函数公式未知&#xff0c;请你计算方程 f(x,y) z 所有可能的正整数 数对 x 和 y。满足条件的结果数对可以按任意顺序返回。 尽管函数的具体式子…...

java基础学习 day41(继承中成员变量和成员方法的访问特点,方法的重写)

继承中&#xff0c;成员变量的访问特点 a. name前什么都不加&#xff0c;name变量的访问采用就近原则&#xff0c;先在局部变量中查找&#xff0c;若没找到&#xff0c;继续在本类的成员变量中查找&#xff0c;若没找到&#xff0c;继续在直接父类的成员变量中查找&#xff0c…...

【c语言进阶】深度剖析整形数据

&#x1f680;write in front&#x1f680; &#x1f4dc;所属专栏&#xff1a; &#x1f6f0;️博客主页&#xff1a;睿睿的博客主页 &#x1f6f0;️代码仓库&#xff1a;&#x1f389;VS2022_C语言仓库 &#x1f3a1;您的点赞、关注、收藏、评论&#xff0c;是对我最大的激励…...

【信息系统项目管理师】项目管理十大知识领域记忆敲出(采购风险沟通干系人)

【信息系统项目管理师】项目管理十大知识领域记忆敲出&#xff08;采购风险沟通干系人&#xff09; 这里写目录标题【信息系统项目管理师】项目管理十大知识领域记忆敲出&#xff08;采购风险沟通干系人&#xff09;一.项目采购管理记忆敲出1.合同管理&#xff1a;2.规划采购管…...

[LeetCode 1237]找出给定方程的正整数解

题目描述 题目链接&#xff1a;[LeetCode 1237]找出给定方程的正整数解 给你一个函数 f(x, y) 和一个目标结果 z&#xff0c;函数公式未知&#xff0c;请你计算方程 f(x,y) z 所有可能的正整数 数对 x 和 y。满足条件的结果数对可以按任意顺序返回。 尽管函数的具体式子未知…...

6.2 构建 RESTful 应用接口

第6章 构建 RESTful 服务 6.1 RESTful 简介 6.2 构建 RESTful 应用接口 6.3 使用 Swagger 生成 Web API 文档 6.4 实战&#xff1a;实现 Web API 版本控制 6.2 构建 RESTful 应用接口 6.2.1 Spring Boot 对 RESTful 的支持 Spring Boot 提供的spring-boot-starter-web组件完全…...

20230218英语学习

How Italian Artist’s Mild Colors Dominate World of Design 温柔的“莫兰迪色”&#xff0c;如何引领设计时尚&#xff1f; The Morandi color scheme has become an across-the-board fashion that now prevails in the world of design.Soft and sophisticated Morandi c…...

Linux单一服务管理systemctl

基本上systemd这个启动服务机制只有systemctl命令来处理&#xff0c;所以全部的操作都需要使用systemctl systemctl管理单一服务 一般来说服务的启动有两个阶段&#xff0c;一个是开机是否启动&#xff0c;以及现在是否启动 systemctl【command】【unit】 command主要有&…...

【GStreamer 】 TX1中CPU和GPU解码显示海康相机RTSP流

大家好&#xff0c;我是虎哥&#xff0c;今天找了一套海康的相机&#xff0c;想后续测试一下DeepStream用网络相机RTSP流做输入看看后续目标识别和分类。但是还是想先实时看看视频&#xff0c;当然&#xff0c;可以选择VLC去查看&#xff0c;顺道我也用GStreamer 来测试了一下&…...

匿名内部类、Lambda表达式、方法引用对比分析

文章目录一、匿名内部类1. 语法格式2. 使用方法① 传统方式② 匿名内部类方式二、Lambda表达式1. 语法格式2. 使用方法① 匿名内部类方式② Lambda表达式方式三、方法引用1. 语法格式2. 使用方法① 类型的静态方法引用② 类型的构造方法引用③ 类型的实例方法引用④ 对象的实例…...

ESXi主机CVE-2021-21972漏洞复现安全处置建议

一、漏洞简介 vSphere 是 VMware 推出的虚拟化平台套件&#xff0c;包含 ESXi、vCenter Server 等一系列的软件。其中 vCenter Server 为 ESXi 的控制中心&#xff0c;可从单一控制点统一管理数据中心的所有 vSphere 主机和虚拟机。 vSphere Client&#xff08;HTML5&#xf…...

研报精选230217

目录 【行业230217毕马威】奢侈品行业新气象【行业230217国信证券】医药生物行业2023年2月投资策略&#xff1a;持续关注疫后复苏和创新两大主线【行业230217国金证券】航空锻造&#xff1a;稳定格局筑专业化壁垒&#xff0c;顺势而为拓产业链深度【个股230217西南证券_招商轮船…...

c++11 标准模板(STL)(std::unordered_set)(一)

定义于头文件 <unordered_set> template< class Key, class Hash std::hash<Key>, class KeyEqual std::equal_to<Key>, class Allocator std::allocator<Key> > class unordered_set;(1)(C11 起)namespace pmr { templ…...

【C语言进阶】你听说过柔性数组吗?

&#x1f466;个人主页&#xff1a;Weraphael ✍&#x1f3fb;作者简介&#xff1a;目前是C语言学习者 ✈️专栏&#xff1a;C语言航路 &#x1f40b; 希望大家多多支持&#xff0c;咱一起进步&#xff01;&#x1f601; 如果文章对你有帮助的话 欢迎 评论&#x1f4ac; 点赞&a…...

[LeetCode]1237. 找出给定方程的正整数解

题目链接&#xff1a;https://leetcode.cn/problems/find-positive-integer-solution-for-a-given-equation/description/ 题目描述&#xff1a; 样例1&#xff1a; 输入&#xff1a;function_id 1, z 5 输出&#xff1a;[[1,4],[2,3],[3,2],[4,1]] 解释&#xff1a;functi…...

【路径规划】基于A*算法和Dijkstra算法的路径规划(Python代码实现)

&#x1f468;‍&#x1f393;个人主页&#xff1a;研学社的博客&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5;&#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密…...

蓝桥杯 stm32 PWM 设置占空比

本文代码使用 HAL 库。 文章目录 前言一、创建CubeMX 工程 ,占空比分析:二、相关函数:1. 获取 CNT函数2.设置CNT为 0 函数(计算器清零)3.开启TIM2_CH1的输入捕获中断函数4.TIM 回调函数三、设置上升沿,下降沿四、在lcd上显示 R40 占空比 详细代码五、设置占空比,输出 PW…...

React 合成事件理解

1 事件三个阶段 捕获、目标、处理 &#xff08;具体百度&#xff0c;后面有空补全&#xff09;2import React from "react";class Test extends React.Component {parentRef;childRef;constructor(props) {super(props);this.parentRef React.createRef();this.chil…...

202302|读书笔记——国图点滴

杂志剪影|看一本赚一本系列 anywhere 随心而行随心而动&#xff0c;极简相生复古文艺 热情洋溢 色彩斑斓 极致优雅 深邃魅力 新生绽放 灿若星空 异彩纷呈含苞待放 惊艳绽放 爱在云端 空中婚礼 暗夜浪漫 策马逐梦橘影相映 浆果红唇 梦幻无暇 永无止境浮光掠影 微酥清风低调奢华…...

Linux 操作系统原理 — NUMA 架构中的多线程调度开销与性能优化

目录 文章目录 目录前言NUMA 架构中的多线程性能开销1、跨 Node 的 Memory 访问开销2、跨 Core 的多线程 Cache 同步开销3、多线程上下文切换开销4、多线程模式切换开销5、中断处理的开销6、TLB 缓存失效的开销7、内存拷贝的开销NUMA 架构中的性能优化:使用多核编程代替多线程…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...