花花酱 LeetCode 228. Summary Ranges

By zxi on June 27, 2018

Problem

Given a sorted integer array without duplicates, return the summary of its ranges.

Example 1:

Input:  [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: 0,1,2 form a continuous range; 4,5 form a continuous range.

Example 2:

Input:  [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: 2,3,4 form a continuous range; 8,9 form a continuous range.

Solution

Time complexity: O(n)

Space complexity: O(k)

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

vector<string> summaryRanges(vector<int>& nums) {

int s = 0;

vector<string> ans;

for (size_t i = 1; i <= nums.size(); ++i) {

if (i == nums.size() || nums[i] != nums[i - 1] + 1) {

if (s == i - 1)

ans.push_back(to_string(nums[s]));

else

ans.push_back(to_string(nums[s]) + "->" + to_string(nums[i - 1]));

s = i;

}

return ans;

}

};

花花酱 LeetCode 849. Maximize Distance to Closest Person

By zxi on June 11, 2018

Problem

In a row of seats, 1 represents a person sitting in that seat, and 0 represents that the seat is empty.

There is at least one empty seat, and at least one person sitting.

Alex wants to sit in the seat such that the distance between him and the closest person to him is maximized.

Return that maximum distance to closest person.

Example 1:

Input: [1,0,0,0,1,0,1]
Output: 2
Explanation: 
If Alex sits in the second open seat (seats[2]), then the closest person has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.

Example 2:

Input: [1,0,0,0]
Output: 3
Explanation: 
If Alex sits in the last seat, the closest person is 3 seats away.
This is the maximum distance possible, so the answer is 3.

Note:

1 <= seats.length <= 20000
seats contains only 0s or 1s, at least one 0, and at least one 1.

Solution

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

int maxDistToClosest(vector<int>& seats) {

int n = seats.size();

int prev = -1;

int ans = 0;

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

if (i == n) ans = max(ans, n - prev - 1);

else if (seats[i]) {

if (prev == -1) ans = i;

else ans = max(ans, (i - prev) / 2);

prev = i;

}

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 396. Rotate Function

By zxi on March 16, 2018

Problem:

Given an array of integers A and let n to be its length.

Assume B_k to be an array obtained by rotating the array A k positions clock-wise, we define a “rotation function” F on A as follow:

F(k) = 0 * B_k[0] + 1 * B_k[1] + ... + (n-1) * B_k[n-1].

Calculate the maximum value of F(0), F(1), ..., F(n-1).

Note:
n is guaranteed to be less than 10⁵.

Example:

A = [4, 3, 2, 6]

F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26

So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

Solution 1: Brute Force

Time complexity: O(n^2) TLE

Space complexity: O(1)

Solution 2: Math

F(K)          =               0A[K] + 1A[K+1] + 2A[K+2] + ... + (n-2)A[K-2] + (n-1)A[K-1]
F(K-1)        =     0A[K-1] + 1A[K] + 2A[K+1] + 3A[K+2] + ... + (n-1)A[K-2]
F(K) - F(K-1) = (n-1)A[K-1] - 1A[K] - 1A[K+1] - 1A[K+2] - ... -     1A[K-2]
              = (n-1)A[K-1] - (1A[K] + 1A[K+1] + ... + 1A[K-2] + 1A[K-1] - 1A[K-1])
              = nA[K-1] - sum(A)
compute F(0)
F(i)          = F(i-1) + nA[i-1] - sum(A)

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 11 ms

class Solution {

public:

int maxRotateFunction(vector<int>& A) {

const int n = A.size();

int sum = 0;

int f = 0;

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

sum += A[i];

f += i * A[i];

}

int ans = f;

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

f = f + sum - n * A[n - i - 1];

ans = max(ans, f);

}

return ans;

}

};

Posts tagged as “array”

花花酱 LeetCode 228. Summary Ranges

Problem

Solution

花花酱 LeetCode 849. Maximize Distance to Closest Person

Problem

Solution

花花酱 LeetCode 832. Flipping an Image

Problem

Solution 1: Brute Force

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

Problem

Solution

花花酱 LeetCode 396. Rotate Function

Problem:

Solution 1: Brute Force

Solution 2: Math