Posts tagged as “easy”

花花酱 LeetCode 405. Convert a Number to Hexadecimal

By zxi on December 7, 2019

Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.

Note:

All letters in hexadecimal (a-f) must be in lowercase.
The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character ‘0’; otherwise, the first character in the hexadecimal string will not be the zero character.
The given number is guaranteed to fit within the range of a 32-bit signed integer.
You must not use any method provided by the library which converts/formats the number to hex directly.
Example 1:

Input:
26

Output:
“1a”
Example 2:

Input:
-1

Output:
“ffffffff”

Solution: Simulation

if input is negative, add 2^32 to it (e.g. set the highest bit to 1)
while num is non zero, mod it by 16 and prepend the remainder to ans string, then divide num by 16.

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

C++

// Author: Huahua

constexpr char kHex[] = "0123456789abcdef";

class Solution {

public:

string toHex(int num) {

if (num == 0) return "0";

long t = num < 0 ? (1LL << 32) + num : num;

string ans;

while (t) {

ans = kHex[t % 16] + ans;

t /= 16;

}

return ans;

}

};

花花酱 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 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;

}

};

花花酱 LeetCode 1266. Minimum Time Visiting All Points

By zxi on November 23, 2019

On a plane there are n points with integer coordinates points[i] = [xi, yi]. Your task is to find the minimum time in seconds to visit all points.

You can move according to the next rules:

In one second always you can either move vertically, horizontally by one unit or diagonally (it means to move one unit vertically and one unit horizontally in one second).
You have to visit the points in the same order as they appear in the array.

Example 1:

Input: points = [[1,1],[3,4],[-1,0]]
Output: 7
Explanation: One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]   
Time from [1,1] to [3,4] = 3 seconds 
Time from [3,4] to [-1,0] = 4 seconds
Total time = 7 seconds

Example 2:

Input: points = [[3,2],[-2,2]]
Output: 5

Constraints:

points.length == n
1 <= n <= 100
points[i].length == 2
-1000 <= points[i][0], points[i][1] <= 1000

Solution: Geometry + Greedy

dx = abs(x1 – x2)
dy = abs(y1 – y2)

go diagonally first for min(dx, dy) steps, and then go straight line for abs(dx – dy) steps.

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

C++

// Author: Huahua

class Solution {

public:

int minTimeToVisitAllPoints(vector<vector<int>>& points) {

int ans = 0;

for (size_t i = 1; i < points.size(); ++i) {

int dx = abs(points[i - 1][0] - points[i][0]);

int dy = abs(points[i - 1][1] - points[i][1]);

ans += min(dx, dy) + abs(dx - dy);

}

return ans;

}

};

花花酱 LeetCode 1237. Find Positive Integer Solution for a Given Equation

By zxi on October 27, 2019

Given a function f(x, y) and a value z, return all positive integer pairs x and y where f(x,y) == z.

The function is constantly increasing, i.e.:

f(x, y) < f(x + 1, y)
f(x, y) < f(x, y + 1)

The function interface is defined like this:

interface CustomFunction {
public:
  // Returns positive integer f(x, y) for any given positive integer x and y.
  int f(int x, int y);
};

For custom testing purposes you’re given an integer function_id and a target z as input, where function_id represent one function from an secret internal list, on the examples you’ll know only two functions from the list.

You may return the solutions in any order.

Example 1:

Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]
Explanation: function_id = 1 means that f(x, y) = x + y

Example 2:

Input: function_id = 2, z = 5
Output: [[1,5],[5,1]]
Explanation: function_id = 2 means that f(x, y) = x * y

Constraints:

1 <= function_id <= 9
1 <= z <= 100
It’s guaranteed that the solutions of f(x, y) == z will be on the range 1 <= x, y <= 1000
It’s also guaranteed that f(x, y) will fit in 32 bit signed integer if 1 <= x, y <= 1000

Solution1 : Brute Force

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {

vector<vector<int>> ans;

for (int x = 1; x <= 1000; ++x) {

if (customfunction.f(x, 1) > z) break;

for (int y = 1; y <= 1000; ++y) {

int t = customfunction.f(x, y);

if (t > z) break;

if (t == z) ans.push_back({x, y});

}

return ans;

}

};