花花酱 LeetCode 739. Daily Temperatures

By zxi on July 16, 2018

Problem

Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

Solution: Stack

Use a stack to track indices of future warmer days. From top to bottom: recent to far away.

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 148 ms

class Solution {

public:

vector<int> dailyTemperatures(vector<int>& temperatures) {

const int n = temperatures.size();

stack<int> s;

vector<int> ans(n);

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

while (!s.empty() && temperatures[s.top()] <= temperatures[i]) s.pop();

ans[i] = s.empty() ? 0 : s.top() - i;

s.push(i);

}

return ans;

}

};

花花酱 LeetCode 350. Intersection of Two Arrays II

By zxi on July 14, 2018

Problem

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?
What if nums1‘s size is small compared to nums2‘s size? Which algorithm is better?
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Solution1: Hashtable

Time complexity: O(m + n)

Space complexity: O(m)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {

unordered_map<int, int> count;

vector<int> ans;

for (int num : nums1)

++count[num];

for (int num : nums2)

if (count.count(num) &&count[num] > 0) {

--count[num];

ans.push_back(num);

}

return ans;

}

};

花花酱 LeetCode 867. Transpose Matrix

By zxi on July 8, 2018

Given a matrix A, return the transpose of A.

The transpose of a matrix is the matrix flipped over it’s main diagonal, switching the row and column indices of the matrix.

Example 1:

Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]

Example 2:

Input: [[1,2,3],[4,5,6]]
Output: [[1,4],[2,5],[3,6]]

Note:

1 <= A.length <= 1000
1 <= A[0].length <= 1000

Solution: Brute Force

Time complexity: O(mn)

Space complexity: O(mn)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

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

int m = A.size();

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

vector<vector<int>> ans(n, vector<int>(m));

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

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

ans[j][i] = A[i][j];

return ans;

}

};

花花酱 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;

}

};

Posts tagged as “array”

花花酱 LeetCode 739. Daily Temperatures

Problem

Solution: Stack

花花酱 LeetCode 350. Intersection of Two Arrays II

Problem

Solution1: Hashtable

花花酱 LeetCode 867. Transpose Matrix

Solution: Brute Force

C++

花花酱 LeetCode 228. Summary Ranges

Problem

Solution

花花酱 LeetCode 849. Maximize Distance to Closest Person

Problem

Solution