diff options
-rw-r--r-- | final_prices_discount.c | 47 | ||||
-rw-r--r-- | final_prices_discount.py | 32 |
2 files changed, 79 insertions, 0 deletions
diff --git a/final_prices_discount.c b/final_prices_discount.c new file mode 100644 index 0000000..488a7d3 --- /dev/null +++ b/final_prices_discount.c @@ -0,0 +1,47 @@ +// 1475. Final Prices With a Special Discount in a Shop +#include "leetcode.h" + +/* + * you are given an integer array 'prices' where 'prices[i]' is the price of the + * i'th item in a shop. there is a special discount for items in the shop. if + * you buy the i'th item, then you will receive a discount equivalent to + * 'prices[j]' where 'j' is the minimum index such that 'j > i' and 'prices[j] + * <= prices[i]'. otherwise, you will not receive any discount at all. return an + * integer array 'answer' where 'answer[i]' is the final price you will pay for + * the i'th item of the shop, considering the special discount + */ + +int *finalPrices(int *prices, int pricesSize, int *returnSize) { + int *ans = (int *)malloc(pricesSize * sizeof(int)); + *returnSize = 0; + for (int i = 0; i < pricesSize; i++) { + bool flag = false; + for (int j = i + 1; j < pricesSize; j++) + if (prices[i] >= prices[j]) { + ans[(*returnSize)++] = prices[i] - prices[j]; + flag = true; + break; + } + if (!flag) + ans[(*returnSize)++] = prices[i]; + } + return ans; +} + +int main() { + int p1[] = {8, 4, 6, 2, 3}, p2[] = {1, 2, 3, 4, 5}, p3[] = {10, 1, 1, 6}; + int rs1, rs2, rs3; + int *fp1 = finalPrices(p1, ARRAY_SIZE(p1), &rs1); + int *fp2 = finalPrices(p2, ARRAY_SIZE(p2), &rs2); + int *fp3 = finalPrices(p3, ARRAY_SIZE(p3), &rs3); + for (int i = 0; i < rs1; i++) + printf("%d ", fp1[i]); // expect: 4 2 4 2 3 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", fp2[i]); // expect: 1 2 3 4 5 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", fp3[i]); // expect: 9 0 1 6 + printf("\n"); + free(fp1), free(fp2), free(fp3); +} diff --git a/final_prices_discount.py b/final_prices_discount.py new file mode 100644 index 0000000..7be4573 --- /dev/null +++ b/final_prices_discount.py @@ -0,0 +1,32 @@ +# 1475. Final Prices With a Special Discount in a Shop + +""" +you are given an integer array 'prices' where 'prices[i]' is the price of the +i'th item in a shop. there is a special discount for items in the shop. if +you buy the i'th item, then you will receive a discount equivalent to +'prices[j]' where 'j' is the minimum index such that 'j > i' and 'prices[j] +<= prices[i]'. otherwise, you will not receive any discount at all. return an +integer array 'answer' where 'answer[i]' is the final price you will pay for +the i'th item of the shop, considering the special discount +""" + + +class Solution(object): + def finalPrices(self, prices): + """ + :type prices: List[int] + :rtype: List[int] + """ + stack = [] + for i, j in enumerate(prices): + while stack and prices[stack[-1]] >= j: + prices[stack.pop()] -= j + stack.append(i) + return prices + + +if __name__ == "__main__": + obj = Solution() + print(obj.finalPrices(prices=[8, 4, 6, 2, 3])) + print(obj.finalPrices(prices=[1, 2, 3, 4, 5])) + print(obj.finalPrices(prices=[10, 1, 1, 6])) |