Huahua’s Tech Road

花花酱 LeetCode 696. Count Binary Substrings

By zxi on March 6, 2018

题目大意：给你一个二进制的字符串，问有多少子串的0个数量等于1的数量。

Problem:

https://leetcode.com/problems/count-binary-substrings/description/

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: "00110011"

Output: 6

Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".

Notice that some of these substrings repeat and are counted the number of times they occur.

Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.

Example 2:

Input: "10101"

Output: 4

Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

Note:

s.length will be between 1 and 50,000.
s will only consist of “0” or “1” characters.

Solution 0: Search

Try all possible substrings and check whether it’s a valid one or not.

Time complexity O(2^n * n) TLE

Space complexity: O(n)

Solution 1: Running Length

For S = “000110”, there are two virtual blocks “[00011]0” and “000[110]” which contains consecutive 0s and 1s or (1s and 0s)

Keep tracking of the running length of 0, 1 for each block

“00011” => ‘0’: 3, ‘1’:2

ans += min(3, 2) => ans = 2 (“[0011]”, “0[01]1”)

“110” => ‘0’: 1, ‘1’: 2

ans += min(1, 2) => ans = 3 (“[0011]”, “0[01]1”, “1[10]”)

We can reuse part of the running length from last block.

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 43 ms

class Solution {

public:

int countBinarySubstrings(string s) {

vector<int> lens(128, 0);

int i = 0;

int l = 0;

int ans = 0;

while (true) {

while (i < s.length() && s[i] == s[l]) ++i;

lens[s[l]] = i - l;

ans += min(lens['0'], lens['1']);

if (i == s.length()) break;

lens[s[i]] = 0;

l = i;

}

return ans;

}

};

花花酱 LeetCode 454. 4Sum II

By zxi on March 5, 2018

题目大意：给你4个组数：A, B, C, D。问有多少组组合的A[i] + B[j] + C[k] + D[l] 的和为0。

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l]is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -2²⁸ to 2²⁸ – 1 and the result is guaranteed to be at most 2³¹ – 1.

Example:

Input:

A = [ 1, 2]

B = [-2,-1]

C = [-1, 2]

D = [ 0, 2]

Output:

Explanation:

The two tuples are:

1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0

2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

Solution 1: HashTable

Split the arrays into two groups: (A, B), (C, D)

Create the Minkowski sum of two groups and count the occurrence of each element.

e.g. A = [1, 2, 3], B = [0, -1, 1]

Minkowski sum(A, B) SAB= [0, 1, 2, 3, 4] => [0:1, 1:2, 2:3, 3:2, 4:1]

for each element s in SAB, check whether -s is in Minkowski sum(C, D) SCD

ans = sum(SAB[s] * SCD[-s]), for all s, that s in SAB and -s in SCD

Time complexity: O(n^2)

Space complexity: O(n^2)

C++

// Author: Huahua

// Running time: 217 ms

class Solution {

public:

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {

unordered_map<int, int> sums;

for (int a : A)

for (int b : B)

++sums[a + b];

int ans = 0;

for (int c : C)

for (int d : D) {

auto it = sums.find(- c - d);

if (it != sums.end()) ans += it->second;

}

return ans;

}

};

Python3

"""

Author: Huahua

Running time: 672 ms

"""

class Solution:

def fourSumCount(self, A, B, C, D):

s = collections.Counter([a + b for a in A for b in B])

return sum(s[-c - d] for c in C for d in D)

Related Problems:

[解题报告] LeetCode 1. Two Sum – 花花酱

花花酱 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 496. Next Greater Element I

By zxi on March 5, 2018

题目大意：给你一个组数A里面每个元素都不相同。再给你一个数组B，元素是A的子集，问对于B中的每个元素，在A数组中相同元素之后第一个比它的元素是多少。

Problem:

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1‘s elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2].

Output: [-1,3,-1]

Explanation:

For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.

For number 1 in the first array, the next greater number for it in the second array is 3.

For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4].

Output: [3,-1]

Explanation:

For number 2 in the first array, the next greater number for it in the second array is 3.

For number 4 in the first array, there is no next greater number for it in the second array, so output -1.

Note:

All elements in nums1 and nums2 are unique.
The length of both nums1 and nums2 would not exceed 1000.

Solution 1: Brute Force

Time complexity: O(n^2)

Space complexity: O(1)

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {

vector<int> ans;

for (int num : findNums) {

ans.push_back(-1);

int index = std::find(nums.begin(), nums.end(), num) - nums.begin();

for (int i = index; i < nums.size(); ++i)

if (nums[i] > num) {

ans.back() = nums[i];

break;

}

return ans;

}

};

Solution 2: HashTable + Brute Force

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {

unordered_map<int, int> indices;

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

indices[nums[i]] = i;

vector<int> ans;

for (int num : findNums) {

ans.push_back(-1);

for (int i = indices[num]; i < nums.size(); ++i)

if (nums[i] > num) {

ans.back() = nums[i];

break;

}

return ans;

}

};

Solution 3: Stack + HashTable

Using a stack to store the nums whose next greater isn’t found yet.

// Author: Huahua

// Running time: 11 ms

class Solution {

public:

vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {

stack<int> s;

unordered_map<int, int> next;

for (int num : nums) {

while (!s.empty() && num > s.top()) {

next[s.top()] = num;

s.pop();

}

s.push(num);

}

vector<int> ans;

for (int num : findNums)

ans.push_back(next.count(num) ? next[num] : -1);

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 696. Count Binary Substrings

花花酱 LeetCode 454. 4Sum II

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

花花酱 LeetCode 513. Find Bottom Left Tree Value

花花酱 LeetCode 496. Next Greater Element I