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.