1.两数之和
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int,int> st;
int len=nums.size();
for (int i=0;i<len;i++){
if (st.find(target-nums[i])==st.end())
st[nums[i]]=i;
else
return {st[target-nums[i]],i};
}
return {-1,-1};
}
};
2.两数相加
给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *head=NULL;
ListNode *tail=NULL;
int c=0;
int sum=0;
while(l1!=NULL||l2!=NULL){
int num1=l1?l1->val:0;
int num2=l2?l2->val:0;
sum=num1+num2+c;
if(!head)
head=tail=new ListNode(sum%10);
else{
tail->next=new ListNode(sum%10);
tail=tail->next;
}
c=sum/10;
if(l1)
l1=l1->next;
if(l2)
l2=l2->next;
}
if(c>0)
tail->next=new ListNode(c);
return head;
}
};
3. 无重复字符的最长子串
class Solution {
public:
int lengthOfLongestSubstring(string s) {
set<char> st;
int len=s.size();
int ans=0;
int r=-1;
for(int i=0;i<len;i++){
if (i!=0)
st.erase(s[i-1]);
while(r+1<len&&st.find(s[r+1])==st.end())
st.insert(s[++r]);
ans=max(ans,r-i+1);
}
return ans;
}
};
4. 寻找两个正序数组的中位数
给定两个大小分别为 m m m 和 n n n 的正序（从小到大）数组 n u m s 1 nums1 nums1 和 n u m s 2 nums2 nums2。请你找出并返回这两个正序数组的中位数.算法的时间复杂度应该为 O ( l o g ( m + n ) ) O(log (m+n)) O(log(m+n))。
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int tot=nums1.size()+nums2.size();
if (tot%2==0){
int left=find(nums1,0,nums2,0,tot/2);
int right=find(nums1,0,nums2,0,tot/2+1);
return (left+right)/2.0;
}
else return (double)find(nums1,0,nums2,0,tot/2+1);
}
int find(vector<int> &nums1,int i,vector<int> &nums2,int j,int k){
if (nums1.size()-i>nums2.size()-j)
return find(nums2,j,nums1,i,k);
if (k==1){
if (nums1.size()==i)
return nums2[j];
else return min(nums1[i],nums2[j]);
}
if (nums1.size()==i)
return nums2[j+k-1];
int si=min((int)nums1.size(),i+k/2);
int sj=j+k/2;
if (nums1[si-1]>nums2[sj-1])
return find(nums1,i,nums2,sj,k-(sj-j));
else return find(nums1,si,nums2,j,k-(si-i));
}
};
5.最长回文子串
class Solution {
public:
string longestPalindrome(string s) {
int n=s.size();
string res;
for(int i=0;i<n;i++){
int l=i-1,r=i+1;
while(l>=0&&r<s.size()&&s[l]==s[r])
l--,r++;
if (r-1-l>res.size())
res=s.substr(l+1,r-1-l);
l=i,r=i+1;
while(l>=0&&r<s.size()&&s[l]==s[r])
l--,r++;
if (r-1-l>res.size())
res=s.substr(l+1,r-1-l);
}
return res;
}
};
10. 正则表达式匹配
给你一个字符串
s
s
s 和一个字符规律
p
p
p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
class Solution {
public:
bool f[35][35];
bool isMatch(string s, string p) {
int n=s.size();
int m=p.size();
s=' '+s;
p=' '+p;
f[0][0]=1;
for(int i=0;i<=n;i++){
for(int j=1;j<=m;j++){
if (j+1<=m&&p[j+1]=='*')
continue;
if (i&&p[j]!='*')
f[i][j]=f[i-1][j-1]&&(s[i]==p[j]||p[j]=='.');
else if (p[j]=='*')
f[i][j]=f[i][j-2]||(i&&f[i-1][j])&&(s[i]==p[j-1]||p[j-1]=='.');
}
}
return f[n][m];
}
};
11. 盛最多水的容器
给定一个长度为
n
n
n 的整数数组
h
e
i
g
h
t
height
height 。有
n
n
n 条垂线，第
i
i
i 条线的两个端点是
(
i
,
0
)
(i, 0)
(i,0) 和
(
i
,
h
e
i
g
h
t
[
i
]
)
(i, height[i])
(i,height[i]) 。
找出其中的两条线，使得它们与
x
x
x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
class Solution {
public:
int maxArea(vector<int>& height) {
int i=0;
int j=height.size()-1;
int maxa=min(height[i],height[j])*(j-i);
while(i<j){
int a=min(height[i],height[j])*(j-i);
maxa=max(maxa,a);
if(height[i]<height[j])
i++;
else
j--;
}
return maxa;
}
};
15. 三数之和
给你一个包含
n
n
n 个整数的数组
n
u
m
s
nums
nums，判断
n
u
m
s
nums
nums 中是否存在三个元素
a
a
a，
b
b
b，
c
c
c ，使得
a
+
b
+
c
=
0
a+b+c=0
a+b+c=0 ？请你找出所有和为
0
0
0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>> resbuf;
int n=nums.size();
sort(nums.begin(),nums.end());
for(int i=0;i<n-1;i++){
if (i>0&&nums[i]==nums[i-1])
continue;
int l=i+1,r=n-1;
while(l<r){
if (nums[l]+nums[i]+nums[r]>0)
r--;
else if (nums[l]+nums[i]+nums[r]<0)
l++;
else if (nums[l]+nums[i]+nums[r]==0){
resbuf.insert({nums[i],nums[l],nums[r]});
l++;
}
}
}
vector<vector<int> > res;
for(auto node:resbuf)
res.push_back(node);
return res;
}
};
17. 电话号码的字母组合
给定一个仅包含数字
2
−
9
2-9
2−9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意
1
1
1 不对应任何字母。
class Solution {
public:
set<char> sc[11];
int n;
vector<string> ans;
string digits;
void dfs(int i,string res){
if (i==n){
ans.push_back(res);
return;
}
for (char ch:sc[digits[i]-'0'])
dfs(i+1,res+ch);
return;
}
vector<string> letterCombinations(string digits) {
if (digits=="")
return ans;
this->digits=digits;
sc[2]={'a','b','c'};
sc[3]={'d','e','f'};
sc[4]={'g','h','i'};
sc[5]={'j','k','l'};
sc[6]={'m','n','o'};
sc[7]={'p','q','r','s'};
sc[8]={'t','u','v'};
sc[9]={'w','x','y','z'};
n=digits.size();
string res="";
dfs(0,res);
return ans;
}
};
19. 删除链表的倒数第 N N N 个结点
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy=new ListNode(0,head);
ListNode *first=head;
for(int i=0;i<n;i++)
first=first->next;
ListNode *second=dummy;
while(first!=NULL){
first=first->next;
second=second->next;
}
ListNode *p=second->next;
second->next=p->next;
delete p;
head=dummy->next;
return head;
}
};
20. 有效的括号
class Solution {
public:
bool check(char c1,char c2){
if (c1=='('&&c2==')'||c1=='{'&&c2=='}'||c1=='['&&c2==']')
return true;
else return false;
}
bool isValid(string s) {
int i=0;
stack<char> stk;
for (int i=0;i<s.size();i++){
if (!stk.empty()&&check(stk.top(),s[i]))
stk.pop();
else
stk.push(s[i]);
}
if (stk.empty())
return true;
else
return false;
}
};
21. 合并两个有序链表
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode *dummy=new ListNode(-1);
ListNode *tail=dummy;
while(list1&&list2){
if (list1->val<list2->val){
tail->next=list1;
tail=tail->next;
list1=list1->next;
}
else {
tail->next=list2;
tail=tail->next;
list2=list2->next;
}
}
if (list1!=NULL)
tail->next=list1;
if (list2!=NULL)
tail->next=list2;
return dummy->next;
}
};
22. 括号生成
class Solution {
public:
string str;
vector<string> res;
int len;
void dfs(int left,int right){
if (len*2==str.size()){
res.push_back(str);
return ;
}
if (left<len){
str.push_back('(');
dfs(left+1,right);
str.pop_back();
}
if (right<left){
str.push_back(')');
dfs(left,right+1);
str.pop_back();
}
}
vector<string> generateParenthesis(int n) {
len=n;
dfs(0,0);
return res;
}
};
23. 合并 K K K个升序链表
class Solution {
public:
struct cmp{
bool operator()(ListNode *a,ListNode*b){
return a->val>b->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode *,vector<ListNode *>,cmp> pq;
ListNode *dummy=new ListNode(-1,NULL);
ListNode *tail=dummy;
for(auto list:lists)
if (list)
pq.push(list);
while(!pq.empty()){
auto p=pq.top();
pq.pop();
tail->next=p;
tail=tail->next;
if (p->next!=NULL){
pq.push(p->next);
p=p->next;
}
}
return dummy->next;
}
};
31. 下一个排列
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int n=nums.size();
int k=n-1;
while(k>0&&nums[k-1]>=nums[k])
k--;
if (k<=0){
reverse(nums.begin(),nums.end());
return;
}
int t=k;
while(t<n&&nums[t]>nums[k-1])
t++;
swap(nums[t-1],nums[k-1]);
sort(nums.begin()+k,nums.end());
return;
}
};
32. 最长有效括号
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> stk;
int ans=0;
stk.push(-1);
int maxlen=s.size();
for (int i=0;i<maxlen;i++){
if (s[i]=='(')
stk.push(i);
else{
stk.pop();
if (stk.empty())
stk.push(i);
else
ans=max(ans,i-stk.top());
}
}
return ans;
}
};
33. 搜索旋转排序数组
整数数组
n
u
m
s
nums
nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，
n
u
m
s
nums
nums 在预先未知的某个下标
k
（
0
<
=
k
<
n
u
m
s
.
l
e
n
g
t
h
）
k（0 <= k < nums.length）
k（0<=k<nums.length）上进行了 旋转，使数组变为$ [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]$（下标 从 0 开始 计数）。例如，
[
0
,
1
,
2
,
4
,
5
,
6
,
7
]
[0,1,2,4,5,6,7]
[0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为
[
4
,
5
,
6
,
7
,
0
,
1
,
2
]
[4,5,6,7,0,1,2]
[4,5,6,7,0,1,2] 。
给你 旋转后 的数组
n
u
m
s
nums
nums 和一个整数
t
a
r
g
e
t
target
target ，如果
n
u
m
s
nums
nums 中存在这个目标值
t
a
r
g
e
t
target
target ，则返回它的下标，否则返回
−
1
-1
−1 。
你必须设计一个时间复杂度为
O
(
l
o
g
n
)
O(log n)
O(logn) 的算法解决此问题。
class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.empty()) return -1;
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (nums[mid] >= nums[0]) l = mid;
else r = mid - 1;
}
if (target >= nums[0]) l = 0;
else l = r + 1, r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
if (nums[r] == target) return r;
return -1;
}
};
34. 在排序数组中查找元素的第一个和最后一个位置
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size()==0)
return {-1,-1};
int l=0;
int r=nums.size()-1;
while(l<r){
int m=(l+r)/2;
if (nums[m]>=target)
r=m;
else l=m+1;
}
int L=l;
if(nums[l]!=target)
return {-1,-1};
l=0;
r=nums.size()-1;
while(l<r){
int m=(l+r+1)/2;
if(nums[m]<=target) l=m;
else r=m-1;
}
int R=r;
return {L,R};
}
};
39. 组合总和
给你一个 无重复元素 的整数数组
c
a
n
d
i
d
a
t
e
s
candidates
candidates 和一个目标整数
t
a
r
g
e
t
target
target ，找出
c
a
n
d
i
d
a
t
e
s
candidates
candidates 中可以使数字和为目标数
t
a
r
g
e
t
target
target 的所有不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
c
a
n
d
i
d
a
t
e
s
candidates
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为
t
a
r
g
e
t
target
target 的不同组合数少于 150 个。
class Solution {
public:
vector<int> candidates;
vector<vector<int>> res;
vector<int> tempres;
int n;
void dfs(int sum,int i){
if (i>=n)
return;
if (sum==0){
res.push_back(tempres);
return;
}
if (sum>=candidates[i]){
tempres.push_back(candidates[i]);
dfs(sum-candidates[i],i);
tempres.pop_back();
dfs(sum,i+1);
}
else dfs(sum,i+1);
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end(),greater<int>());
n=candidates.size();
this->candidates=candidates;
dfs(target,0);
return res;
}
};
42. 接雨水
给定 n n n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
class Solution {
public:
int trap(vector<int>& height) {
int ans=0;
stack<int> stk;
int maxlen=height.size();
for (int i=0;i<maxlen;i++){
while(!stk.empty()&&height[i]>height[stk.top()]){
int h=stk.top();
stk.pop();
if (stk.empty())
break;
int left=stk.top();
int w=i-left-1;
int ht=min(height[left],height[i])-height[h];
ans+=w*ht;
}
stk.push(i);
}
return ans;
}
};
46. 全排列
class Solution {
vector<vector<int> >res;
bool st[10];
int len;
vector<int> vct;
vector<int> nm;
public:
void dfs(int n){
if (n==len)
res.push_back(vct);
for (int i=0;i<len;i++){
if(!st[i]){
st[i]=true;
vct.push_back(nm[i]);
dfs(n+1);
st[i]=false;
vct.pop_back();
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
len=nums.size();
nm=nums;
dfs(0);
return res;
}
};
48. 旋转图像
给定一个 $n × n $的二维矩阵
m
a
t
r
i
x
matrix
matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n=matrix.size();
for(int i=0;i<n/2;i++){
for(int j=0;j<n;j++)
swap(matrix[i][j],matrix[n-i-1][j]);
}
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
swap(matrix[i][j],matrix[j][i]);
}
}
}
};
49. 字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
class Solution {
public:
map<map<char,int>,vector<string>> resbuf;
vector<vector<string>> groupAnagrams(vector<string>& strs) {
for(auto str:strs){
map<char,int> tempset;
for(auto ch:str)
tempset[ch]++;
resbuf[tempset].push_back(str);
}
vector<vector<string> > res;
for(auto node:resbuf){
vector<string> resbuf;
for(auto str:node.second)
resbuf.push_back(str);
res.push_back(resbuf);
}
return res;
}
};
53. 最大子数组和
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int len=nums.size();
vector<int> dp(len);
dp[0]=nums[0];
for (int i=1;i<len;i++){
if (dp[i-1]>=0)
dp[i]=dp[i-1]+nums[i];
else
dp[i]=nums[i];
}
int res=-0x3f3f3f3f;
for (int i=0;i<len;i++)
res=max(res,dp[i]);
return res;
}
};
55. 跳跃游戏
给定一个非负整数数组
n
u
m
s
nums
nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
class Solution {
public:
bool canJump(vector<int>& nums) {
int n=nums.size();
int rightmost=0;
for(int i=0;i<=rightmost;i++){
rightmost=max(rightmost,i+nums[i]);
if (rightmost>=n-1)
return true;
}
return false;
}
};
56. 合并区间
以数组 i n t e r v a l s intervals intervals 表示若干个区间的集合，其中单个区间为 i n t e r v a l s [ i ] = [ s t a r t i , e n d i ] intervals[i] = [start_i, end_i] intervals[i]=[starti,endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end());
int st=intervals[0][0],ed=intervals[0][1];
vector<vector<int>> res;
int n=intervals.size();
for(int i=0;i<n;i++){
if (i&&intervals[i][0]>ed){
res.push_back({st,ed});
st=intervals[i][0];
ed=intervals[i][1];
}
if (intervals[i][0]<=ed&&intervals[i][1]>=ed)
ed=intervals[i][1];
}
res.push_back({st,ed});
return res;
}
};
72. 编辑距离
给你两个单词
w
o
r
d
1
word_1
word1 和
w
o
r
d
2
word_2
word2， 请返回将
w
o
r
d
1
word_1
word1 转换成
w
o
r
d
2
word_2
word2 所使用的最少操作数 。
可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
class Solution {
public:
int dp[501][501];
int minDistance(string word1, string word2) {
int len1=word1.size();
int len2=word2.size();
if(len1*len2==0)
return len1+len2;
for(int i=0;i<=len1;i++)
dp[i][0]=i;
for(int j=0;j<=len2;j++)
dp[0][j]=j;
for(int i=1;i<=len1;i++)
for(int j=1;j<=len2;j++){
if (word1[i-1]==word2[j-1])
dp[i][j]=dp[i-1][j-1];
else
dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
}
return dp[len1][len2];
}
};
75. 荷兰国旗
class Solution {
public:
void sortColors(vector<int>& nums) {
for(int i=0,j=0,k=nums.size()-1;i<=k;){
if (nums[i]==0)
swap(nums[i++],nums[j++]);
else if (nums[i]==2)
swap(nums[i],nums[k--]);
else i++;
}
}
};
76. 最小覆盖子串
给你一个字符串 s s s、一个字符串 t t t。返回 s s s中涵盖 t t t所有字符的最小子串。如果 s s s中不存在涵盖 t t t所有字符的子串，则返回空字符串 “” 。
class Solution {
public:
string minWindow(string s, string t) {
map<char,int> hs,ht;
for(auto c:t)
ht[c]++;
string res;
int n=s.size();
int cnt=0;
for(int i=0,j=0;i<n;i++){
hs[s[i]]++;
if (hs[s[i]]<=ht[s[i]])
cnt++;
while(hs[s[j]]>ht[s[j]])
hs[s[j++]]--;
if (cnt==t.size())
if (res.empty()||i-j+1<res.size())
res=s.substr(j,i-j+1);
}
return res;
}
};
78. 子集
给你一个整数数组
n
u
m
s
nums
nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
int n=nums.size();
for(int mask=0;mask<(1<<n);mask++){
vector<int> tempres;
for(int i=0;i<n;i++)
if (mask>>i&1)
tempres.push_back(nums[i]);
res.push_back(tempres);
}
return res;
}
};
79. 单词搜索
给定一个
m
x
n
m x n
mxn 二维字符网格
b
o
a
r
d
board
board 和一个字符串单词
w
o
r
d
word
word 。如果
w
o
r
d
word
word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
class Solution {
public:
bool st[10][10];
string word;
vector<vector<char>> board;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int m,n;
bool dfs(int i,int j,int pos){
if (pos==word.size())
return true;
for(int k=0;k<4;k++){
int px=i+dx[k];
int py=j+dy[k];
if (px<0||px>=m||py<0||py>=n)
continue;
if (st[px][py])
continue;
if (word[pos]==board[px][py]){
st[px][py]=1;
if (dfs(px,py,pos+1))
return true;
st[px][py]=0;
}
}
return false;
}
bool exist(vector<vector<char>>& board, string word) {
m=board.size();
n=board[0].size();
this->word=word;
this->board=board;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if (board[i][j]==word[0]){
st[i][j]=1;
if (dfs(i,j,1))
return true;
st[i][j]=0;
}
}
}
return false;
}
};
84. 柱状图中最大的矩形
给定
n
n
n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n=heights.size();
vector<int> left(n),right(n);
stack<int> stk;
for(int i=0;i<n;i++){
while(stk.size()&&heights[stk.top()]>=heights[i])
stk.pop();
if (stk.empty())
left[i]=-1;
else left[i]=stk.top();
stk.push(i);
}
while(stk.size())
stk.pop();
for(int i=n-1;i>=0;i--){
while(stk.size()&&heights[stk.top()]>=heights[i])
stk.pop();
if (stk.empty())
right[i]=n;
else right[i]=stk.top();
stk.push(i);
}
int res=0;
for(int i=0;i<n;i++)
res=max(res,(right[i]-left[i]-1)*heights[i]);
return res;
}
};
85. 最大矩形
给定一个仅包含 0 和 1 、大小为 r o w s x c o l s rows x cols rowsxcols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n=heights.size();
vector<int> left(n),right(n);
stack<int> stk;
for(int i=0;i<n;i++){
while(stk.size()&&heights[stk.top()]>=heights[i])
stk.pop();
if (stk.empty())
left[i]=-1;
else left[i]=stk.top();
stk.push(i);
}
while(stk.size())
stk.pop();
for(int i=n-1;i>=0;i--){
while(stk.size()&&heights[stk.top()]>=heights[i])
stk.pop();
if (stk.empty())
right[i]=n;
else right[i]=stk.top();
stk.push(i);
}
int res=0;
for(int i=0;i<n;i++)
res=max(res,(right[i]-left[i]-1)*heights[i]);
return res;
}
int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.empty()||matrix[0].empty())
return 0;
int n=matrix.size();
int m=matrix[0].size();
vector<vector<int>> h(n,vector<int>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if (matrix[i][j]=='1'){
if (i)
h[i][j]=h[i-1][j]+1;
else h[i][j]=1;
}
}
}
int res=0;
for(int i=0;i<n;i++)
res=max(res,largestRectangleArea(h[i]));
return res;
}
};
94. 二叉树的中序遍历
给定一个二叉树的根节点 r o o t root root ，返回 它的 中序 遍历 。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void inorder(TreeNode *root,vector<int> &res){
if (root==NULL)
return;
inorder(root->left,res);
res.push_back(root->val);
inorder(root->right,res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root,res);
return res;
}
};
96. 不同的二叉搜索树
给你一个整数 n n n ，求恰由 n n n 个节点组成且节点值从 1 1 1 到 n n n 互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。
class Solution {
public:
int numTrees(int n) {
vector<int> f(25,0);
f[0]=0;
f[1]=1;
f[2]=2;
if (n<3)
return f[n];
f[0]=1;
for(int i=3;i<=n;i++){
for(int j=0;j<=i-1;j++)
f[i]+=f[j]*f[i-j-1];
}
return f[n];
}
};
98.验证二叉搜索树
class Solution {
public:
long long pre=LONG_MIN;
bool isValidBST(TreeNode* root) {
if(root==NULL)
return true;
if (!isValidBST(root->left))
return false;
if(root->val<=pre)
return false;
pre=root->val;
return isValidBST(root->right);
}
};
101.对称二叉树
class Solution {
public:
bool dfs(TreeNode* p, TreeNode* q) {
if (p==NULL&&q==NULL)
return true;
else if(p==NULL||q==NULL)
return false;
else if (p->val!=q->val)
return false;
else return (dfs(p->left,q->right)&&dfs(p->right,q->left));
}
bool isSymmetric(TreeNode* root) {
return dfs(root,root);
}
};
102. 二叉树的层序遍历
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (root==NULL)
return res;
queue<TreeNode *>q;
q.push(root);
while(!q.empty()){
int qsize=q.size();
res.push_back(vector<int>());
for(int i=0;i<qsize;i++){
auto node=q.front();
q.pop();
res.back().push_back(node->val);
if (node->left!=NULL)
q.push(node->left);
if (node->right!=NULL)
q.push(node->right);
}
}
return res;
}
};
104. 二叉树的最大深度
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root!=NULL)
return max(maxDepth(root->left),maxDepth(root->right))+1;
else return 0;
}
};
105. 从前序与中序遍历序列构造二叉树
class Solution {
public:
unordered_map<int,int> num2idx;
vector<int> preorder;
vector<int> inorder;
int n;
TreeNode *buildTree(int pl,int pr,int il,int ir){
if (pl>pr)
return NULL;
int rval=preorder[pl];
TreeNode *root=new TreeNode(rval);
int rootpos=num2idx[rval];
int len=rootpos-il;
root->left=buildTree(pl+1,pl+len,il,rootpos-1);
root->right=buildTree(pl+len+1,pr,rootpos+1,ir);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
this->preorder=preorder;
this->inorder=inorder;
n=preorder.size();
for(int i=0;i<inorder.size();i++)
num2idx[inorder[i]]=i;
TreeNode *root=buildTree(0,n-1,0,n-1);
return root;
}
};
114. 二叉树展开为链表
class Solution {
public:
void flatten(TreeNode* &root) {
while(root){
TreeNode *p=root->left;
if (p){
while(p->right)
p=p->right;
p->right=root->right;
root->right=root->left;
root->left=NULL;
}
root=root->right;
}
}
};
121. 买卖股票的最佳时机
给定一个数组
p
r
i
c
e
s
prices
prices ，它的第
i
i
i个元素
p
r
i
c
e
s
[
i
]
prices[i]
prices[i]表示一支给定股票第
i
i
i天的价格。
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
class Solution {
public:
int maxProfit(vector<int>& prices) {
stack<int> stk;
int n=prices.size();
int res=0;
for(int i=0;i<n;i++){
if (stk.empty()||prices[i]<stk.top())
stk.push(prices[i]);
res=max(res,prices[i]-stk.top());
}
return res;
}
};
124. 二叉树中的最大路径和
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
class Solution {
int res=-0x3f3f3f3f;
public:
int maxgain(TreeNode* root){
if (root==NULL)
return 0;
int maxleft=max(maxgain(root->left),0);
int maxright=max(maxgain(root->right),0);
int curres=maxleft+maxright+root->val;
res=max(curres,res);
return root->val+max(maxleft,maxright);
}
int maxPathSum(TreeNode* root) {
maxgain(root);
return res;
}
};
128. 最长连续序列
给定一个未排序的整数数组
n
u
m
s
nums
nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为
O
(
n
)
O(n)
O(n) 的算法解决此问题。
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
set<int> st;
for(auto num:nums)
st.insert(num);
int res=0;
for(auto num:nums){
if (st.count(num)&&!st.count(num-1)){
int x=num;
int y=x;
st.erase(x);
while(st.count(y+1)){
y++;
st.erase(y);
}
res=max(res,y-x+1);
}
}
return res;
}
};
136. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res=0;
for(auto num:nums){
res^=num;
}
return res;
}
};
139. 单词拆分
给你一个字符串 s s s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s s s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n=s.size();
vector<int> f(n+1);
f[0]=1;
for(int i=1;i<=n;i++){
for(string word:wordDict){
int len=word.size();
if (i>=len){
if (s.substr(i-len,len)==word)
f[i]|=f[i-len];
}
}
}
return f[n];
}
};
141. 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
class Solution {
public:
bool hasCycle(ListNode *head) {
if (!head || !head->next) return 0;
ListNode *first = head, *second = first->next;
while (first && second)
{
if (first == second) return true;
first = first->next;
second = second->next;
if (second) second = second->next;
}
return false;
}
};
142. 环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
set<ListNode*> st;
while(head){
if (st.count(head))
return head;
st.insert(head);
head=head->next;
}
return NULL;
}
};
146. LRU 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量
c
a
p
a
c
i
t
y
capacity
capacity 初始化 LRU 缓存
int get(int key) 如果关键字
k
e
y
key
key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字
k
e
y
key
key 已经存在，则变更其数据值
v
a
l
u
e
value
value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以
O
(
1
)
O(1)
O(1)的平均时间复杂度运行。
class LRUCache {
public:
struct Node{
int key,val;
Node *left,*right;
Node():key(0),val(0),left(NULL),right(NULL){}
};
Node *hu,*hr,*tu,*tr;
int n;
unordered_map<int,Node *>hash;
void delete_node(Node *p){
p->left->right=p->right;
p->right->left=p->left;
}
void insert_node(Node *head,Node *p){
p->right=head->right;
head->right=p;
p->left=head;
p->right->left=p;
}
LRUCache(int capacity) {
n=capacity;
hu=new Node(),hr=new Node(),tu=new Node(),tr=new Node();
hu->right=tu,tu->left=hu;
hr->right=tr,tr->left=hr;
for(int i=0;i<n;i++){
Node *p=new Node();
insert_node(hr,p);
}
}
int get(int key) {
if (hash[key]){
Node *p=hash[key];
delete_node(p);
insert_node(hu,p);
return p->val;
}
return -1;
}
void put(int key, int value) {
if (hash[key]){
Node *p=hash[key];
delete_node(p);
insert_node(hu,p);
p->val=value;
return;
}
if (!n){
n++;
Node *p=tu->left;
hash[p->key]=0;
delete_node(p);
insert_node(hr,p);
}
n--;
Node *p=hr->right;
p->key=key,p->val=value,hash[key]=p;
delete_node(p);
insert_node(hu,p);
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
148. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
class Solution {
public:
ListNode* sortList(ListNode* head) {
if(head==NULL)
return head;
int n=0;
for(auto p=head;p;p=p->next)
n++;
auto dummy=new ListNode (-1);
dummy->next=head;
for(int i=1;i<n;i*=2){
auto cur=dummy;
for(int j=1;j+i<=n;j+=i*2){
auto p=cur->next,q=p;
for(int k=0;k<i;k++)
q=q->next;
int x=0,y=0;
while(x<i&&y<i&&p&&q){
if (p->val<=q->val){
cur=cur->next=p;
p=p->next;
x++;
}
else{
cur=cur->next=q;
q=q->next;
y++;
}
}
while(x<i&&p){
cur=cur->next=p;
p=p->next;
x++;
}
while(y<i&&q){
cur=cur->next=q;
q=q->next;
y++;
}
cur->next=q;
}
}
return dummy->next;
}
};
152. 乘积最大子数组
给你一个整数数组 n u m s nums nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
class Solution {
public:
int maxProduct(vector<int>& nums) {
int res=nums[0],f=nums[0],g=nums[0];
for(int i=1;i<nums.size();i++){
int num=nums[i];
int fa=f*num;
int ga=g*num;
f=max(num,max(fa,ga));
g=min(num,min(fa,ga));
res=max(res,f);
}
return res;
}
};
155. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
class MinStack {
stack<int> stk;
stack<int> minstk;
public:
MinStack() {
minstk.push(INT_MAX);
}
void push(int val) {
stk.push(val);
if (val<=minstk.top())
minstk.push(val);
}
void pop() {
if (stk.top()==minstk.top())
minstk.pop();
stk.pop();
}
int top() {
return stk.top();
}
int getMin() {
if (minstk.size()==1)
return 0;
return minstk.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
160. 相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int len1=0,len2=0;
ListNode *p1=headA;
while(p1->next!=NULL){
len1++;
p1=p1->next;
}
ListNode *p2=headB;
while(p2->next!=NULL){
len2++;
p2=p2->next;
}
if (len1>len2)
return getIntersectionNode(headB,headA);
p2=headB;
p1=headA;
for(int i=0;i<len2-len1;i++)
p2=p2->next;
while(p1!=NULL&&p2!=NULL&&p1!=p2){
p1=p1->next;
p2=p2->next;
}
if (p1==p2)
return p1;
else return NULL;
}
};
169. 多数元素
给定一个大小为
n
n
n 的数组
n
u
m
s
nums
nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于
⌊
n
/
2
⌋
⌊ n/2 ⌋
⌊n/2⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
class Solution {
public:
int majorityElement(vector<int>& nums) {
int r=0,c=0;
for(auto num:nums){
if (c==0)
r=num;
if (num!=r)
c--;
else c++;
}
return r;
}
};
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
class Solution {
public:
int dp[105];
int rob(vector<int>& nums) {
int len=nums.size();
if (len==0)
return 0;
if (len == 1)
return nums[0];
dp[0]=nums[0];
dp[1]=max(nums[0],nums[1]);
for(int i=2;i<len;i++)
dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
return dp[len-1];
}
};
200. 岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
class Solution {
public:
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int numIslands(vector<vector<char>>& grid) {
int m=grid.size();
int n=grid[0].size();
vector<vector<bool>> st(m,vector<bool>(n,0));
int res=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if (!st[i][j]&&grid[i][j]=='1'){
st[i][j]=1;
res++;
queue<pair<int,int>> q;
q.push({i,j});
while(!q.empty()){
auto [px,py]=q.front();
q.pop();
int tx,ty;
for (int k=0;k<4;k++){
tx=px+dx[k];
ty=py+dy[k];
if (tx<0||tx>=m||ty<0||ty>=n)
continue;
if (st[tx][ty])
continue;
if (grid[tx][ty]!='1')
continue;
q.push({tx,ty});
st[tx][ty]=1;
}
}
}
}
}
return res;
}
};
206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head==NULL)
return head;
ListNode *p2=head->next;
ListNode *p1=head;
p1->next=NULL;
while(p2!=NULL){
ListNode *ptemp=p2->next;
p2->next=p1;
p1=p2;
p2=ptemp;
}
return p1;
}
};
207. 课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
class Solution {
vector<int> G[100005];
int indegree[100005];
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
int n=numCourses;
queue<int> q;
for (auto node:prerequisites){
G[node[0]].push_back(node[1]);
}
memset(indegree,0,sizeof indegree);
for(int i=0;i<n;i++)
for(auto node:G[i])
indegree[node]++;
int count=0;
for (int i=0;i<n;i++)
if (indegree[i]==0)
q.push(i);
while(!q.empty()){
int p=q.front();
q.pop();
count++;
for (auto node:G[p]){
indegree[node]--;
if (indegree[node]==0){
q.push(node);
}
}
}
return count==n;
}
};
208. 实现 Trie (前缀树)
class Trie {
public:
bool isword[300005];
int ne[300005][26];
int idx=0;
Trie() {
memset(isword,0,sizeof isword);
idx=0;
memset(ne,0,sizeof ne);
}
void insert(string word) {
int n=word.size();
int p=0;
for(int i=0;i<n;i++){
int u=word[i]-'a';
if (!ne[p][u]){
ne[p][u]=++idx;
}
p=ne[p][u];
}
isword[p]=1;
}
bool search(string word) {
int n=word.size();
int p=0;
for(int i=0;i<n;i++){
int u=word[i]-'a';
if (!ne[p][u])
return false;
p=ne[p][u];
}
return isword[p];
}
bool startsWith(string prefix) {
int n=prefix.size();
int p=0;
for(int i=0;i<n;i++){
int u=prefix[i]-'a';
if (!ne[p][u])
return false;
p=ne[p][u];
}
return true;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/
215. 数组中的第 K K K个最大元素
给定整数数组
n
u
m
s
nums
nums 和整数
k
k
k，请返回数组中第
k
k
k 个最大的元素。
请注意，你需要找的是数组排序后的第
k
k
k 个最大的元素，而不是第
k
k
k 个不同的元素。
你必须设计并实现时间复杂度为
O
(
n
)
O(n)
O(n) 的算法解决此问题。
class Solution {
public:
int quick_selection(vector<int>& nums,int l,int r,int k){
if (l==r)
return nums[k];
int x=nums[l];
int i=l-1,j=r+1;
while(i<j){
do i++;while(nums[i]<x);
do j--;while(nums[j]>x);
if (i<j)
swap(nums[i],nums[j]);
}
if (k<=j)
return quick_selection(nums,l,j,k);
else return quick_selection(nums,j+1,r,k);
}
int findKthLargest(vector<int>& nums, int k) {
return quick_selection(nums,0,nums.size()-1,nums.size()-k);
}
};
221. 最大正方形
在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int n=matrix.size();
int m=matrix[0].size();
int res=0;
vector<vector<int>> f(n,vector<int>(m,0));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if (i==j&&i==0)
f[i][j]=matrix[i][j]-'0';
else if (i==0||j==0)
f[i][j]=matrix[i][j]-'0';
else if (matrix[i][j]=='1')
f[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+1;
res=max(res,f[i][j]);
}
}
return res*res;
}
};
226. 翻转二叉树
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root==NULL)
return root;
if (root->left!=NULL)
invertTree(root->left);
if (root->right!=NULL)
invertTree(root->right);
swap(root->left,root->right);
return root;
}
};
234. 回文链表
class Solution {
public:
bool isPalindrome(ListNode* head) {
stack<int> stk;
ListNode *p=head;
while(p!=NULL){
stk.push(p->val);
p=p->next;
}
p=head;
while(!stk.empty()){
int t=stk.top();
stk.pop();
if (t!=p->val){
return false;
}
p=p->next;
}
return true;
}
};
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树
T
T
T的两个节点
p
p
p、
q
q
q，最近公共祖先表示为一个节点
x
x
x，满足
x
x
x是
p
p
p、
q
q
q的祖先且
x
x
x的深度尽可能大（一个节点也可以是它自己的祖先）。”
class Solution {
public:
unordered_map<TreeNode *,int> l;
unordered_map<TreeNode *,TreeNode *>f;
void dfs(TreeNode *root){
if (root->left){
f[root->left]=root;
l[root->left]=l[root]+1;
dfs(root->left);
}
if (root->right){
f[root->right]=root;
l[root->right]=l[root]+1;
dfs(root->right);
}
return;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
f[root]=NULL;
l[root]=0;
dfs(root);
int lp=l[p];
int lq=l[q];
while(lp>lq){
p=f[p];
lp=l[p];
}
while(lq>lp){
q=f[q];
lq=l[q];
}
while(p!=q){
p=f[p];
q=f[q];
}
return p;
}
};
238. 除自身以外数组的乘积
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n=nums.size();
vector<int> l(n,1);//左缀
vector<int> r(n,1);//右缀
for(int i=1;i<n;i++)
l[i]=l[i-1]*nums[i-1];
for(int i=n-2;i>=0;i--)
r[i]=r[i+1]*nums[i+1];
vector<int> res(n,1);
for(int i=0;i<n;i++)
res[i]=l[i]*r[i];
return res;
}
};
239. 滑动窗口最大值
给你一个整数数组
n
u
m
s
nums
nums，有一个大小为
k
k
k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的
k
k
k个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dq;
int n=nums.size();
vector<int> ans;
for (int i = 0; i < n; i++) {
if (!dq.empty() && i - k + 1 > dq.front())
dq.pop_front();
while (!dq.empty() && nums[dq.back()] <= nums[i])
dq.pop_back();
dq.push_back(i);
if (i >= k - 1)
ans.push_back(nums[dq.front()]);
}
return ans;
}
};
240. 搜索二维矩阵 II
编写一个高效的算法来搜索
m
x
n
mxn
mxn矩阵
m
a
t
r
i
x
matrix
matrix中的一个目标值
t
a
r
g
e
t
target
target。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty()||matrix[0].empty())
return false;
int n=matrix.size();
int m=matrix[0].size();
int i=0,j=m-1;
while(i<n&&j>=0){
int t=matrix[i][j];
if (t==target)
return true;
else if (t>target)
j--;
else i++;
}
return false;
}
};
279. 完全平方数
给你一个整数
n
n
n，返回和为
n
n
n的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
class Solution {
public:
int numSquares(int n) {
vector<int> f(n+1,0x3f3f3f3f);
f[0]=0;
f[1]=1;
for(int i=2;i<=n;i++){
for(int j=1;j*j<=i;j++)
f[i]=min(f[i],f[i-j*j]+1);
}
return f[n];
}
};
283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n=nums.size();
int i=0,j=0;
for(;i<n;i++){
if (nums[i]!=0){
nums[j]=nums[i];
j++;
}
}
for(;j<n;j++)
nums[j]=0;
}
};
287. 寻找重复数
给定一个包含
n
+
1
n+1
n+1个整数的数组
n
u
m
s
nums
nums，其数字都在
[
1
,
n
]
[1,n]
[1,n] 范围内（包括
1
1
1和
n
n
n），可知至少存在一个重复的整数。
假设
n
u
m
s
nums
nums只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组
n
u
m
s
nums
nums且只用常量级
O
(
1
)
O(1)
O(1)的额外空间。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow=0,fast=0;
do{
slow=nums[slow];
fast=nums[nums[fast]];
}while(slow!=fast);
slow=0;
while(slow!=fast){
slow=nums[slow];
fast=nums[fast];
}
return slow;
}
};
297. 二叉树的序列化与反序列化
class Codec {
public:
string path;
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
dfs_s(root);
return path;
}
void dfs_s(TreeNode* root) {
if (!root) path += "#,";
else {
path += to_string(root->val) + ',';
dfs_s(root->left);
dfs_s(root->right);
}
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
int u = 0;
return dfs_d(data, u);
}
TreeNode* dfs_d(string& data, int& u) {
if (data[u] == '#') {
u += 2;
return NULL;
} else {
int k = u;
while (data[u] != ',') u ++ ;
auto root = new TreeNode(stoi(data.substr(k, u - k)));
u ++ ;
root->left = dfs_d(data, u);
root->right = dfs_d(data, u);
return root;
}
}
};
301. 删除无效的括号
给你一个由若干括号和字母组成的字符串
s
s
s，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
class Solution {
public:
vector<string> ans;
vector<string> removeInvalidParentheses(string s) {
int l = 0, r = 0;
for (auto x: s)
if (x == '(') l ++ ;
else if (x == ')') {
if (l == 0) r ++ ;
else l -- ;
}
dfs(s, 0, "", 0, l, r);
return ans;
}
void dfs(string& s, int u, string path, int cnt, int l, int r) {
if (u == s.size()) {
if (!cnt) ans.push_back(path);
return;
}
if (s[u] != '(' && s[u] != ')') dfs(s, u + 1, path + s[u], cnt, l, r);
else if (s[u] == '(') {
int k = u;
while (k < s.size() && s[k] == '(') k ++ ;
l -= k - u;
for (int i = k - u; i >= 0; i -- ) {
if (l >= 0) dfs(s, k, path, cnt, l, r);
path += '(';
cnt ++, l ++ ;
}
} else if (s[u] == ')') {
int k = u;
while (k < s.size() && s[k] == ')') k ++ ;
r -= k - u;
for (int i = k - u; i >= 0; i -- ) {
if (cnt >= 0 && r >= 0) dfs(s, k, path, cnt, l, r);
path += ')';
cnt --, r ++ ;
}
}
}
};
309. 最佳买卖股票时机含冷冻期
给定一个整数数组
p
r
i
c
e
s
prices
prices，其中第
p
r
i
c
e
s
[
i
]
prices[i]
prices[i]表示第
i
i
i天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
vector<vector<int>> f(n,vector<int>(3,0));
f[0][1]=-prices[0];
int res=0;
for(int i=1;i<n;i++){
f[i][0]=max(f[i-1][0],f[i-1][2]);
f[i][1]=max(f[i-1][0]-prices[i],f[i-1][1]);
f[i][2]=f[i-1][1]+prices[i];
}
return max(f[n-1][0],f[n-1][2]);
}
};
312. 戳气球
有
n
n
n个气球，编号为
0
0
0到
n
−
1
n-1
n−1，每个气球上都标有一个数字，这些数字存在数组
n
u
m
s
nums
nums中。
现在要求你戳破所有的气球。戳破第
i
i
i个气球，你可以获得
n
u
m
s
[
i
−
1
]
∗
n
u
m
s
[
i
]
∗
n
u
m
s
[
i
+
1
]
nums[i-1]*nums[i]*nums[i+1]
nums[i−1]∗nums[i]∗nums[i+1]枚硬币。 这里的
i
−
1
i-1
i−1和
i
+
1
i+1
i+1代表和
i
i
i相邻的两个气球的序号。如果
i
−
1
i-1
i−1或
i
+
1
i+1
i+1超出了数组的边界，那么就当它是一个数字为1的气球。
求所能获得硬币的最大数量。
class Solution {
public:
int maxCoins(vector<int>& nums) {
int n=nums.size();
vector<int> a(n+2,1);
for(int i=0;i<n;i++)
a[i+1]=nums[i];
vector<vector<int>> f(n+2,vector<int>(n+2,0));
for(int len=3;len<=n+2;len++){
for(int i=0;i+len-1<=n+1;i++){
int j=i+len-1;
for(int k=i+1;k<j;k++){
f[i][j]=max(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j]);
}
}
}
return f[0][n+1];
}
};
322. 零钱兑换
给你一个整数数组
c
o
i
n
s
coins
coins，表示不同面额的硬币；以及一个整数
a
m
o
u
n
t
amount
amount，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回
−
1
-1
−1。
你可以认为每种硬币的数量是无限的。
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
sort(coins.begin(),coins.end());
vector<int> f(amount+1,0x3f3f3f3f);
f[0]=0;
for(int i=1;i<=amount;i++){
for(int coin:coins){
if (i>=coin)
f[i]=min(f[i],f[i-coin]+1);
}
}
if (f[amount]==0x3f3f3f3f)
return -1;
else return f[amount];
}
};
337. 打家劫舍 III
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
class Solution {
public:
vector<int> dfs(TreeNode *root){
if (root==NULL)
return {0,0};
vector<int> f(2);
auto l=dfs(root->left);
auto r=dfs(root->right);
f[0]=max(l[0],l[1])+max(r[0],r[1]);
f[1]=l[0]+r[0]+root->val;
return f;
}
int rob(TreeNode* root) {
auto f=dfs(root);
return max(f[0],f[1]);
}
};
338. 比特位计数
给你一个整数 n n n ，对于 0 < = i < = n 0<=i<=n 0<=i<=n中的每个 i i i，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 n+1 n+1的数组 a n s ans ans作为答案。
class Solution {
public:
vector<int> countBits(int n) {
vector<int> f(n+1);
for(int i=1;i<=n;i++){
f[i]=f[i>>1]+(i&1);
}
return f;
}
};
347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> cnt;
for (auto x: nums) cnt[x] ++ ;
int n = nums.size();
vector<int> s(n + 1);
for (auto [x, c]: cnt) s[c] ++ ;
int i = n, t = 0;
while (t < k) t += s[i -- ];
vector<int> res;
for (auto [x, c]: cnt)
if (c > i)
res.push_back(x);
return res;
}
};
394. 字符串解码
class Solution {
public:
string decodeString(string s) {
int u = 0;
return dfs(s, u);
}
string dfs(string& s, int& u) {
string res;
while (u < s.size() && s[u] != ']') {
if (s[u] >= 'a' && s[u] <= 'z' || s[u] >= 'A' && s[u] <= 'Z') res += s[u ++ ];
else if (s[u] >= '0' && s[u] <= '9') {
int k = u;
while (s[k] >= '0' && s[k] <= '9') k ++ ;
int x = stoi(s.substr(u, k - u));
u = k + 1;
string y = dfs(s, u);
u ++ ; // 过滤掉右括号
while (x -- ) res += y;
}
}
return res;
}
};
399. 除法求值
给你一个变量对数组
e
q
u
a
t
i
o
n
s
equations
equations和一个实数值数组
v
a
l
u
e
s
values
values作为已知条件，其中
e
q
u
a
t
i
o
n
s
i
=
A
i
,
B
i
equations_i=A_i,B_i
equationsi=Ai,Bi和
v
a
l
u
e
s
i
values_i
valuesi共同表示等式
A
i
/
B
i
=
v
a
l
u
e
s
i
A_i/B_i=values_i
Ai/Bi=valuesi。每个
A
i
A_i
Ai或
B
i
B_i
Bi是一个表示单个变量的字符串。
另有一些以数组
q
u
e
r
i
e
s
queries
queries表示的问题，其中
q
u
e
r
i
e
s
j
=
C
j
,
D
j
queries_j=C_j,D_j
queriesj=Cj,Dj表示第
j
j
j个问题，请你根据已知条件找出
C
j
/
D
j
=
C_j/D_j=
Cj/Dj=? 的结果作为答案。
返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
class Solution {
public:
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
unordered_set<string> vers;
unordered_map<string, unordered_map<string, double>> d;
for (int i = 0; i < equations.size(); i ++ ) {
auto a = equations[i][0], b = equations[i][1];
auto c = values[i];
d[a][b] = c, d[b][a] = 1 / c;
vers.insert(a), vers.insert(b);
}
for (auto k: vers)
for (auto i: vers)
for (auto j: vers)
if (d[i][k] && d[j][k])
d[i][j] = d[i][k] * d[k][j];
vector<double> res;
for (auto q: queries) {
auto a = q[0], b = q[1];
if (d[a][b]) res.push_back(d[a][b]);
else res.push_back(-1);
}
return res;
}
};
402. 移掉K位数字
class Solution {
public:
string removeKdigits(string num, int k) {
k = min(k, (int)num.size());
string res;
for (auto c: num) {
while (k && res.size() && res.back() > c) {
k -- ;
res.pop_back();
}
res += c;
}
while (k -- ) res.pop_back();
k = 0;
while (k < res.size() && res[k] == '0') k ++ ;
if (k == res.size()) res += '0';
return res.substr(k);
}
};
406. 根据身高重建队列
假设有打乱顺序的一群人站成一个队列，数组
p
e
o
p
l
e
people
people表示队列中一些人的属性（不一定按顺序）。每个
p
e
o
p
l
e
i
=
h
i
,
k
i
people_i=h_i, k_i
peoplei=hi,ki表示第
i
i
i个人的身高为
h
i
h_i
hi，前面正好有
k
i
k_i
ki个身高大于或等于
h
i
h_i
hi的人。
请你重新构造并返回输入数组
p
e
o
p
l
e
people
people所表示的队列。返回的队列应该格式化为数组
q
u
e
u
e
queue
queue ，其中
q
u
e
u
e
j
=
h
j
,
k
j
queue_j=h_j,k_j
queuej=hj,kj是队列中第
j
j
j个人的属性（
q
u
e
u
e
0
queue_0
queue0是排在队列前面的人）。
class Solution {
public:
int n;
vector<int> tr;
int lowbit(int x) {
return x & -x;
}
void add(int x, int v) {
for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}
int query(int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
n = people.size();
tr.resize(n + 1);
sort(people.begin(), people.end(), [](vector<int>a, vector<int>b) {
if (a[0] != b[0]) return a[0] < b[0];
return a[1] > b[1];
});
vector<vector<int>> res(n);
for (auto p: people) {
int h = p[0], k = p[1];
int l = 1, r = n;
while (l < r) {
int mid = l + r >> 1;
if (mid - query(mid) >= k + 1) r = mid;
else l = mid + 1;
}
res[r - 1] = p;
add(r, 1);
}
return res;
}
};
/*
class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
auto cmp = [](const vector<int>& a, const vector<int>& b) {
if(a[0] != b[0]) return a[0] < b[0];
return a[1] > b[1];
};
sort(people.begin(), people.end(), cmp);
int n = people.size();
vector<vector<int>> res(n);
for(auto &p: people) {
int k = p[1] + 1;
for(auto &seg: res)
if(seg.empty()) {
k --;
if(!k) {
seg = p;
break;
}
}
}
return res;
}
};
*/
416. 分割等和子集
给你一个 只包含正整数的非空数组 n u m s nums nums请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
class Solution {
public:
bool canPartition(vector<int>& nums) {
bitset<10001> f;
f[0] = 1;
int sum = 0;
for (auto x: nums) {
f |= f << x;
sum += x;
}
if (sum % 2) return false;
return f[sum / 2];
}
};
437. 路径总和 III
给定一个二叉树的根节点
r
o
o
t
root
root，和一个整数
t
a
r
g
e
t
S
u
m
targetSum
targetSum，求该二叉树里节点值之和等于
t
a
r
g
e
t
S
u
m
targetSum
targetSum的路径的数目。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
class Solution {
public:
unordered_map<int, int> cnt;
int res = 0;
int pathSum(TreeNode* root, int sum) {
cnt[0] ++ ;
dfs(root, sum, 0);
return res;
}
void dfs(TreeNode* root, int sum, int cur) {
if (!root) return;
cur += root->val;
res += cnt[cur - sum];
cnt[cur] ++ ;
dfs(root->left, sum, cur), dfs(root->right, sum, cur);
cnt[cur] -- ;
}
};
438. 找到字符串中所有字母异位词
给定两个字符串
s
s
s和
p
p
p，找到
s
s
s中所有
p
p
p的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
unordered_map<char, int> cnt;
for (auto c: p) cnt[c] ++ ;
vector<int> res;
int tot = cnt.size();
for (int i = 0, j = 0, satisfy = 0; i < s.size(); i ++ ) {
if ( -- cnt[s[i]] == 0) satisfy ++ ;
while (i - j + 1 > p.size()) {
if (cnt[s[j]] == 0) satisfy -- ;
cnt[s[j ++ ]] ++ ;
}
if (satisfy == tot) res.push_back(j);
}
return res;
}
};
448. 找到所有数组中消失的数字
给你一个含 n n n个整数的数组 n u m s nums nums，其中 n u m s i nums_i numsi在区间 [ 1 , n ] [1, n] [1,n]内。请你找出所有在 [ 1 , n ] [1,n] [1,n]范围内但没有出现在 n u m s nums nums中的数字，并以数组的形式返回结果。
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
for (auto x: nums) {
x = abs(x);
if (nums[x - 1] > 0) nums[x - 1] *= -1;
}
vector<int> res;
for (int i = 0; i < nums.size(); i ++ )
if (nums[i] > 0)
res.push_back(i + 1);
return res;
}
};
461. 汉明距离
class Solution {
public:
int hammingDistance(int x, int y) {
int res = 0;
while (x || y) {
res += (x & 1) ^ (y & 1);
x >>= 1, y >>= 1;
}
return res;
}
};
494. 目标和
给你一个整数数组
n
u
m
s
nums
nums和一个整数
t
a
r
g
e
t
target
target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，
n
u
m
s
=
[
2
,
1
]
nums=[2,1]
nums=[2,1]，可以在2之前添加 ‘+’ ，在1之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于
t
a
r
g
e
t
target
target的不同表达式的数目。
class Solution {
public:
int findTargetSumWays(vector<int>& a, int S) {
if (S < -1000 || S > 1000) return 0;
int n = a.size(), Offset = 1000;
vector<vector<int>> f(n + 1, vector<int>(2001));
f[0][Offset] = 1;
for (int i = 1; i <= n; i ++ )
for (int j = -1000; j <= 1000; j ++ ) {
if (j - a[i - 1] >= -1000)
f[i][j + Offset] += f[i - 1][j - a[i - 1] + Offset];
if (j + a[i - 1] <= 1000)
f[i][j + Offset] += f[i - 1][j + a[i - 1] + Offset];
}
return f[n][S + Offset];
}
};
538. 把二叉搜索树转换为累加树
class Solution {
public:
int sum = 0;
TreeNode* convertBST(TreeNode* root) {
dfs(root);
return root;
}
void dfs(TreeNode* root) {
if (!root) return;
dfs(root->right);
int x = root->val;
root->val += sum;
sum += x;
dfs(root->left);
}
};
543. 二叉树的直径
class Solution {
public:
int ans = 0;
int diameterOfBinaryTree(TreeNode* root) {
dfs(root);
return ans;
}
int dfs(TreeNode* root) {
if (!root) return 0;
int left = dfs(root->left), right = dfs(root->right);
ans = max(ans, left + right);
return max(left, right) + 1;
}
};
560. 和为 K K K的子数组
给你一个整数数组 n u m s nums nums和一个整数 k k k，请你统计并返回该数组中和为 k k k的连续子数组的个数 。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
vector<int> s(n + 1);
for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + nums[i - 1];
unordered_map<int, int> hash;
hash[0] = 1;
int res = 0;
for (int i = 1; i <= n; i ++ ) {
res += hash[s[i] - k];
hash[s[i]] ++ ;
}
return res;
}
};
581. 最短无序连续子数组
给你一个整数数组
n
u
m
s
nums
nums，你需要找出一个连续子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的最短子数组，并输出它的长度。
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l + 1 < nums.size() && nums[l + 1] >= nums[l]) l ++ ;
if (l == r) return 0;
while (r - 1 >= 0 && nums[r - 1] <= nums[r]) r -- ;
for (int i = l + 1; i < nums.size(); i ++ )
while (l >= 0 && nums[l] > nums[i])
l -- ;
for (int i = r - 1; i >= 0; i -- )
while (r < nums.size() && nums[r] < nums[i])
r ++ ;
return r - l - 1;
}
};
617. 合并二叉树
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (t2) swap(t1, t2); // 可以保证t1一定不为空
if (!t1) return NULL;
if (t2) t1->val += t2->val;
t1->left = mergeTrees(t1->left, t2 ? t2->left : NULL);
t1->right = mergeTrees(t1->right, t2 ? t2->right : NULL);
return t1;
}
};
621. 任务调度器
给你一个用字符数组
t
a
s
k
s
tasks
tasks表示的CPU需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在1个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。
然而，两个相同种类的任务之间必须有长度为整数
n
n
n的冷却时间，因此至少有连续
n
n
n个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的 最短时间 。
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
unordered_map<char, int> hash;
for (auto c: tasks) hash[c] ++ ;
int maxc = 0, cnt = 0;
for (auto [k, v]: hash) maxc = max(maxc, v);
for (auto [k, v]: hash)
if (maxc == v)
cnt ++ ;
return max((int)tasks.size(), (maxc - 1) * (n + 1) + cnt);
}
};
647. 回文子串
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。文章来源：https://www.toymoban.com/news/detail-677605.html
class Solution {
public:
int countSubstrings(string s) {
int res = 0;
for (int i = 0; i < s.size(); i ++ ) {
// 枚举长度为奇数的情况
for (int j = i, k = i; j >= 0 && k < s.size(); j --, k ++ ) {
if (s[j] != s[k]) break;
res ++ ;
}
// 偶数情况
for (int j = i, k = i + 1; j >= 0 && k < s.size(); j --, k ++ ) {
if (s[j] != s[k]) break;
res ++ ;
}
}
return res;
}
};
739. 每日温度
给定一个整数数组 t e m p e r a t u r e s temperatures temperatures，表示每天的温度，返回一个数组 a n s w e r answer answer，其中 a n s w e r i answer_i answeri是指对于第 i i i天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。文章来源地址https://www.toymoban.com/news/detail-677605.html
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
stack<int> stk;
vector<int> res(T.size());
for (int i = T.size() - 1; i >= 0; i -- ) {
while (stk.size() && T[i] >= T[stk.top()]) stk.pop();
if (stk.size()) res[i] = stk.top() - i;
stk.push(i);
}
return res;
}
};
到了这里，关于Leetcode hot100题 个人整理版的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
