Posts tagged as “easy”

花花酱 LeetCode 231. Power of Two

By zxi on December 7, 2021

Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2^x.

Example 1:

Input: n = 1
Output: true
Explanation: 2⁰ = 1

Example 2:

Input: n = 16
Output: true
Explanation: 2⁴ = 16

Example 3:

Input: n = 3
Output: false

Example 4:

Input: n = 4
Output: true

Example 5:

Input: n = 5
Output: false

Constraints:

-2³¹ <= n <= 2³¹ - 1

Solution: 1 bit set

Any power of two has only 1 bit set in the binary format. e.g. 1=0b01, 2=0b10, 4=0b100, 8=0b1000

use popcount.

C++

// Author: Huahua

class Solution {

public:

bool isPowerOfTwo(int n) {

return n > 0 ? __builtin_popcount(n) == 1 : false;

}

};

2. Use (n) & (n – 1) to remove the last set bit, so it should be zero.

C++

// Author: Huahua

class Solution {

public:

bool isPowerOfTwo(int n) {

return n > 0 ? !(n & (n - 1)) : false;

}

};

花花酱 LeetCode 2094. Finding 3-Digit Even Numbers

By zxi on December 4, 2021

You are given an integer array digits, where each element is a digit. The array may contain duplicates.

You need to find all the unique integers that follow the given requirements:

The integer consists of the concatenation of three elements from digits in any arbitrary order.
The integer does not have leading zeros.
The integer is even.

For example, if the given digits were [1, 2, 3], integers 132 and 312 follow the requirements.

Return a sorted array of the unique integers.

Example 1:

Input: digits = [2,1,3,0]
Output: [102,120,130,132,210,230,302,310,312,320]
Explanation: 
All the possible integers that follow the requirements are in the output array. 
Notice that there are no odd integers or integers with leading zeros.

Example 2:

Input: digits = [2,2,8,8,2]
Output: [222,228,282,288,822,828,882]
Explanation: 
The same digit can be used as many times as it appears in digits. 
In this example, the digit 8 is used twice each time in 288, 828, and 882.

Example 3:

Input: digits = [3,7,5]
Output: []
Explanation: 
No even integers can be formed using the given digits.

Example 4:

Input: digits = [0,2,0,0]
Output: [200]
Explanation: 
The only valid integer that can be formed with three digits and no leading zeros is 200.

Example 5:

Input: digits = [0,0,0]
Output: []
Explanation: 
All the integers that can be formed have leading zeros. Thus, there are no valid integers.

Constraints:

3 <= digits.length <= 100
0 <= digits[i] <= 9

Solution: Enumerate all three digits even numbers

Check 100, 102, … 998. Use a hashtable to check whether all digits are covered by the given digits.

Time complexity: O(1000*lg(1000))
Space complexity: O(10)

C++

// Author: Huahua

class Solution {

public:

vector<int> findEvenNumbers(vector<int>& digits) {

vector<int> counts(10);

for (int d : digits) ++counts[d];

vector<int> ans;

for (int x = 100; x < 1000; x += 2) {

bool valid = true;

vector<int> c(10);

for (int t = x; t > 0; t /= 10)

valid &= (++c[t % 10] <= counts[t % 10]);

if (valid) ans.push_back(x);

}

return ans;

}

};

花花酱 LeetCode 199. Binary Tree Right Side View

By zxi on November 28, 2021

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

Example 2:

Input: root = [1,null,3]
Output: [1,3]

Example 3:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Solution: Pre-order traversal

By using pre-order traversal, the right most node will be the last one to visit in each level.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> rightSideView(TreeNode* root) {

vector<int> ans;

function<void(TreeNode*, int)> dfs = [&](TreeNode* root, int d) {

if (!root) return;

if (ans.size() < d + 1) ans.push_back(0);

ans[d] = root->val;

dfs(root->left, d + 1);

dfs(root->right, d + 1);

};

dfs(root, 0);

return ans;

}

};

花花酱 LeetCode 191. Number of 1 Bits

By zxi on November 28, 2021

Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).

Note:

Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3, the input represents the signed integer. -3.

Example 1:

Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:

Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:

Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

Constraints:

The input must be a binary string of length 32.

Follow up: If this function is called many times, how would you optimize it?

Solution: Bit Operation

Use n & 1 to get the lowest bit of n.
Use n >>= 1 to right shift n for 1 bit, e.g. removing the last bit.

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

C++

// Author: Huahua

class Solution {

public:

int hammingWeight(uint32_t n) {

int ans = 0;

while (n) {

ans += n & 1;

n >>= 1;

}

return ans;

}

};

花花酱 LeetCode 171. Excel Sheet Column Number

By zxi on November 28, 2021

Given a string columnTitle that represents the column title as appear in an Excel sheet, return its corresponding column number.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

Example 1:

Input: columnTitle = "A"
Output: 1

Example 2:

Input: columnTitle = "AB"
Output: 28

Example 3:

Input: columnTitle = "ZY"
Output: 701

Example 4:

Input: columnTitle = "FXSHRXW"
Output: 2147483647

Constraints:

1 <= columnTitle.length <= 7
columnTitle consists only of uppercase English letters.
columnTitle is in the range ["A", "FXSHRXW"].

Solution: Base conversion

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

C++

// Author: Huahua

class Solution {

public:

int titleToNumber(string s) {

int ans = 0;

for (int i = s.length() - 1, cur = 0; i >= 0; --i) {

cur = cur ? cur * 26 : 1;

ans += (s[i] - 'A' + 1) * cur;

}

return ans;

}

};

Posts tagged as “easy”

花花酱 LeetCode 231. Power of Two

Solution: 1 bit set

C++

C++

花花酱 LeetCode 2094. Finding 3-Digit Even Numbers

Solution: Enumerate all three digits even numbers

C++

花花酱 LeetCode 199. Binary Tree Right Side View

Solution: Pre-order traversal

C++

花花酱 LeetCode 191. Number of 1 Bits

Solution: Bit Operation

C++

花花酱 LeetCode 171. Excel Sheet Column Number

Solution: Base conversion

C++

Related Problems