Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.
Note:
You can assume that you can always reach the last index.
Alex and Lee play a game with piles of stones. There are an even number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].
The objective of the game is to end with the most stones. The total number of stones is odd, so there are no ties.
Alex and Lee take turns, with Alex starting first. Each turn, a player takes the entire pile of stones from either the beginning or the end of the row. This continues until there are no more piles left, at which point the person with the most stones wins.
Assuming Alex and Lee play optimally, return True if and only if Alex wins the game.
Example 1:
Input: [5,3,4,5]Output: trueExplanation:
Alex starts first, and can only take the first 5 or the last 5.
Say he takes the first 5, so that the row becomes [3, 4, 5].
If Lee takes 3, then the board is [4, 5], and Alex takes 5 to win with 10 points.
If Lee takes the last 5, then the board is [3, 4], and Alex takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alex, so we return true.
Note:
2 <= piles.length <= 500
piles.length is even.
1 <= piles[i] <= 500
sum(piles) is odd.
Solution 1: min-max (TLE)
Time complexity: O(2^n)
Space complexity: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Author: Huahua
// Running time: TLE 26/46 passed.
classSolution{
public:
boolstoneGame(vector<int>&piles){
returnscore(piles,0,piles.size()-1)>0;
}
private:
intscore(constvector<int>&piles,intl,intr){
if(l==r)returnpiles[l];
returnmax(piles[l]-score(piles,l+1,r),
piles[r]-score(piles,l,r-1));
}
};
Solution 2: min-max + memorization
Time complexity: O(n^2)
Space complexity: O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Author: Huahua
// Running time: 12 ms
classSolution{
public:
boolstoneGame(vector<int>&piles){
constintn=piles.size();
m_=vector<vector<int>>(n,vector<int>(n,INT_MIN));
returnscore(piles,0,n-1)>0;
}
private:
vector<vector<int>>m_;
intscore(constvector<int>&piles,intl,intr){
if(l==r)returnpiles[l];
if(m_[l][r]==INT_MIN)
m_[l][r]=max(piles[l]-score(piles,l+1,r),
piles[r]-score(piles,l,r-1));
returnm_[l][r];
}
};
Solution 3: min-max + DP
Time complexity: O(n^2)
Space complexity: O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Author: Huahua
// Running time: 8 ms
classSolution{
public:
boolstoneGame(vector<int>&piles){
constintn=piles.size();
// dp[i][j] := max(your_stones - op_stones) for piles[i] ~ piles[j]
A Tic-Tac-Toe board is given as a string array board. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.
The board is a 3 x 3 array, and consists of characters " ", "X", and "O". The ” ” character represents an empty square.
Here are the rules of Tic-Tac-Toe:
Players take turns placing characters into empty squares (” “).
The first player always places “X” characters, while the second player always places “O” characters.
“X” and “O” characters are always placed into empty squares, never filled ones.
The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
The game also ends if all squares are non-empty.
No more moves can be played if the game is over.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Example1:
Input:board=["O "," "," "]
Output:false
Explanation:The first player always plays"X".
Example2:
Input:board=["XOX"," X "," "]
Output:false
Explanation:Players take turns making moves.
Example3:
Input:board=["XXX"," ","OOO"]
Output:false
Example4:
Input:board=["XOX","O O","XOX"]
Output:true
Note:
board is a length-3 array of strings, where each string board[i] has length 3.
Each board[i][j] is a character in the set {" ", "X", "O"}.
Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.
Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.
Example 1:
Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2.
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.
Hence, player 1 will never be the winner and you need to return False.
Example 2:
Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
Note:
1 <= length of the array <= 20.
Any scores in the given array are non-negative integers and will not exceed 10,000,000.
If the scores of both players are equal, then player 1 is still the winner.
Solution 1: Recursion
Time complexity: O(2^n)
Space complexity: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Author: Huahua
// Running time: 67 ms
classSolution{
public:
boolPredictTheWinner(vector<int>&nums){
returngetScore(nums,0,nums.size()-1)>=0;
}
private:
// Max diff (my_score - op_score) of subarray nums[l] ~ nums[r].
