New Problem Solution - "1718. Construct the Lexicographically Largest Valid Sequence"

haoel · haoel · commit e836fa7db966 · 2021-04-24T17:40:52.000+08:00
diff --git a/README.md b/README.md
@@ -84,6 +84,7 @@ LeetCode
 |1733|[Minimum Number of People to Teach](https://leetcode.com/problems/minimum-number-of-people-to-teach/) | [C++](./algorithms/cpp/minimumNumberOfPeopleToTeach/MinimumNumberOfPeopleToTeach.cpp)|Medium|
 |1732|[Find the Highest Altitude](https://leetcode.com/problems/find-the-highest-altitude/) | [C++](./algorithms/cpp/findTheHighestAltitude/FindTheHighestAltitude.cpp)|Easy|
 |1725|[Number Of Rectangles That Can Form The Largest Square](https://leetcode.com/problems/number-of-rectangles-that-can-form-the-largest-square/) | [C++](./algorithms/cpp/numberOfRectanglesThatCanFormTheLargestSquare/NumberOfRectanglesThatCanFormTheLargestSquare.cpp)|Easy|
+|1718|[Construct the Lexicographically Largest Valid Sequence](https://leetcode.com/problems/construct-the-lexicographically-largest-valid-sequence/) | [C++](./algorithms/cpp/constructTheLexicographicallyLargestValidSequence/ConstructTheLexicographicallyLargestValidSequence.cpp)|Medium|
 |1717|[Maximum Score From Removing Substrings](https://leetcode.com/problems/maximum-score-from-removing-substrings/) | [C++](./algorithms/cpp/maximumScoreFromRemovingSubstrings/MaximumScoreFromRemovingSubstrings.cpp)|Medium|
 |1716|[Calculate Money in Leetcode Bank](https://leetcode.com/problems/calculate-money-in-leetcode-bank/) | [C++](./algorithms/cpp/calculateMoneyInLeetcodeBank/CalculateMoneyInLeetcodeBank.cpp)|Easy|
 |1711|[Count Good Meals](https://leetcode.com/problems/count-good-meals/) | [C++](./algorithms/cpp/countGoodMeals/CountGoodMeals.cpp)|Medium|
diff --git a/algorithms/cpp/constructTheLexicographicallyLargestValidSequence/ConstructTheLexicographicallyLargestValidSequence.cpp b/algorithms/cpp/constructTheLexicographicallyLargestValidSequence/ConstructTheLexicographicallyLargestValidSequence.cpp
@@ -0,0 +1,93 @@
+// Source : https://leetcode.com/problems/construct-the-lexicographically-largest-valid-sequence/
+// Author : Hao Chen
+// Date   : 2021-04-24
+
+/***************************************************************************************************** 
+ *
+ * Given an integer n, find a sequence that satisfies all of the following:
+ * 
+ * 	The integer 1 occurs once in the sequence.
+ * 	Each integer between 2 and n occurs twice in the sequence.
+ * 	For every integer i between 2 and n, the distance between the two occurrences of i is 
+ * exactly i.
+ * 
+ * The distance between two numbers on the sequence, a[i] and a[j], is the absolute difference of 
+ * their indices, |j - i|.
+ * 
+ * Return the lexicographically largest sequence. It is guaranteed that under the given constraints, 
+ * there is always a solution. 
+ * 
+ * A sequence a is lexicographically larger than a sequence b (of the same length) if in the first 
+ * position where a and b differ, sequence a has a number greater than the corresponding number in b. 
+ * For example, [0,1,9,0] is lexicographically larger than [0,1,5,6] because the first position they 
+ * differ is at the third number, and 9 is greater than 5.
+ * 
+ * Example 1:
+ * 
+ * Input: n = 3
+ * Output: [3,1,2,3,2]
+ * Explanation: [2,3,2,1,3] is also a valid sequence, but [3,1,2,3,2] is the lexicographically largest 
+ * valid sequence.
+ * 
+ * Example 2:
+ * 
+ * Input: n = 5
+ * Output: [5,3,1,4,3,5,2,4,2]
+ * 
+ * Constraints:
+ * 
+ * 	1 <= n <= 20
+ ******************************************************************************************************/
+
+class Solution {
+private:
+    void print(vector<int>& v) {
+        cout << "[" ;
+        for(int i=0; i<v.size()-1; i++){
+            cout << v[i] << ",";
+        }
+        cout << v[v.size()-1] << "]" << endl;
+    }
+public:
+    vector<int> constructDistancedSequence(int n) {
+        vector<int> result(2*n-1, 0);
+        vector<bool> available(n+1, true); // an array remember which num hasn't been chosen.
+        available[0] = false;
+        
+        dfs(available, result, 0, n);
+        
+        return result;
+    }
+    
+    bool dfs(vector<bool>& available, vector<int>& result, int pos, int cnt){
+        //the `cnt` means how many number has been processed.
+        if (cnt == 0) return true;
+        
+        //start from the bigger number.
+        int n = 0;
+        for(int i = available.size()-1; i > 0; i--){
+            // if the number has already been chosen, skip to next one.
+            if (!available[i]) continue;
+            //if the number cannot be put into the array, skip to next one
+            if ( i > 1 && pos + i >= result.size()) continue;
+            if ( i > 1 && (result[pos] != 0 || result[pos+i] != 0)) continue;
+            
+            // choose the current number `i`
+            available[i] = false;
+            result[pos] = i;
+            if (i > 1) result[pos+i] = i;
+            int next_pos = pos;
+            while( next_pos < result.size() && result[next_pos]!=0) next_pos++;
+            
+            //print(result);
+            if (dfs(available, result, next_pos, cnt-1)) return true; 
+            
+            // if failed to find the answer. roll back.
+            available[i] = true;
+            result[pos] = 0;
+            if (i > 1) result[pos+i] = 0;
+        }
+        
+        return false;
+    }
+};
