Huahua’s Tech Road

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

}

};

花花酱 LeetCode 168. Excel Sheet Column Title

By zxi on November 28, 2021

Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.

For example:

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

Example 1:

Input: columnNumber = 1
Output: "A"

Example 2:

Input: columnNumber = 28
Output: "AB"

Example 3:

Input: columnNumber = 701
Output: "ZY"

Example 4:

Input: columnNumber = 2147483647
Output: "FXSHRXW"

Constraints:

1 <= columnNumber <= 2³¹ - 1

Solution: Base conversion

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

C++

// Author: Huahua

class Solution {

public:

string convertToTitle(int n) {

string ans;

do {

n--;

ans += 'A' + (char)(n % 26);

n /= 26;

} while (n);

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

return ans;

}

};

花花酱 LeetCode 166. Fraction to Recurring Decimal

By zxi on November 28, 2021

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

If multiple answers are possible, return any of them.

It is guaranteed that the length of the answer string is less than 10⁴ for all the given inputs.

Example 1:

Input: numerator = 1, denominator = 2
Output: "0.5"

Example 2:

Input: numerator = 2, denominator = 1
Output: "2"

Example 3:

Input: numerator = 2, denominator = 3
Output: "0.(6)"

Example 4:

Input: numerator = 4, denominator = 333
Output: "0.(012)"

Example 5:

Input: numerator = 1, denominator = 5
Output: "0.2"

Constraints:

-2³¹ <= numerator, denominator <= 2³¹ - 1
denominator != 0

Solution: Hashtable

Time complexity: O(?)

C++

// Author: Huahua

class Solution {

public:

string fractionToDecimal(int numerator, int denominator) {

stringstream ss,ss2;

long long n = numerator;

long long d = denominator;

if ( n > 0 && d < 0 || n < 0 && d > 0) {

ss << "-";

n = abs(n);

d = abs(d);

}

ss << (n / d);

long long r = n % d;

bool loop = false;

int count = 0;

int loop_start;

if (r) {

n = r;

ss << ".";

unordered_map<int, int> rs;

rs[r] = 0;

while (r) {

n = n*10;

r = n % d;

ss2 << (n / d);

n = r;

if (r && rs.count(r)) {

loop = true;

loop_start = rs[r];

break;

}

rs[r] = ++count;

}

if (loop) {

auto s2 = ss2.str();

ss << s2.substr(0, loop_start) << "(" << s2.substr(loop_start) << ")";

} else {

ss << ss2.str();

}

return ss.str();

}

};

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

花花酱 LeetCode 168. Excel Sheet Column Title

Solution: Base conversion

C++

Related Problems

花花酱 LeetCode 166. Fraction to Recurring Decimal

Solution: Hashtable

C++

Huahua's Tech Road

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

花花酱 LeetCode 168. Excel Sheet Column Title

Solution: Base conversion

C++

Related Problems

花花酱 LeetCode 166. Fraction to Recurring Decimal

Solution: Hashtable

C++