update lc

lzyrapx · Aug 9, 2020 · 4468177 · 4468177
1 parent e75271d
commit 4468177
Show file tree

Hide file tree

Showing 3 changed files with 112 additions and 0 deletions.
diff --git a/LeetCode/Medium/0777.cpp b/LeetCode/Medium/0777.cpp
@@ -0,0 +1,42 @@
+class Solution {
+public:
+    // L 只能左移，R 只能右移, 并且只能和 X 进行交换
+    bool canTransform(string start, string end) {
+        int len = start.size();
+        if(start.size() != end.size()) {
+            return false;
+        }
+        int i = 0;
+        int j = 0;
+        while(true){
+            while(i < len && start[i] == 'X') {
+                i++;
+            }
+            while(j < len && end[j] == 'X') {
+                j++;
+            }
+            if(i == len || j == len) {
+                if(i == len && j == len) {
+                    return true;
+                }
+                return false;
+            }
+            if(start[i] != end[j]) {
+                return false;
+            }
+            else {
+                // start 中 L 左边的 X 比 end 中 L 左边的 X 还少， 因为 L 左边的 X 只会减少
+                if(start[i] == 'L' && i < j) {
+                    return false;
+                }
+                // start 中 R 左边的 X 比 start 中 R 左边的 X 还多，因为 R 左边的 X 只会增多
+                if(start[i] == 'R' && i > j) {
+                    return false;
+                }
+            }
+            i++;
+            j++;
+        }
+        return true;
+    }
+};
diff --git a/LeetCode/Medium/1238.cpp b/LeetCode/Medium/1238.cpp
@@ -0,0 +1,23 @@
+class Solution {
+public:
+    // 按题目要求构造一个数组，满足格雷码的性质
+    vector<int> circularPermutation(int n, int start) {
+        vector<int>ans;
+        ans.push_back(start);
+        for(int i = 0; i < n; i++) {
+            for(int j = ans.size() - 1; j >= 0; --j) {
+                ans.push_back(ans[j] ^ (1 << i));
+            }
+        }
+        return ans;
+    }
+    /*
+    思路：
+    比如n=3, start=2的情况：
+    首先将2(010)加入数组
+    将010最后一位翻转得到3(011)，此时数组为010,011
+    将010与011的第二位翻转并逆序加入，得到010,011,001,000
+    同上，得到010,011,001,000,100,101,111,110
+
+    */
+};
diff --git a/LeetCode/Medium/1253.cpp b/LeetCode/Medium/1253.cpp
@@ -0,0 +1,47 @@
+class Solution {
+public:
+    // 构造满足以下条件的 2 * n 的0-1矩阵,构造不了就输出空矩阵
+    // 1. 第一行的和为 upper
+    // 2. 第二行的和为 lower
+    // 3. 第 i 列的和为 colsum[i]
+    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
+        vector<vector<int>>ans(2, vector<int>(colsum.size(), 0));
+        int colSum = 0;
+        for(int i = 0; i < colsum.size(); i++) {
+            colSum += colsum[i];
+        }
+        if(colSum != upper + lower) {
+            return {};
+        }
+        // 处理colsum[i]==2的情况
+        int a = 0; // 第一行
+        int b = 0; // 第二行
+        for(int i = 0; i < colsum.size(); i++) {
+            if(colsum[i] == 2) {
+                ans[0][i] = 1;
+                ans[1][i] = 1;
+                a++;
+                b++;
+            }
+        }
+        if(a > upper || b > lower) {
+            return {};
+        }
+        for(int i = 0 ; i < colsum.size(); i++) {
+            if(colsum[i] == 1) {
+                if(a < upper) {
+                    ans[0][i] = 1;
+                    a++;
+                }
+                else if(b < lower) {
+                    ans[1][i] = 1;
+                    b++;
+                }
+                else {
+                    return {};
+                }
+            }
+        }
+        return ans;
+    }
+};