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

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

• 穷举

 /**
 * // This is the CustomFunction's API interface.
 * // You should not implement it, or speculate about its implementation
 * class CustomFunction {
 *      f(x: number, y: number): number {}
 * }
 */

function findSolution(customfunction: CustomFunction, z: number): number[][] {

    const results: number[][] = [];
    
    for(let x = 1; x <= 1000; ++x) {
        for(let y = 1; y <= 1000; ++y) {
            if(customfunction.f(x, y) === z) {
                results.push([x, y]);
            }
        }
    }

    return results;
};

• 二分法(基础版)

/**
 * // This is the CustomFunction's API interface.
 * // You should not implement it, or speculate about its implementation
 * class CustomFunction {
 *      f(x: number, y: number): number {}
 * }
 */

function findSolution(customfunction: CustomFunction, z: number): number[][] {

    const results: number[][] = [];

    for (let x = 1; x <= 1000; ++x) {

        if (customfunction.f(x, 1) > z) {
            break;
        }

        let leftY: number = 1,
            rightY: number = 1000;

        while (leftY <= rightY) {

            const mid = (leftY + rightY) >>> 2,
                current = customfunction.f(x, mid);

            if (current === z) {
                results.push([x, mid]);
                break;
            } else if (current > z) {
                rightY--;
            } else {
                leftY++;
            }
        }
    }

    return results;
};

• 二分法(进阶版)

/**
 * // This is the CustomFunction's API interface.
 * // You should not implement it, or speculate about its implementation
 * class CustomFunction {
 *      f(x: number, y: number): number {}
 * }
 */

function findSolution(customfunction: CustomFunction, z: number): number[][] {

    const results: number[][] = [];

    let x: number = 1,
        y: number = 10000;

    while (x <= 10000 && y >= 1) {
        const current: number = customfunction.f(x, y);
        if (current === z) { 
            results.push([x, y]);
            x++; 
            y--;
        } else if (current > z) {
            y--;
        } else {
            x++;
        }
    }

    return results;
};