面试经典150题：数组/字符串合集

新专栏，预计两个月写完吧，每天下班回来抽空做几道题。会把做题计划顺序记录下来，如果你有缘，刷到这个开篇序列，那就跟着文章去练题吧。初学者可以慢慢来

88. 合并两个有序数组

    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int i=m-1;int j=n-1;int k=m+n-1;//从后往前插while(j>=0){if(i>=0&&nums1[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(vector<int>& nums, int val) {int i=0,j=0;while(j<nums.size()){if(nums[j]!=val){nums[i]=nums[j];j++;i++;}else{j++;}}return i;}

26. 删除有序数组中的重复项

    int removeDuplicates(vector<int>& nums) {int i=0,j=0;while(j<nums.size()){if(nums[i]==nums[j]){j++;}else{++i;nums[i]=nums[j];j++;}}return i+1;}

80. 删除有序数组中的重复项 II

    int removeDuplicates(vector<int>& nums) {int i=0,j=0;while(j<nums.size()){if(i<2||nums[j]!=nums[i-2]){nums[i++]=nums[j];}j++;}return i;}

169. 多数元素

方法太多了，我写三个就行

    int majorityElement(vector<int>& nums) {sort(nums.begin(),nums.end());return nums[nums.size()/2];}int majorityElement(vector<int>& nums) {unordered_map<int,int>mp;int ans=0;for(const auto &x:nums){mp[x]++;if(mp[x]>nums.size()/2){ans=x;}}return ans;}摩尔投票法只满足超过一半的投票，符合题意玩的就是票数抵消，留下存活的那个int majorityElement(vector<int>& nums) {//摩尔投票法，一种很奇妙的思路int candition=0;//候选人int vote=0;//票数for(auto x:nums){if(vote==0)candition=x;if(x==candition)vote++;if(x!=candition)vote--;}return candition;}

189. 轮转数组

第一句为了防止越界，这力扣限制服了,,写了两种方法

    void rotate(vector<int>& nums, int k) {k%=nums.size();vector<int>vv;vv.reserve(nums.size()*2);vv.insert(vv.end(),nums.begin(),nums.end());vv.insert(vv.end(),nums.begin(),nums.end());vector<int>vp(vv.begin()+nums.size()-k,vv.begin()+nums.size()*2-k);nums=vp;}void rotate(vector<int>& 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(vector<int>& prices) {vector<vector<int>>dp(prices.size(),vector<int>(2));dp[0][0]=-prices[0]; //有股票dp[0][1]=0;  //没有股票for(int i=1;i<prices.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(vector<int>& prices) {//0 手里没股票 ，1手里有股票vector<vector<int>>dp(prices.size(),vector<int>(2));dp[0][0]=0;dp[0][1]=-prices[0];for(int i=1;i<prices.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(vector<int>& nums) {int n=nums.size()-1;int cover=0;for(int i=0;i<=cover;++i){cover=max(nums[i]+i,cover);if(cover>=n){return true;}}return false;}

45.跳跃游戏2

    int jump(vector<int>& nums) {if(nums.size()==1){return 0;}int n=nums.size()-1;int cover=0;int ans=0;int cur=0;for(int i=0;i<nums.size();++i){cover=max(i+nums[i],cover);if(i==cur){ans++;cur=cover;if(cover>=n){break;}}}return ans;}

274. H 指数

    int hIndex(vector<int>& citations) {//默认h为文章数，对引用量排序，如果小于h，将h--。int lens=citations.size();if(lens==0){return 0;}int h=lens;sort(citations.begin(),citations.end());for(auto x:citations){if(x<h){h--;}}return h;}

380. O(1) 时间插入、删除和获取随机元素

用vector的下标和map做映射

class RandomizedSet {
private:vector<int>vv;unordered_map<int,int>mp; //key->val  vaule->index
public:RandomizedSet() {srand((unsigned int)time(NULL));}bool insert(int val) {if(mp.count(val)){return false;}int idx=vv.size();mp[val]=idx;vv.push_back(val);return true;}bool remove(int val) {if(!mp.count(val)){return false;}int preidx=mp[val];int curidx=vv.size()-1;vv[preidx]=vv[curidx];//更新map 对应下标mp[vv[preidx]]=preidx;//删除vv.pop_back();mp.erase(val);return true;}int getRandom() {int idx=rand()%vv.size();return vv[idx];}
};

238. 除自身以外数组的乘积

    vector<int> productExceptSelf(vector<int>& nums) {//左乘积 * 右乘积int ml=1;vector<int>vv(nums.size(),1);for(int i=1;i<nums.size();++i){ml*=nums[i-1];vv[i]=ml;}int mr=1;for(int i=nums.size()-2;i>=0;--i){mr*=nums[i+1];vv[i]*=mr;}return vv;}

134.加油站

    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {/*     if(accumulate(gas.begin(),gas.end(),0)<accumulate(cost.begin(),cost.end(),0)){return -1;}*///不要上面那句就加一个total 记录完整一路看有没有剩油int total=0;int cur=0;int index=0;for(int i=0;i<gas.size();++i){total+=gas[i]-cost[i];cur+=gas[i]-cost[i];if(cur<0){index=i+1;cur=0;}}   return total<0?-1:index;}

135. 分发糖果

    int candy(vector<int>& ratings) {//每个孩子都至少有一个糖果vector<int>res(ratings.size(),1);//从前往后，把右边分数高的糖果多一个for(int i=0;i<ratings.size()-1;++i){if(ratings[i]<ratings[i+1]){res[i+1]=res[i]+1;}}//从后往前，把左边分数高的糖果多分一个//局部还要贪心，要给第i个孩子分当前糖果和右边糖果数+1的最大值//给到当前孩子糖果，因为这样才能保证局部此时第i个孩子的糖果，比左边右边相邻都大//体现到全局就是每每相邻的两个孩子，分数最大的那个一定糖果最多for(int i=ratings.size()-1;i>0;--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(vector<int>& height) {int ans=0;int value=0;int index=0;for(int i=0;i<height.size();++i){if(height[i]>value){value=height[i];index=i;}}int st=0;for(int i=0;i<index;++i){if(height[i]>st){st=height[i];}else{ans+=st-height[i];}}st=0;for(int i=height.size()-1;i>index;--i){if(height[i]>st){st=height[i];}else{ans+=st-height[i];}}return ans;}

双指针

int trap(vector<int>& height) {int left=0;int right=height.size()-1;int ans=0;int mlhi=height[0];int rlhi=height[height.size()-1];while(left<right){mlhi=max(mlhi,height[left]);rlhi=max(rlhi,height[right]);if(mlhi>rlhi){ans+=rlhi-height[right];right--;}else{ans+=mlhi-height[left];left++;}}return ans;}

单调栈 递减

 int trap(vector<int>& height) {stack<int>sk;sk.push(0);int ans=0;for(int i=1;i<height.size();++i){while(!sk.empty()&&height[i]>height[sk.top()]){int righthright=height[i];int curheight=height[sk.top()];sk.pop();if(!sk.empty()){int leftheight=height[sk.top()];int chang=i-sk.top()-1;int gao=min(righthright,leftheight)-curheight;ans+=chang*gao;}}sk.push(i);}return ans;}

13. 罗马数字转整数

 int romanToInt(string s) {int res=0;for(int i=0;i<s.size();++i){if(s[i]=='V')res+=5;else if(s[i]=='L')res+=50;else if(s[i]=='D')res+=500;else if(s[i]=='M')res+=1000;else if(s[i]=='I'){ //一点代码技巧res=s[i+1]=='V'||s[i+1]=='X'?res-1:res+1;}else if(s[i]=='X'){res=s[i+1]=='L'||s[i+1]=='C'?res-10:res+10;}else{res=s[i+1]=='D'||s[i+1]=='M'?res-100:res+100;}}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 i=0;i<sizeof(arr)/sizeof(arr[0]);++i){while(num>=arr[i]){num-=arr[i];ans+=btr[i];}}return ans;}

58. 最后一个单词的长度

    int lengthOfLastWord(string s) {int count=0;int i=s.size()-1;for(i;i>=0;){if(count&&s[i]==' '){break;}if(s[i]==' '){i--;}else{count++;i--;}}return count;}

14. 最长公共前缀

学习minmax_element

    string longestCommonPrefix(vector<string>& strs) {if(strs.empty())return "";auto p=minmax_element(strs.begin(),strs.end());for(int i=0;i<p.first->size();++i){if(p.first->at(i)!=p.second->at(i)){return p.first->substr(0,i);}}return *p.first;}

    string longestCommonPrefix(vector<string>& strs) {//纵向对比，横向去扫描//abcf//ab//absif(strs.empty()){return "";}string res="";for(int j=0;j<strs[0].size();++j){for(int i=0;i<strs.size();++i){if(strs[0][j]!=strs[i][j]){return res;}  }res+=strs[0][j];}return res;}

151. 反转字符串中的单词

直接重构字符串，，不用erase去写了，erase版本好麻烦写起来

    string reverseWords(string s) {//重构字符串，去重多余空格int slow=0;for(int i=0;i<s.size();++i){if(s[i]!=' '){if(slow!=0) //处理中间，只放一个空格{s[slow++]=' ';} while(s[i]!=' '&&i<s.size()){s[slow++]=s[i++];}}}s.resize(slow);int j=0;for(int i=0;i<s.size();++i){if(s[i]==' '){reverse(s.begin()+j,s.begin()+i);j=i+1;}}reverse(s.begin()+j,s.end());reverse(s.begin(),s.end());return s;}

 

6. N 字形变换 

    string convert(string s, int numRows) {string  res="";if(numRows==1)return s;vector<string>vv(numRows);int k=0;int flg=1;//标志转向for(int i=0;i<s.size();++i){vv[k]+=s[i];if(k==0||k==numRows-1){flg*=-1;}k+=flg>0?-1:1;}for(auto x:vv){res+=x;}return res;}

28. 找出字符串中第一个匹配项的下标 

要用kmp。麻烦，

暴力解法：

  int strStr(string haystack, string needle) {if(haystack.size()<needle.size()){return -1;}int index=INT_MAX;int k=0;for(int i=0;i<haystack.size();++i){for(int j=i;j<haystack.size();++j){if(haystack[j]==needle[k]){k++;if(k==needle.size()){index=i;return i;}}else{k=0;break;}}}return -1;}

kmp:  面试的时候要是面试官让你去写kmp，就把屎盆子扣他脑门，，看着代码感觉不多，思想是极其巧妙的，很难理解，而且稍微一变形，你会难的你根本不知道用kmp从何下手，Knuth-Morris-Pratt 三兄弟，花了若干年研究的成果，在网上各路大神眼里，居然是个简单算法。。。

总之除非你把kmp理解的非常非常清楚，随便一个类型题就就能在15分钟内靠理解的kmp搞出来，那你可以去申请图灵奖了

反正我是每次写到这题就是暴力，然后看看kmp题解，看懂一次 过几天就忘了

    void ex(int *arr,const string&needle){int j=0;arr[0]=j;for(int i=1;i<needle.size();++i){while(j>0&&needle[j]!=needle[i]){j=arr[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 j=0;for(int i=0;i<haystack.size();++i){while(j>0&&haystack[i]!=needle[j]) //回退{j=arr[j-1];}if(haystack[i]==needle[j]){j++;}if(j==needle.size()){return i-needle.size()+1;}}return -1;}