写点什么

LeetCode 题解:1237. 找出给定方程的正整数解,双指针,详细注释

作者:Lee Chen
  • 2023-02-18
    福建
  • 本文字数:580 字

    阅读完需:约 2 分钟

LeetCode题解:1237. 找出给定方程的正整数解,双指针,详细注释

原题链接:https://leetcode.cn/problems/find-positive-integer-solution-for-a-given-equation/


解题思路:


  1. 回顾题目给出的两个条件:

  2. f(x, y) < f(x + 1, y)

  3. f(x, y) > f(x, y - 1),由f(x, y) < f(x, y + 1)变化而来

  4. 如果我们先声明let x = 1, y = 1000,相对于z有以下几种情况:

  5. f(x, y) < z时,只需要将x++

  6. f(x, y) > z时,只需要将y--

  7. f(x, y) === z时,当前xy是一个解

  8. x === 1000y === 1时,所有的解都已经查找出来


/** * @param {CustomFunction} customfunction * @param {integer} z * @return {integer[][]} */var findSolution = function(customfunction, z) {  let result = [] // 存储结果
for ( // x默认值为左边界,y默认值为右边界 let x = 1, y = 1000; // x向右移动,y向左移动,x和y都到达边界时,表示已经查找到所有结果,退出循环 x <= 1000 && y >= 1; ) { // 计算当前x、y对应的结果 const subResult = customfunction.f(x, y)
// f(x, y) < f(x + 1, y) if (subResult < z) { x++ } // f(x, y) > f(x, y - 1) else if(subResult > z) { y-- } else { // f(x, y) === z,存储[x, y],并移动x和y result.push([x++, y--]) } }
return result};
复制代码


复杂度分析:


  • 时间复杂度:

  • 空间复杂度:。返回值不计入空间复杂度

发布于: 2023-02-18阅读数: 29
用户头像

Lee Chen

关注

还未添加个人签名 2018-08-29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:1237. 找出给定方程的正整数解,双指针,详细注释_LeetCode_Lee Chen_InfoQ写作社区