剑指offer（三）

11. 旋转数组的最小数字

二分法，书上说考的是二分法。。

class Solution { public: int minNumberInRotateArray(vector<int> rotateArray) { int size=rotateArray.size(); if(size==0) return 0; if(size==1) return rotateArray[0]; int begin=0,end=size-1; while(begin<end){ int mid=begin+(end-begin)/2; if(rotateArray[mid]>rotateArray[end]) begin=mid+1; else if(rotateArray[mid]==rotateArray[end]) end-=1; else { end=mid; } } return rotateArray[end]; } };

12. 矩阵中的路径

回溯，使用的递归

class Solution { public: bool hasPath(char* matrix, int rows, int cols, char* str) { for(int i=0;i<rows;i++){ for(int j=0;j<cols;j++){ if(matrix[i*cols+j]==str[0]){ vector<vector<int>> flag(rows,vector<int>(cols,0)); if(has(flag,matrix,rows,cols,i,j,str,0)) return true; } } } return false; } private: bool has(vector<vector<int>> flag,char* matrix,int rows, int cols, int row, int col, char* str, int indexstr){ if(flag[row][col]==1 || row<0 ||col<0 || row>=rows || col>=cols || matrix[row*cols+col]!=str[indexstr]) return false; if(str[indexstr+1]=='\0') return true; //需先令flag=1，否则先判断是正确的字符就会造成重复遍历 flag[row][col]=1; if(has(flag,matrix,rows,cols,row,col+1,str,indexstr+1) || has(flag,matrix,rows,cols,row,col-1,str,indexstr+1) || has(flag,matrix,rows,cols,row+1,col,str,indexstr+1) || has(flag,matrix,rows,cols,row-1,col,str,indexstr+1)) return true; flag[row][col]=0; return false; } };

13. 机器人的运动范围

class Solution { public: int movingCount(int threshold, int rows, int cols) { vector<vector<int>> flag(rows,vector<int>(cols,0)); int count=0; //将不能运动的点标为1 for(int i=0;i<rows;i++){ for(int j=0;j<cols;j++){ int ii=i ,jj=j; int hold=0; while(ii>=1){ hold+=ii%10; ii/=10; } while(jj>=1){ hold+=jj%10; jj/=10; } if(hold>threshold) flag[i][j]=1; } } //将运动到的点标为2 moving(threshold, 0, 0,rows,cols,flag); //统计2的个数 for(int i=0;i<rows;i++){ for(int j=0;j<cols;j++){ if(flag[i][j]==2) count++; } } return count; } private: void moving(int threshold,int row,int col,int rows,int cols,vector<vector<int>>& flag){ if(row<0||col<0||row>=rows || col>=cols) return; if(flag[row][col]) return; flag[row][col]=2; moving(threshold, row+1, col ,rows,cols,flag); moving(threshold, row-1, col ,rows,cols,flag); moving(threshold, row , col+1,rows,cols,flag); moving(threshold, row , col-1,rows,cols,flag); return; } };

书上的方法，更简洁明了。

class Solution { public: int movingCount(int threshold, int rows, int cols) { if(rows<=0||cols<=0||threshold<0) return 0; //flag用于标记是否已被访问，防止重复计数； vector<vector<int>> flag(rows,vector<int>(cols,0)); return moving(threshold, 0, 0,rows,cols,flag); } private: int moving(int threshold,int row,int col,int rows,int cols,vector<vector<int>>& flag){ if(row<0||col<0||row>=rows || col>=cols||flag[row][col]==1) return 0; flag[row][col]=1; int hold=0; int ii=row,jj=col; while(ii>=1){ hold+=ii%10; ii/=10; } while(jj>=1){ hold+=jj%10; jj/=10; } if(hold>threshold) return 0;; int count=0; count = 1+moving(threshold, row+1, col ,rows,cols,flag)+moving(threshold, row-1, col ,rows,cols,flag)+moving(threshold, row , col+1,rows,cols,flag)+moving(threshold, row , col-1,rows,cols,flag); return count; } };

14. 二进制中1的个数

自己的笨方法

class Solution { public: int NumberOf1(int n) { int count=0; if(n>=0){ while(n>0){ if(n&1) count++; n=n>>1; } } else{ int x=0; while(n!=-1){ if(n&1) count++; n=n>>1; x++; } count+=(32-x); } return count; } };

书上的方法，n&(n-1)可以将最右边的1变为0

class Solution { public: int NumberOf1(int n) { int count=0; while(n!=0){ n=n&(n-1); count++; } return count; } };

15. 数值的整数次方

class Solution { public: double Power(double base, int exponent) { if(!base) return 0; if(exponent==0) return 1; double result; int n=abs(exponent); while(n--){ result*=base; } if(exponent<0) return 1/result; else return result; } };

这个方法可以将时间复杂度降低一半

class Solution { public: double Power(double base, int exponent) { //if(!base) return 0; if(exponent==0) return 1; if(exponent==1) return base; int exp=abs(exponent); double result=1.0; while(exp>1){ if(exp&1) result*=base; result*=result; exp>>=1; } if(exp&1) result*=base; return exponent>0? result : 1/result; } };