网站开发服务合同模板,微分销平台搭建,h5页面制作用什么软件,信誉好的宜昌网站建设文章目录 旋转数组的最小数字比较版本号 旋转数组的最小数字
题目链接#xff1a;旋转数组的最小数字
解题思路1#xff1a;遍历求最小值
代码如下#xff1a; int minNumberInRotateArray(vectorint rotateArray) {int min rotateArray[0];for(auto const… 文章目录 旋转数组的最小数字比较版本号 旋转数组的最小数字
题目链接旋转数组的最小数字
解题思路1遍历求最小值
代码如下 int minNumberInRotateArray(vectorint rotateArray) {int min rotateArray[0];for(auto const e: rotateArray){if(e min){min e;}}return min;}解题思路2比大小最小的值一定是从数组最大值开始减小的那个值也就是说第一次不是递增的那个值就是最小值另一种情况是数组的第一个值比如[1,2,2,2,2]这种情况
代码如下 int minNumberInRotateArray(vectorint rotateArray) {for(int i0; irotateArray.size()-1; i){if(rotateArray[i1] rotateArray[i])return rotateArray[i1];}return rotateArray[0];}解题思路3二分
我们将旋转的前后部分看作两段两段分别有序此时我们可以试一试二分我们将大问题不断划分为小问题不断的缩减区间最终得到最小值所在区间得到最小值。
我们用双指针指向区间首尾再求得区间中间值如果区间中点值大于区间最右侧值那么说明最小值在[mid,right]之间如果小于那么最小值在[left,mid]之间如果相等那就逐步缩小范围一步一步跨过相等的那些值再进行比较
代码如下 int minNumberInRotateArray(vectorint rotateArray) {int left 0;int right rotateArray.size() - 1;while(left right){int mid (left right) / 2;if(rotateArray[mid] rotateArray[right]){left mid 1;}else if(rotateArray[mid] rotateArray[right]){right--;}else {right mid;}}return rotateArray[left];}比较版本号
题目链接比较版本号
解题思路双指针
我们用点来对版本号字符串进行分割比较这两个版本号直接使用双指针来进行比较两个指针分别指向两个字符串进行比较
同时由于前导零不参与比较我们不知道数字前面有多少个前导零所以还是将字符串转化为数字比较更方便
代码如下 int compare(string version1, string version2) {int n1 version1.size();int n2 version2.size();int i 0;//version1的指针int j 0;//version2的指针while(i n1 || j n2){long long num1 0;while(i n1 version1[i] ! .){num1 num1*10 (version1[i]-0);i;}i;long long num2 0;while(j n2 version2[j] ! .){num2 num2*10 (version2[j]-0);j;}j;if(num1 num2) return 1;if(num1 num2) return -1;}return 0;}解题思路2分割后比较
以点为间隔将字符串进行分割分割转化为数字存放进数组再依次取出数组中的元素进行一一对比得出结果
代码如下 //拆分版本号的辅助函数void splitstring(vectorint nums, string version){int n version.size(), num 0;for(int i0; in; i){if(version[i] .){nums.push_back(num);num 0;}else{num num*10 (version[i]-0);}}nums.push_back(num);//最后一段数字}int compare(string version1, string version2) {vectorint nums1, nums2;splitstring(nums1, version1);splitstring(nums2, version2);int n1 nums1.size();int n2 nums2.size();int p1 0, p2 0;for(int i0; imax(n1,n2); i){p1 i n1 ? nums1[i] : 0;p2 i n2 ? nums2[i] : 0;if(p1 p2) return 1;if(p1 p2) return -1;}return 0;}
