本文屬于「征服LeetCode」系列文章之一，這一系列正式開(kāi)始于2021/08/12。由于LeetCode上部分題目有鎖，本系列將至少持續(xù)到刷完所有無(wú)鎖題之日為止；由于LeetCode還在不斷地創(chuàng)建新題，本系列的終止日期可能是永遠(yuǎn)。在這一系列刷題文章中，我不僅會(huì)講解多種解題思路及其優(yōu)化，還會(huì)用多種編程語(yǔ)言實(shí)現(xiàn)題解，涉及到通用解法時(shí)更將歸納總結(jié)出相應(yīng)的算法模板。

為了方便在PC上運(yùn)行調(diào)試、分享代碼文件，我還建立了相關(guān)的倉(cāng)庫(kù)。在這一倉(cāng)庫(kù)中，你不僅可以看到LeetCode原題鏈接、題解代碼、題解文章鏈接、同類(lèi)題目歸納、通用解法總結(jié)等，還可以看到原題出現(xiàn)頻率和相關(guān)企業(yè)等重要信息。如果有其他優(yōu)選題解，還可以一同分享給他人。

由于本系列文章的內(nèi)容隨時(shí)可能發(fā)生更新變動(dòng)，歡迎關(guān)注和收藏征服LeetCode系列文章目錄一文以作備忘。

Given a callable function f(x, y) with a hidden formula and a value z, reverse engineer the formula and return all positive integer pairs x and y where f(x,y) == z. You may return the pairs in any order.

While the exact formula is hidden, the function is monotonically increasing, i.e.:

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

The function interface is defined like this:

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);
};

We will judge your solution as follows:

• The judge has a list of 9 hidden implementations of CustomFunction, along with a way to generate an answer key of all valid pairs for a specific z.
• The judge will receive two inputs: a function_id (to determine which implementation to test your code with), and the target z.
• The judge will call your findSolution and compare your results with the answer key.
• If your results match the answer key, your solution will be Accepted.

題意：給你一個(gè)函數(shù)??f(x, y)?和一個(gè)目標(biāo)結(jié)果?z，函數(shù)公式未知，計(jì)算方程?f(x,y) == z?所有可能的正整數(shù) 數(shù)對(duì)?x 和 y。滿足條件的結(jié)果數(shù)對(duì)可以按任意順序返回。盡管函數(shù)的具體式子未知，但它是單調(diào)遞增函數(shù)，也就是說(shuō)：

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

---

解法1 雙重循環(huán)

由于數(shù)據(jù)不大，可以直接暴力循環(huán)。

• 時(shí)間復(fù)雜度：$O(n^2)$
• 空間復(fù)雜度：$O(1)$

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

---

解法2 二分

類(lèi)似LeetCode 15 三數(shù)之和，循環(huán)遍歷 $x$ ，然后對(duì)單調(diào)遞增的 $y$ 進(jìn)行二分搜索。

• 時(shí)間復(fù)雜度：$O(n\log n)$ 。
• 空間復(fù)雜度：$O(1)$

class Solution {
public:vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {vector<vector<int>> ans;for (int x = 1; x <= 1000; ++x) {int yl = 1, yh = 1000;while (yl <= yh) {int mid = (yl + yh) / 2, tz = customfunction.f(x, mid);if (tz == z) {ans.push_back({x, mid});break;} else if (tz > z) yh = mid - 1; // 說(shuō)明y太大了else yl = mid + 1;}}return ans;}
};

---

解法3 抽象BST

官解告訴我們這是240題搜索二維矩陣II的變形題，如果題目讀不懂，不妨看看本題前身240題搜索二維矩陣II是一道怎樣的題目——這道題的題目含義就非常清晰了。最關(guān)鍵的信息在于，對(duì)于給定的 $m\times n$ 矩陣 matrix ，存在以下性質(zhì)：

• 每行的元素從左到右升序排列
• 每列的元素從上到下升序排列

用數(shù)學(xué)語(yǔ)言來(lái)表達(dá)的話，就是對(duì)于下標(biāo)為 $(x,y)$ 的元素 $matrix[x][y]$ ，（在不越界的情況下）一定存在以下兩個(gè)關(guān)系：

• $matrix[x][y]<matrix[x][y+1]$ ，即同一行的元素從左往右單調(diào)遞增
• $matrix[x][y]<matrix[x+1][y]$ ，即同一列的元素從上往下單調(diào)遞增
  
  我們對(duì)240題的搜索過(guò)程如下所示：
  
  如果我們把整個(gè)矩陣 matrix 看作是一棵二叉樹(shù)，每一個(gè)值都是一個(gè)節(jié)點(diǎn)，把起始點(diǎn) $(0,n?1)$ 看作根節(jié)點(diǎn)，左邊的值看作是左節(jié)點(diǎn)，下面的值看作是右節(jié)點(diǎn)，那么這個(gè)二維矩陣可以抽象成一顆二叉搜索樹(shù)BST。我們的搜尋過(guò)程，其實(shí)也遵循BST的搜索原則。

從而對(duì)于本題，我們也可以這么做：

1. 把解也就是 x 和 y 類(lèi)似上圖一樣，看做一個(gè)二維矩陣，高寬均是1000（取值范圍）
2. 從二維數(shù)組右上角開(kāi)始，即 $x=1,y=1000$ 為起始點(diǎn)，將這個(gè)起始點(diǎn)看為二叉搜索樹(shù)的根節(jié)點(diǎn)
3. 由于函數(shù)方程具有單調(diào)性，也就是任一點(diǎn)向左 $(y?1)$ 結(jié)果遞減，任一點(diǎn)向下 $(x+1)$ 結(jié)果遞增
4. 從起始點(diǎn)來(lái)看，向左對(duì)應(yīng)二叉搜索樹(shù)的左子結(jié)點(diǎn)，向下對(duì)應(yīng)二叉搜索樹(shù)的右子結(jié)點(diǎn)
5. 從起始點(diǎn)逐個(gè)得到當(dāng)前 $x$ 和 $y$ 的方程結(jié)果，比目標(biāo)值大則向左移動(dòng)，比目標(biāo)值小則向下移動(dòng)
6. 特別處理：如果已經(jīng)找到了當(dāng)前方程的解之一，怎么移動(dòng)都可以，往左或往下或往左下都行。

完整代碼如下所示：

• 時(shí)間復(fù)雜度：$O(n)$ 。
• 空間復(fù)雜度：$O(1)$ 。

class Solution {
public:vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {vector<vector<int>> ans;int x = 1, y = 1000; // x向右,f=(x,y)遞增,y向下,f(x,y)遞減while (x <= 1000 && y >= 1) {int tz = customfunction.f(x, y);if (tz == z) { // x,y合適ans.push_back({x, y});++x; // 或者--y} else if (tz < z) ++x; // tz太小,增加x以增加tzelse --y; // tz太大,減少y以減少tz}return ans;}
};