花花酱 LeetCode 970. Powerful Integers

By zxi on January 5, 2019

Given two non-negative integers x and y, an integer is powerful if it is equal to x^i + y^j for some integers i >= 0 and j >= 0.

Return a list of all powerful integers that have value less than or equal to bound.

You may return the answer in any order. In your answer, each value should occur at most once.

Example 1:

Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation: 
2 = 2^0 + 3^0
3 = 2^1 + 3^0
4 = 2^0 + 3^1
5 = 2^1 + 3^1
7 = 2^2 + 3^1
9 = 2^3 + 3^0
10 = 2^0 + 3^2

Example 2:

Input: x = 3, y = 5, bound = 15
Output: [2,4,6,8,10,14]

Note:

1 <= x <= 100
1 <= y <= 100
0 <= bound <= 10^6

Solution: Brute Force

Time complexity: O(log(bound) / log(x) * log(bound) / log(y))
Space complexity: O(log(bound) / log(x) * log(bound) / log(y))

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

vector<int> powerfulIntegers(int x, int y, int bound) {

unordered_set<int> ans;

for (int a = 1; a < bound; a *= x) {

for (int b = 1; a + b <= bound; b *= y) {

ans.insert(a + b);

if (y == 1) break;

}

if (x == 1) break;

}

return {begin(ans), end(ans)};

}

};

花花酱 LeetCode 965. Univalued Binary Tree

By zxi on December 30, 2018

Problem

A binary tree is univalued if every node in the tree has the same value.

Return true if and only if the given tree is univalued.

Example 1:

Input: [1,1,1,1,1,null,1]
Output: true

Example 2:

Input: [2,2,2,5,2]
Output: false

Note:

The number of nodes in the given tree will be in the range [1, 100].
Each node’s value will be an integer in the range [0, 99].

Solution: Recursion

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

C++

// Author: Huahua, running time: 0 ms

class Solution {

public:

bool isUnivalTree(TreeNode* root) {

if (!root) return true;

if (root->left && root->val != root->left->val) return false;

if (root->right && root->val != root->right->val) return false;

return isUnivalTree(root->left) && isUnivalTree(root->right);

}

};

Python3

# Author: Huahua, running time: 68 ms

class Solution:

def isUnivalTree(self, root):

if not root: return True

if root.left and root.left.val != root.val: return False

if root.right and root.right.val != root.val: return False

return self.isUnivalTree(root.left) and self.isUnivalTree(root.right)

花花酱 LeetCode 961. N-Repeated Element in Size 2N Array

By zxi on December 23, 2018

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.

Return the element repeated N times.

Example 1:

Input: [1,2,3,3]
Output: 3

Example 2:

Input: [2,1,2,5,3,2]
Output: 2

Example 3:

Input: [5,1,5,2,5,3,5,4]
Output: 5

Note:

4 <= A.length <= 10000
0 <= A[i] < 10000
A.length is even

Solution: Randomization

Randomly pick two numbers in the array, if they are the same (25% probability) return the number, do it until the two numbers are the same.

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

C++

// Author: Huahua, running time: 72 ms

class Solution {

public:

int repeatedNTimes(vector<int>& A) {

int i = 0;

int j = 0;

while (i == j || A[i] != A[j]) {

i = rand() % A.size();

j = rand() % A.size();

}

return A[i];

}

};

花花酱 LeetCode 111. Minimum Depth of Binary Tree

By zxi on December 15, 2018

Problem

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

return its minimum depth = 2.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 4 ms

class Solution {

public:

int minDepth(TreeNode* root) {

if (!root) return 0;

if (!root->left && !root->right) return 1;

int l = root->left ? minDepth(root->left) : INT_MAX;

int r = root->right ? minDepth(root->right) : INT_MAX;

return min(l, r) + 1;

}

};

Python3

class Solution:

def minDepth(self, root):

if not root: return 0

if not root.left and not root.right: return 1

l = self.minDepth(root.left)

r = self.minDepth(root.right)

if not root.left: return 1 + r

if not root.right: return 1 + l

return 1 + min(l, r)

Problem

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

return its depth = 3.

Solution: Recursion

maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right)) + 1

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 4 ms

class Solution {

public:

int maxDepth(TreeNode* root) {

if (!root) return 0;

int l = maxDepth(root->left);

int r = maxDepth(root->right);

return max(l, r) + 1;

}

};

Python3

# Author: Huahua, 80 ms

class Solution:

def maxDepth(self, root):

if not root: return 0

l = self.maxDepth(root.left)

r = self.maxDepth(root.right)

return max(l, r) + 1

Posts tagged as “easy”

花花酱 LeetCode 970. Powerful Integers

Solution: Brute Force

C++

花花酱 LeetCode 965. Univalued Binary Tree

Problem

Solution: Recursion

C++

Python3

Related Problems

花花酱 LeetCode 961. N-Repeated Element in Size 2N Array

Solution: Randomization

C++

花花酱 LeetCode 111. Minimum Depth of Binary Tree

Problem

Solution: Recursion

C++

Python3

Related Problem

花花酱 LeetCode 104. Maximum Depth of Binary Tree

Problem

Solution: Recursion

C++

Python3