花花酱 LeetCode 868. Binary Gap

By zxi on July 14, 2018

Problem

Given a positive integer N, find and return the longest distance between two consecutive 1’s in the binary representation of N.

If there aren’t two consecutive 1’s, return 0.

Example 1:

Input: 22
Output: 2
Explanation: 
22 in binary is 0b10110.
In the binary representation of 22, there are three ones, and two consecutive pairs of 1's.
The first consecutive pair of 1's have distance 2.
The second consecutive pair of 1's have distance 1.
The answer is the largest of these two distances, which is 2.

Example 2:

Input: 5
Output: 2
Explanation: 
5 in binary is 0b101.

Example 3:

Input: 6
Output: 1
Explanation: 
6 in binary is 0b110.

Example 4:

Input: 8
Output: 0
Explanation: 
8 in binary is 0b1000.
There aren't any consecutive pairs of 1's in the binary representation of 8, so we return 0.\

Note:

1 <= N <= 10^9

Solution: Bit

Time complexity: O(logN)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int binaryGap(int N) {

int l = -1;

int ans = 0;

for (int i = 0; i < 31; ++i)

if (N & (1 << i)) {

if (l >= 0)

ans = max(ans, i - l);

l = i;

}

return ans;

}

};

花花酱 LeetCode 559. Maximum Depth of N-ary Tree

By zxi on July 14, 2018

Problem

Given a n-ary 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.

For example, given a 3-ary tree:

We should return its max depth, which is 3.

Note:

The depth of the tree is at most 1000.
The total number of nodes is at most 5000.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 40 ms

class Solution {

public:

int maxDepth(Node* root) {

if (root == nullptr) return 0;

int depth = 0;

for (auto child : root->children)

depth = max(depth, maxDepth(child));

return depth + 1;

}

};

Problem

Given an n-ary tree, return the postorder traversal of its nodes’ values.

For example, given a 3-ary tree:

Return its postorder traversal as: [5,6,3,2,4,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution 1: Recursive

C++

// Author: Huahua

// Running time: 44 ms

class Solution {

public:

vector<int> postorder(Node* root) {

vector<int> ans;

postorder(root, ans);

return ans;

}

private:

void postorder(Node* root, vector<int>& ans) {

if (!root) return;

for (auto child : root->children)

postorder(child, ans);

ans.push_back(root->val);

}

};

Solution 2: Iterative

C++

// Author: Huahua

// Running time: 44 ms

class Solution {

public:

vector<int> postorder(Node* root) {

if (!root) return {};

vector<int> ans;

stack<Node*> s;

s.push(root);

while (!s.empty()) {

const Node* node = s.top(); s.pop();

ans.push_back(node->val);

for (auto child : node->children)

s.push(child);

}

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

return ans;

}

};

Problem

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Your KthLargest class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method KthLargest.add, return the element representing the kth largest element in the stream.

Example:

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8

Note:
You may assume that nums‘ length ≥ k-1 and k ≥ 1.

Solution: BST / Min Heap

Time complexity: O(nlogk)

Space complexity: O(k)

C++ / BST

// Author: Huahua

// Running time: 32 ms

class KthLargest {

public:

KthLargest(int k, vector<int> nums): k_(k) {

for (int num : nums)

add(num);

}

int add(int val) {

s_.insert(val);

if (s_.size() > k_)

s_.erase(s_.begin());

return *s_.begin();

}

private:

const int k_;

multiset<int> s_;

};

C++ / Min Heap

// Author: Huahua

// Running time: 28 ms

class KthLargest {

public:

KthLargest(int k, vector<int> nums): k_(k) {

for (int num : nums)

add(num);

}

int add(int val) {

s_.push(val);

if (s_.size() > k_)

s_.pop();

return s_.top();

}

private:

const int k_;

priority_queue<int, vector<int>, greater<int>> s_; // min heap

};

花花酱 LeetCode 700. Search in a Binary Search Tree

By zxi on July 12, 2018

Problem

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node’s value equals the given value. Return the subtree rooted with that node. If such node doesn’t exist, you should return NULL.

For example,

Given the tree:
        4
       / \
      2   7
     / \
    1   3

And the value to search: 2

You should return this subtree:

      2     
     / \   
    1   3

In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.

Solution: Recursion

Time complexity: O(logn ~ n)

Space complexity: O(logn ~ n)

// Author: Huahua

// Running time: 24 ms

class Solution {

public:

TreeNode* searchBST(TreeNode* root, int val) {

if (root == nullptr) return nullptr;

if (val == root->val)

return root;

else if (val > root->val)

return searchBST(root->right, val);

return searchBST(root->left, val);

}

};

Posts tagged as “easy”

花花酱 LeetCode 868. Binary Gap

Problem

Solution: Bit

花花酱 LeetCode 559. Maximum Depth of N-ary Tree

Problem

Solution: Recursion

Related Problems

花花酱 LeetCode 590. N-ary Tree Postorder Traversal

Problem

Solution 1: Recursive

C++

Solution 2: Iterative

C++

Related Problems

花花酱 LeetCode 703. Kth Largest Element in a Stream

Problem

Solution: BST / Min Heap

花花酱 LeetCode 700. Search in a Binary Search Tree

Problem

Solution: Recursion