chapDivideAndConquer.tex

\chapter{分治法}


\section{Pow(x,n)} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:pow}


\subsubsection{描述}
Implement pow(x, n).


\subsubsection{分析}
二分法，$x^n = x^{n/2} \times x^{n/2} \times x^{n\%2}$


\subsubsection{代码}
\begin{Code}
//LeetCode, Pow(x, n)
// 二分法，$x^n = x^{n/2} * x^{n/2} * x^{n\%2}$
// 时间复杂度O(logn)，空间复杂度O(1)
class Solution {
public:
    double pow(double x, int n) {
        if (n < 0) return 1.0 / power(x, -n);
        else return power(x, n);
    }
private:
    double power(double x, int n) {
        if (n == 0) return 1;
        double v = power(x, n / 2);
        if (n % 2 == 0) return v * v;
        else return v * v * x;
    }
};
\end{Code}


\subsubsection{相关题目}

\begindot
\item Sqrt(x)，见 \S \ref{sec:sqrt}
\myenddot


\section{Sqrt(x)} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:sqrt}

\subsubsection{描述}
Implement int \fn{sqrt(int x)}.

Compute and return the square root of \fn{x}.


\subsubsection{分析}
二分查找


\subsubsection{代码}
\begin{Code}
// LeetCode, Sqrt(x)
// 二分查找
// 时间复杂度O(logn)，空间复杂度O(1)
class Solution {
public:
    int sqrt(int x) {
        int left = 1, right = x / 2;
        int last_mid;  // 记录最近一次mid

        if (x < 2) return x;

        while(left <= right) {
            const int mid = left + (right - left) / 2;
            if(x / mid > mid) { // 不要用 x > mid * mid，会溢出
                left = mid + 1;
                last_mid = mid;
            } else if(x / mid < mid) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return last_mid;
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item Pow(x)，见 \S \ref{sec:pow}
\myenddot