Posts tagged as “medium”

花花酱 LeetCode 17. Letter Combinations of a Phone Number

By zxi on December 29, 2017

题目大意：给你一串电话号码，输出可以由这串电话号码打出的所有字符串。

Problem:

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

1 2	Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Solution 1: DFS

C++

// Author: Huahua

// Runtime: 0 ms

class Solution {

public:

vector<string> letterCombinations(string digits) {

if (digits.empty()) return {};

vector<vector<char>> d(10);

d[0] = {' '};

d[1] = {};

d[2] = {'a','b','c'};

d[3] = {'d','e','f'};

d[4] = {'g','h','i'};

d[5] = {'j','k','l'};

d[6] = {'m','n','o'};

d[7] = {'p','q','r','s'};

d[8] = {'t','u','v'};

d[9] = {'w','x','y','z'};

string cur;

vector<string> ans;

dfs(digits, d, 0, cur, ans);

return ans;

}

private:

void dfs(const string& digits,

const vector<vector<char>>& d,

int l, string& cur, vector<string>& ans) {

if (l == digits.length()) {

ans.push_back(cur);

return;

}

for (const char c : d[digits[l] - '0']) {

cur.push_back(c);

dfs(digits, d, l + 1, cur, ans);

cur.pop_back();

}

};

Java

// Author: Huahua

// Running time: 3 ms

class Solution {

public List<String> letterCombinations(String digits) {

String[] d = new String[]{" ",

"",

"abc",

"def",

"ghi",

"jkl",

"mno",

"pqrs",

"tuv",

"wxyz"};

char[] cur = new char[digits.length()];

List<String> ans = new ArrayList<>();

dfs(digits, d, 0, cur, ans);

return ans;

}

private void dfs(String digits, String[] d,

int l, char[] cur, List<String> ans) {

if (l == digits.length()) {

if (l > 0) ans.add(new String(cur));

return;

}

String s = d[Character.getNumericValue(digits.charAt(l))];

for (int i = 0; i < s.length(); ++i) {

cur[l] = s.charAt(i);

dfs(digits, d, l + 1, cur, ans);

}

Python3

"""

Author: Huahua

Running time: 60 ms

"""

class Solution:

def letterCombinations(self, digits):

def dfs(digits, d, l, cur, ans):

if l == len(digits):

if l > 0: ans.append("".join(cur))

return

for c in d[ord(digits[l]) - ord('0')]:

cur[l] = c

dfs(digits, d, l + 1, cur, ans)

d = [" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv","wxyz"]

cur = [' ' for _ in range(len(digits))]

ans = []

dfs(digits, d, 0, cur, ans)

return ans

Solution 2: BFS

C++

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

vector<string> letterCombinations(string digits) {

if (digits.empty()) return {};

vector<vector<char>> d(10);

d[0] = {' '};

d[1] = {};

d[2] = {'a','b','c'};

d[3] = {'d','e','f'};

d[4] = {'g','h','i'};

d[5] = {'j','k','l'};

d[6] = {'m','n','o'};

d[7] = {'p','q','r','s'};

d[8] = {'t','u','v'};

d[9] = {'w','x','y','z'};

vector<string> ans{""};

for (char digit : digits) {

vector<string> tmp;

for (const string& s : ans)

for (char c : d[digit - '0'])

tmp.push_back(s + c);

ans.swap(tmp);

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 4 ms

class Solution {

public List<String> letterCombinations(String digits) {

if (digits.length() == 0) return new ArrayList<String>();

String[] d = new String[]{" ",

"",

"abc",

"def",

"ghi",

"jkl",

"mno",

"pqrs",

"tuv",

"wxyz"};

List<String> ans = new ArrayList<>();

ans.add("");

for (char digit : digits.toCharArray()) {

List<String> tmp = new ArrayList<>();

for (String t : ans) {

String s = d[Character.getNumericValue(digit)];

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

tmp.add(t + s.charAt(i));

}

ans = tmp;

}

return ans;

}

Python

"""

Author: Huahua

Running time: 61 ms

"""

class Solution:

def letterCombinations(self, digits):

if not digits: return []

d = [" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv","wxyz"]

ans = [""]

for digit in digits:

tmp = []

for s in ans:

for c in d[ord(digit) - ord('0')]:

tmp.append(s + c)

ans = tmp

return ans

花花酱 LeetCode 742. Closest Leaf in a Binary Tree

By zxi on December 12, 2017

Problem:

Given a binary tree where every node has a unique value, and a target key k, find the value of the closest leaf node to target k in the tree.

Here, closest to a leaf means the least number of edges travelled on the binary tree to reach any leaf of the tree. Also, a node is called a leaf if it has no children.

In the following examples, the input tree is represented in flattened form row by row. The actual root tree given will be a TreeNode object.

Example 1:

Input:

root = [1, 3, 2], k = 1

Diagram of binary tree:

/ \

3 2

Output: 2 (or 3)

Explanation: Either 2 or 3 is the closest leaf node to the target of 1.

Example 2:

Input:

root = [1], k = 1

Output: 1

Explanation: The closest leaf node is the root node itself.

Example 3:

Input:

root = [1,2,3,4,null,null,null,5,null,6], k = 2

Diagram of binary tree:

/ \

2 3

Output: 3

Explanation: The leaf node with value 3 (and not the leaf node with value 6) is closest to the node with value 2.

Note:

root represents a binary tree with at least 1 node and at most 1000 nodes.
Every node has a unique node.val in range [1, 1000].
There exists some node in the given binary tree for which node.val == k.

题目大意:

给你一棵树，每个节点的值都不相同。

给定一个节点值，让你找到离这个节点距离最近的叶子节点的值。

Idea:

Shortest path from source to any leaf nodes in a undirected unweighted graph.

问题转换为在无向/等权重的图中找一条从起始节点到任意叶子节点最短路径。

Solution:

C++ / DFS + BFS

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Runtime: 16 ms

class Solution {

public:

int findClosestLeaf(TreeNode* root, int k) {

graph_.clear();

start_ = nullptr;

buildGraph(root, nullptr, k);

queue<TreeNode*> q;

q.push(start_);

unordered_set<TreeNode*> seen;

while (!q.empty()) {

int size = q.size();

while (size-->0) {

TreeNode* curr = q.front();

q.pop();

seen.insert(curr);

if (!curr->left && !curr->right) return curr->val;

for (TreeNode* node : graph_[curr])

if (!seen.count(node)) q.push(node);

}

return 0;

}

private:

void buildGraph(TreeNode* node, TreeNode* parent, int k) {

if (!node) return;

if (node->val == k) start_ = node;

if (parent) {

graph_[node].push_back(parent);

graph_[parent].push_back(node);

}

buildGraph(node->left, node, k);

buildGraph(node->right, node, k);

}

unordered_map<TreeNode*, vector<TreeNode*>> graph_;

TreeNode* start_;

};

花花酱 LeetCode 11. Container With Most Water

By zxi on December 3, 2017

Problem:

Given n non-negative integers a₁, a₂, …, a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

Examples:

input: [1 3 2 4]
output: 6
explanation: use 3, 4, we have the following, which contains (4th-2nd) * min(3, 4) = 2 * 3 = 6 unit of water.

|~~|

Idea:

Two pointers

Time complexity: O(n)

Space complexity: O(1)

Solution:

C++ two pointers

// Author: Huahua

// Runtime: 19 ms

class Solution {

public:

int maxArea(const vector<int>& height) {

int ans = 0;

int l = 0;

int r = height.size() - 1;

while (l < r) {

int h = min(height[l], height[r]);

ans = max(ans, h * (r - l));

if (height[l] < height[r])

++l;

else

--r;

}

return ans;

}

};

Java

// Author: Huahua

// Runtime: 13 ms

class Solution {

public int maxArea(int[] height) {

int l = 0;

int r = height.length - 1;

int ans = 0;

while (l < r) {

int h = Math.min(height[l], height[r]);

ans = Math.max(ans, h * (r - l));

if (height[l] < height[r])

++l;

else

--r;

}

return ans;

}

花花酱 LeetCode 98. Validate Binary Search Tree

By zxi on November 11, 2017

Problem:

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Example 1:

/ \

1 3

Binary tree [2,1,3], return true.

Example 2:

/ \

2 3

Binary tree [1,2,3], return false.

Solution 1

Traverse the tree and limit the range of each subtree and check whether root’s value is in the range.

Time complexity: O(n)

Space complexity: O(n)

Note: in order to cover the range of -2^31 ~ 2^31-1, we need to use long or nullable integer.

C++/long

class Solution {

public:

bool isValidBST(TreeNode* root) {

return isValidBST(root, LLONG_MIN, LLONG_MAX);

}

private:

bool isValidBST(TreeNode* root, long min_val, long max_val) {

if (!root) return true;

if (root->val <= min_val || root->val >= max_val)

return false;

return isValidBST(root->left, min_val, root->val)

&& isValidBST(root->right, root->val, max_val);

}

};

C++/nullable

class Solution {

public:

bool isValidBST(TreeNode* root) {

return isValidBST(root, nullptr, nullptr);

}

private:

bool isValidBST(TreeNode* root, int* min_val, int* max_val) {

if (!root) return true;

if ((min_val && root->val <= *min_val)

||(max_val && root->val >= *max_val))

return false;

return isValidBST(root->left, min_val, &root->val)

&& isValidBST(root->right, &root->val, max_val);

}

};

Java/nullable

// Author: Huahua

// Running time: 1 ms

class Solution {

public boolean isValidBST(TreeNode root) {

return isValidBST(root, null, null);

}

private boolean isValidBST(TreeNode root, Integer min, Integer max) {

if (root == null) return true;

if ((min != null && root.val <= min)

||(max != null && root.val >= max))

return false;

return isValidBST(root.left, min, root.val)

&& isValidBST(root.right, root.val, max);

}

Solution 2

Do an in-order traversal, the numbers should be sorted, thus we only need to compare with the previous number.

Time complexity: O(n)

Space complexity: O(n)

C++

class Solution {

public:

bool isValidBST(TreeNode* root) {

prev_ = nullptr;

return inOrder(root);

}

private:

TreeNode* prev_;

bool inOrder(TreeNode* root) {

if (!root) return true;

if (!inOrder(root->left)) return false;

if (prev_ && root->val <= prev_->val) return false;

prev_ = root;

return inOrder(root->right);

}

};

Java

// Author: Huahua

// Running time: 1 ms

class Solution {

private TreeNode prev;

public boolean isValidBST(TreeNode root) {

prev = null;

return inOrder(root);

}

private boolean inOrder(TreeNode root) {

if (root == null) return true;

if (!inOrder(root.left)) return false;

if (prev != null && root.val <= prev.val) return false;

prev = root;

return inOrder(root.right);

}

Solution 2: Priority queue / max heap

Time complexity: O(n) + O(nlogk)

Space complexity: O(n)

C++

// Author: Huahuas

// Running time: 16 ms

class Solution {

public:

vector<int> topKFrequent(vector<int>& nums, int k) {

unordered_map<int, int> count;

for (const int num : nums)

++count[num];

priority_queue<pair<int, int>> q;

for (const auto& pair : count) {

q.emplace(-pair.second, pair.first);

if (q.size() > k) q.pop();

}

vector<int> ans;

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

ans.push_back(q.top().second);

q.pop();

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 56 ms

class Solution {

public List<Integer> topKFrequent(int[] nums, int k) {

Map<Integer, Integer> counts = new HashMap<>();

for (int num : nums)

counts.put(num, counts.getOrDefault(num, 0) + 1);

PriorityQueue<int[]> queue = new PriorityQueue<>((x, y) -> x[0] - y[0]);

for (Integer num : counts.keySet()) {

queue.offer(new int[]{counts.get(num), num});

if (queue.size() > k) queue.poll();

}

List<Integer> ans = new ArrayList<>();

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

ans.add(queue.poll()[1]);

return ans;

}

Python

"""

Author: Huahua

Running time: 56 ms

"""

class Solution:

def topKFrequent(self, nums, k):

counts = collections.Counter(nums)

h = []

for num in counts.keys():

heapq.heappush(h, (counts[num], num))

if len(h) > k: heapq.heappop(h)

return [heapq.heappop(h)[1] for i in range(k)]

Solution 3: Bucket Sort

Time complexity: O(n)

Space complexity: O(n)

C++/hashmap

class Solution {

public:

vector<int> topKFrequent(vector<int>& nums, int k) {

unordered_map<int, int> count;

int max_freq = 1;

for (const int num : nums)

max_freq = max(max_freq, ++count[num]);

map<int, vector<int>> buckets;

for (const auto& kv : count)

buckets[kv.second].push_back(kv.first);

vector<int> ans;

for (int i = max_freq; i >= 1; --i) {

auto it = buckets.find(i);

if (it == buckets.end()) continue;

ans.insert(ans.end(), it->second.begin(), it->second.end());

if (ans.size() == k) return ans;

}

return ans;

}

};

C++/array

class Solution {

public:

vector<int> topKFrequent(vector<int>& nums, int k) {

unordered_map<int, int> count;

for (const int num : nums)

++count[num];

vector<vector<int>> buckets(nums.size() + 1);

for (const auto& kv : count)

buckets[kv.second].push_back(kv.first);

vector<int> ans;

for (auto it = buckets.rbegin(); it != buckets.rend(); ++it) {

const vector<int>& keys = *it;

if (keys.empty()) continue;

ans.insert(ans.begin(), keys.begin(), keys.end());

if (ans.size() == k) return ans;

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 23 ms

class Solution {

public List<Integer> topKFrequent(int[] nums, int k) {

List[] buckets = new List[nums.length + 1];

Map<Integer, Integer> counts = new HashMap<>();

for (int num : nums)

counts.put(num, counts.getOrDefault(num, 0) + 1);

for (int num : counts.keySet()) {

int count = counts.get(num);

if (buckets[count] == null)

buckets[count] = new ArrayList<Integer>();

buckets[count].add(num);

}

List<Integer> ans = new ArrayList<>();

for (int i = buckets.length - 1; i > 0 && ans.size() < k; --i) {

if (buckets[i] != null) ans.addAll(buckets[i]);

}

return ans;

}

Python

"""

Author: Huahua

Running time: 64 ms

"""

class Solution:

def topKFrequent(self, nums, k):

counts = collections.Counter(nums)

buckets = [[] for _ in range(len(nums) + 1)]

for num in counts.keys():

buckets[counts[num]].append(num)

ans = []

for i in range(len(nums), 0, -1):

ans += buckets[i]

if len(ans) == k: return ans

return ans

Posts tagged as “medium”

花花酱 LeetCode 17. Letter Combinations of a Phone Number

C++

Java

Python3

C++

Java

Python

花花酱 LeetCode 742. Closest Leaf in a Binary Tree

花花酱 LeetCode 11. Container With Most Water

花花酱 LeetCode 98. Validate Binary Search Tree

Solution 1

C++/long

C++/nullable

Java/nullable

Solution 2

C++

Java

Related Problem

花花酱 LeetCode 347. Top K Frequent Elements

Solution 2: Priority queue / max heap

C++

Java

Python

Solution 3: Bucket Sort

C++/hashmap

C++/array

Java

Python

Related Problems