diff options
-rw-r--r-- | find_good_days_rob_bank.c | 62 | ||||
-rw-r--r-- | find_good_days_rob_bank.py | 46 |
2 files changed, 108 insertions, 0 deletions
diff --git a/find_good_days_rob_bank.c b/find_good_days_rob_bank.c new file mode 100644 index 0000000..a60cedc --- /dev/null +++ b/find_good_days_rob_bank.c @@ -0,0 +1,62 @@ +// 2100. Find Good Days to Rob the Bank +#include "leetcode.h" + +/* + * you and a gang of thieves are planning on robbing a bank. you are given a + * 0-indexed integer array 'security' where 'security[i]' is the number of + * guards on duty on the i'th day. the days are numbered starting from 0. you + * are also given an integer 'time'. the i'th day is a good day to rob the bank + * if there are at least 'time' days before and after the i'th day, the number + * of guards at the bank for the 'time' days before/after 'i' are + * non-increasing/non-decreasing. return a list of all days (0-indexed) that are + * good days to rob the bank. the order that the days are returned in does not + * matter + */ + +int *goodDaysToRobBank(int *security, int securitySize, int time, + int *returnSize) { + int **duty = (int **)malloc(securitySize * sizeof(int *)); + int *ans = (int *)malloc(securitySize * sizeof(int)); + *returnSize = 0; + for (int i = 0; i < securitySize; i++) + duty[i] = (int *)calloc(1, sizeof(int) * 2); + for (int i = 1, guards = security[0], cnt = 0; i < securitySize; i++) { + cnt = guards >= security[i] ? cnt + 1 : 0; + guards = security[i]; + duty[i][0] = cnt; + } + for (int i = securitySize - 2, guards = security[securitySize - 1], cnt = 0; + i >= 0; i--) { + cnt = guards >= security[i] ? cnt + 1 : 0; + guards = security[i]; + duty[i][1] = cnt; + } + for (int i = 0; i < securitySize; i++) { + if (duty[i][0] >= time && duty[i][1] >= time) { + ans[*returnSize] = i; + (*returnSize)++; + } + free(duty[i]); + } + free(duty); + return ans; +} + +int main() { + int s1[] = {5, 3, 3, 3, 5, 6, 2}, rs1; + int s2[] = {1, 1, 1, 1, 1}, rs2; + int s3[] = {1, 2, 3, 4, 5, 6}, rs3; + int *gdtrb1 = goodDaysToRobBank(s1, ARRAY_SIZE(s1), 2, &rs1); + int *gdtrb2 = goodDaysToRobBank(s2, ARRAY_SIZE(s2), 0, &rs2); + int *gdtrb3 = goodDaysToRobBank(s3, ARRAY_SIZE(s3), 2, &rs3); + for (int i = 0; i < rs1; i++) + printf("%d ", gdtrb1[i]); // expect: 2 3 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", gdtrb2[i]); // expect: 0 1 2 3 4 + printf("\n"); + for (int i = 0; i < rs3; i++) + printf("%d ", gdtrb3[i]); // expect: NULL + printf("\n"); + free(gdtrb1), free(gdtrb2), free(gdtrb3); +} diff --git a/find_good_days_rob_bank.py b/find_good_days_rob_bank.py new file mode 100644 index 0000000..ab5c808 --- /dev/null +++ b/find_good_days_rob_bank.py @@ -0,0 +1,46 @@ +# 2100. Find Good Days to Rob the Bank + +""" +you and a gang of thieves are planning on robbing a bank. you are given a +0-indexed integer array 'security' where 'security[i]' is the number of +guards on duty on the i'th day. the days are numbered starting from 0. you +are also given an integer 'time'. the i'th day is a good day to rob the bank +if there are at least 'time' days before and after the i'th day, the number +of guards at the bank for the 'time' days before/after 'i' are +non-increasing/non-decreasing. return a list of all days (0-indexed) that are +good days to rob the bank. the order that the days are returned in does not +matter +""" + + +class Solution(object): + def goodDaysToRobBank(self, security, time): + """ + :type security: List[int] + :type time: int + :rtype: List[int] + """ + left, right = [1], [1] + n, curr = len(security), 1 + for i in range(1, n): + if security[i] <= security[i - 1]: + curr += 1 + else: + curr = 1 + left.append(curr) + curr = 1 + for i in range(n - 2, -1, -1): + if security[i] <= security[i + 1]: + curr += 1 + else: + curr = 1 + right.append(curr) + right.reverse() + return [i for i in range(n) if left[i] >= time + 1 and right[i] >= time + 1] + + +if __name__ == "__main__": + obj = Solution() + print(obj.goodDaysToRobBank(security=[5, 3, 3, 3, 5, 6, 2], time=2)) + print(obj.goodDaysToRobBank(security=[1, 1, 1, 1, 1], time=0)) + print(obj.goodDaysToRobBank(security=[1, 2, 3, 4, 5, 6], time=2)) |