diff options
-rw-r--r-- | max_total_damage_spell_casting.c | 42 | ||||
-rw-r--r-- | max_total_damage_spell_casting.py | 45 | ||||
-rw-r--r-- | taking_max_energy_mystic_dungeon.c | 35 | ||||
-rw-r--r-- | taking_max_energy_mystic_dungeon.py | 36 |
4 files changed, 158 insertions, 0 deletions
diff --git a/max_total_damage_spell_casting.c b/max_total_damage_spell_casting.c new file mode 100644 index 0000000..d229f6f --- /dev/null +++ b/max_total_damage_spell_casting.c @@ -0,0 +1,42 @@ +// 3186. Maximum Total Damage With Spell Casting +#include "leetcode.h" + +/* + * a magician has various spells. you are given an array 'power', where each + * element represents the damage of a spell. multiple spells can have the same + * damage value. it is a known fact that if a magician decides to cast a spell + * with a damage of 'power[i]', they cannot cast any spell with a damage of + * 'power[i] - 2', 'power[i] - 1', 'power[i] + 1', or 'power[i] + 2'. each spell + * can only be cast once. return the maximum possible total damage that a + * magician can cast. + */ + +long long maximumTotalDamage(int *power, int powerSize) { + long long freq[100001] = {0}, dp[100001] = {0}; + for (int i = 0; i < powerSize; i++) + freq[power[i]]++; + int keys[100001], n = 0; + for (int i = 0; i <= 100000; i++) + if (freq[i]) + keys[n++] = i; + dp[0] = freq[keys[0]] * keys[0]; + for (int i = 1; i < n; i++) { + long long take = freq[keys[i]] * keys[i]; + int prev = -1; + for (int j = i - 1; j >= 0; j--) + if (keys[j] <= keys[i] - 3) { + prev = j; + break; + } + if (prev >= 0) + take += dp[prev]; + dp[i] = dp[i - 1] > take ? dp[i - 1] : take; + } + return dp[n - 1]; +} + +int main() { + int p1[] = {1, 1, 3, 4}, p2[] = {7, 1, 6, 6}; + printf("%lld\n", maximumTotalDamage(p1, ARRAY_SIZE(p1))); // expect: 6 + printf("%lld\n", maximumTotalDamage(p2, ARRAY_SIZE(p2))); // expect: 13 +} diff --git a/max_total_damage_spell_casting.py b/max_total_damage_spell_casting.py new file mode 100644 index 0000000..946bf15 --- /dev/null +++ b/max_total_damage_spell_casting.py @@ -0,0 +1,45 @@ +# 3186. Maximum Total Damage With Spell Casting +from collections import Counter + +""" +a magician has various spells. you are given an array 'power', where each +element represents the damage of a spell. multiple spells can have the same +damage value. it is a known fact that if a magician decides to cast a spell +with a damage of 'power[i]', they cannot cast any spell with a damage of +'power[i] - 2', 'power[i] - 1', 'power[i] + 1', or 'power[i] + 2'. each spell +can only be cast once. return the maximum possible total damage that a +magician can cast. +""" + + +class Solution(object): + def maximumTotalDamage(self, power): + """ + :type power: List[int] + :rtype: int + """ + freq = Counter(power) + keys = sorted(freq) + n = len(keys) + dp = [0] * n + dp[0] = freq[keys[0]] * keys[0] + for i in range(1, n): + take = freq[keys[i]] * keys[i] + l, r, ans = 0, i - 1, -1 + while l <= r: + mid = (l + r) // 2 + if keys[mid] <= keys[i] - 3: + ans = mid + l = mid + 1 + else: + r = mid - 1 + if ans >= 0: + take += dp[ans] + dp[i] = max(dp[i - 1], take) + return dp[-1] + + +if __name__ == "__main__": + obj = Solution() + print(obj.maximumTotalDamage(power=[1, 1, 3, 4])) + print(obj.maximumTotalDamage(power=[7, 1, 6, 6])) diff --git a/taking_max_energy_mystic_dungeon.c b/taking_max_energy_mystic_dungeon.c new file mode 100644 index 0000000..1838d1a --- /dev/null +++ b/taking_max_energy_mystic_dungeon.c @@ -0,0 +1,35 @@ +// 3147. Taking Maximum Energy From the Mystic Dungeon +#include "leetcode.h" + +/* + * in a mystic dungeon, 'n' magicians are standing in a line. each magician has + * an attribute that gives you energe. some magicians can give you negative + * energy, which means taking energy from you. you have been cursed in such a + * way that after absorbing energy from magician 'i', you will be instantly + * transported to magician '(i + k)'. this process will be repeated until you + * reach the magician where '(i + k)' does not exist. in other words, you will + * choose a starting point until you reach the end of the magicians sequence, + * absorbing all the energy during the journey. you are given an array 'energy' + * and an integer 'k'. return the maximum possible energy you can gain. note + * that when you are reach a magician, you must take energy from them, whether + * it is positive or negative. + */ + +int maximumEnergy(int *energy, int energySize, int k) { + int *dp = (int *)malloc(energySize * sizeof(int)); + int ans = INT_MIN; + for (int i = energySize - 1; i >= 0; --i) { + int next = (i + k < energySize) ? dp[i + k] : 0; + dp[i] = energy[i] + next; + if (dp[i] > ans) + ans = dp[i]; + } + free(dp); + return ans; +} + +int main() { + int e1[] = {5, 2, -10, -5, -1}, e2[] = {-2, -3, -1}; + printf("%d\n", maximumEnergy(e1, ARRAY_SIZE(e1), 3)); // expect: 3 + printf("%d\n", maximumEnergy(e2, ARRAY_SIZE(e2), 2)); // expect: -1 +} diff --git a/taking_max_energy_mystic_dungeon.py b/taking_max_energy_mystic_dungeon.py new file mode 100644 index 0000000..a4f39bd --- /dev/null +++ b/taking_max_energy_mystic_dungeon.py @@ -0,0 +1,36 @@ +# 3147. Taking Maximum Energy From the Mystic Dungeon + +""" +in a mystic dungeon, 'n' magicians are standing in a line. each magician has +an attribute that gives you energe. some magicians can give you negative +energy, which means taking energy from you. you have been cursed in such a +way that after absorbing energy from magician 'i', you will be instantly +transported to magician '(i + k)'. this process will be repeated until you +reach the magician where '(i + k)' does not exist. in other words, you will +choose a starting point until you reach the end of the magicians sequence, +absorbing all the energy during the journey. you are given an array 'energy' +and an integer 'k'. return the maximum possible energy you can gain. note +that when you are reach a magician, you must take energy from them, whether +it is positive or negative. +""" + + +class Solution(object): + def maximumEnergy(self, energy, k): + """ + :type energy: List[int] + :type k: int + :rtype: int + """ + ans, n = float("-inf"), len(energy) + dp = [0] * n + for i in range(n - 1, -1, -1): + dp[i] = energy[i] + (dp[i + k] if i + k < n else 0) + ans = max(ans, dp[i]) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.maximumEnergy(energy=[5, 2, -10, -5, 1], k=3)) + print(obj.maximumEnergy(energy=[-2, -3, -1], k=2)) |