电商网站建设的维护要多少钱,百度推广找谁做,国际新闻最新消息十条摘抄,网络品牌推广案例新专栏#xff0c;预计两个月写完吧#xff0c;每天下班回来抽空做几道题。会把做题计划顺序记录下来#xff0c;如果你有缘#xff0c;刷到这个开篇序列#xff0c;那就跟着文章去练题吧。初学者可以慢慢来 88. 合并两个有序数组 void merge(vectorint nums…新专栏预计两个月写完吧每天下班回来抽空做几道题。会把做题计划顺序记录下来如果你有缘刷到这个开篇序列那就跟着文章去练题吧。初学者可以慢慢来 88. 合并两个有序数组 void merge(vectorint nums1, int m, vectorint nums2, int n) {int im-1;int jn-1;int kmn-1;//从后往前插while(j0){if(i0nums1[i]nums2[j]){nums1[k--]nums1[i];i--;}else{nums1[k--]nums2[j];j--;}}} 27. 移除元素
这是前后指针覆盖做的也可以双向指针交换做思路 i从0开始j从尾巴开始如果i的值不等于val那就如果等于了就和j的值交换j--i不变下一轮再交换来的i还是不是val是的话继续交换j--这样循环 int removeElement(vectorint nums, int val) {int i0,j0;while(jnums.size()){if(nums[j]!val){nums[i]nums[j];j;i;}else{j;}}return i;} 26. 删除有序数组中的重复项 int removeDuplicates(vectorint nums) {int i0,j0;while(jnums.size()){if(nums[i]nums[j]){j;}else{i;nums[i]nums[j];j;}}return i1;} 80. 删除有序数组中的重复项 II int removeDuplicates(vectorint nums) {int i0,j0;while(jnums.size()){if(i2||nums[j]!nums[i-2]){nums[i]nums[j];}j;}return i;} 169. 多数元素
方法太多了我写三个就行 int majorityElement(vectorint nums) {sort(nums.begin(),nums.end());return nums[nums.size()/2];}int majorityElement(vectorint nums) {unordered_mapint,intmp;int ans0;for(const auto x:nums){mp[x];if(mp[x]nums.size()/2){ansx;}}return ans;}摩尔投票法只满足超过一半的投票符合题意玩的就是票数抵消留下存活的那个int majorityElement(vectorint nums) {//摩尔投票法一种很奇妙的思路int candition0;//候选人int vote0;//票数for(auto x:nums){if(vote0)canditionx;if(xcandition)vote;if(x!candition)vote--;}return candition;} 189. 轮转数组
第一句为了防止越界这力扣限制服了,,写了两种方法 void rotate(vectorint nums, int k) {k%nums.size();vectorintvv;vv.reserve(nums.size()*2);vv.insert(vv.end(),nums.begin(),nums.end());vv.insert(vv.end(),nums.begin(),nums.end());vectorintvp(vv.begin()nums.size()-k,vv.begin()nums.size()*2-k);numsvp;}void rotate(vectorint nums, int k) {k%nums.size();reverse(nums.begin(),nums.begin()nums.size()-k);reverse(nums.begin()nums.size()-k,nums.end());reverse(nums.begin(),nums.end());} 121. 买卖股票的最佳时机 int maxProfit(vectorint prices) {vectorvectorintdp(prices.size(),vectorint(2));dp[0][0]-prices[0]; //有股票dp[0][1]0; //没有股票for(int i1;iprices.size();i){dp[i][0]max(-prices[i],dp[i-1][0]);dp[i][1]max(dp[i-1][1],dp[i-1][0]prices[i]);}return dp[prices.size()-1][1];} 122. 买卖股票的最佳时机 II int maxProfit(vectorint prices) {//0 手里没股票 1手里有股票vectorvectorintdp(prices.size(),vectorint(2));dp[0][0]0;dp[0][1]-prices[0];for(int i1;iprices.size();i){dp[i][1]max(dp[i-1][0]-prices[i],dp[i-1][1]);dp[i][0]max(dp[i-1][0],dp[i-1][1]prices[i]);}return dp[prices.size()-1][0];} 55. 跳跃游戏
只要范围覆盖能到就行 bool canJump(vectorint nums) {int nnums.size()-1;int cover0;for(int i0;icover;i){covermax(nums[i]i,cover);if(covern){return true;}}return false;}
45.跳跃游戏2 int jump(vectorint nums) {if(nums.size()1){return 0;}int nnums.size()-1;int cover0;int ans0;int cur0;for(int i0;inums.size();i){covermax(inums[i],cover);if(icur){ans;curcover;if(covern){break;}}}return ans;} 274. H 指数 int hIndex(vectorint citations) {//默认h为文章数对引用量排序如果小于h将h--。int lenscitations.size();if(lens0){return 0;}int hlens;sort(citations.begin(),citations.end());for(auto x:citations){if(xh){h--;}}return h;} 380. O(1) 时间插入、删除和获取随机元素
用vector的下标和map做映射
class RandomizedSet {
private:vectorintvv;unordered_mapint,intmp; //key-val vaule-index
public:RandomizedSet() {srand((unsigned int)time(NULL));}bool insert(int val) {if(mp.count(val)){return false;}int idxvv.size();mp[val]idx;vv.push_back(val);return true;}bool remove(int val) {if(!mp.count(val)){return false;}int preidxmp[val];int curidxvv.size()-1;vv[preidx]vv[curidx];//更新map 对应下标mp[vv[preidx]]preidx;//删除vv.pop_back();mp.erase(val);return true;}int getRandom() {int idxrand()%vv.size();return vv[idx];}
}; 238. 除自身以外数组的乘积 vectorint productExceptSelf(vectorint nums) {//左乘积 * 右乘积int ml1;vectorintvv(nums.size(),1);for(int i1;inums.size();i){ml*nums[i-1];vv[i]ml;}int mr1;for(int inums.size()-2;i0;--i){mr*nums[i1];vv[i]*mr;}return vv;}
134.加油站 int canCompleteCircuit(vectorint gas, vectorint cost) {/* if(accumulate(gas.begin(),gas.end(),0)accumulate(cost.begin(),cost.end(),0)){return -1;}*///不要上面那句就加一个total 记录完整一路看有没有剩油int total0;int cur0;int index0;for(int i0;igas.size();i){totalgas[i]-cost[i];curgas[i]-cost[i];if(cur0){indexi1;cur0;}} return total0?-1:index;} 135. 分发糖果 int candy(vectorint ratings) {//每个孩子都至少有一个糖果vectorintres(ratings.size(),1);//从前往后把右边分数高的糖果多一个for(int i0;iratings.size()-1;i){if(ratings[i]ratings[i1]){res[i1]res[i]1;}}//从后往前把左边分数高的糖果多分一个//局部还要贪心要给第i个孩子分当前糖果和右边糖果数1的最大值//给到当前孩子糖果因为这样才能保证局部此时第i个孩子的糖果比左边右边相邻都大//体现到全局就是每每相邻的两个孩子分数最大的那个一定糖果最多for(int iratings.size()-1;i0;--i){if(ratings[i-1]ratings[i]){res[i-1]max(res[i-1],res[i]1);}}return accumulate(res.begin(),res.end(),0);} 42. 接雨水
我有篇博客详细讲了这个题的做法用了五种方法
这块我演示三种推荐的
找到最高点左右两边求雨水 int trap(vectorint height) {int ans0;int value0;int index0;for(int i0;iheight.size();i){if(height[i]value){valueheight[i];indexi;}}int st0;for(int i0;iindex;i){if(height[i]st){stheight[i];}else{ansst-height[i];}}st0;for(int iheight.size()-1;iindex;--i){if(height[i]st){stheight[i];}else{ansst-height[i];}}return ans;}
双指针
int trap(vectorint height) {int left0;int rightheight.size()-1;int ans0;int mlhiheight[0];int rlhiheight[height.size()-1];while(leftright){mlhimax(mlhi,height[left]);rlhimax(rlhi,height[right]);if(mlhirlhi){ansrlhi-height[right];right--;}else{ansmlhi-height[left];left;}}return ans;}
单调栈 递减 int trap(vectorint height) {stackintsk;sk.push(0);int ans0;for(int i1;iheight.size();i){while(!sk.empty()height[i]height[sk.top()]){int righthrightheight[i];int curheightheight[sk.top()];sk.pop();if(!sk.empty()){int leftheightheight[sk.top()];int changi-sk.top()-1;int gaomin(righthright,leftheight)-curheight;anschang*gao;}}sk.push(i);}return ans;} 13. 罗马数字转整数 int romanToInt(string s) {int res0;for(int i0;is.size();i){if(s[i]V)res5;else if(s[i]L)res50;else if(s[i]D)res500;else if(s[i]M)res1000;else if(s[i]I){ //一点代码技巧ress[i1]V||s[i1]X?res-1:res1;}else if(s[i]X){ress[i1]L||s[i1]C?res-10:res10;}else{ress[i1]D||s[i1]M?res-100:res100;}}return res;}
12.整数转罗马数字 string intToRoman(int num) {//哈希int arr[]{1000,900,500,400,100,90,50,40,10,9,5,4,1};string btr[]{M,CM,D,CD,C,XC,L,XL,X,IX,V,IV,I};string ans;for(int i0;isizeof(arr)/sizeof(arr[0]);i){while(numarr[i]){num-arr[i];ansbtr[i];}}return ans;} 58. 最后一个单词的长度 int lengthOfLastWord(string s) {int count0;int is.size()-1;for(i;i0;){if(counts[i] ){break;}if(s[i] ){i--;}else{count;i--;}}return count;} 14. 最长公共前缀
学习minmax_element string longestCommonPrefix(vectorstring strs) {if(strs.empty())return ;auto pminmax_element(strs.begin(),strs.end());for(int i0;ip.first-size();i){if(p.first-at(i)!p.second-at(i)){return p.first-substr(0,i);}}return *p.first;} string longestCommonPrefix(vectorstring strs) {//纵向对比横向去扫描//abcf//ab//absif(strs.empty()){return ;}string res;for(int j0;jstrs[0].size();j){for(int i0;istrs.size();i){if(strs[0][j]!strs[i][j]){return res;} }resstrs[0][j];}return res;} 151. 反转字符串中的单词
直接重构字符串不用erase去写了erase版本好麻烦写起来 string reverseWords(string s) {//重构字符串去重多余空格int slow0;for(int i0;is.size();i){if(s[i]! ){if(slow!0) //处理中间只放一个空格{s[slow] ;} while(s[i]! is.size()){s[slow]s[i];}}}s.resize(slow);int j0;for(int i0;is.size();i){if(s[i] ){reverse(s.begin()j,s.begin()i);ji1;}}reverse(s.begin()j,s.end());reverse(s.begin(),s.end());return s;} 6. N 字形变换 string convert(string s, int numRows) {string res;if(numRows1)return s;vectorstringvv(numRows);int k0;int flg1;//标志转向for(int i0;is.size();i){vv[k]s[i];if(k0||knumRows-1){flg*-1;}kflg0?-1:1;}for(auto x:vv){resx;}return res;} 28. 找出字符串中第一个匹配项的下标
要用kmp。麻烦
暴力解法 int strStr(string haystack, string needle) {if(haystack.size()needle.size()){return -1;}int indexINT_MAX;int k0;for(int i0;ihaystack.size();i){for(int ji;jhaystack.size();j){if(haystack[j]needle[k]){k;if(kneedle.size()){indexi;return i;}}else{k0;break;}}}return -1;}
kmp: 面试的时候要是面试官让你去写kmp就把屎盆子扣他脑门看着代码感觉不多思想是极其巧妙的很难理解而且稍微一变形你会难的你根本不知道用kmp从何下手Knuth-Morris-Pratt 三兄弟花了若干年研究的成果在网上各路大神眼里居然是个简单算法。。。
总之除非你把kmp理解的非常非常清楚随便一个类型题就就能在15分钟内靠理解的kmp搞出来那你可以去申请图灵奖了
反正我是每次写到这题就是暴力然后看看kmp题解看懂一次 过几天就忘了 void ex(int *arr,const stringneedle){int j0;arr[0]j;for(int i1;ineedle.size();i){while(j0needle[j]!needle[i]){jarr[j-1];}if(needle[i]needle[j]){j;}arr[i]j;}}int strStr(string haystack, string needle) {if(needle.size()0){return -1;}int arr[needle.size()];ex(arr,needle);int j0;for(int i0;ihaystack.size();i){while(j0haystack[i]!needle[j]) //回退{jarr[j-1];}if(haystack[i]needle[j]){j;}if(jneedle.size()){return i-needle.size()1;}}return -1;}
