新专栏，预计两个月写完吧，每天下班回来抽空做几道题。会把做题计划顺序记录下来，如果你有缘，刷到这个开篇序列，那就跟着文章去练题吧。初学者可以慢慢来
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
//abs
if(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搞出来，那你可以去申请图灵奖了文章来源：https://www.toymoban.com/news/detail-480986.html
反正我是每次写到这题就是暴力，然后看看kmp题解，看懂一次 过几天就忘了文章来源地址https://www.toymoban.com/news/detail-480986.html
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;
}到了这里，关于面试经典150题：数组/字符串合集的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
