头像

ShawnPei


访客:1148

离线:11小时前



题目描述

blablabla

样例

blablabla

算法1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return NULL;
        if (root==p || root==q) return root;
        auto left=lowestCommonAncestor(root->left,p,q);
        auto right=lowestCommonAncestor(root->right,p,q);
        if (left && right) return root;
        if (left) return left;
        return right;

    }
};



题目描述

blablabla

样例

blablabla

算法1

class Solution {
public:
    int strToInt(string str) {
        long long res=0;
        bool isneg=false;
        int i=0,j=str.size();
        while (i<j && str[i]==' ') i++;
        if (str[i]=='-') i++,isneg=true;
        else if (str[i]=='+') i++;
        else if (!(str[i]>='0' && str[i]<='9')) return 0;
        for (;i<j && str[i]>=0 && str[i]<='9';i++) {
            if (isneg) res=res*10-(str[i]-'0');
            else res=res*10+str[i]-'0';
        }
        if (res>INT_MAX) res=INT_MAX;
        else if (res<INT_MIN) res=INT_MIN;
        return res;
    }
};



题目描述

blablabla

样例

blablabla

算法1

将数组拆分为left和right两部分,left[i]=A[i-1]*left[i-1],right[i]=A[i+1]*right[i+1]
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> B(A.size());
        vector<int> left(A.size(),1);
        vector<int> right(A.size(),1);
        for (int i=1;i<A.size();i++) {
            left[i]=A[i-1]*left[i-1];
            // cout<<left[i]<<' ';
        }
        for (int i=A.size()-2;i>=0;i--) {
            right[i]=A[i+1]*right[i+1];
            // cout<<right[i]<<' ';
        }
        for (int i=0;i<A.size();i++) {
            B[i]=left[i]*right[i];
            // cout<<B[i]<<' ';
        }
        return B;
    }
};



题目描述

blablabla

样例

blablabla

算法1

class Solution {
public:
    int maxDiff(vector<int>& nums) {
        int n=nums.size();
        if (n==0) return 0;
        vector<vector<int> > f(n,vector<int>(2));
        for (int i=0;i<n;i++) {
            if (i-1==-1) {
                f[i][0]=0;
                f[i][1]=-nums[i];
                continue;
            }
            f[i][0]=max(f[i-1][0],f[i-1][1]+nums[i]);
            f[i][1]=max(f[i-1][1],-nums[i]);
        }
        return f[n-1][0];
    }
};



题目描述

blablabla

样例

blablabla

算法1

1.排序删除0
2.判重
3.末尾和第一个非零数之间相差不超过4
class Solution {
public:
    bool isContinuous( vector<int> nums ) {
        if (nums.empty()) return false;
        int k=0;
        sort(nums.begin(),nums.end());
        while (!nums[k]) k++;
        for (int i=k+1;i<nums.size();i++) {
            if (nums[i]==nums[i-1]) {
                return false;
            }
        }
        return nums.back()-nums[k]<=4;
    }
};



题目描述

blablabla

样例

blablabla

算法1

状态表示f(i,j)表示前i次,点数为j的方案数
状态转移:f(i,j)+=f(i-1,j-k),k表示当前前的点数,j表示总和
class Solution {
public:
    vector<int> numberOfDice(int n) {
        vector<vector<int> > f(n+1, vector<int>(6*n+1));
        f[0][0]=1;
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=6*i;j++) {
                for (int k=1;k<=min(j,6);k++) {
                    f[i][j]+=f[i-1][j-k];
                }
            }
        }
        vector<int> res;
        for (int i=n;i<=6*n;i++) res.push_back(f[n][i]);
        return res;
    }
};




题目描述

blablabla

样例

blablabla

算法1(单调队列)

利用单调队列维护一个单调递减的队列,队首元素为每个窗口的最大值
class Solution {
public:
    vector<int> maxInWindows(vector<int>& nums, int k) {
        int n=nums.size();
        vector<int> res;
        deque<int> q;
        for (int i=0;i<n;i++) {
            while (q.size() && q.front()<=i-k) q.pop_front();
            while (q.size() && nums[q.back()]<=nums[i]) q.pop_back();
            q.push_back(i);
            if (i>=k-1) res.push_back(nums[q.front()]);
        }
        return res;
    }
};



题目描述

blablabla

样例

blablabla

算法1

class Solution {
public:
    string leftRotateString(string str, int n) {
        reverse(str.begin(),str.begin()+n);
        reverse(str.begin()+n,str.end());
        reverse(str.begin(),str.end());
        return str;
    }
};



题目描述

blablabla

样例

blablabla

算法1(双指针)

利用双指针先对整个字符串翻转,然后,在对翻转后的字符串中的每个单词进行翻转
class Solution {
public:
    string reverseWords(string s) {
        for (int i=0,j=s.size()-1;i<j;i++,j--) swap(s[i],s[j]);
        for (int i=0;i<s.size();i++) {
            int j=i;
            while (j<s.size() && s[j]!=' ') j++;
            for (int a=i,b=j-1;a<b;a++,b--) swap(s[a],s[b]);
            i=j;
        }
        return s;
    }
};



题目描述

blablabla

样例

blablabla

算法1(双指针)

class Solution {
public:
    vector<vector<int> > findContinuousSequence(int sum) {
        vector<vector<int>> res;
        for (int i=1,j=1,s=1;i<sum;i++) {
            while (s<sum) s+=++j;
            if (s==sum && j-i+1>1) {
                vector<int> line;
                for (int k=i;k<=j;k++) line.push_back(k);
                res.push_back(line);
            }
            s-=i;
        }
        return res;
    }
};