Posts tagged as “medium”

花花酱 LeetCode 15. 3Sum

By zxi on March 6, 2018

题目大意：给你一个数组，让你找出3个数的和为0的所有组合。

Problem:

https://leetcode.com/problems/3sum/description/

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:

[

[-1, 0, 1],

[-1, -1, 2]

]

Solution 1: Hashtable

Time complexity: O(n^2)
Space complexity: O(n)

// Author: Huahua

class Solution {

public:

vector<vector<int>> threeSum(vector<int>& nums) {

sort(begin(nums), end(nums));

const int n = nums.size();

unordered_map<int, int> c;

for (int x : nums) ++c[x];

vector<vector<int>> ans;

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

if (i && nums[i] == nums[i - 1]) continue;

for (int j = i + 1; j < n; ++j) {

if (j - 1 != i && nums[j] == nums[j - 1]) continue;

const int t = 0 - nums[i] - nums[j];

// nums[i] <= nums[j] <= nums[k]

if (t < nums[j]) continue;

if (!c.count(t)) continue;

// Make sure we have enough count

if (c[t] >= 1 + (nums[i] == t) + (nums[j] == t))

ans.push_back({nums[i], nums[j], t});

}

return ans;

}

};

Solution 2: Sorting + Two pointers

Time complexity: O(nlogn + n^2)

Space complexity: O(1)

C++

class Solution {

public:

vector<vector<int>> threeSum(vector<int>& nums) {

vector<vector<int>> ans;

std::sort(nums.begin(), nums.end());

const int n = nums.size();

for (int i = 0; i < n - 2; ++i) {

if (nums[i] > 0) break;

if (i > 0 && nums[i] == nums[i - 1]) continue;

int l = i + 1;

int r = n - 1;

while (l < r) {

if (nums[i] + nums[l] + nums[r] == 0) {

ans.push_back({nums[i], nums[l++], nums[r--]});

while (l < r && nums[l] == nums[l - 1]) ++l;

while (l < r && nums[r] == nums[r + 1]) --r;

} else if (nums[i] + nums[l] + nums[r] < 0) {

++l;

} else {

--r;

}

return ans;

}

};

Related Problems:

花花酱 LeetCode 515. Find Largest Value in Each Tree Row

By zxi on March 5, 2018

题目大意：给你一棵树，返回每一层最大的元素的值。

You need to find the largest value in each row of a binary tree.

Example:

<b>Input:</b>

/ \

3 2

/ \ \

5 3 9

<b>Output:</b> [1, 3, 9]

Solution 1: Inorder traversal + depth info

C++

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

vector<int> largestValues(TreeNode* root) {

vector<int> ans;

inorder(root, 0, ans);

return ans;

}

private:

void inorder(TreeNode* root, int d, vector<int>& ans) {

if (root == nullptr) return;

while (ans.size() <= d) ans.push_back(INT_MIN);

inorder(root->left, d + 1, ans);

ans[d] = max(ans[d], root->val);

inorder(root->right, d + 1, ans);

}

};

Python3

"""

Author: Huahua

Running time: 72 ms (beats 100%)

"""

class Solution:

def largestValues(self, root):

def inorder(root, d, ans):

if not root: return ans

if len(ans) <= d: ans += [float('-inf')]

inorder(root.left, d + 1, ans)

if root.val > ans[d]: ans[d] = root.val

inorder(root.right, d + 1, ans)

return ans

return inorder(root, 0, [])

花花酱 LeetCode 513. Find Bottom Left Tree Value

By zxi on March 5, 2018

题目大意：给你一棵树，返回左下角（最后一行最左面）的节点的值。

https://leetcode.com/problems/find-bottom-left-tree-value/description/

Problem:

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:

Input:

/ \

1 3

Output:

Example 2:

Input:

/ \

2 3

/ / \

4 5 6

Output:

Note: You may assume the tree (i.e., the given root node) is not NULL.

Solution 1: Inorder traversal with depth info

The first node visited in the deepest row is the answer.

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int findBottomLeftValue(TreeNode* root) {

int max_row = -1;

int ans;

dfs(root, 0, max_row, ans);

return ans;

}

private:

void inorder(TreeNode* root, int row, int& max_row, int& ans) {

if (root == nullptr) return;

inorder(root->left, row + 1, max_row, ans);

if (row > max_row) {

ans = root->val;

max_row = row;

}

inorder(root->right, row + 1, max_row, ans);

}

};

Python3

"""

Author: Huahua

Running time: 92 ms

"""

class Solution:

def inorder(self, root, row):

if not root: return

self.inorder(root.left, row + 1)

if row > self.max_row:

self.max_row, self.ans = row, root.val

self.inorder(root.right, row + 1)

def findBottomLeftValue(self, root):

self.ans, self.max_row = 0, -1

self.inorder(root, 0)

return self.ans

花花酱 LeetCode 792. Number of Matching Subsequences

By zxi on March 3, 2018

题目大意：给你一些单词，问有多少单词出现在字符串S的子序列中。

https://leetcode.com/problems/number-of-matching-subsequences/description/

Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.

Example :

Input:

S = "abcde"

words = ["a", "bb", "acd", "ace"]

Output: 3

Explanation: There are three words in <code>words</code> that are a subsequence of <code>S</code>: "a", "acd", "ace".

Note:

All words in words and S will only consists of lowercase letters.
The length of S will be in the range of [1, 50000].
The length of words will be in the range of [1, 5000].
The length of words[i] will be in the range of [1, 50].

Solution 1: Brute Force

Time complexity: O((S + L) * W)

C++ w/o cache TLE

Space complexity: O(1)

C++ w/ cache 155 ms

Space complexity: O(W * L)

// Author: Huahua

// Running time: 155 ms

class Solution {

public:

int numMatchingSubseq(const string& S, vector<string>& words) {

int ans = 0;

unordered_map<string, bool> m;

for (const string& word : words) {

auto it = m.find(word);

if (it == m.end()) {

bool match = isMatch(word, S);

ans += m[word] = match;

} else {

ans += it->second;

}

return ans;

}

private:

bool isMatch(const string& word, const string& S) {

int start = 0;

for (const char c : word) {

bool found = false;

for (int i = start; i < S.length(); ++i)

if (S[i] == c) {

found = true;

start = i + 1;

break;

}

if (!found) return false;

}

return true;

}

};

Solution 2: Indexing+ Binary Search

Time complexity: O(S + W * L * log(S))

Space complexity: O(S)

S: length of S

W: number of words

L: length of a word

C++

// Author: Huahua

// Running time: 183 ms

class Solution {

public:

int numMatchingSubseq(const string& S, vector<string>& words) {

vector<vector<int>> pos(128);

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

pos[S[i]].push_back(i);

int ans = 0;

for (const string& word : words)

ans += isMatch(word, pos);

return ans;

}

private:

unordered_map<string, bool> m_;

bool isMatch(const string& word, const vector<vector<int>>& pos) {

if (m_.count(word)) return m_[word];

int last_index = -1;

for (const char c : word) {

const vector<int>& p = pos[c];

const auto it = std::lower_bound(p.begin(), p.end(), last_index + 1);

if (it == p.end()) return m_[word] = false;

last_index = *it;

}

return m_[word] = true;

}

};

Java

// Author: Huahua

// Running time: 135 ms

class Solution {

private List<List<Integer>> pos;

private boolean isMatch(String word) {

int l = -1;

for (char c : word.toCharArray()) {

List<Integer> p = pos.get(c);

int index = Collections.binarySearch(p, l + 1);

if (index < 0) index = -index - 1;

if (index >= p.size()) return false;

l = p.get(index);

}

return true;

}

public int numMatchingSubseq(String S, String[] words) {

pos = new ArrayList<>();

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

pos.add(new ArrayList<Integer>());

char[] s = S.toCharArray();

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

pos.get(s[i]).add(i);

int ans = 0;

for (String word : words)

if (isMatch(word)) ++ans;

return ans;

}

Python 3:

w/o cache

"""

Author: Huahua

Running time: 1120 ms

"""

class Solution:

def numMatchingSubseq(self, S, words):

import bisect

def isMatch(word):

l = -1

for c in word:

index = bisect.bisect_left(pos[c], l + 1)

if index == len(pos[c]): return 0

l = pos[c][index]

return 1

pos = {chr(i + ord('a')) : [] for i in range(26)}

for i, c in enumerate(S):

pos[c].append(i)

return sum(map(isMatch, words))

w/ cache

"""

Author: Huahua

Running time: 632 ms

"""

class Solution:

def numMatchingSubseq(self, S, words):

import bisect

def isMatch(word):

if word in m: return m[word]

l = -1

for c in word:

index = bisect.bisect_left(pos[c], l + 1)

if index == len(pos[c]):

m[word] = 0

return 0

l = pos[c][index]

m[word] = 1

return 1

m = {}

pos = {chr(i + ord('a')) : [] for i in range(26)}

for i, c in enumerate(S):

pos[c].append(i)

return sum(map(isMatch, words))

花花酱 LeetCode 795. Number of Subarrays with Bounded Maximum

By zxi on March 3, 2018

题目大意：问一个数组中有多少个子数组的最大元素值在[L, R]的范围里。

We are given an array A of positive integers, and two positive integers L and R (L <= R).

Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least L and at most R.

Example :

Input:

A = [2, 1, 4, 3]

L = 2

R = 3

Output: 3

Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].

Solution 1:

C++

// Author: Huahua

// Running time: 42 ms

class Solution {

public:

int numSubarrayBoundedMax(vector<int>& A, int L, int R) {

return count(A, R) - count(A, L - 1);

}

private:

// Count # of sub arrays whose max element is <= N

int count(const vector<int>& A, int N) {

int ans = 0;

int cur = 0;

for (int a: A) {

if (a <= N)

ans += ++cur;

else

cur = 0;

}

return ans;

}

};

Solution 2: One pass

C++

// Author: Huahua

// Running time: 38 ms

class Solution {

public:

int numSubarrayBoundedMax(vector<int>& A, int L, int R) {

int ans = 0;

int left = -1;

int right = -1;

for (int i = 0; i < A.size(); ++i) {

if (A[i] >= L) right = i;

if (A[i] > R) left = i;

ans += (right - left);

}

return ans;

}

};