Huahua’s Tech Road

花花酱 LeetCode 1275. Find Winner on a Tic Tac Toe Game

By zxi on December 1, 2019

Tic-tac-toe is played by two players A and B on a 3 x 3 grid.

Here are the rules of Tic-Tac-Toe:

Players take turns placing characters into empty squares (” “).
The first player A always places “X” characters, while the second player B always places “O” characters.
“X” and “O” characters are always placed into empty squares, never on 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.

Given an array moves where each element is another array of size 2 corresponding to the row and column of the grid where they mark their respective character in the order in which A and B play.

Return the winner of the game if it exists (A or B), in case the game ends in a draw return “Draw”, if there are still movements to play return “Pending”.

You can assume that moves is valid (It follows the rules of Tic-Tac-Toe), the grid is initially empty and A will play first.

Example 1:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"
Explanation: "A" wins, he always plays first.
"X  "    "X  "    "X  "    "X  "    "X  "
"   " -> "   " -> " X " -> " X " -> " X "
"   "    "O  "    "O  "    "OO "    "OOX"

Example 2:

Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: "B"
Explanation: "B" wins.
"X  "    "X  "    "XX "    "XXO"    "XXO"    "XXO"
"   " -> " O " -> " O " -> " O " -> "XO " -> "XO " 
"   "    "   "    "   "    "   "    "   "    "O  "

Example 3:

Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Output: "Draw"
Explanation: The game ends in a draw since there are no moves to make.
"XXO"
"OOX"
"XOX"

Example 4:

Input: moves = [[0,0],[1,1]]
Output: "Pending"
Explanation: The game has not finished yet.
"X  "
" O "
"   "

Constraints:

1 <= moves.length <= 9
moves[i].length == 2
0 <= moves[i][j] <= 2
There are no repeated elements on moves.
moves follow the rules of tic tac toe.

Solution: Simulation

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

string tictactoe(vector<vector<int>>& moves) {

vector<vector<string>> b(3, vector<string>(3, "#"));

bool A = true;

for (const auto& move : moves) {

b[move[0]][move[1]] = A ? "A" : "B";

A = !A;

}

for (int i = 0; i < 3; ++i) {

if (b[i][0] == b[i][1] && b[i][2] == b[i][1] && b[i][0] != "#")

return b[i][0];

if (b[0][i] == b[1][i] && b[2][i] == b[1][i] && b[0][i] != "#")

return b[0][i];

}

if (b[0][0] == b[1][1] && b[1][1] == b[2][2] && b[1][1] != "#")

return b[1][1];

if (b[2][0] == b[1][1] && b[1][1] == b[0][2] && b[1][1] != "#")

return b[1][1];

return moves.size() == 9 ? "Draw" : "Pending";

}

};

花花酱 LeetCode 1274. Number of Ships in a Rectangle

By zxi on December 1, 2019

(This problem is an interactive problem.)

On the sea represented by a cartesian plane, each ship is located at an integer point, and each integer point may contain at most 1 ship.

You have a function Sea.hasShips(topRight, bottomLeft) which takes two points as arguments and returns true if and only if there is at least one ship in the rectangle represented by the two points, including on the boundary.

Given two points, which are the top right and bottom left corners of a rectangle, return the number of ships present in that rectangle. It is guaranteed that there are at most 10 ships in that rectangle.

Submissions making more than 400 calls to hasShips will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

Example :

Input: 
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3
Explanation: From [0,0] to [4,4] we can count 3 ships within the range.

Constraints:

On the input ships is only given to initialize the map internally. You must solve this problem “blindfolded”. In other words, you must find the answer using the given hasShips API, without knowing the ships position.
0 <= bottomLeft[0] <= topRight[0] <= 1000
0 <= bottomLeft[1] <= topRight[1] <= 1000

Solution: Divide and Conquer

If the current rectangle contains ships, subdivide it into 4 smaller ones until
1) no ships contained
2) the current rectangle is a single point (e.g. topRight == bottomRight)

Time complexity: O(logn)
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

// Modify the interface to pass sea as a reference.

int countShips(Sea& sea, vector<int> topRight, vector<int> bottomLeft) {

int x1 = bottomLeft[0], y1 = bottomLeft[1];

int x2 = topRight[0], y2 = topRight[1];

if (x1 > x2 || y1 > y2 || !sea.hasShips(topRight, bottomLeft))

return 0;

if (x1 == x2 && y1 == y2)

return 1;

int xm = x1 + (x2 - x1) / 2;

int ym = y1 + (y2 - y1) / 2;

return countShips(sea, {xm, ym}, {x1, y1}) + countShips(sea, {xm, y2}, {x1, ym + 1})

+ countShips(sea, {x2, ym}, {xm + 1, y1}) + countShips(sea, {x2, y2}, {xm + 1, ym + 1});

}

};

花花酱 LeetCode 1273. Delete Tree Nodes

By zxi on November 30, 2019

A tree rooted at node 0 is given as follows:

The number of nodes is nodes;
The value of the i-th node is value[i];
The parent of the i-th node is parent[i].

Remove every subtree whose sum of values of nodes is zero.

After doing so, return the number of nodes remaining in the tree.

Example 1:

Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
Output: 2

Constraints:

1 <= nodes <= 10^4
-10^5 <= value[i] <= 10^5
parent.length == nodes
parent[0] == -1 which indicates that 0 is the root.

Solution: Inorder Traversal

For each node, return the sum of all its subtrees and number of nodes including itself after removal.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int deleteTreeNodes(int nodes, vector<int>& parent, vector<int>& value) {

vector<vector<int>> g(nodes);

for (int i = 1; i < nodes; ++i)

g[parent[i]].push_back(i);

// Returns <sum, nodes> of subtree n.

function<pair<int,int>(int)> traverse = [&](int n) {

int sum = value[n];

int count = 1;

for (int x : g[n]) {

auto [s, c] = traverse(x);

sum += s;

count += s ? c : 0;

}

return make_pair(sum, sum ? count : 0);

};

return traverse(0).second;

}

};

花花酱 LeetCode 1272. Remove Interval

By zxi on November 30, 2019

Given a sorted list of disjoint intervals, each interval intervals[i] = [a, b] represents the set of real numbers x such that a <= x < b.

We remove the intersections between any interval in intervals and the interval toBeRemoved.

Return a sorted list of intervals after all such removals.

Example 1:

Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
Output: [[0,1],[6,7]]

Example 2:

Input: intervals = [[0,5]], toBeRemoved = [2,3]
Output: [[0,2],[3,5]]

Constraints:

1 <= intervals.length <= 10^4
-10^9 <= intervals[i][0] < intervals[i][1] <= 10^9

Solution: Geometry

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& r) {

vector<vector<int>> ans;

for (const auto& i : intervals)

// Does not intersect

if (i[1] <= r[0] || i[0] >= r[1])

ans.push_back(i);

else {

// i starts first

if (i[0] < r[0])

ans.push_back({i[0], r[0]});

// i ends later

if (i[1] > r[1])

ans.push_back({r[1], i[1]});

}

return ans;

}

};

花花酱 LeetCode 1271. Hexspeak

By zxi on November 30, 2019

A decimal number can be converted to its Hexspeak representation by first converting it to an uppercase hexadecimal string, then replacing all occurrences of the digit 0 with the letter O, and the digit 1 with the letter I. Such a representation is valid if and only if it consists only of the letters in the set {"A", "B", "C", "D", "E", "F", "I", "O"}.

Given a string num representing a decimal integer N, return the Hexspeak representation of N if it is valid, otherwise return "ERROR".

Example 1:

Input: num = "257"
Output: "IOI"
Explanation:  257 is 101 in hexadecimal.

Example 2:

Input: num = "3"
Output: "ERROR"

Constraints:

1 <= N <= 10^12
There are no leading zeros in the given string.
All answers must be in uppercase letters.

Solution: Simulation

Time complexity: O(logn)
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

string toHexspeak(string num) {

long n = stol(num);

string ans;

while (n) {

int r = n % 16;

char c;

if (r == 0) c = 'O';

else if (r == 1) c = 'I';

else if (r >= 10 && r <= 15) c = 'A' + r - 10;

else return "ERROR";

ans += c;

n >>= 4;

}

reverse(begin(ans), end(ans));

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1275. Find Winner on a Tic Tac Toe Game

Solution: Simulation

C++

花花酱 LeetCode 1274. Number of Ships in a Rectangle

Solution: Divide and Conquer

C++

花花酱 LeetCode 1273. Delete Tree Nodes

Solution: Inorder Traversal

C++

花花酱 LeetCode 1272. Remove Interval

Solution: Geometry

C++

花花酱 LeetCode 1271. Hexspeak

Solution: Simulation

C++