aboutsummaryrefslogtreecommitdiff
path: root/other/predict_winner.cpp
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
committerJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
commit7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch)
treeeb7a24ee2067f92245c57bb118e85a1baf15df50 /other/predict_winner.cpp
parent5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff)
downloadleetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz
leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip
chore: move cpp and rust code to directory
Diffstat (limited to 'other/predict_winner.cpp')
-rw-r--r--other/predict_winner.cpp40
1 files changed, 40 insertions, 0 deletions
diff --git a/other/predict_winner.cpp b/other/predict_winner.cpp
new file mode 100644
index 0000000..edf9ee3
--- /dev/null
+++ b/other/predict_winner.cpp
@@ -0,0 +1,40 @@
+// 486. Predict the Winner
+#include "leetcode.h"
+
+/*
+ * given an integer array 'nums'. two players are playing a game with this
+ * array: player 1 and player 2. player 1 and player 2 take turns, with player 1
+ * starting first. both players start the game with a score of zero. at each
+ * turn, the player takes one of the numbers from either end of the array (ie.
+ * 'nums[0]', or 'nums[nums.len - 1]') which reduces the size of the array by
+ * one. the player adds the chosen number to their score. the game ends when
+ * there are no more elements in the array. return 'true' if player 1 can win
+ * the game. if the scores of both players are equal, then player 1 is still the
+ * winner, and you should also return 'true'. you may assume that both players
+ * are playing optimally.
+ */
+
+class Solution {
+ bool check_win(int ans, int total) { return ans >= total - ans; }
+ int max_score(vector<int> &nums, int total, int i, int j) {
+ if (i > j)
+ return 0;
+ return total - min(max_score(nums, total - nums[i], i + 1, j),
+ max_score(nums, total - nums[j], i, j - 1));
+ }
+
+public:
+ bool PredictTheWinner(vector<int> &nums) {
+ int total = 0;
+ for (auto i : nums)
+ total += i;
+ return check_win(max_score(nums, total, 0, nums.size() - 1), total);
+ }
+};
+
+int main() {
+ Solution obj;
+ vector<int> n1 = {1, 5, 2}, n2 = {1, 5, 233, 7};
+ printf("%d\n", obj.PredictTheWinner(n1)); // expect: 0
+ printf("%d\n", obj.PredictTheWinner(n2)); // expect: 1
+}