LeetCode刷题笔记

LeetCode 53 Maximum Subarray

1.O(n)

class Solution {public:    int maxSubArray(vector<int>& nums) {        int n=nums.size();        int max=-2147483648;        int si=0;//0...i元素和        int sj=0;//0..j元素和        int minsi=0;        for(int j=0;j<n;j++)        {            sj+=nums[j];            if(si<minsi)                minsi=si;            if(sj-minsi>max)//i..j元素和最大值                max=sj-minsi;            si+=nums[j];              }        return max;            }

};

2.贪心算法  O（n）

class Solution { public:     int maxSubArray(vector<int>& nums) {         int n=nums.size();         int max=-2147483648;         int sum=0;         for(int i=0;i<n;i++)         {             sum+=nums[i];             if(sum>max)                 max=sum;             if(sum<0)                 sum=0;         }         return max;     } };

LeetCode 128.   Longest Consecutive Sequence

1.O(n) 哈希表实现

class Solution {public:    int longestConsecutive(vector<int>& nums) {        if(nums.size()<=0)            return nums.size();        unordered_set<int> hash(nums.begin(),nums.end());        int res=1;        for(int n:nums)        {            if(hash.find(n)==hash.end())//哈希表查找                continue;            hash.erase(n);//找到后删除该元素            int prev=n-1,next=n+1;            while(hash.find(prev)!=hash.end())                hash.erase(prev--);            while(hash.find(next)!=hash.end())                hash.erase(next++);            res=max(res,next-prev-1);        }        return res;            }};

LeetCode 152.   Maximum Product Subarray

1. 双重循环 O(n^2）

class Solution {public:    int maxProduct(vector<int>& nums) {        int n=nums.size();        int max=-2147483648;                 for(int start=0;start<n;start++)        {            int product=1;            for(int end=start+1;end<=n;end++)            {                product*=nums[end-1];                if(product>max)                    max=product;            }                  }                     return max;            }};

2. O(n) 算法

class Solution {public:    int maxProduct(vector<int>& nums) {        int n=nums.size();        int product=nums[0];        int rmin,rmax;//保存当前最大值和最小值        rmin=product;        rmax=product;        for(int i=1;i<n;i++)        {            if(nums[i]<0)                swap(rmin,rmax);//若当前项为负值，则交换当前最大值和最小值            rmin=min(nums[i],rmin*nums[i]);            rmax=max(nums[i],rmax*nums[i]);            product=max(rmax,product);        }        return product;    }

};

LeetCode 155 Min Stack

class MinStack {private:    std::stack<int> stack;//正常的操作    std::stack<int> minstack;//维护最小值    public:    /** initialize your data structure here. */       MinStack() {                  }        void push(int x) {

        stack.push(x);

        if(minstack.empty()||(!minstack.empty()&&x<=minstack.top()))//只有小于顶部元素的值才压栈            minstack.push(x);    }        void pop() {        if(!stack.empty())        {            if(stack.top()==minstack.top())//只有在最小值栈顶端的元素才出栈                minstack.pop();            stack.pop();               }            }        int top() {        if(!stack.empty())            return stack.top();            }        int getMin() {        if(!minstack.empty())            return minstack.top();            }

};

LeetCode 394 Decode String

class Solution {public:    string decodeString(string s) {        stack<string> chars;//存字符串        stack<int> nums;//存数字        string res;        int num = 0;        for(char c : s) {            if(isdigit(c)) {                num = num*10 + (c-'0');                                          }            else if(isalpha(c)) {                res.push_back(c);                            }            else if(c == '[') {                chars.push(res);                nums.push(num);                res = "";                num = 0;            }            else if(c == ']') {                string tmp = res;//存开始的字符                for(int i = 0; i < nums.top()-1; ++i) {                    res += tmp;                }                res = chars.top() + res;//和之前的结果相连                chars.pop(); nums.pop();            }        }        return res;     }};