easy Archives - Page 44 of 75 - Huahua's Tech Road

花花酱 LeetCode 1295. Find Numbers with Even Number of Digits

By zxi on December 26, 2019

Given an array nums of integers, return how many of them contain an even number of digits.

Example 1:

Input: nums = [12,345,2,6,7896]
Output: 2
Explanation: 
12 contains 2 digits (even number of digits). 
345 contains 3 digits (odd number of digits). 
2 contains 1 digit (odd number of digits). 
6 contains 1 digit (odd number of digits). 
7896 contains 4 digits (even number of digits). 
Therefore only 12 and 7896 contain an even number of digits.

Example 2:

Input: nums = [555,901,482,1771]
Output: 1 
Explanation: 
Only 1771 contains an even number of digits.

Constraints:

1 <= nums.length <= 500
1 <= nums[i] <= 10^5

Solution: Math

Time complexity: O(n * log(max(num)))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int findNumbers(vector<int>& nums) {

return count_if(begin(nums), end(nums), [](int num) {

int d = 0;

do { ++d; } while (num /= 10);

return d % 2 == 0;

});

}

};

Python3

# Author: Huahua

class Solution:

def findNumbers(self, nums: List[int]) -> int:

return sum([len(str(x)) % 2 == 0 for x in nums])

花花酱 LeetCode 1287. Element Appearing More Than 25% In Sorted Array

By zxi on December 14, 2019

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time.

Return that integer.

Example 1:

1 2	<strong>Input:</strong> arr = [1,2,2,6,6,6,6,7,10] <strong>Output:</strong> 6

Constraints:

1 <= arr.length <= 10^4
0 <= arr[i] <= 10^5

Solution 1: Linear Scan

if arr[i] == arr[i + len/4] => arr[i] is the special integer.

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

C++

// Author: Huahua

class Solution {

public:

int findSpecialInteger(vector<int>& arr) {

int s = arr.size() / 4;

for (int i = 0; i + s < arr.size(); ++i)

if (arr[i] == arr[i + s]) return arr[i];

return -1;

}

};

Solution 2: Binary Search

The answer must be one of (s[0], s[l/4], s[l/2], s[l*3/4])
Using binary search to find the range of each number, the one has more than 1/4 of total elements is the answer.

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

C++

// Author: Huahua

class Solution {

public:

int findSpecialInteger(vector<int>& arr) {

const int s = arr.size() / 4;

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

const int x = arr[i * s];

const auto [it1, it2] = equal_range(begin(arr), end(arr), x);

if (it2 - it1 > s) return x;

}

return -1;

}

};

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

}

};

Posts tagged as “easy”

花花酱 LeetCode 1295. Find Numbers with Even Number of Digits

Solution: Math

C++

Python3

花花酱 LeetCode 1287. Element Appearing More Than 25% In Sorted Array

Solution 1: Linear Scan

C++

Solution 2: Binary Search

C++

花花酱 LeetCode 405. Convert a Number to Hexadecimal

Solution: Simulation

C++

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

Solution: Simulation

C++

花花酱 LeetCode 1271. Hexspeak

Solution: Simulation

C++