剑指offer中数据结构与算法部分笔记(2)

class Linuxidc {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        if(threshold<=0||rows<=0||cols<=0) return 0;
        bool *visited=new bool[rows*cols];
        for(int i=0;i<rows*cols;i++)
            visited[i]=false;
        int res=getCount(rows,cols,0,0,threshold,visited);
        delete[] visited;
        return res;
    }
    int getCount(int rows,int cols,int row,int col,int threshold,bool* visited){
        int count=0;
        if(!visited[row*cols+col]&&(getSum(row,col)<=threshold)&&row>=0&&col>=0&&row<rows&&col<cols){
            visited[row*cols+col]=true;
            count=1+getCount(rows,cols,row-1,col,threshold,visited)+getCount(rows,cols,row+1,col,threshold,visited)+getCount(rows,cols,row,col-1,threshold,visited)+getCount(rows,cols,row,col+1,threshold,visited);
        }
        return count;
    }
    int getSum(int rows,int cols){
        int sum=0;
        while(rows>0||cols>0){
            sum+=(rows%10+cols%10);
            rows/=10;
            cols/=10;
        }
        return sum;
    }
};

2.4.4 动态规划与贪婪算法

动规：

分解成很多子问题；

整体的问题依赖于子问题

子问题之间还有相互重叠的更小的子问题

从上往下分析，从下往上求解（顺序先计算出小问题的最优解并存储下来）

题-剪绳子：使用动态规划来做（两个循环 O（n方））；用贪婪法（o（1）的时间和空间，需要证明）；

2.4.5 位运算

与、或、异或、左右移（计算效率比乘除高）；

注意右移时如果是负数的话补的是1，还有把整数减去1之后与原来的数做位与运算后结果相当于把整数的二进制表示中最右边的1变为0，很多二进制问题可以用这个套路；

题-二进制中1的个数

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

Linux公社的RSS地址：https://www.linuxidc.com/rssFeed.aspx