0942 added.

liuyubobobo · liuyubobobo · commit f732b24c36c6 · 2018-11-17T22:28:57.000-08:00
diff --git a/0942-DI-String-Match/cpp-0942/CMakeLists.txt b/0942-DI-String-Match/cpp-0942/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.12)
+project(C)
+
+set(CMAKE_CXX_STANDARD 11)
+
+add_executable(C main2.cpp)
diff --git a/0942-DI-String-Match/cpp-0942/main.cpp b/0942-DI-String-Match/cpp-0942/main.cpp
@@ -0,0 +1,53 @@
+/// Source : https://leetcode.com/problems/di-string-match/
+/// Author : liuyubobobo
+/// Time   : 2018-11-17
+
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+
+/// Generating the result from 0
+/// Adding the offset at last
+///
+/// Time Complexity: O(n)
+/// Space Complexity: O(1)
+class Solution {
+public:
+    vector<int> diStringMatch(string S) {
+
+        int n = S.size();
+        vector<int> res(n + 1, 0);
+
+        int minv = 0, maxv = 0;
+        for(int i = 0; i < S.size(); i ++){
+            int x;
+            if(S[i] == 'I')
+                x = ++maxv;
+            else
+                x = --minv;
+
+            res[i + 1] = x;
+        }
+
+        for(int& e: res)
+            e += -minv;
+        return res;
+    }
+};
+
+
+void print_vec(const vector<int>& vec){
+    for(int e: vec)
+        cout << e << " ";
+    cout << endl;
+}
+
+int main() {
+
+    string S1 = "IDID";
+    print_vec(Solution().diStringMatch(S1));
+
+    return 0;
+}
diff --git a/0942-DI-String-Match/cpp-0942/main2.cpp b/0942-DI-String-Match/cpp-0942/main2.cpp
@@ -0,0 +1,50 @@
+/// Source : https://leetcode.com/problems/di-string-match/
+/// Author : liuyubobobo
+/// Time   : 2018-11-17
+
+#include <iostream>
+#include <vector>
+#include <cassert>
+
+using namespace std;
+
+
+/// Generating the result from min value 0 and max value n - 1
+///
+/// Time Complexity: O(n)
+/// Space Complexity: O(1)
+class Solution {
+public:
+    vector<int> diStringMatch(string S) {
+
+        int n = S.size();
+        vector<int> res(n + 1, 0);
+
+        int l = 0, h = n;
+        for(int i = 0; i < S.size(); i ++){
+            if(S[i] == 'I')
+                res[i] = l ++;
+            else
+                res[i] = h --;
+        }
+
+        assert(l == h);
+        res.back() = l;
+        return res;
+    }
+};
+
+
+void print_vec(const vector<int>& vec){
+    for(int e: vec)
+        cout << e << " ";
+    cout << endl;
+}
+
+int main() {
+
+    string S1 = "IDID";
+    print_vec(Solution().diStringMatch(S1));
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -597,4 +597,5 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 939 | [Minimum Area Rectangle](https://leetcode.com/problems/minimum-area-rectangle/) | [solution](https://leetcode.com/problems/minimum-area-rectangle/solution/) | [C++](0939-Minimum-Area-Rectangle/cpp-0939/) | | |
 | 940 | [Distinct Subsequences II](https://leetcode.com/problems/distinct-subsequences-ii/) | [solution](https://leetcode.com/problems/distinct-subsequences-ii/solution/) | [C++](0940-Distinct-Subsequences-II/cpp-0940/) | | |
 | 941 | [Valid Mountain Array](https://leetcode.com/problems/valid-mountain-array/) | [solution](https://leetcode.com/problems/valid-mountain-array/solution/) | [C++](0941-Valid-Mountain-Array/cpp-0941/) | | |
+| 942 | [DI String Match](https://leetcode.com/problems/di-string-match/) | [solution](https://leetcode.com/problems/di-string-match/solution/) | [C++](0942-DI-String-Match/cpp-0942/) | | |
 | | | | | | |
