update medium

lzyrapx · Aug 8, 2020 · 24d2a3c · 24d2a3c
1 parent 6530963
commit 24d2a3c
Show file tree

Hide file tree

Showing 4 changed files with 93 additions and 0 deletions.
diff --git a/LeetCode/Medium/0386.cpp b/LeetCode/Medium/0386.cpp
@@ -0,0 +1,17 @@
+class Solution {
+public:
+    void dfs(vector<int>&ans, int cur, int n) {
+        if(cur > n) return;
+        ans.push_back(cur);
+        for(int i = 0; i <= 9; i++) {
+            dfs(ans, cur * 10 + i, n);
+        }
+    }
+    vector<int> lexicalOrder(int n) {
+        vector<int>ans;
+        for(int i = 1; i <= 9; i++) {
+            dfs(ans,i, n);
+        }
+        return ans;
+    }
+};
diff --git a/LeetCode/Medium/0388.py b/LeetCode/Medium/0388.py
@@ -0,0 +1,23 @@
+class Solution:
+    # 找最长的文件路径深度，输出最长路径长度
+    def lengthLongestPath(self, input: str) -> int:
+        stk = []
+        ans = 0
+        lines = input.split("\n")
+        for line in lines:
+            level = 0
+            for ch in line:
+                if ch == '\t':
+                    level += 1
+                else:
+                    break
+            line = line[level:]
+            while len(stk) > level:
+                stk.pop()
+            stk.append(line)
+            if line.find(".") != -1:
+                s = "/".join(stk)
+                ans = max(len(s), ans)
+        return ans
+
+
diff --git a/LeetCode/Medium/0738.cpp b/LeetCode/Medium/0738.cpp
@@ -0,0 +1,20 @@
+class Solution {
+public:
+    int monotoneIncreasingDigits(int N) {
+       if(N == 0){
+           return 0;
+       }
+        string num = to_string(N);
+        int id = num.size();
+        for(int i = num.size() - 1; i >= 1; --i) {
+            if(num[i] < num[i - 1]) { // 不符合
+                num[i - 1]--;
+                id = i;
+            }
+        }
+        for(int i = id; i < num.size(); i++){
+            num[i] = '9';
+        }
+        return stoi(num);
+    }
+};
diff --git a/LeetCode/Medium/0756.cpp b/LeetCode/Medium/0756.cpp
@@ -0,0 +1,33 @@
+class Solution {
+public:
+    // 问能不能构成以bottom为最后一层的树
+    unordered_map<string,vector<char>>mp;
+    bool pyramidTransition(string bottom, vector<string>& allowed) {
+        for(string str: allowed) {
+            mp[str.substr(0, 2)].push_back(str.back());
+        }
+        string upper = ""; // 上一层
+        // bottom 是当前层
+        return dfs(bottom, upper, 0);
+    }
+    bool dfs(string bottom, string upper, int pos) {
+        if(pos == bottom.size() - 1){
+            if(upper.size() == 1) { // 最顶层只有一个就说明可以构成
+                return true;
+            }
+            bottom = upper;
+            upper = "",
+            pos = 0;
+        }
+        vector<char>&ve = mp[bottom.substr(pos, 2)];
+        if(ve.empty()) {
+            return false;
+        }
+        for(int i = 0; i < ve.size(); i++){
+            if(dfs(bottom, upper + ve[i], pos + 1)) {
+                return true;
+            }
+        }
+        return false;
+    }
+};