网站建设升级,三分钟做网站,手机网站开发需求文档,公益404 wordpress一、数组中重复的数字题目描述#xff1a;在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的#xff0c;但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如#xff0c;如果输入长度为7的数组{2,3,1… 一、数组中重复的数字题目描述在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如如果输入长度为7的数组{2,3,1,0,2,5,3}那么对应的输出是第一个重复的数字2。解题思路考虑用哈希表进行操作。第一遍遍历整个数组更新哈希表值第二遍遍历哈希表中对应元素值大于1的元素输出该元素即为待查找元素。classSolution {
public:// Parameters:// numbers: an array of integers// length: the length of array numbers// duplication: (Output) the duplicated number in the array number// Return value: true if the input is valid, and there are some duplications in the array number// otherwise falseboolduplicate(int numbers[], int length, int* duplication){//判空操作if(numbersNULL||length0)returnfalse;//定义并遍历哈希表int hashpub[7]{0};for(int i0;ilength;i){hashpub[numbers[i]];}for(int j0;jlength;j){if(hashpub[numbers[j]]1){duplication[0]numbers[j];returntrue;}}returnfalse;}
};二、二维数组中的查找题目在一个二维数组中每个一维数组的长度相同每一行都按照从左到右递增的顺序排序每一列都按照从上到下递增的顺序排序。请完成一个函数输入这样的一个二维数组和一个整数判断数组中是否含有该整数。解题思路本题可以从左下角或者右上角两个方向进行搜索以从左下角搜索为例若左下角的数字小于待查找数字则应该继续往该行右侧查找若左下角的数字大于待查找数字则应该从上面的行查找。#方法一从左下角开始遍历
classSolution {
public:boolFind(int target, vectorvectorint array){//判空操作if(array.empty())returnfalse;int rowarray.size()-1; //行遍历int column0;while(row0columnarray[0].size()){if(array[row][column]target)returntrue;elseif(array[row][column]target){row--;}elsecolumn;}returnfalse;}
};
#方法二从右上角开始遍历
classSolution {
public:boolFind(int target, vectorvectorint array){if(array.empty())return0;int row0;int colarray[0].size()-1;while(col0rowarray.size()){if(targetarray[row][col])return1;elseif(targetarray[row][col])col--;elserow;}return0;}
};三、构建乘积数组题目给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]A[0]*A[1]*...*A[i-1]*A[i1]*...*A[n-1]。不能使用除法。注意规定B[0] A[1] * A[2] * ... * A[n-1]B[n-1] A[0] * A[1] * ... * A[n-2];解题思路这里可以考虑B[j](A[0]*...*A[j-1])*(A[j1]*...*A[n-1])两部分分别求解先对右半部分乘再对左半部分乘。classSolution {
public:vectorint multiply(const vectorint A){int nA.size();vectorintB(n);int ret1;//求右边for(int i0;in;ret*A[i]){B[i]ret;}ret1;for(int jn-1;j0;ret*A[j--]){B[j]*ret;}return B;}
};四、调整数组顺序使奇数位于偶数前面题目描述输入一个整数数组实现一个函数来调整该数组中数字的顺序使得所有的奇数位于数组的前半部分所有的偶数位于数组的后半部分并保证奇数和奇数偶数和偶数之间的相对位置不变。解题思路本题要求不仅仅是奇数部分位于前半部分还有偶数部分位于后半部分要想保证相对位置不变就不能单纯通过穷举遍历来进行交换因此在这里我用冒泡排序来解决时间复杂度是编辑。classSolution {
public:voidreOrderArray(vectorint array){//使用冒泡排序for(int i0;iarray.size();i) //外层控制趟数for(int jarray.size()-1;ji;j--)if(array[j]%2!0array[j-1]%20){int tmparray[j];array[j]array[j-1];array[j-1]tmp;}}
};五、旋转数组的最小数字考点查找题目把一个数组最开始的若干个元素搬到数组的末尾我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转该数组的最小值为1。NOTE给出的所有元素都大于0若数组大小为0请返回0。解题思路本题可以考虑使用顺序查找的方法时间复杂度为o(n)。同时亦可以考虑使用二分查找的思路由题目可以知后面部分总比前面部分小那么只要将中间元素和左右两边进行对比就可以知道最小值是在哪一边了然后循环使用这种方法最终只要right和left相邻则right值即为最小值位置。注意在《剑指offer》中指出了两种我们需要考虑的情况1、若排序数组的前面0个数字跑到最后面即数组没变化那么这时候第一个元素就是最小值不用进行这么多遍历了2、如果存在只挪动了1个元素的数组如{0,1,1,1}-{1,0,1,1}这时候只能靠直接遍历了classSolution {
public:intminNumberInRotateArray(vectorint rotateArray){//判空操作if(rotateArray.empty())return0;int left0,rightrotateArray.size()-1,midleft;while(rotateArray[left]rotateArray[right]){mid(leftright)/2;if(right-left1){midright;break;}if(rotateArray[mid]rotateArray[right])rightmid;elseif(rotateArray[mid]rotateArray[left])leftmid;if(rotateArray[left]rotateArray[mid]rotateArray[left]rotateArray[right])returnByOrder(rotateArray,left,right);}if(leftright)return0;return rotateArray[mid];}intByOrder(vectorinta,int l,int r){int mina[l];for(int il;ir;i)if(a[i]min){mina[i];}return min;}
};六、调整数组顺序使奇数位于偶数前面题目描述输入一个整数数组实现一个函数来调整该数组中数字的顺序使得所有的奇数位于数组的前半部分所有的偶数位于数组的后半部分并保证奇数和奇数偶数和偶数之间的相对位置不变。解题思路两次遍历第一次遍历只保存奇数的数第二次保存在第一次的基础上只是这次保留的是偶数。classSolution {
public:voidreOrderArray(vectorint array){int sizearray.size();if(size0) return;vectorintres;for(int i0;isize;i){if(array[i]%2!0)res.push_back(array[i]);}for(int i0;isize;i){if(array[i]%20)res.push_back(array[i]);}arrayres;}
};反思如果题目没有相对位置不变的要求那么考虑使用快慢指针头指针遍历前面的尾指针遍历后面的头指针遍历到偶数就和尾指针交换值尾指针遍历到奇数就和头指针交换值。classSolution {
public:voidreOrderArray(vectorint array){int sizearray.size();if(size0) return;int begin0,endsize-1;while(beginend){while(beginendarray[begin]%2!0)begin;while(beginendarray[end]%20)end--;//交换if(beginend){int tmparray[begin];array[begin]array[end];array[end]tmp;}}}
};七、旋转矩阵题目要求实现矩阵顺时针旋转90度解题思路找到替换公式本题迎刃而解。即编辑//方法一时间复杂度和空间复杂度皆为O(n^2)classSolution {
public:voidrotate(vectorvectorint matrix){int n matrix.size();// C 这里的 拷贝是值拷贝会得到一个新的数组auto matrix_new matrix;for (int i 0; i n; i) {for (int j 0; j n; j) {matrix_new[j][n - i - 1] matrix[i][j];}}// 这里也是值拷贝matrix matrix_new;}
};
//方法二节省空间复杂度的办法classSolution {
public:voidrotate(vectorvectorint matrix){int n matrix.size();for (int i 0; i n / 2; i) {for (int j 0; j (n 1) / 2; j) {int temp matrix[i][j];matrix[i][j] matrix[n - j - 1][i];matrix[n - j - 1][i] matrix[n - i - 1][n - j - 1];matrix[n - i - 1][n - j - 1] matrix[j][n - i - 1];matrix[j][n - i - 1] temp;}}}
};反思 水平翻转编辑 主对角线翻转八、数组中只出现一次的数字题目描述一个整型数组里除了两个数字之外其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。解题思路本题考查了异或操作。 首先从头到尾遍历遍历出来不相同的数字 然后通过位运算便利出来第二个出现了一次的数字 最后找出来第一个出现了一次的数字classSolution {
public:voidFindNumsAppearOnce(vectorint data,int* num1,int *num2){int lendata.size();if(len2) return;int counter0;//先从头到尾遍历遍历出来不同的数字for(int i0;ilen;i)counterdata[i]^counter;int flag1;while(flag){if(flagcounter)break;flagflag1; //逐个遍历}for(int i0;ilen;i){if((data[i]flag)) *num1*num1^data[i];else *num2*num2^data[i];}}
};九、数字在排序数组中出现的次数题目描述:统计一数字在排序数组中出现的次数。解题思路使用两次遍历的方法第一次使用二人查找把相同的末位元素遍历出来第二遍在数相同的有多少个。classSolution {
public:intGetNumberOfK(vectorint data ,int k){int start,end,mid,count0,i;unsignedint len data.size();if(!len)return0;start 0;end len-1;mid start;while(startend){mid (startend)/2;if(k data[mid])start mid1;if(kdata[mid])end mid-1;if(kdata[mid])break;}imid;while( (i0) (kdata[i])){i--;count;}imid1;while((ilen) (kdata[i]) ){i;count;}return count;}
};十、剑指 Offer II 001. 整数除法力扣题目描述:给定两个整数 a 和 b 求它们的除法的商 a/b 要求不得使用乘号 *、除号 / 以及求余符号 % 。解题思路使用减法代替除法。classSolution {publicintdivide(int a, int b) {if(aInteger.MIN_VALUEb-1)return Integer.MAX_VALUE;int sign((a0)^(b0))?-1:1;if(a0)a-a;if(b0)b-b;int res0;while(ab){a-b;res;}return sign1?res:-res;}
}
