🏆一、零矩阵
编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。
👓①存坐标求解
这道题比较简单的解法就是我们把这个二维数组遍历一遍，然后对于等于0的我们创建一个临时二维数组存储它的横纵坐标。这样，我们再通过临时二维数组就能找到所有为0的数，再把它所在的行和列的数置为0就解决了。
时间复杂度：0(M*N)
空间复杂度：0(M*N)
void setZeroes(int** matrix, int matrixSize, int* matrixColSize) { int ret[matrixSize*(*matrixColSize)][2]; int count=0; for(int i=0;i<matrixSize;++i) { for(int j=0;j<*matrixColSize;++j) { if(matrix[i][j]==0) { ret[count][0]=i; ret[count][1]=j; count++; } } } for(int i=0;i<count;++i) { for(int j=0;j<*matrixColSize;++j) { matrix[ret[i][0]][j]=0; } for(int m=0;m<matrixSize;++m) { matrix[m][ret[i][1]]=0; } } }
👓②标记求解
这道题目的优化就是能否降低它的空间复杂度呢？
1、具体思路：
我们采取标记的方式，二次遍历。第一次遍历，用一个变量flag(初始为false)来表示第一列是否有0，如果那一行的第一个数为0，就将flag置为true；如果数组中哪个数据为0，就把这一列的第一个数和这一行的第一个数置为0.
第二次遍历：我们倒着遍历，对于第一列不遍历，对于每个数执行这样的判断：如果这个数所在的这一行第一个数为0或者它所在的这一列第一个数为0就把它置为0，然后对于不遍历的第一列，由于我们在第一次遍历时标记它是否有0，如果flag为true就置这一行第一个数为0。
void setZeroes(int** matrix, int matrixSize, int* matrixColSize) { int m=matrixSize; int n=*matrixColSize; int flag=false; for(int i=0;i<m;++i) { if(!matrix[i][0]) flag=true; for(int j=1;j<n;++j) { if(!matrix[i][j]) { matrix[i][0]=matrix[0][j]=0;//这是在做标记 } } } //倒着 for(int i=m-1;i>=0;--i) { for(int j=1;j<n;++j) { if(!matrix[i][0]||!matrix[0][j]) { matrix[i][j]=0; } } if(flag) { matrix[i][0]=0; } } }
解释一下上述操作：
1、flag变量用于标记第一列是否有0，有0的话这一列最后肯定要全置为0；
2、对于《如果数组中哪个数据为0，就把这一列的第一个数和这一行的第一个数置为0》这一操作，也是一种标记功能，因为哪个数据为0它所在的行和列必须全为0，方便我们第二次遍历查看。
3、第二次遍历要倒着遍历，正着遍历会对后续判断造成误导。
🏆二、剪绳子
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
👓①动态规划
刚拿道这道题目是比较头疼的，因为一段长度为n的绳子，我们要把它分成几段，要这几段加起来等于n，还要它们乘起来乘积最大，这个问题确实比较麻烦。但是凡事都是正难则反，我们能不能把复杂的问题转换成我们熟悉的简单的问题呢？我们来思考一些问题，计算几个数的乘积最大，是比较麻烦的，比较简单的是计算两个数的乘积最大，那么我们能不能把这个问题转化成计算两个数的乘积呢？
有的老铁可能困惑，我两个数的乘积就能保证最大吗？这里就要再分化一下，如果它的两个数分别也是由两个数加和，然后乘积最大，如此递归下去，就递归到了一个数他恰好是分成两个数乘积最大！！！
这道题我们再来分析一下：
这是比较特殊的几种情况，到了长度为4，情况就变得复杂了，但是他也是两个数相乘时最大（2*2）.所以从4开始，我们要把它们的最大乘积存储到一个数组中，到了5还是从数组中取两个数看哪一对乘积最大，再存储到数组里，这样就能得出每个长度分成若干长度的最大乘积。
时间复杂度：O(n^2)
空间复杂度：O(n)
int cuttingRope(int n) { //绳子最短要可以分成两段 if(n<2) return 0; if(n==2) return 1; if(n==3) return 2; int *TemStore=(int*)malloc(sizeof(int)*(n+1)); if(TemStore==NULL) { perror("malloc fail"); exit(-1); } //对数组进行初始化 TemStore[0]=0; TemStore[1]=1; TemStore[2]=2; TemStore[3]=3; //为什么初始化这几个，因为最短绳子从长度为4开始 int max_length=0; for(int i=4;i<=n;++i) { max_length=0; for(int j=1;j<=i/2;++j)//超过一般就要重复了 { int tmp=TemStore[j]*TemStore[i-j]; if(tmp>max_length) max_length=tmp; TemStore[i]=max_length; } } return TemStore[n]; }
👓②贪婪算法
如果我们按照这样的方式来剪绳子，则各段绳子的长度的乘积将最大；当n>=5时，我们要仅可能多地剪长度为3的绳子，当剩下的绳子长度为4时，把绳子剪成两段长度为2的绳子。
问题：
为什么尽可能多地去剪长度为3的绳子呢？这背后的数学理论比较复杂，简单来说：任何大于1的数都可以由2或3来组成，既然要求乘积最大，那么自然是3越多越好，所以要尽可能多地剪去3，但是当剩下绳子长度为4时，简称两端长度为2的绳子显然乘积更大。
int cuttingRope(int n) { if(n<2) return 0; if(n==2) return 1; if(n==3) return 2; //特殊处理后 int timesOf3=n/3;//有timesOf3段长度为3的绳子 if(n-timesOf3*3==1)//说明剩余了4根绳子，但是由于我们除以3不能余4，只能是1 timesOf3-=1; int timesOf2=(n-timesOf3*3)/2;//2段长度为2的绳子 return (int)pow(3,timesOf3)*(int)pow(2,timesOf2); }
时间复杂度：O(1)
空间复杂度：O(1)
