aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--plates_between_candles.c64
-rw-r--r--plates_between_candles.py36
2 files changed, 100 insertions, 0 deletions
diff --git a/plates_between_candles.c b/plates_between_candles.c
new file mode 100644
index 0000000..20121f3
--- /dev/null
+++ b/plates_between_candles.c
@@ -0,0 +1,64 @@
+// 2055. Plates Between Candles
+#include "leetcode.h"
+
+/*
+ * there is a long table with a line of plates and candles arranged on top of
+ * it. you are given a 0-indexed string 's' consisting of characters '*' and '|'
+ * only where '*' represents a plate and '|' represents a candle. return an
+ * integer array 'answer' where 'answer[i]' is the answer to the i'th query.
+ */
+
+int *platesBetweenCandles(char *s, int **queries, int queriesSize,
+ int *queriesColSize, int *returnSize) {
+ int n = strlen(s), cnt = 0, lidx = -1, ridx = -1;
+ int *dp = (int *)calloc(n, sizeof(int));
+ int *left = (int *)calloc(n, sizeof(int));
+ int *right = (int *)calloc(n, sizeof(int));
+ for (int i = 0; i < n; i++) {
+ if (s[i] == '*')
+ cnt++;
+ else
+ lidx = i;
+ dp[i] = cnt;
+ left[i] = lidx;
+ }
+ for (int i = n - 1; i >= 0; i--) {
+ if (s[i] == '|')
+ ridx = i;
+ right[i] = ridx;
+ }
+ *returnSize = queriesSize;
+ int *ans = (int *)malloc((*returnSize) * sizeof(int));
+ for (int i = 0; i < queriesSize; i++) {
+ int r = right[queries[i][0]], l = left[queries[i][1]];
+ ans[i] = (r == -1 || l == -1 || r >= l) ? 0 : dp[l] - dp[r];
+ }
+ free(dp);
+ free(left);
+ free(right);
+ return ans;
+}
+
+int main() {
+ int q1i[2][2] = {{2, 5}, {5, 9}},
+ q2i[5][2] = {{1, 17}, {4, 5}, {14, 17}, {5, 11}, {15, 16}};
+ char *s1 = "**|**|***|", *s2 = "***|**|*****|**||**|*";
+ struct two_d_arr *q1 =
+ two_d_arr_init(ARRAY_SIZE(q1i), ARRAY_SIZE(q1i[0]), q1i);
+ struct two_d_arr *q2 =
+ two_d_arr_init(ARRAY_SIZE(q2i), ARRAY_SIZE(q2i[0]), q2i);
+ int rs1, *pbc1 = platesBetweenCandles(s1, q1->arr, q1->row_size, q1->col_size,
+ &rs1);
+ int rs2, *pbc2 = platesBetweenCandles(s2, q2->arr, q2->row_size, q2->col_size,
+ &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", pbc1[i]); // expect: 2 3
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", pbc2[i]); // expect: 9 0 0 0 0
+ printf("\n");
+ free(pbc1);
+ free(pbc2);
+ two_d_arr_free(q1);
+ two_d_arr_free(q2);
+}
diff --git a/plates_between_candles.py b/plates_between_candles.py
new file mode 100644
index 0000000..a1eec44
--- /dev/null
+++ b/plates_between_candles.py
@@ -0,0 +1,36 @@
+# 2055. Plates Between Candles
+import bisect
+
+"""
+there is a long table with a line of plates and candles arranged on top of
+it. you are given a 0-indexed string 's' consisting of characters '*' and '|'
+only where '*' represents a plate and '|' represents a candle. return an
+integer array 'answer' where 'answer[i]' is the answer to the i'th query.
+"""
+
+
+class Solution(object):
+ def platesBetweenCandles(self, s, queries):
+ """
+ :type s: str
+ :type queries: List[List[int]]
+ :rtype: List[int]
+ """
+ dp = [i for i, j in enumerate(s) if j == "|"]
+ ans = []
+ for a, b in queries:
+ i = bisect.bisect_left(dp, a)
+ j = bisect.bisect(dp, b) - 1
+ ans.append((dp[j] - dp[i]) - (j - i) if i < j else 0)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.platesBetweenCandles(s="**|**|***|", queries=[[2, 5], [5, 9]]))
+ print(
+ obj.platesBetweenCandles(
+ s="***|**|*****|**||**|*",
+ queries=[[1, 17], [4, 5], [14, 17], [5, 11], [15, 16]],
+ )
+ )