תיאור השאלה
Given a non-negative integer x, return the square root of x rounded down to the nearest integer. You may not use any built-in exponent function or operator.
איך פותרים?
חיפוש בינארי על התשובה: מחפשים את המספר הגדול ביותר m כך ש־m·m ≤ x. אם m·m קטן או שווה ל־x שומרים אותו וממשיכים ימינה, אחרת שמאלה. סיבוכיות: O(log x).
פתרון קוד
JavaScript
Python
function mySqrt(x) {
let left = 0;
let right = x;
let answer = 0;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (mid * mid <= x) {
answer = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return answer;
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.