5 problems solved.

lintcoder · lintcoder · commit 081a0422ca19 · 2020-01-04T19:22:47.000+08:00
diff --git a/src/155.cpp b/src/155.cpp
@@ -0,0 +1,51 @@
+class MinStack {
+public:
+    /** initialize your data structure here. */
+    MinStack() {
+        len = 0;
+    }
+    
+    void push(int x) {
+        st.push_back(x);
+        ++len;
+        if (len == 1)
+            minval = x;
+        else
+            minval = x < minval ? x : minval;
+    }
+    
+    void pop() {
+        if (len > 0)
+        {
+            --len;
+            st.erase(--st.end());
+            if (len > 0)
+            {
+                auto lim = st.end();
+                int t = *st.begin();
+                for (auto iter = st.begin(); iter != lim; ++iter)
+                    if (*iter < t)
+                        t = *iter;
+                minval = t;
+            }
+        }
+    }
+    
+    int top() {
+        if (len > 0)
+            return st.back();
+        else
+            return 0;
+    }
+    
+    int getMin() {
+        if (len > 0)
+            return minval;
+        else
+            return 0;
+    }
+    
+    list<int> st;
+    int minval;
+    int len;
+};
diff --git a/src/31.cpp b/src/31.cpp
@@ -0,0 +1,23 @@
+void nextPermutation(vector<int>& nums) {
+        int len = nums.size();
+        if (len <= 1)
+        	return;
+        if (len == 2)
+        	swap(nums[0], nums[1]);
+        else
+        {
+        	int i = len - 1;
+        	while (i > 0 && nums[i-1] >= nums[i])
+        		--i;
+        	if (i == 0)
+        		reverse(nums.begin(), nums.end());
+        	else
+        	{
+        		int j = len - 1;
+        		while (j >= i && nums[j] <= nums[i-1])
+        			--j;
+        		swap(nums[i-1], nums[j]);
+        		reverse(nums.begin()+i, nums.end());
+        	}
+        }
+    }
diff --git a/src/46.cpp b/src/46.cpp
@@ -0,0 +1,17 @@
+vector<vector<int>> permute(vector<int>& nums) {
+        sort(nums.begin(), nums.end());
+        int len = nums.size();
+        long long total = 1;
+        for (int i = len; i >= 1; --i)
+            total *= i;
+        vector<vector<int>> res(total, vector<int>(len, 0));
+        res[0].assign(nums.begin(), nums.end());
+        
+        int i = 1;
+        while (next_permutation(nums.begin(), nums.end()))
+        {
+            res[i++].assign(nums.begin(), nums.end());
+        }
+        
+        return move(res);
+    }
diff --git a/src/53.cpp b/src/53.cpp
@@ -0,0 +1,36 @@
+int maxSubArray(vector<int>& nums) {
+        int len = nums.size();
+        if (len == 0)
+            return 0;
+        if (len == 1)
+            return nums[0];
+        
+        int i = 1;
+        int maxsum = nums[0];
+        int tmp = maxsum;
+        while (i < len)
+        {
+            if (tmp <= 0)
+            {
+                if (nums[i] >= tmp)
+                {
+                    tmp = nums[i];
+                    if (tmp > maxsum)
+                        maxsum = tmp;
+                }    
+                ++i;
+            }
+            else
+            {
+                tmp += nums[i];
+                if (tmp > maxsum)
+                    maxsum = tmp;
+                ++i;
+            }
+        }
+        
+        if (tmp > maxsum)
+            maxsum = tmp;
+        
+        return maxsum;
+    }
diff --git a/src/56.cpp b/src/56.cpp
@@ -0,0 +1,33 @@
+vector<vector<int>> merge(vector<vector<int>>& intervals) {
+        int len = intervals.size();
+        if (len <= 1)
+            return move(intervals);
+        
+        auto cmp = [](vector<int>& a, vector<int>& b) {
+            return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]);
+        };
+        
+        sort(intervals.begin(), intervals.end(), cmp);
+        
+        vector<vector<int>> res;
+        int b = intervals[0][0], e = intervals[0][1];
+        int i = 1;
+        while (i < len)
+        {
+            if (intervals[i][0] > e)
+            {
+                res.push_back({b, e});
+                b = intervals[i][0];
+                e = intervals[i][1];
+                ++i;
+            }
+            else
+            {
+                e = intervals[i][1] > e ? intervals[i][1] : e;
+                ++i;
+            }
+        }
+        res.push_back({b, e});
+        
+        return move(res);
+    }
