leetcode-biweek-52

OneCodeMonkey · OneCodeMonkey · commit e2d924b624ab · 2021-05-16T21:10:28.000+08:00
diff --git a/contest/leetcode_biweek_52_problmes/leetcode_1859_Sorting_the_Sentence.java b/contest/leetcode_biweek_52_problmes/leetcode_1859_Sorting_the_Sentence.java
@@ -0,0 +1,22 @@
+// AC:
+// Runtime: 5 ms, faster than 100.00% of Java online submissions for Sorting the Sentence.
+// Memory Usage: 38.5 MB, less than 100.00% of Java online submissions for Sorting the Sentence.
+// Using tree map to sort key.
+// T:O(n), S:O(n), n = len(s)
+//
+class Solution {
+    public String sortSentence(String s) {
+        TreeMap<Integer, String> record = new TreeMap<>();
+        String[] sArr = s.split(" ");
+        for (String item: sArr) {
+            Integer index = Integer.parseInt(String.valueOf(item.charAt(item.length() - 1)));
+            record.put(index, item.substring(0, item.length() - 1));
+        }
+        StringBuilder ret = new StringBuilder();
+        for (Integer i: record.keySet()) {
+            ret.append(record.get(i));
+            ret.append(" ");
+        }
+        return ret.substring(0, ret.length() - 1);
+    }
+}
diff --git a/contest/leetcode_biweek_52_problmes/leetcode_1860_Incremental_Memory_Leak.java b/contest/leetcode_biweek_52_problmes/leetcode_1860_Incremental_Memory_Leak.java
@@ -0,0 +1,29 @@
+// AC:
+// Runtime: 8 ms, faster than 100.00% of Java online submissions for Incremental Memory Leak.
+// Memory Usage: 38.3 MB, less than 100.00% of Java online submissions for Incremental Memory Leak.
+// simulation... it seems that brute-force can pass. Any way I haven't thought out better solution...
+// complexity:  T: O(sqrt(max(m1, m2))), S: O(1)
+// 
+class Solution {
+    public int[] memLeak(int memory1, int memory2) {
+        int second = 1;
+        while (memory1 >= second || memory2 >= second) {
+            if (memory1 >= memory2) {
+                if (memory1 >= second) {
+                    memory1 -= second;
+                } else {
+                    break;
+                }
+            } else {
+                if (memory2 >= second) {
+                    memory2 -= second;
+                } else {
+                    break;
+                }
+            }
+            second++;
+        }
+        int[] ret = new int[]{second, memory1, memory2};
+        return ret;
+    }
+}
diff --git a/contest/leetcode_biweek_52_problmes/leetcode_1861_Rotating_the_Box.java b/contest/leetcode_biweek_52_problmes/leetcode_1861_Rotating_the_Box.java
@@ -0,0 +1,66 @@
+// AC:
+// Runtime: 2056 ms, faster than 50.00% of Java online submissions for Rotating the Box.
+// Memory Usage: 64.7 MB, less than 100.00% of Java online submissions for Rotating the Box.
+// my thought: using string split(obstacle), and combine every part to make stone fall down.
+// complexity: T:O(m * n), S:O(m * n)
+// 
+class Solution {
+    public char[][] rotateTheBox(char[][] box) {
+        int row = box.length, col = box[0].length;
+        char[][] ret = new char[col][row];
+        List<List<Character>> record = new LinkedList<>();
+        for (int i = 0; i < row; i++) {
+            // 逐行下落
+            List<Character> temp = new LinkedList<>();
+            StringBuilder tempStr = new StringBuilder();
+            for (int j = 0; j <= col - 1; j++) {
+                tempStr.append(box[i][j]);
+            }
+            tempStr.append("#");
+            String[] tempArr = tempStr.toString().split("\\*");
+            if (tempArr.length == 0) {
+                for (int t = 0; t < tempStr.length(); t++) {
+                    temp.add('*');
+                }
+            } else {
+                for (String part : tempArr) {
+                    if (part.isEmpty()) {
+                        temp.add('*');
+                        continue;
+                    }
+                    int countEmpty = 0, countStone = 0;
+                    for (char item : part.toCharArray()) {
+                        if (item == '#') {
+                            countStone++;
+                        }
+                        if (item == '.') {
+                            countEmpty++;
+                        }
+                    }
+                    for (int k = 0; k < countEmpty; k++) {
+                        temp.add('.');
+                    }
+                    for (int k = 0; k < countStone; k++) {
+                        temp.add('#');
+                    }
+
+                    temp.add('*');
+                }
+                // 去除末尾 *
+                if (temp.get(temp.size() - 1) == '*') {
+                    temp.remove(temp.size() - 1);
+                }
+            }
+            temp.remove(temp.size() - 1);
+            record.add(temp);
+        }
+        // rotate
+        for (int i = 0; i < col; i++) {
+            for (int j = 0; j < row; j++) {
+                ret[i][j] = record.get(row - 1 - j).get(i);
+            }
+        }
+
+        return ret;
+    }
+}
