feat: add solutions to lc problems

yanglbme · yanglbme · commit 15001cca9488 · 2022-05-15T15:36:00.000+08:00
* No.2273.Find Resultant Array After Removing Anagrams
* No.2274.Maximum Consecutive Floors Without Special Floors
* No.2275.Largest Combination With Bitwise AND Greater Than Zero
* No.2276.Count Integers in Intervals
diff --git a/solution/1300-1399/1377.Frog Position After T Seconds/Solution.py b/solution/1300-1399/1377.Frog Position After T Seconds/Solution.py
@@ -1,5 +1,7 @@
 class Solution:
-    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
+    def frogPosition(
+        self, n: int, edges: List[List[int]], t: int, target: int
+    ) -> float:
         g = defaultdict(list)
         for u, v in edges:
             g[u].append(v)
diff --git a/solution/2200-2299/2273.Find Resultant Array After Removing Anagrams/README.md b/solution/2200-2299/2273.Find Resultant Array After Removing Anagrams/README.md
@@ -65,7 +65,9 @@ words 中不存在互为字母异位词的两个相邻字符串，所以无需
 <!-- 这里可写当前语言的特殊实现逻辑 -->
 
 ```python
-
+class Solution:
+    def removeAnagrams(self, words: List[str]) -> List[str]:
+        return [w for i, w in enumerate(words) if i == 0 or sorted(w) != sorted(words[i - 1])]
 ```
 
 ### **Java**
diff --git a/solution/2200-2299/2273.Find Resultant Array After Removing Anagrams/README_EN.md b/solution/2200-2299/2273.Find Resultant Array After Removing Anagrams/README_EN.md
@@ -52,7 +52,9 @@ No two adjacent strings in words are anagrams of each other, so no operations ar
 ### **Python3**
 
 ```python
-
+class Solution:
+    def removeAnagrams(self, words: List[str]) -> List[str]:
+        return [w for i, w in enumerate(words) if i == 0 or sorted(w) != sorted(words[i - 1])]
 ```
 
 ### **Java**
diff --git a/solution/2200-2299/2273.Find Resultant Array After Removing Anagrams/Solution.py b/solution/2200-2299/2273.Find Resultant Array After Removing Anagrams/Solution.py
@@ -0,0 +1,7 @@
+class Solution:
+    def removeAnagrams(self, words: List[str]) -> List[str]:
+        return [
+            w
+            for i, w in enumerate(words)
+            if i == 0 or sorted(w) != sorted(words[i - 1])
+        ]
diff --git a/solution/2200-2299/2274.Maximum Consecutive Floors Without Special Floors/README.md b/solution/2200-2299/2274.Maximum Consecutive Floors Without Special Floors/README.md
@@ -55,7 +55,13 @@
 <!-- 这里可写当前语言的特殊实现逻辑 -->
 
 ```python
-
+class Solution:
+    def maxConsecutive(self, bottom: int, top: int, special: List[int]) -> int:
+        special.sort()
+        ans = max(special[0] - bottom, top - special[-1])
+        for i in range(1, len(special)):
+            ans = max(ans, special[i] - special[i - 1] - 1)
+        return ans
 ```
 
 ### **Java**
diff --git a/solution/2200-2299/2274.Maximum Consecutive Floors Without Special Floors/README_EN.md b/solution/2200-2299/2274.Maximum Consecutive Floors Without Special Floors/README_EN.md
@@ -47,7 +47,13 @@ Therefore, we return the maximum number which is 3 floors.
 ### **Python3**
 
 ```python
-
+class Solution:
+    def maxConsecutive(self, bottom: int, top: int, special: List[int]) -> int:
+        special.sort()
+        ans = max(special[0] - bottom, top - special[-1])
+        for i in range(1, len(special)):
+            ans = max(ans, special[i] - special[i - 1] - 1)
+        return ans
 ```
 
 ### **Java**
diff --git a/solution/2200-2299/2274.Maximum Consecutive Floors Without Special Floors/Solution.py b/solution/2200-2299/2274.Maximum Consecutive Floors Without Special Floors/Solution.py
@@ -0,0 +1,7 @@
+class Solution:
+    def maxConsecutive(self, bottom: int, top: int, special: List[int]) -> int:
+        special.sort()
+        ans = max(special[0] - bottom, top - special[-1])
+        for i in range(1, len(special)):
+            ans = max(ans, special[i] - special[i - 1] - 1)
+        return ans
diff --git a/solution/2200-2299/2275.Largest Combination With Bitwise AND Greater Than Zero/README.md b/solution/2200-2299/2275.Largest Combination With Bitwise AND Greater Than Zero/README.md
@@ -53,14 +53,26 @@
 
 <!-- 这里可写通用的实现逻辑 -->
 
+**方法一：位运算**
+
+大于 0，实际上就是要求存在某个二进制位（0-31），满足所有数字的这一位均为 1。
+
 <!-- tabs:start -->
 
 ### **Python3**
 
 <!-- 这里可写当前语言的特殊实现逻辑 -->
 
 ```python
-
+class Solution:
+    def largestCombination(self, candidates: List[int]) -> int:
+        ans = 0
+        for i in range(32):
+            t = 0
+            for x in candidates:
+                t += (x >> i) & 1
+            ans = max(ans, t)
+        return ans
 ```
 
 ### **Java**
diff --git a/solution/2200-2299/2275.Largest Combination With Bitwise AND Greater Than Zero/README_EN.md b/solution/2200-2299/2275.Largest Combination With Bitwise AND Greater Than Zero/README_EN.md
@@ -52,7 +52,15 @@ The size of the combination is 2, so we return 2.
 ### **Python3**
 
 ```python
-
+class Solution:
+    def largestCombination(self, candidates: List[int]) -> int:
+        ans = 0
+        for i in range(32):
+            t = 0
+            for x in candidates:
+                t += (x >> i) & 1
+            ans = max(ans, t)
+        return ans
 ```
 
 ### **Java**
diff --git a/solution/2200-2299/2275.Largest Combination With Bitwise AND Greater Than Zero/Solution.py b/solution/2200-2299/2275.Largest Combination With Bitwise AND Greater Than Zero/Solution.py
@@ -0,0 +1,9 @@
+class Solution:
+    def largestCombination(self, candidates: List[int]) -> int:
+        ans = 0
+        for i in range(32):
+            t = 0
+            for x in candidates:
+                t += (x >> i) & 1
+            ans = max(ans, t)
+        return ans
diff --git a/solution/2200-2299/2276.Count Integers in Intervals/README.md b/solution/2200-2299/2276.Count Integers in Intervals/README.md
@@ -62,6 +62,10 @@ countIntervals.count();    // 返回 8
 
 <!-- 这里可写通用的实现逻辑 -->
 
+**方法一：线段树**
+
+区间求和问题，且值域较大，采用动态开点线段树。
+
 <!-- tabs:start -->
 
 ### **Python3**
@@ -77,6 +81,118 @@ countIntervals.count();    // 返回 8
 <!-- 这里可写当前语言的特殊实现逻辑 -->
 
 ```java
+class Node {
+    Node left;
+    Node right;
+    int l;
+    int r;
+    int mid;
+    int v;
+    int add;
+
+    public Node(int l, int r) {
+        this.l = l;
+        this.r = r;
+        this.mid = (l + r) >> 1;
+    }
+}
+
+class SegmentTree {
+    private Node root = new Node(1, (int) 1e9 + 1);
+
+    public SegmentTree() {
+
+    }
+
+    public void modify(int l, int r, int v) {
+        modify(l, r, v, root);
+    }
+
+    public void modify(int l, int r, int v, Node node) {
+        if (l > r) {
+            return;
+        }
+        if (node.l >= l && node.r <= r) {
+            node.v = node.r - node.l + 1;
+            node.add = v;
+            return;
+        }
+        pushdown(node);
+        if (l <= node.mid) {
+            modify(l, r, v, node.left);
+        }
+        if (r > node.mid) {
+            modify(l, r, v, node.right);
+        }
+        pushup(node);
+    }
+
+    public int query(int l, int r) {
+        return query(l, r, root);
+    }
+
+    public int query(int l, int r, Node node) {
+        if (l > r) {
+            return 0;
+        }
+        if (node.l >= l && node.r <= r) {
+            return node.v;
+        }
+        pushdown(node);
+        int v = 0;
+        if (l <= node.mid) {
+            v += query(l, r, node.left);
+        }
+        if (r > node.mid) {
+            v += query(l, r, node.right);
+        }
+        return v;
+    }
+
+    public void pushup(Node node) {
+        node.v = node.left.v + node.right.v;
+    }
+
+    public void pushdown(Node node) {
+        if (node.left == null) {
+            node.left = new Node(node.l, node.mid);
+        }
+        if (node.right == null) {
+            node.right = new Node(node.mid + 1, node.r);
+        }
+        if (node.add != 0) {
+            Node left = node.left, right = node.right;
+            left.add = node.add;
+            right.add = node.add;
+            left.v = left.r - left.l + 1;
+            right.v = right.r - right.l + 1;
+            node.add = 0;
+        }
+    }
+}
+
+class CountIntervals {
+    private SegmentTree tree = new SegmentTree();
+
+    public CountIntervals() {
+
+    }
+    
+    public void add(int left, int right) {
+        tree.modify(left, right, 1);
+    }
+    
+    public int count() {
+        return tree.query(1, (int) 1e9);
+    }
+}
+
+/**
+ * Your CountIntervals object will be instantiated and called as such:
+ * CountIntervals obj = new CountIntervals();
+ * obj.add(left,right);
+ * int param_2 = obj.count();
+ */
 
 ```
 
diff --git a/solution/2200-2299/2276.Count Integers in Intervals/README_EN.md b/solution/2200-2299/2276.Count Integers in Intervals/README_EN.md
@@ -68,6 +68,118 @@ countIntervals.count();    // return 8
 ### **Java**
 
 ```java
+class Node {
+    Node left;
+    Node right;
+    int l;
+    int r;
+    int mid;
+    int v;
+    int add;
+
+    public Node(int l, int r) {
+        this.l = l;
+        this.r = r;
+        this.mid = (l + r) >> 1;
+    }
+}
+
+class SegmentTree {
+    private Node root = new Node(1, (int) 1e9 + 1);
+
+    public SegmentTree() {
+
+    }
+
+    public void modify(int l, int r, int v) {
+        modify(l, r, v, root);
+    }
+
+    public void modify(int l, int r, int v, Node node) {
+        if (l > r) {
+            return;
+        }
+        if (node.l >= l && node.r <= r) {
+            node.v = node.r - node.l + 1;
+            node.add = v;
+            return;
+        }
+        pushdown(node);
+        if (l <= node.mid) {
+            modify(l, r, v, node.left);
+        }
+        if (r > node.mid) {
+            modify(l, r, v, node.right);
+        }
+        pushup(node);
+    }
+
+    public int query(int l, int r) {
+        return query(l, r, root);
+    }
+
+    public int query(int l, int r, Node node) {
+        if (l > r) {
+            return 0;
+        }
+        if (node.l >= l && node.r <= r) {
+            return node.v;
+        }
+        pushdown(node);
+        int v = 0;
+        if (l <= node.mid) {
+            v += query(l, r, node.left);
+        }
+        if (r > node.mid) {
+            v += query(l, r, node.right);
+        }
+        return v;
+    }
+
+    public void pushup(Node node) {
+        node.v = node.left.v + node.right.v;
+    }
+
+    public void pushdown(Node node) {
+        if (node.left == null) {
+            node.left = new Node(node.l, node.mid);
+        }
+        if (node.right == null) {
+            node.right = new Node(node.mid + 1, node.r);
+        }
+        if (node.add != 0) {
+            Node left = node.left, right = node.right;
+            left.add = node.add;
+            right.add = node.add;
+            left.v = left.r - left.l + 1;
+            right.v = right.r - right.l + 1;
+            node.add = 0;
+        }
+    }
+}
+
+class CountIntervals {
+    private SegmentTree tree = new SegmentTree();
+
+    public CountIntervals() {
+
+    }
+    
+    public void add(int left, int right) {
+        tree.modify(left, right, 1);
+    }
+    
+    public int count() {
+        return tree.query(1, (int) 1e9);
+    }
+}
+
+/**
+ * Your CountIntervals object will be instantiated and called as such:
+ * CountIntervals obj = new CountIntervals();
+ * obj.add(left,right);
+ * int param_2 = obj.count();
+ */
 
 ```
 
diff --git a/solution/2200-2299/2276.Count Integers in Intervals/Solution.java b/solution/2200-2299/2276.Count Integers in Intervals/Solution.java
