How to use row_cls method in pom

Best Python code snippet using pom_python

947_remove_stones.py

Source:947_remove_stones.py

1"""2947. Most Stones Removed with Same Row or Column (Medium)3On a 2D plane, we place stones at some integer coordinate points.  Each coordinate point may have at most one stone.4Now, a move consists of removing a stone that shares a column or row with another stone on the grid.5What is the largest possible number of moves we can make?6Example 1:7Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]8Output: 59Example 2:10Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]11Output: 312Example 3:13Input: stones = [[0,0]]14Output: 015Note:161 <= stones.length <= 1000170 <= stones[i][j] < 1000018"""19"""20Problem:21we can remove a stone if and only if,22there is another stone in the same column OR row.23We try to remove as many as stones as possible.24Find more details in chinese on the jianshu25One sentence to solve:26Connected stones can be reduced to 1 stone,27the maximum stones can be removed = stones number - islands number.28so just count the number of "islands".291. Connected stones30Two stones are connected if they are in the same row or same col.31Connected stones will build a connected graph.32It's obvious that in one connected graph,33we can't remove all stones.34We have to have one stone left.35An intuition is that, in the best strategy, we can remove until 1 stone.36I guess you may reach this step when solving the problem.37But the important question is, how?382. A failed strategy39Try to remove the least degree stone40Like a tree, we try to remove leaves first.41Some new leaf generated.42We continue this process until the root node left.43However, there can be no leaf.44When you try to remove the least in-degree stone,45it won't work on this "8" like graph:46[[1, 1, 0, 0, 0],47[1, 1, 0, 0, 0],48[0, 1, 1, 0, 0],49[0, 0, 1, 1, 1],50[0, 0, 0, 1, 1]]51The stone in the center has least degree = 2.52But if you remove this stone first,53the whole connected stones split into 2 parts,54and you will finish with 2 stones left.553. A good strategy56In fact, the proof is really straightforward.57You probably apply a DFS, from one stone to next connected stone.58You can remove stones in reversed order.59In this way, all stones can be removed but the stone that you start your DFS.60One more step of explanation:61In the view of DFS, a graph is explored in the structure of a tree.62As we discussed previously,63a tree can be removed in topological order,64from leaves to root.654. Count the number of islands66We call a connected graph as an island.67One island must have at least one stone left.68The maximum stones can be removed = stones number - islands number69The whole problem is transferred to:70What is the number of islands?71You can show all your skills on a DFS implementation,72and solve this problem as a normal one.735. Unify index74Struggle between rows and cols?75You may duplicate your codes when you try to the same thing on rows and cols.76In fact, no logical difference between col index and rows index.77An easy trick is that, add 10000 to col index.78So we use 0 ~ 9999 for row index and 10000 ~ 19999 for col.796. Search on the index, not the points80When we search on points,81we alternately change our view on a row and on a col.82We think:83a row index, connect two stones on this row84a col index, connect two stones on this col.85In another viewï¼86A stone, connect a row index and col.87Have this idea in mind, the solution can be much simpler.88The number of islands of points,89is the same as the number of islands of indexes.907. Union-Find91I use union find to solve this problem.92As I mentioned, the elements are not the points, but the indexes.93for each point, union two indexes.94return points number - union number95Copy a template of union-find,96write 2 lines above,97you can solve this problem in several minutes.98Complexity99union and find functions have worst case O(N), amortize O(1)100The whole union-find solution with path compression,101has O(N) Time, O(N) Space102If you have any doubts on time complexity,103please refer to wikipedia first.104"""105class Solution(object):106    def removeStones(self, stones):107        """108        :type stones: List[List[int]]109        :rtype: int110        """111        row_memo = {}112        col_memo = {}113        class_list = [] # class_id to parent114        for i, j in stones:115            # print(i, j)116            row_cls = row_memo.get(i, len(class_list))117            col_cls = col_memo.get(j, len(class_list))118            if row_cls == col_cls and row_cls < len(class_list):119                continue120            elif row_cls == col_cls and row_cls == len(class_list):121                row_memo[i] = len(class_list)122                col_memo[j] = len(class_list)123                class_list.append(-1)124            elif row_cls == len(class_list) or col_cls == len(class_list):125                cls_label = min(row_cls, col_cls)126                row_memo[i] = cls_label127                col_memo[j] = cls_label128            else:129                # union find130                while class_list[row_cls] != -1:131                    row_cls = class_list[row_cls]132                while class_list[col_cls] != -1:133                    col_cls = class_list[col_cls]134                if row_cls != col_cls:135                    min_ = min(row_cls, col_cls)136                    max_ = max(row_cls, col_cls)137                    if max_ != min_:138                        class_list[max_] = min_139        return len(stones) - class_list.count(-1)140    def solve2(self, points):141        UF = {}142        def find(x):143            if x != UF[x]:144                UF[x] = find(UF[x])145            return UF[x]146        def union(x, y):147            UF.setdefault(x, x)148            UF.setdefault(y, y)149            UF[find(x)] = find(y)150        for i, j in points:151            union(i, ~j)152        return len(points) - len({find(x) for x in UF})153if __name__ == "__main__":154    a = Solution()155    """156    print(a.removeStones([[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]))157    print(a.removeStones([[0,0],[0,2],[1,1],[2,0],[2,2]]))158    print(a.removeStones([[0,0]]))159    print(a.removeStones([[1,0],[0,1],[1,1]]))160    print(a.removeStones([[0,1],[1,2],[1,3],[3,3],[2,3],[0,2]]))161    print(a.removeStones([[3,2],[0,0],[3,3],[2,1],[2,3],[2,2],[0,2]]))162    """...

base.py

Source:base.py

...92        if self.skip_header_row:93            self.csv_reader.__next__()94            self.skip_header_row = False95        96        return self.row_cls(*self.csv_reader.__next__())979899class Writer:100    def __init__(self, row_cls, file):101        self.columns = row_cls._dialect.columns102        self._writer = csv.writer(file, row_cls._dialect.csv_dialect)103        self.needs_header_row = row_cls._dialect.has_header_row104105    def writerow(self, row):106        if self.needs_header_row:107            values = [column.title.title() for column in self.columns]108            self._writer.writerow(values)109            self.needs_header_row = False110        values = [getattr(row, column.name) for column in self.columns]
...

Automation Testing Tutorials

Learn to execute automation testing from scratch with LambdaTest Learning Hub. Right from setting up the prerequisites to run your first automation test, to following best practices and diving deeper into advanced test scenarios. LambdaTest Learning Hubs compile a list of step-by-step guides to help you be proficient with different test automation frameworks i.e. Selenium, Cypress, TestNG etc.