add 1718

fishercoder1534 · fishercoder1534 · commit b98de6c56743 · 2021-01-09T12:06:15.000-08:00
diff --git a/README.md b/README.md
@@ -8,6 +8,7 @@ _If you like this project, please leave me a star._ &#9733;
 
 |  #  |      Title     |   Solutions   | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|--------|-------------|-------------
+|1718|[Construct the Lexicographically Largest Valid Sequence](https://leetcode.com/problems/construct-the-lexicographically-largest-valid-sequence/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1718.java) ||Medium|Backtracking, Recursion|
 |1716|[Calculate Money in Leetcode Bank](https://leetcode.com/problems/calculate-money-in-leetcode-bank/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1716.java) ||Easy|Math, Greedy|
 |1711|[Count Good Meals](https://leetcode.com/problems/count-good-meals/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1711.java) ||Medium|Array, HashTable, Two Pointers|
 |1710|[Maximum Units on a Truck](https://leetcode.com/problems/maximum-units-on-a-truck/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1710.java) ||Easy|Greedy, Sort|
diff --git a/src/main/java/com/fishercoder/solutions/_1718.java b/src/main/java/com/fishercoder/solutions/_1718.java
@@ -0,0 +1,43 @@
+package com.fishercoder.solutions;
+
+public class _1718 {
+    public static class Solution1 {
+        public int[] constructDistancedSequence(int n) {
+            int[] result = new int[n * 2 - 1];
+            boolean[] visited = new boolean[n + 1];
+            backtracking(0, result, visited, n);
+            return result;
+        }
+
+        private boolean backtracking(int index, int[] result, boolean[] visited, int n) {
+            if (index == result.length) {
+                return true;
+            }
+            if (result[index] != 0) {
+                return backtracking(index + 1, result, visited, n);
+            } else {
+                for (int i = n; i > 0; i--) {
+                    if (visited[i]) {
+                        continue;
+                    }
+                    visited[i] = true;
+                    result[index] = i;
+                    if (i == 1) {
+                        if (backtracking(index + 1, result, visited, n)) {
+                            return true;
+                        }
+                    } else if (index + i < result.length && result[index + i] == 0) {
+                        result[i + index] = i;
+                        if (backtracking(index + 1, result, visited, n)) {
+                            return true;
+                        }
+                        result[index + i] = 0;
+                    }
+                    result[index] = 0;
+                    visited[i] = false;
+                }
+            }
+            return false;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1718Test.java b/src/test/java/com/fishercoder/_1718Test.java
@@ -0,0 +1,22 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1718;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertArrayEquals;
+
+public class _1718Test {
+    private static _1718.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1718.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        assertArrayEquals(new int[]{3, 1, 2, 3, 2}, solution1.constructDistancedSequence(3));
+    }
+
+}
