aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--count_num_complete_component.c73
-rw-r--r--count_num_complete_component.py48
-rw-r--r--find_kth_char_str_game2.c28
-rw-r--r--find_kth_char_str_game2.py29
-rw-r--r--min_cost_walk_weight_graph.cpp72
-rw-r--r--min_cost_walk_weight_graph.py72
-rw-r--r--shopping_offers.c122
-rw-r--r--shopping_offers.py49
8 files changed, 493 insertions, 0 deletions
diff --git a/count_num_complete_component.c b/count_num_complete_component.c
new file mode 100644
index 0000000..a6ede23
--- /dev/null
+++ b/count_num_complete_component.c
@@ -0,0 +1,73 @@
+// 2685. Count the Number of Complete Components
+#include "leetcode.h"
+
+/*
+ * you are given an integer 'n'. there is an undirected graph with 'n' vertices,
+ * numbered from 0 to 'n - 1'. you are given a 2d integer array 'edges' where
+ * 'edges[i] = [a_i, b_i]' denotes that there exists an undirected edge
+ * connecting vertices 'a_i' and 'b_i'. return the number of complete connected
+ * components of the graph. a connected component is a subgraph of a graph in
+ * which there exists a path between any two vertices and no vertex of the
+ * subgraph shares an edge with a vertex outside of the subgraph. a connected
+ * component is said to be complete if there exists an edge between every pair
+ * of its vertices
+ */
+
+int countCompleteComponents(int n, int **edges, int edgesSize,
+ int *edgesColSize) {
+ int *vertices = (int *)calloc(n, sizeof(int));
+ int *edge_cnt = (int *)calloc(n, sizeof(int));
+ int *vert_cnt = (int *)calloc(n, sizeof(int));
+ int group = 1, ans = 0;
+ for (int i = 0; i < edgesSize; i++) {
+ int v1 = edges[i][0];
+ int v2 = edges[i][1];
+ if (!(vertices[v1] + vertices[v2])) {
+ vertices[v1] = vertices[v2] = group;
+ edge_cnt[group] = 2;
+ vert_cnt[group++] = 1;
+ } else if (!vertices[v1]) {
+ vertices[v1] = vertices[v2];
+ ++edge_cnt[vertices[v2]];
+ ++vert_cnt[vertices[v2]];
+ } else if (!vertices[v2]) {
+ vertices[v2] = vertices[v1];
+ ++edge_cnt[vertices[v1]];
+ ++vert_cnt[vertices[v1]];
+ } else if (vertices[v1] == vertices[v2])
+ ++vert_cnt[vertices[v1]];
+ else {
+ vert_cnt[vertices[v1]] += vert_cnt[vertices[v2]] + 1;
+ edge_cnt[vertices[v1]] += edge_cnt[vertices[v2]];
+ edge_cnt[vertices[v2]] = vert_cnt[vertices[v2]] = 0;
+ for (int i = 0; i < n; i++)
+ if (vertices[i] == vertices[v2])
+ vertices[i] = vertices[v1];
+ }
+ }
+ int connect_cnt = 0;
+ for (int i = 1; i < group; i++) {
+ int edges = edge_cnt[i], verts = vert_cnt[i];
+ if (edges && (edges * (edges - 1) / 2 == verts))
+ ++ans;
+ connect_cnt += edges;
+ }
+ free(vert_cnt);
+ free(edge_cnt);
+ free(vertices);
+ return ans + (n - connect_cnt);
+}
+
+int main() {
+ int e1i[4][2] = {{0, 1}, {0, 2}, {1, 2}, {3, 4}},
+ e2i[5][2] = {{0, 1}, {0, 2}, {1, 2}, {3, 4}, {3, 5}};
+ struct two_d_arr e1, e2;
+ two_d_arr_init(&e1, ARRAY_SIZE(e1i), ARRAY_SIZE(e1i[0]), e1i);
+ two_d_arr_init(&e2, ARRAY_SIZE(e2i), ARRAY_SIZE(e2i[0]), e2i);
+ printf("%d\n", countCompleteComponents(6, e1.arr, e1.row_size,
+ e1.col_size)); // expect: 3
+ printf("%d\n", countCompleteComponents(6, e2.arr, e2.row_size,
+ e2.col_size)); // expect: 1
+ two_d_arr_free(&e1);
+ two_d_arr_free(&e2);
+}
diff --git a/count_num_complete_component.py b/count_num_complete_component.py
new file mode 100644
index 0000000..6b8a592
--- /dev/null
+++ b/count_num_complete_component.py
@@ -0,0 +1,48 @@
+# 2685. Count the Number of Complete Components
+
+"""
+you are given an integer 'n'. there is an undirected graph with 'n' vertices,
+numbered from 0 to 'n - 1'. you are given a 2d integer array 'edges' where
+'edges[i] = [a_i, b_i]' denotes that there exists an undirected edge
+connecting vertices 'a_i' and 'b_i'. return the number of complete connected
+components of the graph. a connected component is a subgraph of a graph in
+which there exists a path between any two vertices and no vertex of the
+subgraph shares an edge with a vertex outside of the subgraph. a connected
+component is said to be complete if there exists an edge between every pair
+of its vertices
+"""
+
+
+class Solution(object):
+ def countCompleteComponents(self, n, edges):
+ """
+ :type n: int
+ :type edges: List[List[int]]
+ :rtype: int
+ """
+ graph = [[] for _ in range(n)]
+ for i, j in edges:
+ graph[i].append(j)
+ graph[j].append(i)
+ vis, ans = [False] * n, 0
+ for i in range(n):
+ if vis[i]:
+ continue
+ bfs = [i]
+ vis[i] = True
+ for j in bfs:
+ for k in graph[j]:
+ if not vis[k]:
+ bfs.append(k)
+ vis[k] = True
+ if all(len(graph[j]) == len(bfs) - 1 for j in bfs):
+ ans += 1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countCompleteComponents(n=6, edges=[[0, 1], [0, 2], [1, 2], [3, 4]]))
+ print(
+ obj.countCompleteComponents(n=6, edges=[[0, 1], [0, 2], [1, 2], [3, 4], [3, 5]])
+ )
diff --git a/find_kth_char_str_game2.c b/find_kth_char_str_game2.c
new file mode 100644
index 0000000..08202e6
--- /dev/null
+++ b/find_kth_char_str_game2.c
@@ -0,0 +1,28 @@
+// 3307. Find the K-th Character in String Game II
+#include "leetcode.h"
+
+/*
+ * alice and bob are playing a game. initially, alice has a string 'word = "a"'.
+ * you are given a positive integer 'k'. you are also given an integer array
+ * 'operations' where 'operations[i]' represents the type of i'th operation. now
+ * bob will ask alice to perform all operations in sequence: if 'operations[i]
+ * == 0', append a copy of 'word' to itself. if 'operations[i] == 1', generate a
+ * new string by changing each character in 'word' to its next character in the
+ * english alphabet, and append it to the origin 'word'. return the value of the
+ * k'th character in 'word' after performing all the operations.
+ */
+
+char kthCharacter(long long k, int *operations, int operationsSize) {
+ int ans = 0;
+ k--;
+ for (int i = 0; i < operationsSize && i < 60; ++i)
+ if ((k >> i) % 2)
+ ans += operations[i];
+ return (char)('a' + ans % 26);
+}
+
+int main() {
+ int o1[] = {0, 0, 0}, o2[] = {0, 1, 0, 1};
+ printf("%c\n", kthCharacter(5, o1, ARRAY_SIZE(o1))); // expect: a
+ printf("%c\n", kthCharacter(10, o2, ARRAY_SIZE(o2))); // expect: b
+}
diff --git a/find_kth_char_str_game2.py b/find_kth_char_str_game2.py
new file mode 100644
index 0000000..118641e
--- /dev/null
+++ b/find_kth_char_str_game2.py
@@ -0,0 +1,29 @@
+# 3307. Find the K-th Character in String Game II
+
+"""
+alice and bob are playing a game. initially, alice has a string 'word = "a"'.
+you are given a positive integer 'k'. you are also given an integer array
+'operations' where 'operations[i]' represents the type of i'th operation. now
+bob will ask alice to perform all operations in sequence: if 'operations[i]
+== 0', append a copy of 'word' to itself. if 'operations[i] == 1', generate a
+new string by changing each character in 'word' to its next character in the
+english alphabet, and append it to the origin 'word'. return the value of the
+k'th character in 'word' after performing all the operations.
+"""
+
+
+class Solution(object):
+ def kthCharacter(self, k, operations):
+ """
+ :type k: int
+ :type operations: List[int]
+ :rtype: str
+ """
+ ans = (k - 1) & sum(v << i for i, v in enumerate(operations))
+ return chr(ord("a") + ans.bit_count() % 26)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.kthCharacter(k=5, operations=[0, 0, 0]))
+ print(obj.kthCharacter(k=10, operations=[0, 1, 0, 1]))
diff --git a/min_cost_walk_weight_graph.cpp b/min_cost_walk_weight_graph.cpp
new file mode 100644
index 0000000..79f3a8b
--- /dev/null
+++ b/min_cost_walk_weight_graph.cpp
@@ -0,0 +1,72 @@
+// 3108. Minimum Cost Walk in Weighted Graph
+#include "leetcode.h"
+
+/*
+ * there is an undirected weighted graph with 'n' vertices labeled from 0 to 'n
+ * - 1'. you are given the integer 'n' and an array 'edges', where 'edges[i] =
+ * [u_i, v_i, w_i]' indicates that there is an edge between vertices 'u_i' and
+ * 'v_i' with a weight of 'w_i'. a walk on the graph is a sequence of vertices
+ * and edges. the walk starts and ends with a vertex, and each edge connects the
+ * vertex that comes before it and the vertex that comes after it. it's
+ * important to note that a walk may visit the same edge or vertex more than
+ * once. return the array 'answer' where 'answer[i]' denotes the minimum cost of
+ * a walk for query 'i'.
+ */
+
+class Solution {
+public:
+ vector<int> minimumCost(int n, vector<vector<int>> &edges,
+ vector<vector<int>> &query) {
+ vector<vector<int>> adj(n);
+ vector<int> cnt(n, (1 << 30) - 1);
+ for (vector<int> e : edges) {
+ int u = e[0], v = e[1], k = e[2];
+ adj[u].push_back(v);
+ adj[v].push_back(u);
+ cnt[u] &= k;
+ cnt[v] &= k;
+ }
+ queue<int> q;
+ vector<int> group(n, -1);
+ for (int i = 0; i < n; i++) {
+ if (group[i] == -1) {
+ group[i] = i;
+ q.push(i);
+ while (!q.empty()) {
+ int u = q.front();
+ q.pop();
+ cnt[i] &= cnt[u];
+ for (int v : adj[u]) {
+ if (group[v] == -1) {
+ group[v] = i;
+ q.push(v);
+ }
+ }
+ }
+ }
+ }
+ vector<int> ans;
+ for (vector<int> qs : query) {
+ int s = qs[0], t = qs[1];
+ if (s == t)
+ ans.push_back(0);
+ else
+ ans.push_back(group[s] == group[t] ? cnt[group[s]] : -1);
+ }
+ return ans;
+ }
+};
+
+int main() {
+ Solution obj;
+ vvd e1 = {{0, 1, 7}, {1, 3, 7}, {1, 2, 1}}, q1 = {{0, 3}, {3, 4}};
+ vvd e2 = {{0, 2, 7}, {0, 1, 15}, {1, 2, 6}, {1, 2, 1}}, q2 = {{1, 2}};
+ vector<int> mc1 = obj.minimumCost(5, e1, q1);
+ vector<int> mc2 = obj.minimumCost(3, e2, q2);
+ for (auto i : mc1)
+ printf("%d ", i); // expect: 1 -1
+ printf("\n");
+ for (auto i : mc2)
+ printf("%d ", i); // expect: 0
+ printf("\n");
+}
diff --git a/min_cost_walk_weight_graph.py b/min_cost_walk_weight_graph.py
new file mode 100644
index 0000000..b1d2415
--- /dev/null
+++ b/min_cost_walk_weight_graph.py
@@ -0,0 +1,72 @@
+# 3108. Minimum Cost Walk in Weighted Graph
+
+"""
+there is an undirected weighted graph with 'n' vertices labeled from 0 to 'n
+- 1'. you are given the integer 'n' and an array 'edges', where 'edges[i] =
+[u_i, v_i, w_i]' indicates that there is an edge between vertices 'u_i' and
+'v_i' with a weight of 'w_i'. a walk on the graph is a sequence of vertices
+and edges. the walk starts and ends with a vertex, and each edge connects the
+vertex that comes before it and the vertex that comes after it. it's
+important to note that a walk may visit the same edge or vertex more than
+once. return the array 'answer' where 'answer[i]' denotes the minimum cost of
+a walk for query 'i'.
+"""
+
+
+class UnionFind:
+ def __init__(self, size):
+ self.parent = [i for i in range(size)]
+ self.rank = [0 for _ in range(size)]
+ self.d = [~0 for _ in range(size)]
+
+ def find(self, node):
+ if self.parent[node] != node:
+ self.parent[node] = self.find(self.parent[node])
+ return self.parent[node]
+
+ def union(self, a, b, val):
+ p1, p2 = self.find(a), self.find(b)
+ if self.rank[p1] > self.rank[p2]:
+ self.parent[p2] = p1
+ self.d[p1] &= self.d[p2] & val
+ elif self.rank[p1] < self.rank[p2]:
+ self.parent[p1] = p2
+ self.d[p2] &= self.d[p1] & val
+ else:
+ self.parent[p1] = p2
+ self.d[p2] &= self.d[p1] & val
+ self.rank[p2] += 1
+
+
+class Solution(object):
+ def minimumCost(self, n, edges, query):
+ """
+ :type n: int
+ :type edges: List[List[int]]
+ :type query: List[List[int]]
+ :rtype: List[int]
+ """
+ uf = UnionFind(n)
+ for u, v, w in edges:
+ uf.union(u, v, w)
+ ans = []
+ for u, v in query:
+ if uf.find(u) != uf.find(v):
+ ans.append(-1)
+ else:
+ ans.append(uf.d[uf.find(u)])
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.minimumCost(
+ n=5, edges=[[0, 1, 7], [1, 3, 7], [1, 2, 1]], query=[[0, 3], [3, 4]]
+ )
+ )
+ print(
+ obj.minimumCost(
+ n=3, edges=[[0, 2, 7], [0, 1, 15], [1, 2, 6], [1, 2, 1]], query=[[1, 2]]
+ )
+ )
diff --git a/shopping_offers.c b/shopping_offers.c
new file mode 100644
index 0000000..bc7b735
--- /dev/null
+++ b/shopping_offers.c
@@ -0,0 +1,122 @@
+// 638. Shopping Offers
+#include "leetcode.h"
+
+/*
+ * in leetcode store, there are 'n' items to sell. each item has a price.
+ * however, there are some special offers, and a special offer consists of one
+ * or more different kinds of items with a sale price. you are given an integer
+ * array 'price' where 'price[i]' is the price of the i'th item, and an integer
+ * array 'needs' where 'needs[i]' is the number of pieces the i'th item you want
+ * to buy. you are also given an array 'special', where 'special[i]' is of size
+ * 'n + 1' where 'special[i][j]' is the number of pieces of the j'th item in the
+ * i'th other. return the lowest price you have to pay for exactly certain items
+ * as given, where you could make optimal use of the special offers. you are not
+ * allowed to buy more items that you want, even if that would lower the overall
+ * price.
+ */
+
+#define MOD 1009
+
+struct node {
+ struct node *next;
+ int key;
+ int val;
+};
+
+struct node *hash[MOD];
+
+void hash_init(void) { memset((void *)hash, 0, sizeof(hash)); }
+
+void hash_push(int key, int val) {
+ int idx = key % MOD;
+ struct node *tmp = (struct node *)malloc(sizeof(struct node));
+ tmp->key = key;
+ tmp->val = val;
+ tmp->next = hash[idx];
+ hash[idx] = tmp;
+}
+
+int hash_pop(int key) {
+ int idx = key % MOD;
+ struct node *tmp = hash[idx];
+ for (; tmp; tmp = tmp->next)
+ if (tmp->key == key)
+ return tmp->val;
+ return -1;
+}
+
+void hash_free(void) {
+ for (int i = 0; i < MOD; i++)
+ for (struct node *tmp = hash[i], *del; tmp;) {
+ del = tmp;
+ tmp = tmp->next;
+ free(del);
+ }
+}
+
+int lowest_price(int n, int need, int *prices, int **special, int specialSize,
+ int *specialColSize) {
+ int min = INT_MAX, price = 0, tmp;
+ bool accept = true;
+ if (!need)
+ return 0;
+ price = hash_pop(need);
+ if (price >= 0)
+ return price;
+ price = 0;
+ tmp = need;
+ for (int i = 0; i < n; i++) {
+ price += prices[i] * (tmp & 0x0F);
+ tmp >>= 4;
+ }
+ min = fmin(min, price);
+ for (int i = 0; i < specialSize; i++) {
+ tmp = need;
+ accept = true;
+ for (int j = 0; j < n; j++) {
+ int quantity = (tmp >> (j * 4)) & 0x0F;
+ if (quantity >= special[i][j]) {
+ quantity -= special[i][j];
+ tmp &= ~(0x0F << (j * 4));
+ tmp |= (quantity << (j * 4));
+ } else {
+ accept = false;
+ break;
+ }
+ }
+ if (accept) {
+ price = special[i][n] + lowest_price(n, tmp, prices, special, specialSize,
+ specialColSize);
+ min = fmin(min, price);
+ }
+ }
+ hash_push(need, min);
+ return min;
+}
+
+int shoppingOffers(int *price, int priceSize, int **special, int specialSize,
+ int *specialColSize, int *needs, int needsSize) {
+ int need = 0, ans;
+ hash_init();
+ for (int i = 0; i < needsSize; i++)
+ need |= (needs[i] << (i * 4));
+ ans = lowest_price(priceSize, need, price, special, specialSize,
+ specialColSize);
+ hash_free();
+ return ans;
+}
+
+int main() {
+ int p1[] = {2, 5}, s1i[2][3] = {{3, 0, 5}, {1, 2, 10}}, n1[] = {3, 2};
+ int p2[] = {2, 3, 4}, s2i[2][4] = {{1, 1, 0, 4}, {2, 2, 1, 9}},
+ n2[] = {1, 2, 1};
+ struct two_d_arr s1, s2;
+ two_d_arr_init(&s1, ARRAY_SIZE(s1i), ARRAY_SIZE(s1i[0]), s1i);
+ two_d_arr_init(&s2, ARRAY_SIZE(s2i), ARRAY_SIZE(s2i[0]), s2i);
+ printf("%d\n", shoppingOffers(p1, ARRAY_SIZE(p1), s1.arr, s1.row_size,
+ s1.col_size, n1, ARRAY_SIZE(n1))); // expect: 14
+ printf("%d\n", shoppingOffers(p2, ARRAY_SIZE(p2), s2.arr, s2.row_size,
+ s2.col_size, n2, ARRAY_SIZE(n2))); // expect: 11
+ two_d_arr_free(&s1);
+ two_d_arr_free(&s2);
+}
diff --git a/shopping_offers.py b/shopping_offers.py
new file mode 100644
index 0000000..42da709
--- /dev/null
+++ b/shopping_offers.py
@@ -0,0 +1,49 @@
+# 638. Shopping Offers
+
+"""
+in leetcode store, there are 'n' items to sell. each item has a price.
+however, there are some special offers, and a special offer consists of one
+or more different kinds of items with a sale price. you are given an integer
+array 'price' where 'price[i]' is the price of the i'th item, and an integer
+array 'needs' where 'needs[i]' is the number of pieces the i'th item you want
+to buy. you are also given an array 'special', where 'special[i]' is of size
+'n + 1' where 'special[i][j]' is the number of pieces of the j'th item in the
+i'th other. return the lowest price you have to pay for exactly certain items
+as given, where you could make optimal use of the special offers. you are not
+allowed to buy more items that you want, even if that would lower the overall
+price.
+"""
+
+
+class Solution(object):
+ def shoppingOffers(self, price, special, needs):
+ """
+ :type price: List[int]
+ :type special: List[List[int]]
+ :type needs: List[int]
+ :rtype: int
+ """
+ dp = {}
+
+ def dfs(curr):
+ val = sum(curr[i] * price[i] for i in range(len(needs)))
+ for *spec, cost in special:
+ tmp = [curr[j] - spec[j] for j in range(len(needs))]
+ if min(tmp) >= 0: # skip deals that exceed needs
+ val = min(val, dp.get(tuple(tmp), dfs(tmp)) + cost)
+ dp[tuple(curr)] = val
+ return val
+
+ return dfs(needs)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.shoppingOffers(price=[2, 5], special=[[3, 0, 5], [1, 2, 10]], needs=[3, 2])
+ )
+ print(
+ obj.shoppingOffers(
+ price=[2, 3, 4], special=[[1, 1, 0, 4], [2, 2, 1, 9]], needs=[1, 2, 1]
+ )
+ )