双指针
有序数组的两数之和
题号:167
链接:167. 两数之和 II - 输入有序数组 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:给你一个有序数组,在这个数组中找出两个数字,使其和等于target
题解:使用双指针从数组两端进行遍历,若sum>target,则大数取小,即j–,反之则小数取大,即i++,如图
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int start=0;
int end=numbers.size()-1;
int sum=0;
// vector<int> ans;
while(start<end)
{
sum=numbers[start]+numbers[end];
if(sum==target)
{
// ans.push_back(start+1);
// ans.push_back(end+1);
return {start+1,end+1};
}
else if(sum<target)
{
start++;
}
else{
end--;
}
}
return {-1,-1};
}
};
两数平方和
题号:633
链接:633. 平方数之和 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:给定一个非负整数 c
,你要判断是否存在两个整数 a
和 b
,使得 a^2 + b^2 = c
。
题解:双指针从两端向中间遍历,其中尾指针设置为sqrt(c)+1,判断平方和是否等于c,若不等,则移动双指针,考虑到整数溢出问题,数据类型采用long
class Solution {
public:
bool judgeSquareSum(int c) {
long i=0;
long j=sqrt(c)+1;
// int j=c;
if(c<0) return false;
while(i<=j)
{
long mul=i*i+j*j;
if(mul==c)
{
return true;
}
else if(mul<c)
i++;
else
j--;
}
return false;
}
};
反转字符串元音字母
题号:345
链接:345. 反转字符串中的元音字母 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:给你一个字符串 s ,仅反转字符串中的所有元音字母,并返回结果字符串。
元音字母包括 ‘a’、’e’、’i’、’o’、’u’,且可能以大小写两种形式出现。
题解:双指针从两端遍历字符串,当查到元音字母时进行交换
class Solution {
public:
string reverseVowels(string s) {
string voewl="aeiouAEIOU";
int i=0,j=s.length()-1;
char ch;
while(i<j)
{
while(voewl.find(s[i])==-1 && i<j) i++;
while(voewl.find(s[j])==-1 && i<j) j--;
if(i<j)
{
ch=s[i];
s[i]=s[j];
s[j]=ch;
}
i++;
j--;
}
return s;
}
};
回文字符串
题号:680
链接:680. 验证回文字符串 Ⅱ - 力扣(LeetCode) (leetcode-cn.com)
题目描述:给定一个非空字符串 s
,最多删除一个字符。判断是否能成为回文字符串。
题解:使用双指针从两端遍历字符串,当遇到字符不等时分别判定左指针+1时和右指针-1时剩下的字符串是否为回文串
class Solution {
public:
bool isPalindrome(string s,int i,int j)//判断是否为回文字符串
{
while(i<j)
{
if(s[i]==s[j])
{
i++;
j--;
}
else
{
return false;
}
}
return true;
}
bool validPalindrome(string s) {
int i=0,j=s.length()-1;
if(j<0) return false;
while(i<j)
{
if(s[i]!=s[j])//遇到不等的字符
return isPalindrome(s,i+1,j) || isPalindrome(s,i,j-1);//判断(s,i+1,j)与(s,i,j-1)是否为回文串
i++;
j--;
}
return true;
}
};
归并两个有序数组
题号:88
链接:88. 合并两个有序数组 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:有两个有序数组nums1(长度为m+n,元素数目为m)与nums2(长度为n,元素数目为n),现需将两个有序数组归并为一个有序数组,并将归并后的结果放入nums1中
题解:由于题目要求将归并后的数组放入nums1中,且nums1长度为m+n,为避免归并时的元素覆盖数组nums1原值,因此需要从两个数组的末端开始比较
1.设置指针i指向nums1[m-1]
指针j指向nums2[n-1]
指针t指向nums1[m+n-1]
2.比较两指针i与j的元素值,将大值放入nums1[t]中
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i=m-1,j=n-1,t=m+n-1;
while(i>=0 && j>=0)
{
if(nums1[i]>nums2[j]) nums1[t--]=nums1[i--];
else nums1[t--]=nums2[j--];
}
if(i>=0) return;
while(j>=0) nums1[t--]=nums2[j--];
}
};
判断链表中是否存在环路
题号:141
链接:141. 环形链表 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
题解:使用快慢指针法,其中快指针一次移动2步,慢指针一次移动1步,若链表中存在环路,则两指针必定会相遇,否则两指针将永远不会相遇
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* f=head;
ListNode* l=head;
while(f!=NULL && f->next!=NULL)//必须先判断f是否为空,再判断f->next是否为空
{
f=f->next->next;
l=l->next;
if(l==f)
return true;
}
return false;
}
};
题号:142
链接:142. 环形链表 II - 力扣(LeetCode) (leetcode-cn.com)
题目描述:给你一个链表的头节点 head ,判断链表中是否有环,若有环,则返回环路入口节点。
题解:
"""
原理:首先初始化快指针 fast = head.next.next 和 slow = head.next,
此时快指针走的路长为2, m慢指针走的路长为1,之后令快指针每次走两步,
慢指针每次走一步,这样快指针走的路长始终是慢指针走的路长的两倍,
若不存在环,直接返回None,
若存在环,则 fast 与 slow 肯定会在若干步之后相遇;
性质1:
设从head需要走 a 步到达环的入口,如果环存在的话,
再走 b 步可以再次到达该入口(即环的长度为b),
如果存在环的话,上述描述的 快指针 fast 和
慢指针slow 必然会相遇,且此时slow走的路长
小于 a + b(可以自行证明),设其为 a + x,
当快慢指针相遇时,快指针已经至少走完一圈环了,
不妨设相遇时走了完整的m圈(m >= 1),有:
快指针走的路长为 a + mb + x
慢指针走的路长为 a + x
由于快指针fast 走的路长始终是慢指针的 2倍,所以:
a + mb + x = 2(a + x)
化简可得:
a = mb - x ------------- (*)
当快指针与慢指针相遇时,由于 <性质1> 的存在,
可以在链表的开头初始化一个新的指针,
称其为 detection, 此时 detection 距离环的入口的距离为 a,
此时令 detection 和 fast 每次走一步,
会发现当各自走了 a 步之后,两个指针同时到达了环的入口,理由分别如下:
detection不用说了,走了a步肯定到刚好到入口
fast已经走过的距离为 a + mb + x,当再走 a 步之后,
fast走过的总距离为 2a + mb + x,带入性质1的(*)式可得:
2a + mb + x = a + 2mb,会发现,fast此时刚好走完了
整整 2m 圈环,正好处于入口的位置。
基于此,我们可以进行循环,直到 detection 和
fast 指向同一个对象,此时指向的对象恰好为环的入口。
"""
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast=head;
ListNode* slow=head;//设置快慢指针
int count=0;//记录指针相遇次数
while(fast!=NULL && fast->next!=NULL)
{
//快指针走两步,慢指针走一步,如果链表中存在环路,则两指针一定会相遇
fast=fast->next->next;
slow=slow->next;
if(fast==slow)//若指针相遇,则说明链表中存在环路
{
count++;
if(count==1)//两指针在第一次相遇时,在表头设置检测指针,此后两指针与检测指针同时移动一步,则当检测指针与fast指针相遇的位置就是链表环路入口位置
{
ListNode* dection=head;
while(dection!=fast)
{
dection=dection->next;
fast=fast->next;
}
return dection;
}
}
}
return NULL;
}
};
最长子序列
题号:524
链接:524. 通过删除字母匹配到字典里最长单词 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:给你一个元素为字符串的字典dictionary以及一个字符串s,字符串s可通过删除某些字符后与字典中的字符串元素匹配,试找出长度最长的子序列,若长度相等,则返回字母序最小的子序列
示例 1:
输入:s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出:"apple"
示例 2:
输入:s = "abpcplea", dictionary = ["a","b","c"]
输出:"a"
题解:第一步:将字典中的每一个字符串元素作为匹配模板,并将给出的字符串s视为待匹配字符串,比较两个字符串的每一个字符,若相等则两指针同时后移。若出现不等字符,则将s的指针后移继续与模板进行匹配。若模板指针指向模板字符串的尾部,则说明s中存在一个子序列与字典中的元素匹配,否则说明不存在这样的子序列
第二步:将每次得到的子序列与下一次循环遍历匹配的字符串元素进行比较,若该子序列长度较大或者该子序列的字母序较小,说明当前子序列暂时是最长子序列
class Solution {
public:
bool isSubStr(string s,string target)
{
//字典中的每一个元素视为匹配模板,字符串s为待匹配者
//比较每一个字符,若s[i]==target[j],则两指针同时后移匹配下一个字符
//若s[i]!=target[j],则待匹配字符串s指针i后移,模板指针j不动
//若模板指针j到达尾部,则匹配成功,若待匹配指针i已经到达尾部,但模板指针尚未到达尾部,则字符串s与模板字符串无法匹配
int j=0;
for(int i=0;i<s.length() && j<target.length();i++)
{
if(s[i]==target[j])
j++;
}
return j==target.length();
}
string findLongestWord(string s, vector<string>& dictionary) {
string longWord="";
for(string target:dictionary)//使用增强for循环遍历字典每一个元素
{
int l1=longWord.length();
int l2=target.length();
//若当前得到的子序列长度大于当前字典中的正在遍历的元素长度,则说明当前得到的子序列已经局部最大,跳过本轮循环
//若当前得到的子序列与target不等或者其串中字母序较小,也可以跳过本轮循环比较
if(l1>l2 || (l1==l2 && longWord.compare(target)<0))
continue;
if(isSubStr(s,target))
longWord=target;
}
return longWord;
}
};
排序
数组中第k大元素
题号:215
链接:215. 数组中的第K个最大元素 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:给定整数数组 nums
和整数 k
,请返回数组中第 **k**
个最大的元素。
请注意,你需要找的是数组排序后的第 k
个最大的元素,而不是第 k
个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
题解:利用大根堆的构建及排序特点,每交换一次大根时就找到一次极大值,在交换第k次时进行返回即可
class Solution {
public:
void swap(int& a,int &b)
{
int temp=a;
a=b;
b=temp;
}
void heapAdjust(vector<int>& nums,int p,int n)//大根堆调整
{
int temp=nums[p];
for(int i=2*p+1;i<n;i=i*2+1)
{
if(i+1<n && nums[i+1]>nums[i]) i++;
if(temp>nums[i]) break;
nums[p]=nums[i];
p=i;
}
nums[p]=temp;
}
int findKthLargest(vector<int>& nums, int k) {
int n=nums.size(),j;
for(int i=n/2-1;i>=0;i--)
heapAdjust(nums,i,n);//构建初始大根堆
for(j=n-1;j>=n-k;j--)//每次交换就找到一个极大值,故只需要交换k次即可跳出循环输出结果
{
swap(nums[0],nums[j]);//交换
heapAdjust(nums,0,j);//重新调整大根堆
}
return nums[j+1];
}
};
贪心算法
分配饼干
题号:455
链接:455. 分发饼干 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。
对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。
虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
题解:首先给孩子的胃口值g[i]与饼干大小s[j]进行升序排序,然后给每一个孩子进行试分配,如果满足s[j]>=g[i],则饼干分配完毕,可以得到满足的孩子也加一,否则就让下一个饼干再试分配给该孩子,直到饼干分配完毕或者所有孩子均已得到满足
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int n=g.size();
int m=s.size();
int i=0,j=0;
while(i<n && j<m)
{
if(s[j]>=g[i])
{
i++;
}
j++;
}
return i;
}
};
无重叠区间
题号:435
链接:435. 无重叠区间 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:给定一个区间的集合 intervals ,其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 。
示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后,剩下的区间没有重叠。
示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间,因为它们已经是无重叠的了。
题解:将区间按照左端进行排序,排序后遍历区间判别是否有重叠,但每次选取的end端需选取最小的作为保留区间
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if(intervals.size()==0) return 0;
// 将区间按照start进行排序
sort(intervals.begin(),intervals.end(),[](vector<int> &v1,vector<int> &v2){return v1[0]<v2[0];});
int num=0;
// 选取第一个区间边界,用于判别与其临近的区间是否有重叠
int end=intervals[0][1];
for(int i=1;i<intervals.size();i++)
{
// 当有区间发生重叠时,就将重叠的区间加1
if(intervals[i][0]<end)
{
num++;
// 选取end端小的边界作为不重复区间的边界
if(intervals[i][1]<end)
end=intervals[i][1];
}
else
end=intervals[i][1];
}
return num;
}
};
投飞镖刺破气球
题号:452
链接:452. 用最少数量的箭引爆气球 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭,若有一个气球的直径的开始和结束坐标为 xstart,xend, 且满足 xstart ≤ x ≤ xend,则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后,可以无限地前进。
给你一个数组 points ,返回引爆所有气球所必须射出的 最小 弓箭数 。
示例 1:
输入:points = [[10,16],[2,8],[1,6],[7,12]]
输出:2
解释:气球可以用2支箭来爆破:
-在x = 6处射出箭,击破气球[2,8]和[1,6]。
-在x = 11处发射箭,击破气球[10,16]和[7,12]。
示例 2:
输入:points = [[1,2],[3,4],[5,6],[7,8]]
输出:4
解释:每个气球需要射出一支箭,总共需要4支箭。
示例 3:
输入:points = [[1,2],[2,3],[3,4],[4,5]]
输出:2
解释:气球可以用2支箭来爆破:
- 在x = 2处发射箭,击破气球[1,2]和[2,3]。
- 在x = 4处射出箭,击破气球[3,4]和[4,5]。
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
int n=points.size();
if(n==0) return 0;
sort(points.begin(),points.end(),[](vector<int>& v1,vector<int>& v2){return v1[0]<v2[0];});
int count=1;//若气球个数不为0,则至少需要一根箭
for(int i=1;i<n;i++)
{
if(points[i][0]>points[i-1][1])//区间没有重叠时,需要一支箭
{
count++;
}
else//当区间存在重叠时
{
points[i][1]=min(points[i-1][1],points[i][1]);
}
}
return count;
}
};
买卖股票最佳时机
题号:121
链接:121. 买卖股票的最佳时机 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
示例 1:
输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
示例 2:
输入:prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 没有交易完成, 所以最大利润为 0
题解:该题可用暴力搜索进行求解,但时间复杂度为o(n^2^),不能满足题解要求,考虑使用贪心算法,每次遍历股票值,当选择到当前的最小值时就开始买入,此后继续进行遍历求最大收益,遍历结束时获取到的最大收益就是最终结果,耗时为O(n)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
int min=prices[0],maxProfit=0;
for(int i=1;i<n;i++)
{
if(prices[i]<min)
min=prices[i];
else{
maxProfit=((prices[i]-min)>maxProfit)?(prices[i]-min):maxProfit;
}
}
return maxProfit;
}
};
买卖股票最佳时机Ⅱ
题号:122
链接:122. 买卖股票的最佳时机 II - 力扣(LeetCode) (leetcode-cn.com)
题目描述:给定一个数组 prices ,其中 prices[i] 表示股票第 i 天的价格。
在每一天,你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它,然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1:
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
示例 3:
输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
题解:只要今天的股票比明天的股票小,就将今天的股票买入,然后在明天卖出
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
int maxProfit=0;
for(int i=1;i<n;i++)
{
//只要今天价格小于明天价格,就在今天买入,明天卖出
if(prices[i]>prices[i-1])
maxProfit+=prices[i]-prices[i-1];
}
return maxProfit;
}
};
种植花朵
题号:605
链接:605. 种花问题 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:假设有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花不能种植在相邻的地块上,它们会争夺水源,两者都会死去。
给你一个整数数组 flowerbed 表示花坛,由若干 0 和 1 组成,其中 0 表示没种植花,1 表示种植了花。另有一个数 n ,能否在不打破种植规则的情况下种入 n 朵花?能则返回 true ,不能则返回 false。
示例 1:
输入:flowerbed = [1,0,0,0,1], n = 1
输出:true
示例 2:
输入:flowerbed = [1,0,0,0,1], n = 2
输出:false
题解:贪心思想,只要满足连续的3个0就种植花朵,在数组的头尾两端各插入一个0以解决边界问题(防御式编程思想)
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
//防御式编程思想,在数组的两端各插入一个0,以解决边界问题
flowerbed.insert(flowerbed.begin(),0);
flowerbed.insert(flowerbed.end(),0);
int num=flowerbed.size();
int sum=0;
for(int i=0;i<num && sum<n;)//时间优化,只要满足种植花的数目就跳出循环
{
//贪心思想,当出现连续的3个0时就种植一朵花
if(i+2<num && flowerbed[i]==0 && flowerbed[i+1]==0 && flowerbed[i+2]==0)
{
flowerbed[++i]=1;
sum++;
// if(sum>=n) return true;
}
else i++;
}
// if(sum>=n) return true;
// return false;
return (sum>=n);
}
};
判断是否为子序列
题号:392
链接:392. 判断子序列 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,”ace”是”abcde”的一个子序列,而”aec”不是)。
示例 1:
输入:s = "abc", t = "ahbgdc"
输出:true
示例 2:
输入:s = "axc", t = "ahbgdc"
输出:false
class Solution {
public:
bool isSubsequence(string s, string t) {
int m=s.size(),n=t.size();
int i=0,j=0;
while(i<m && j<n)//双指针指向待匹配序列与模板序列,若指针指向字符相等就后移,否则模板序列指针后移继续匹配
{
if(s[i]==t[j])
{
i++;
j++;
}
else
{
j++;
}
}
if(i==m) return true;
else return false;
}
};
非递减数列
题号:665
链接:665. 非递减数列 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:给你一个长度为 n 的整数数组 nums ,请你判断在 最多 改变 1 个元素的情况下,该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的: 对于数组中任意的 i (0 <= i <= n-2),总满足 nums[i] <= nums[i + 1]。
示例 1:
输入: nums = [4,2,3]
输出: true
解释: 你可以通过把第一个 4 变成 1 来使得它成为一个非递减数列。
示例 2:
输入: nums = [4,2,1]
输出: false
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
题解:如下图所示
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int n=nums.size();
int count =0;
for(int i=1;i+1<n;)
{
if(nums[i-1]<=nums[i] && nums[i]<=nums[i+1])
i++;
else
{
if(nums[i]<nums[i-1] && nums[i]>nums[i+1])
return false;
if(nums[i-1]<=nums[i] && nums[i-1]>nums[i+1])
{
nums[i+1]=nums[i];
count++;
i++;
continue;
}
if(nums[i-1]<=nums[i] && nums[i-1]<=nums[i+1])
{
nums[i]=nums[i+1];
count++;
i++;
continue;
}
if(nums[i-1]>nums[i+1] && nums[i]<=nums[i+1])
{
nums[i-1]=nums[i];
count++;
i++;
continue;
}
if(nums[i-1]<=nums[i+1] && nums[i]<=nums[i+1])
{
nums[i]=nums[i-1];
count++;
i++;
continue;
}
}
}
return count<=1;
}
};
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int n=nums.size();
int count =0;
for(int i=0;i+1<n && count<2;i++)
{
if(nums[i]<=nums[i+1])
continue;
if(i-1>=0 && nums[i-1]>nums[i+1])//等号不能省略,否则会由于&&运算的bug导致程序出错
nums[i+1]=nums[i];
else
nums[i]=nums[i+1];
count++;
}
return count<=1;
}
};
最大子数组的和
题号:53
链接:53. 最大子数组和 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。
示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
示例 2:
输入:nums = [1]
输出:1
示例 3:
输入:nums = [5,4,-1,7,8]
输出:23
题解:f(n) = max(f(n-1) + A[n], A[n])
sum=f(n-1)+a(n)表示当前局部最优值,如果sum>=a(n),说明sum>=0,则令sum=f(n-1)+a(n);
如果sum<=a(n)说明sum<=0,即此时f(n-1)拖累了a(n),则令sum=a(n)
判断局部最优sum与全局最优max的最大值,求取全局最优max
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n=nums.size();
int max=nums[0],sum=nums[0];
for(int i=1;i<n;i++)
{
if(sum+nums[i]>=nums[i])
sum+=nums[i];
else sum=nums[i];
max=(sum>max)?sum:max;
}
return max;
}
};
二分法
搜索插入位置
题号:35
链接:35. 搜索插入位置 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
二分法的两种情况
- 定义区间为左闭右闭,即[left,right],则n=nums.size()
此时low<high且high=mid
- 定义区间为左闭右开,即[left,right),则n=nums.size()-1
此时low<=high且high=mid+1
左闭右开
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int low=0,high=nums.size()-1;//定义搜索区间为左闭右开
while(low<=high)
{
int mid=low+(high-low)/2;
if(nums[mid]==target) return mid;
if(nums[mid]<target) low=mid+1;
else high=mid-1;
}
return high+1;
}
};
左闭右闭
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int low=0,high=nums.size();//定义搜索区间为左闭右闭
while(low<high)
{
int mid=low+(high-low)/2;
if(nums[mid]==target) return mid;
if(nums[mid]<target) low=mid+1;
else high=mid;
}
return high;
}
};
x的平方根
题号:69
链接:69. x 的平方根 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1:
输入:x = 4
输出:2
示例 2:
输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
class Solution {
public:
int mySqrt(int x) {
if(x<=1) return x;
long l=1,h=x;
while(l<=h)
{
long mid=(l+h)/2;
long q=mid*mid;
if(q==x) return mid;
if(q<x) l=mid+1;
else h=mid-1;
}
return h;//退出循环时h=l-1,故应取小数
}
};
有序数组中大于目标字母的最小字母
题号:744
链接:744. 寻找比目标字母大的最小字母 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:给你一个排序后的字符列表 letters ,列表中只包含小写英文字母。另给出一个目标字母 target,请你寻找在这一有序列表里比目标字母大的最小字母。
在比较时,字母是依序循环出现的。举个例子:
如果目标字母 target = ‘z’ 并且字符列表为 letters = [‘a’, ‘b’],则答案返回 ‘a’
示例 1:
输入: letters = ["c", "f", "j"],target = "a"
输出: "c"
示例 2:
输入: letters = ["c","f","j"], target = "c"
输出: "f"
示例 3:
输入: letters = ["c","f","j"], target = "d"
输出: "f"
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
int n=letters.size();
// for(int i=0;i<n;i++)
// {
// if(target<letters[i])
// return letters[i];
// }
// return letters[0];
int l=0,h=n-1;
while(l<=h)
{
int mid=l+(h-l)/2;//防止int数据溢出
if(target<letters[mid]) h=mid-1;//边界问题处理
else l=mid+1;
}
return letters[l%n];
}
};
有序数组中的单一元素
题号:540
链接:540. 有序数组中的单一元素 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:给你一个仅由整数组成的有序数组,其中每个元素都会出现两次,唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
示例 1:
输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:
输入: nums = [3,3,7,7,10,11,11]
输出: 10
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int n=nums.size();
if(n%2==0) return -1;
if(n==1) return nums[0];
int low=0,high=n-1;
while(low<high)
{
int mid=low+(high-low)/2;
// int mid=(low+high)/2;
if(nums[mid]==nums[mid-1])//中间值与左边是否相等
{
if((high-mid)%2==0) high=mid-2;//左奇右偶
else low=mid+1;
}
else
{
if(nums[mid]==nums[mid+1])//中间值与右边是否相等
{
if((high-mid+1)%2==0) high=mid-1;//左奇右偶
else low=mid+2;
}
else return nums[mid];//中间值与两边都不相等,故结果就是中间值
}
}
return nums[low];
}
};
第一个错误的版本
题号:540
链接:278. 第一个错误的版本 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n],你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例 1:
输入:n = 5, bad = 4
输出:4
解释:
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以,4 是第一个错误的版本。
示例 2:
输入:n = 1, bad = 1
输出:1
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
if(n==1) return 1;
int l=0,h=n-1;
while(l<=h)
{
int mid=l+(h-l)/2;
if(!isBadVersion(mid)) l=mid+1;
else h=mid-1;
}
return l;
}
};
寻找旋转排序数组中的最小值
题号:153
链接:153. 寻找旋转排序数组中的最小值 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到:
若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次,则可以得到 [0,1,2,4,5,6,7]
注意,数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1:
输入:nums = [3,4,5,1,2]
输出:1
解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。
示例 2:
输入:nums = [4,5,6,7,0,1,2]
输出:0
解释:原数组为 [0,1,2,4,5,6,7] ,旋转 4 次得到输入数组。
示例 3:
输入:nums = [11,13,15,17]
输出:11
解释:原数组为 [11,13,15,17] ,旋转 4 次得到输入数组。
题解:由于数组原本有序,旋转后产生了间断点,断点两侧均为有序数组,本题可以视为寻找间断点。
当nums[mid]<nums[h]时,说明断点在左侧区间,反之断点在右侧区间
class Solution {
public:
int findMin(vector<int>& nums) {
int l=0,h=nums.size()-1;
while(l<h)
{
int mid=l+(h-l)/2;
if(nums[mid]<nums[h]) h=mid;
else l=mid+1;
}
return nums[l];
}
};
字符串
串中单词个数
题号:434
链接:434. 字符串中的单词数 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:统计字符串中的单词个数,这里的单词指的是连续的不是空格的字符。
请注意,你可以假定字符串里不包括任何不可打印的字符。
示例:
输入: "Hello, my name is John"
输出: 5
解释: 这里的单词是指连续的不是空格的字符,所以 "Hello," 算作 1 个单词。
题解:遍历字符串,当第一个字符不是空格,第二个字符是空格时就判定为一个单词分界标志,判定第一个字符是否是空格可排除空串等情况
class Solution {
public:
int countSegments(string s) {
int num=0;
int n=s.size();
if(n==0) return num;
for(int i=0;i<n;i++)
{
if(i==0 && s[i]!=' ') num++;
if(i+1<n && s[i]==' ' && s[i+1]!=' ') num++;
}
return num;
}
};