From a96b65cbfad7f62f3db6b2eab105e4e25c0414c5 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Fri, 27 Jun 2025 12:23:02 -0600 Subject: chore: remove old cpp and rust solutions --- other/build_matrix_conditions.cpp | 98 --------------------------------------- 1 file changed, 98 deletions(-) delete mode 100644 other/build_matrix_conditions.cpp (limited to 'other/build_matrix_conditions.cpp') diff --git a/other/build_matrix_conditions.cpp b/other/build_matrix_conditions.cpp deleted file mode 100644 index e192dda..0000000 --- a/other/build_matrix_conditions.cpp +++ /dev/null @@ -1,98 +0,0 @@ -// 2392. Build a Matrix With Conditions -#include "leetcode.h" - -/* - * you are givne a positive integer 'k'. you are also given a 2d integer array - * 'rowConditions' of size 'n' where 'rowConditions[i] = [above_i, below_i]' and - * a 2d integer array 'colConditions' of size 'm' where 'colConditions[i] = - * [left_i, right_i]'. the two arrays contain integers from 1 to 'k'. you have - * to build a 'k * k' matrix that contains each of the numbers from 1 to 'k' - * exactly once. the remaining cells should satisfy the following conditions. - * the number 'above_i' should appear in a row that is strictly above the row at - * which the number 'below_i' appears for all 'i'. the number 'left_i' should - * appear in a column that is strictly left of the column at which the number - * 'right_i' appears for all 'i'. return any matrix that satisfies these - * conditions. - */ - -class Solution { -private: - vector colour; - vector visited; - bool dfs(int v, vector> &graph) { - colour[v] = 1; - for (int i : graph[v]) { - if (!colour[i]) { - if (dfs(i, graph)) - return true; - } else if (colour[i] == 1) - return true; - } - colour[v] = 2; - return false; - } - bool find_cycle(vector> &graph, int n) { - colour.assign(n, 0); - for (int i = 0; i < n; i++) - if (!colour[i] && dfs(i, graph)) - return true; - return false; - } - void dfs2(int v, vector> &graph, vector &res) { - visited[v] = true; - for (int i : graph[v]) - if (!visited[i]) - dfs2(i, graph, res); - res.push_back(v); - } - void topo_sort(vector> &graph, int n, vector &res) { - visited.assign(n, false); - res.clear(); - for (int i = 0; i < n; ++i) - if (!visited[i]) - dfs2(i, graph, res); - reverse(res.begin(), res.end()); - } - -public: - vector> buildMatrix(int k, vector> &rowConditions, - vector> &colConditions) { - vector> g1(k), g2(k); - for (auto i : rowConditions) - g1[i[0] - 1].push_back(i[1] - 1); - for (auto i : colConditions) - g2[i[0] - 1].push_back(i[1] - 1); - if (find_cycle(g1, k) || find_cycle(g2, k)) - return vector>(); - vector a1, a2; - topo_sort(g1, k, a1); - topo_sort(g1, k, a2); - vector> ans(k, vector(k)); - map m; - for (int i = 0; i < k; i++) - m[a2[i]] = i; - for (int i = 0; i < k; i++) - ans[i][m[a1[i]]] = a1[i] + 1; - return ans; - } -}; - -int main() { - Solution obj; - vvd rc1 = {{1, 2}, {3, 2}}, cc1 = {{2, 1}, {3, 2}}; - vvd rc2 = {{1, 2}, {2, 3}, {3, 1}, {2, 3}}, cc2 = {{2, 1}}; - vvd bm1 = obj.buildMatrix(3, rc1, cc1), - bm2 = obj.buildMatrix(3, rc2, cc2); - for (int i = 0; i < bm1.size(); i++) { - for (int j = 0; j < bm1[0].size(); j++) - printf("%d ", bm1[i][j]); - printf("\n"); - } - printf("\n"); - for (int i = 0; i < bm2.size(); i++) { - for (int j = 0; j < bm2[0].size(); j++) - printf("%d ", bm2[i][j]); - printf("\n"); - } - printf("\n"); -} -- cgit v1.2.3