15. 三数之和
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<int> vec;
vector<vector<int>> ans;
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size();i++)
{
if(i>0&&nums[i]==nums[i-1]) continue;
int l=i+1,r=nums.size()-1;
while(l<r)
{
int sum=nums[i]+nums[l]+nums[r];
if(sum==0)
{
ans.push_back({nums[i],nums[l],nums[r]});
while(l<r&&nums[l]==nums[l+1]) l++;
while(l<r&&nums[r]==nums[r-1]) r--;
l++;
r--;
}
else if(sum>0) r--;
else l++;
}
}
return ans;
}
};
53. 最大子数组和
dp，空间优化
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int pre=nums[0];
int ans=nums[0];
for(int i=1;i<nums.size();i++)
{
pre=max(pre+nums[i],nums[i]);
ans=max(ans,pre);
}
return ans;
}
};
54. 螺旋矩阵
class Solution {
public:
bool v[15][15];
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int n=matrix.size(),m=matrix[0].size();
int dx[]={0,1,0,-1},dy[]={1,0,-1,0}; //方向数组，向下x正，右y正
vector<int> vec;
v[0][0]=true; //从0,0开始
for(int x=0,y=0,d=0,k=1;k<=m*n;k++)
{
vec.push_back(matrix[x][y]);
int a=x+dx[d],b=y+dy[d];
if(a<0||a>=n||b<0||b>=m||v[a][b]) //出界或访问过则更正位置
{
d=(d+1)%4;
a=x+dx[d];
b=y+dy[d];
}
if(a>=0&&b>=0) v[a][b]=true; //防止下标溢出
x=a;
y=b;
}
return vec;
}
};
59. 螺旋矩阵 II
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>>vec(n,vector<int>(n));
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
for(int x=0,y=0,k=1,d=0;k<=n*n;k++)
{
vec[x][y]=k;
int a=x+dx[d];
int b=y+dy[d];
if(a<0||a>=n||b<0||b>=n||vec[a][b])
{
d=(d+1)%4;
a=x+dx[d];
b=y+dy[d];
}
x=a;
y=b;
}
return vec;
}
};
148. 排序链表
/**
* 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* get(ListNode* node)
{
while(node->next!=nullptr) node=node->next;
return node;
}
ListNode* sortList(ListNode* head) {
if(head==nullptr||head->next==nullptr) return head;
auto l=new ListNode(-1);
auto m=new ListNode(-1);
auto r=new ListNode(-1);
auto ltail=l,mtail=m,rtail=r;
int x=head->val;
while(head!=nullptr)
{
if(head->val<x)
{
ltail->next=head;
ltail=ltail->next;
}
else if(head->val>x)
{
rtail->next=head;
rtail=rtail->next;
}
else
{
mtail->next=head;
mtail=mtail->next;
}
head=head->next;
}
ltail->next=rtail->next=mtail->next=nullptr;
l->next=sortList(l->next);
r->next=sortList(r->next);
get(l)->next=m->next;
get(l)->next=r->next;
return l->next;
}
};
160. 相交链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
auto a=headA,b=headB;
while(a!=b)
{
if(a==nullptr) a=headB;
else a=a->next;
if(b==nullptr) b=headA;
else b=b->next;
}
return a;
}
};
最大公约数
求a和b的最大公约数
int gcd(int a,int b)
{
if(b==0) return a;
return gcd(b,a%b);
}
##快速幂
给定 n 组 ai,bi,pi，对于每组数据，求出 a*b mod p 的值。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含三个整数 ai,bi,pi。
输出格式
对于每组数据，输出一个结果，表示 abiimodpi 的值。
每个结果占一行。
数据范围
1≤n≤100000,
1≤ai,bi,pi≤2×109
输入样例：
2
3 2 5
4 3 9
输出样例：
4
1
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int f(int a,int k,int p)
{
long long ans=1,aa=a;
while(k)
{
if(k&1) ans=ans*aa%p;
k>>=1;
aa=aa*aa%p;
}
return ans;
}
int main()
{
int n;
cin>>n;
while (n -- )
{
int a,b,c;
cin>>a>>b>>c;
cout<<f(a,b,c)<<endl;
}
}
5. 最长回文子串
中心拓展法
class Solution {
public:
string longestPalindrome(string s) {
int len=1,maxs=0,maxl=0,l,r;
for(int i=0;i<s.size();i++)
{
l=i-1,r=i+1;
while(l>=0&&s[i]==s[l])
{
l--;
len++;
}
while(r<s.size()&&s[i]==s[r])
{
r++;
len++;
}
while(l>=0&&r<s.size()&&s[r]==s[l])
{
r++;
l--;
len+=2;
}
if(len>maxl)
{
maxl=len;
maxs=l;
}
len=1;
}
return s.substr(maxs+1,maxl);
}
};
415. 字符串相加
class Solution {
public:
string add(vector<int>&a,vector<int>& b)
{
string s;
int t=0;
for(int i=0;i<a.size()||i<b.size();i++)
{
if(i<a.size()) t+=a[i];
if(i<b.size()) t+=b[i];
s.insert(s.begin(), t%10+'0');
t/=10;
}
if(t) s.insert(s.begin(), '1');
return s;
}
string addStrings(string num1, string num2) {
string s;
vector<int> a,b;
//倒序
for(int i=num1.size()-1;i>=0;i--) a.push_back(num1[i]-'0');
for(int i=num2.size()-1;i>=0;i--) b.push_back(num2[i]-'0');
s=add(a,b);
return s;
}
};
92. 反转链表 II
头插法
/**
* 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* reverseBetween(ListNode* head, int left, int right) {
ListNode* dummy=new ListNode(-1);
dummy->next=head;
auto cur=head;
ListNode* pre=dummy;
for(int i=0;i<left-1;i++)
{
cur=cur->next;
pre=pre->next;
}
for(int i=0;i<right-left;i++)
{
ListNode* t=cur->next;
cur->next=t->next;
t->next=pre->next;
pre->next=t;
}
return dummy->next;
}
};
300. 最长递增子序列
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int dp[10000];
dp[0]=1;
int ans=1;
for(int i=1;i<nums.size();i++)
{
dp[i]=1; //每个单独的元素为长度为1的子序列
for(int j=0;j<i;j++)
{
if(nums[j]<nums[i]) dp[i]=max(dp[j]+1,dp[i]);
ans=max(ans,dp[i]);
}
}
return ans;
}
};
31. 下一个排列
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int i;
for(i=nums.size()-1;i>0;i--) //从后往前找到第一个a[i-1]<a[i]，
{
if(nums[i-1]<nums[i]) break;
}
if(i==0) //找不到就翻转返回
{
reverse(nums.begin(),nums.end());
return ;
}
int j;
for(j=nums.size()-1;j>=0;j--)
{
if(nums[i-1]<nums[j]) //从后往前找到第一个a[i-1]<a[j],并交换
{
swap(nums[i-1],nums[j]);
break;
}
}
reverse(nums.begin()+i, nums.end()); //从i开始翻转
}
};
129. 求根节点到叶节点数字之和
/**
* 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:
int sumNumbers(TreeNode* root) {
return dfs(root,0);
}
int dfs(TreeNode* root,int sum)
{
if(root==nullptr) return 0;
int s=sum*10+root->val;
if(root->left==nullptr&&root->right==nullptr) return s;
return dfs(root->left,s)+dfs(root->right,s);
}
};
108. 将有序数组转换为二叉搜索树
/**
* 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:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return f(nums,0,nums.size()-1);
}
TreeNode* f(vector<int>& nums,int l,int r)
{
if(l>r) return nullptr; //递归结束条件
int mid=l+((r-l)>>1);
auto root=new TreeNode(nums[mid]); //中间结点为根节点
root->left=f(nums,l,mid-1); //递归处理左右两边
root->right=f(nums,mid+1,r);
return root;
}
};
337. 打家劫舍 III
class Solution {
public:
int rob(TreeNode* root) {
return max(dfs(root)[0],dfs(root)[1]);
}
vector<int> dfs(TreeNode*root)
{
if(root==nullptr) return{0,0};
vector<int> left=dfs(root->left);
vector<int> right=dfs(root->right);
vector<int> dp(2);
dp[0]=max(left[0],left[1])+max(right[0],right[1]);
dp[1]=left[0]+right[0]+root->val;
return dp;
}
};
- 后序遍历 左右根
- dp[0]表示不投当前节点，dp[1]表示偷当前节点
- 如果偷当前节点，不能偷左右孩子，则dp[1]=left[0]+right[0]+root->val;
- 如果不偷当前节点，则偷不偷左右孩子都可以，取最大的，即dp[0]=max(left[0],left[1])+max(right[0],right[1]);
- 返回偷或者不偷的最大值
122. 买卖股票的最佳时机 II
dp版
class Solution {
public:
int maxProfit(vector<int>& prices) {
int dp[50000][2]; //0代表当前无股票，1代表当前有股票
dp[0][1]=-prices[0];
for(int i=1;i<prices.size();i++)
{
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
}
return dp[prices.size()-1][0]; //最后一定不持股（卖出）利润最大
}
};
dp优化版
class Solution {
public:
int maxProfit(vector<int>& prices) {
int dp0=0,dp1=-prices[0];
for(int i=1;i<prices.size();i++)
{
int tdp0=max(dp0,dp1+prices[i]);
int tdp1=max(dp1,dp0-prices[i]);
dp0=tdp0;
dp1=tdp1;
}
return dp0;
}
};
Q.E.D.