diff options
-rw-r--r-- | count_num_complete_component.c | 73 | ||||
-rw-r--r-- | count_num_complete_component.py | 48 | ||||
-rw-r--r-- | find_kth_char_str_game2.c | 28 | ||||
-rw-r--r-- | find_kth_char_str_game2.py | 29 | ||||
-rw-r--r-- | min_cost_walk_weight_graph.cpp | 72 | ||||
-rw-r--r-- | min_cost_walk_weight_graph.py | 72 | ||||
-rw-r--r-- | shopping_offers.c | 122 | ||||
-rw-r--r-- | shopping_offers.py | 49 |
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] + ) + ) |