推荐网站在线看兄弟们,微信商城在哪里进入,普斯泰网站建设,建设网站个人网上银行33.搜索旋转排序数组
这题如果数组不进行循环平移那用二分做就很简单#xff0c;平移后其实也可以用二分做#xff0c;重点在于二分里面如何check。平移后数组可以分成两段各自升序的数组#xff0c;并且第一段值大于第二段值。check的时候分两种情况#xff0c;一种是tar…33.搜索旋转排序数组
这题如果数组不进行循环平移那用二分做就很简单平移后其实也可以用二分做重点在于二分里面如何check。平移后数组可以分成两段各自升序的数组并且第一段值大于第二段值。check的时候分两种情况一种是target nums[0]这时候target只可能出现在第一段上所以二分到第二段时可以直接return true。第二种情况是target nums[0]这时候target只可能出现在第二段上所以二分到第一段时可以直接return false。
class Solution {
public:int search(vectorint nums, int target) {int ans -1, l 0, r nums.size()-1;while(l r){int mid lr1;if(target nums[0]){if(nums[mid] target || nums[mid] nums[0]){ans mid;r mid-1;}else l mid1;}else{if(nums[mid] target nums[mid] nums[0]){ans mid;r mid-1;}else l mid1;}}if(ans -1 || nums[ans] ! target) return -1;return ans;}
};
31.下一个排列
这道题可以找找规律53421-54123以及54132-54213这两个例子可以看出来每个排列尾部总有一个降序序列然后这个降序序列左边第一个数字一定会被改变并且是与降序序列中某个数字进行了交换交换以后后面的降序序列需要重新排序为升序。
class Solution {
public:void nextPermutation(vectorint nums) {/*5342154123541325421354231*/int index nums.size()-1;while(index 0 nums[index] nums[index-1])index--;if(index 0){sort(nums.begin(), nums.end());return;}for(int i nums.size()-1; i 0; i--){if(nums[i] nums[index-1]){swap(nums[i], nums[index-1]);sort(nums.begin()index, nums.end());break;}}}
};
88.合并两个有序数组
简单的归并操作。
class Solution {
public:void merge(vectorint nums1, int m, vectorint nums2, int n) {vectorint a(nums1.size());int idx1 0, idx2 0;for(int i 0; i a.size(); i){if(idx1 m) a[i] nums2[idx2];else if(idx2 n) a[i] nums1[idx1];else if(nums1[idx1] nums2[idx2]) a[i] nums2[idx2];else a[i] nums1[idx1];}nums1 a;}
};
56.合并区间
比较经典的题目了按左端点排序然后遍历一遍区间维护出当前合并区间的最右端点如果某个新区间左端点大于当前的最右端点那就没法合并了反之可以合并进去。
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {sort(intervals.begin(), intervals.end());vectorvectorint res;int mxr -0x3f3f3f3f, mnl 0x3f3f3f3f;for(int i 0; i intervals.size(); i){if(intervals[i][0] mxr){mxr max(mxr, intervals[i][1]);}else{if(mxr ! -0x3f3f3f3f) res.push_back({mnl, mxr});mnl intervals[i][0];mxr intervals[i][1];}}res.push_back({mnl, mxr});return res;}
};
162.寻找峰值
如果只有一个峰值那就是三分但这里有多个峰值。其实二分也能做根据mid左右的值来判断收缩到哪个区间如果mid-1、mid、mid1位置的值是递增的那选择右区间更好一些如果是递减的那就左区间。
class Solution {
public:int findPeakElement(vectorint nums) {int l 0, r nums.size()-1;while(l r){int mid lr1;int lnum mid?nums[mid-1]:0x80000000;int rnum midnums.size()-1?nums[mid1]:0x80000000;if(nums[mid] lnum nums[mid] rnum)return mid;else if(nums[mid] lnum nums[mid] rnum)l mid1;elser mid-1;}return 0;}
};
4.寻找两个正序数组的中位数
这道题直接归并的话复杂度是O(n)但题目要求log级的复杂度所以这样肯定行不通。正解的话需要先了解怎么求第k小数如果有两个升序数组可以比较它们第k/2个元素大小如果nums1[k/2] nums2[k/2]那么nums1[0~k/2]一定都不可能是第k小数因为此时如果把两数组归并起来那nums1[0~k/2]都排在nums2[k/2]前面都达不到第k小的位置。这样就可以把nums1[0~k/2]这些元素排除掉由于排除了k/21个元素找第k小就相当于在剩下的元素中找第k-(k/21)小。当某个数组中元素全被排除掉或者k 1时达到终态此时退出递归。因为每次都排除掉一半的元素所以时间复杂度是O(logn)。
实现的时候有些细节要注意比如k/2时可以直接下取整访问nums[k/2]可能会越界这时候直接取它最后一个元素vector的size()方法返回无符号数运算时需要转为带符号数。
class Solution {
public:int findTopK(vectorint nums1, int st1, vectorint nums2, int st2, int k){if(st1 (int)nums1.size()-1) return nums2[st2k-1];if(st2 (int)nums2.size()-1) return nums1[st1k-1];if(k 1) return min(nums1[st1], nums2[st2]);int mid k/2-1;int a st1midnums1.size()-1?nums1.size()-1:st1mid;int b st2midnums2.size()-1?nums2.size()-1:st2mid;if(nums1[a] nums2[b])return findTopK(nums1, st1, nums2, b1, k-(b-st21));else return findTopK(nums1, a1, nums2, st2, k-(a-st11));}double findMedianSortedArrays(vectorint nums1, vectorint nums2) {if((nums1.size()nums2.size())1)return findTopK(nums1, 0, nums2, 0, (nums1.size()nums2.size()1)/2);else{int a findTopK(nums1, 0, nums2, 0, (nums1.size()nums2.size())/2);int b findTopK(nums1, 0, nums2, 0, (nums1.size()nums2.size())/21);return (ab)/2.0;}}
};
215.数组中的第K个最大元素
类似快速排序的思路快排中对数组进行一趟操作可以保证第一个元素最终处在正确的位置也就是其左边的元素均小于等于它右边的元素均大于等于它。利用这个特性寻找第k大理想情况下可以每趟排除一半的数据量平均时间复杂度是nn/2n/4n/8...1 O(n)。但这种方法在数据升序时会退化到O(n^2)为了避免退化在每次选取基准元素时应该随机选取。即使加入了随机化当数组元素值全相同时还是会退化到O(n^2)这时候可以用双路或三路快排。
还有一种方法是用优先队列维护一个长度为k的升序的优先队列这种方法时间复杂度为O(nlogk)。
//优先队列做法
class Solution {
public:int findKthLargest(vectorint nums, int k) {priority_queueint, vectorint, greaterint q;for(int i 0; i nums.size(); i){q.push(nums[i]);if(q.size() k) q.pop();}return q.top();}
};
//快排做法
class Solution {
public:int findTopK(vectorint nums, int l, int r, int k){int x rand()%(r-l1)l;swap(nums[x], nums[l]);int i l, j r;while(i j){while(nums[i] nums[j] i j) j--;swap(nums[i], nums[j]); while(nums[i] nums[j] i j) i;swap(nums[i], nums[j]); }if(k r-i) return findTopK(nums, i1, r, k);else if(k r-i1) return nums[i];else return findTopK(nums, l, i-1, k-(r-i1));}int findKthLargest(vectorint nums, int k) {srand(time(NULL));return findTopK(nums, 0, nums.size()-1, k);}
};
34.在排序数组中查找元素的第一个和最后一个位置
两次二分就出来了。
class Solution {
public:vectorint searchRange(vectorint nums, int target) {vectorint res;int ans -1, l 0, r nums.size()-1;while(l r){int mid lr1;if(nums[mid] target){ans mid;r mid-1;}else l mid1;}if(ans ! -1 nums[ans] ! target) res.push_back(-1);else res.push_back(ans);ans -1, l 0, r nums.size()-1;while(l r){int mid lr1;if(nums[mid] target){ans mid;l mid1;}else r mid-1;}if(ans ! -1 nums[ans] ! target) res.push_back(-1);else res.push_back(ans);return res;}
};
283.移动零
遍历一遍数组就行了。
class Solution {
public:void moveZeroes(vectorint nums) {int len 0;for(int i 0; i nums.size(); i)if(nums[i]) nums[len] nums[i];for(int i len; i nums.size(); i)nums[i] 0;}
};
153.寻找旋转排序数组中的最小值
分两种情况一种是旋转完仍然升序直接返回第一个元素另一种是分成了两段升序的数组这时候二分就行了check条件也很明显。
class Solution {
public:int findMin(vectorint nums) {if(nums[0] nums[nums.size()-1]) return nums[0];int ans -1, l 0, r nums.size()-1;while(l r){int mid lr1;if(nums[mid] nums[0]){ans mid;r mid-1;}else l mid1;}return nums[ans];}
};
136.只出现一次的数字
思维题全部按位异或。
class Solution {
public:int singleNumber(vectorint nums) {int ans 0;for(int i 0; i nums.size(); i)ans ^ nums[i];return ans;}
};
55.跳跃游戏
一开始想的是dp区间和过了以后发现还有更简单的方法。直接维护当前能跳到的最远位置如果走到了最远位置以外那就return false。
//dp区间和做法
class Solution {
public:bool canJump(vectorint nums) {vectorint dp(nums.size());dp[nums.size()-1] 1;for(int i nums.size()-2; i 0; i--){int r min((int)nums.size()-1, inums[i]);int sum dp[i1]-(rnums.size()-1?0:dp[r1]);if(sum) dp[i] dp[i1]1;else dp[i] dp[i1];}if(nums.size() 1) return true;return dp[0]!dp[1];}
};
//更好的dp做法
class Solution {
public:bool canJump(vectorint nums) {int mx 0;for(int i 0; i nums.size(); i) {if(i mx) return false;mx max(mx, inums[i]);}return true;}};
