Posts published in “Array”

花花酱 LeetCode 830. Positions of Large Groups

By zxi on May 13, 2018

Problem

In a string S of lowercase letters, these letters form consecutive groups of the same character.

For example, a string like S = "abbxxxxzyy" has the groups "a", "bb", "xxxx", "z" and "yy".

Call a group large if it has 3 or more characters. We would like the starting and ending positions of every large group.

The final answer should be in lexicographic order.

Example 1:

Input: "abbxxxxzzy"
Output: [[3,6]]
Explanation: "xxxx" is the single large group with starting 3 and ending positions 6.

Example 2:

Input: "abc"
Output: []
Explanation: We have "a","b" and "c" but no large group.

Example 3:

Input: "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]

Note: 1 <= S.length <= 1000

Solution: Brute Force

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 18 ms

class Solution {

public:

vector<vector<int>> largeGroupPositions(string S) {

constexpr int kLargeGroupSize = 3;

const int n = S.size();

vector<vector<int>> ans;

int c = 0;

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

if (i == n || S[i] != S[i - 1]) {

if (c >= kLargeGroupSize) ans.push_back({i - c, i - 1});

c = 0;

}

return ans;

}

};

花花酱 LeetCode 832. Flipping an Image

By zxi on May 13, 2018

Problem

Given a binary matrix A, we want to flip the image horizontally, then invert it, and return the resulting image.

To flip an image horizontally means that each row of the image is reversed. For example, flipping [1, 1, 0] horizontally results in [0, 1, 1].

To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [0, 1, 1] results in [1, 0, 0].

Example 1:

Input: [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

Example 2:

Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

Notes:

1 <= A.length = A[0].length <= 20
0 <= A[i][j] <= 1

Solution 1: Brute Force

Time complexity: O(m*n)

Space complexity: O(m*n)

C++

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

vector<vector<int>> flipAndInvertImage(vector<vector<int>>& A) {

auto B = A;

int m = A.size();

int n = A[0].size();

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

for (int j = 0; j < n; ++j)

B[i][j] = 1 - A[i][n - j - 1];

return B;

}

};

花花酱 LeetCode 448. Find All Numbers Disappeared in an Array

By zxi on March 23, 2018

Problem

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

Solution

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 128 ms (beats 93.70%)

class Solution {

public:

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

for (size_t i = 0; i != nums.size(); ++i) {

int index = abs(nums[i]) - 1;

if (nums[index] > 0) nums[index] *= -1;

}

vector<int> ans;

for (size_t i = 0; i != nums.size(); ++i)

if (nums[i] > 0) ans.push_back(i + 1);

return ans;

}

};

花花酱 LeetCode 414. Third Maximum Number

By zxi on March 17, 2018

Problem

https://leetcode.com/problems/third-maximum-number/description/

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:

Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.

Example 2:

Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

Solution: Set

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int thirdMax(vector<int>& nums) {

set<int> s;

for (int num : nums) {

s.insert(num);

if (s.size() > 3) s.erase(s.begin());

}

return s.size() != 3 ? *s.rbegin() : *s.begin();

}

};

Python3

"""

Author: Huahua

Running time: 52 ms

"""

class Solution:

def thirdMax(self, nums):

s = set()

for num in nums:

s.add(num)

if len(s) > 3: s.remove(min(s))

return min(s) if len(s) == 3 else max(s)

花花酱 LeetCode 413. Arithmetic Slices

By zxi on March 17, 2018

题目大意：返回所有子数组中等差数列的个数。

Problem

https://leetcode.com/problems/arithmetic-slices/description/

A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequence:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], …, A[Q – 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.

Example:

A = [1, 2, 3, 4]

return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

Solution 0: Reduction

Reduce the problem to # of all 1 sub arrays.

B[i – 2] = is_slice(A[i], A[i+1], A[i+2])

Time Complexity: O(n)

Space Complexity: O(n)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int numberOfArithmeticSlices(vector<int>& A) {

if (A.size() < 3) return 0;

vector<int> B(A.size() - 2, 0);

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

if (A[i - 1] - A[i - 2] == A[i] - A[i - 1])

B[i - 2] = 1;

}

return all1SubArrays(B);

}

private:

// return number of arrays whose values are all ones.

int all1SubArrays(const vector<int>& A) {

int sum = 0;

int curr = 0;

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

if (A[i]) sum += ++curr;

else curr = 0;

return sum;

}

};

Solution 1: Combined

C++

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int numberOfArithmeticSlices(vector<int>& A) {

int sum = 0;

int curr = 0;

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

if (A[i - 1] - A[i - 2] == A[i] - A[i - 1]) {

sum += ++curr;

} else {

curr = 0;

}

return sum;

}

};

Posts published in “Array”

花花酱 LeetCode 830. Positions of Large Groups

Problem

Solution: Brute Force

花花酱 LeetCode 832. Flipping an Image

Problem

Solution 1: Brute Force

花花酱 LeetCode 448. Find All Numbers Disappeared in an Array

Problem

Solution

花花酱 LeetCode 414. Third Maximum Number

Problem

Solution: Set

花花酱 LeetCode 413. Arithmetic Slices

Problem

Example:

Solution 0: Reduction

Solution 1: Combined

Related Problems: