第1周：数值计算篇

2019年3月19日 上午9:51

针对的问题以及要达到的目的：

1. 数值计算，我并没有按网上的教程以及一些书的目录的步骤去学习算法，他们很多都是从堆栈开始讲起的。
2. 我认为这样不好的原因：
   1. 目的性不强，这样会导致学习效率低下，并且会很快忘记。
3. 我的做法：
   1. 结合当前的切实问题和需要来针对性的练习

主要参考文章：

1. LeetCode总结 — 数值计算篇 - Code Ganker - CSDN博客
   1. LeetCode Reverse Integer 翻转整数 - Grandyang - 博客园
   2. Reverse Integer — LeetCode - Code Ganker - CSDN博客

链接：

1. Reverse Integer - LeetCode
2. Palindrome Number - LeetCode
3. Sqrt(x) - LeetCode
4. Pow(x, n) - LeetCode

详情：

1. Reverse Integer - LeetCode

   class Solution {
   public:
       int reverse(int x) {
           //考虑可以溢出:1000*0009
           
           
           //负数转正数
           int neg = 0;
           
           if(x<0){
               //排除：-128~127中的-128去反128就直接溢出了
               if(x == (-1*INT_MAX -1)) return 0;
               
               x *= -1;
               neg = 1;
           }
           
           //反转
           long long rev=0;
           while(x>0){
               rev = rev*10 + x%10;//赋值的过程都可能溢出，所以要检验
               if(rev > INT_MAX){
                   return 0;
               }
               
               x = x/10;
           }
           
           //检验溢出
           if(rev > INT_MAX){
               return 0;
           }
           else if(neg){
               return -rev;
           }
           else{
               return rev;
           }
           
       }
   };

2. Palindrome Number - LeetCode

   class Solution {
   public:
       bool isPalindrome(int x) {
           //考虑负数
           if(x<0){
               return false;
           }  
           int div = x;
           int index = 1;
           int ten = 1;
           //统计长度index
           while(div >= 10){
               div = div/10;
               index++;
               //计算倍数
               ten *= 10;
           }
           
           cout<<index<<endl;
           //首尾进行比较
           for(int i=0; i <= index/2 ; i++){
               //取首
               int begin = x/ten;
               begin = begin%10;
               ten /= 10;
               
               int end;
               //计算倍数
               int k = i;
               int temp=1;
               while(k--){
                   temp*=10;
               }
               //取尾
               end = x/(temp);
               end = end%10;
               
               //cout<<begin<<" "<<end <<" "<<i<<endl;
               //比较
               if(begin != end) return false;          
           }
           
           return true;
           
       }
   };

3. Sqrt(x) - LeetCode

   class Solution {
   public:
       int mySqrt(int x) {
           //变成二分搜索问题
           
           if(x == 0) return 0;
           if(x == 1) return 1;
           
           long long begin=0;
           long long end=x;
           long long mid = (begin+end)/2;
           
           while(begin <= end){
               
               long long temp = mid*mid;
               if(temp == x){
                   return mid;
               }
               else if(temp > x){
                   end = mid;
               }
               else if(temp < x){
                   if((mid+1)*(mid+1) > x){
                       return mid;
                   }
                   begin = mid;
               }
               
               mid = (begin+end)/2;
           }
           return 0;
       }
   };

4. Pow(x, n) - LeetCode

   /*
   没过的例子：
   1.00000
   -2147483648
   
   
   Input
   34.00515
   -3
   Output
   0.00086
   Expected
   3e-05
   
   2
   -1
   
   */
   class Solution {
   public:
       double myPow(double x, int n) {
           if(n == 1) return x;
           if(n == 0) return 1;
           
           int flag = 0;
           long long n_2= n;
           if(n < 0){
               flag = 1;
               n_2 *= -1;//-2147483648去反会溢出
           }
           
           double temp = myPow(x,n_2/2);
           if(n_2%2 == 1){
               temp= temp*temp*x;
           }
           else{
               temp= temp*temp;
           }
           cout<<flag<<endl;
           if(flag == 1){
               return 1/temp;
           }
           return temp;
           
       }
   };