50. Pow(x, n)

快速幂的思路很简单，就是对于一个数 k ，我们求其 n 次幂，就只需要将n进行拆分就行

  1. 即：
  2. 对于 k^9 来说，9可以表示为 1001，即 2^3 + 2^0
  3. 即求：k^(2^3) + k^(2^0)
  5. 那么求解的时候就可以：
  6.     左移幂，不断乘以2，
  7.     如果最后一位为1的时候，说明这个幂可以放入作为幂次计算
  8.     此时将幂次计算进去即可

代码如下：

  1.  pub fn my_pow(mut x: f64, mut n: i32) -> f64 {
  2.      if n == 0 { return 1.0; }
  3.      // 注意这一句，在负数最大的时候会溢出，边界
  4.      let mut n = n as i64;
  5.      if n < 0 {
  6.          x = 1.0_f64 / x;
  7.          n = -n;
  8.      }
  9.      let mut res = 1.0;
  10.      let mut contribute = x;
  11.      while n > 0 {
  12.          if n & 1 == 1 {
  13.              res *= contribute;
  14.          }
  15.          n = n >> 1;
  16.          // 注意每一次的增加的值都是自身相乘
  17.          contribute *= contribute;
  18.      }
  20.      res
  21.  }

上面的快速幂算法可以引导出倍增算法，我们可以使用这种思想实现乘法

从快速幂到倍增：实现乘法

直接看代码：
注意比较倍增与二次幂的区别

  1. // 倍增的思想实现乘法
  2. pub fn multiply(mut x: i64, mut y: i64) -> i64{
  3.     // 对于x*y，我们可以转换为 x*y(2)
  4.     // 比如 k * 9 = k * (1001) = k + k * 8 = k + (k + K)重复8次    倍增
  5.     // 比较二次幂: k^9 = k^(1001) = (k*K)重复8次 + K                倍乘
  6.     let mut res = 0;
  7.     let mut flag = 0;
  8.     // 处理正负问题
  9.     if (x<0 && y>0) || (y<0 && x>0) {
  10.         flag = 1;
  11.     }
  12.     if x < 0 { x = -x; }
  13.     if y < 0 { y = -y; }
  15.     while y > 0 {
  16.        if y & 1 == 1 {
  17.            res += x;
  18.        }
  19.        y = y >> 1;
  20.        x += x;
  21.     }
  22.     return match flag {
  23.         0 => res,
  24.         1 => -res,
  25.         _ => panic!("wrong!!!!")
  26.     }
  27. }

倍增的应用：29. 两数相除

两数相除的暴力解法就是o(n)的一直减下去，另一个做法就是使用中间值去试乘
注意一个点：这儿只能用右二分，返回左

  1. // 两数相除:x/y
  2. pub fn divide(mut x: i32, mut y: i32) -> i32 {
  3.     // 这个情况很恶心，在x为i32::MIN时会被绕过
  4.     if y == 1 { return x; }
  5.     let mut flag = 0;
  6.     // 注意处理溢出，很简单，转换即可
  7.     let mut x = x as i64;
  8.     let mut y = y as i64;
  9.     // 处理正负问题
  10.     if (x<0 && y>0) || (y<0 && x>0) {
  11.         flag = 1;
  12.     }
  13.     if x < 0 { x = -x; }
  14.     if y < 0 { y = -y; }
  16.     let mut l = 0 as i64;
  17.     let mut r = x;
  18.     while l < r {
  19.         let mid = l + ((r - l +1) >> 1);
  20.         if Self::multiply(mid, y) <= x {
  21.             l = mid ;
  22.         }else { r = mid -1 ; }
  23.     }
  25.     // 因为返回i32，所以还要处理溢出
  26.     if l > i32::MAX as i64 || l < i32::MIN as i64 {
  27.         return i32::MAX
  28.     }else { 
  29.         return match flag {
  30.             0 => l as i32,
  31.             1 => -l as i32,
  32.             _ => panic!("!!!!")
  33.         }
  34.     }
  35. }