花花酱 LeetCode 885. Boats to Save People

By zxi on August 4, 2018

Problem

The i-th person has weight people[i], and each boat can carry a maximum weight of limit.

Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person. (It is guaranteed each person can be carried by a boat.)

Example 1:

Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)

Example 2:

Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)

Example 3:

Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)

Note:

1 <= people.length <= 50000
1 <= people[i] <= limit <= 30000

Solution: Greedy + Two Pointers

Time complexity: O(nlogn)

Space complexity: O(1)

Put one heaviest guy and put the lightest guy if not full.

// Author: Huahua

// Running time: 80 ms

class Solution {

public:

int numRescueBoats(vector<int>& people, int limit) {

sort(people.rbegin(), people.rend());

int i = 0;

int j = people.size() - 1;

int ans = 0;

while (i <= j) {

++ans;

if (i == j) break;

if (people[i++] + people[j] <= limit) --j;

}

return ans;

}

};

花花酱 LeetCode 345. Reverse Vowels of a String

By zxi on July 19, 2018

Problem

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = “hello”, return “holle”.

Example 2:
Given s = “leetcode”, return “leotcede”.

Note:
The vowels does not include the letter “y”.

Solution

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

string reverseVowels(string s) {

int i = 0;

int j = s.size() - 1;

while (i < j) {

while (!isVowel(s[i]) && i < j) ++i;

while (!isVowel(s[j]) && i < j) --j;

swap(s[i++], s[j--]);

}

return s;

}

private:

bool isVowel(char c) {

c = tolower(c);

return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';

}

};

花花酱 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 11. Container With Most Water

By zxi on December 3, 2017

Problem:

Given n non-negative integers a₁, a₂, …, a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

Examples:

input: [1 3 2 4]
output: 6
explanation: use 3, 4, we have the following, which contains (4th-2nd) * min(3, 4) = 2 * 3 = 6 unit of water.

|~~|

Idea:

Two pointers

Time complexity: O(n)

Space complexity: O(1)

Solution:

C++ two pointers

// Author: Huahua

// Runtime: 19 ms

class Solution {

public:

int maxArea(const vector<int>& height) {

int ans = 0;

int l = 0;

int r = height.size() - 1;

while (l < r) {

int h = min(height[l], height[r]);

ans = max(ans, h * (r - l));

if (height[l] < height[r])

++l;

else

--r;

}

return ans;

}

};

Java

// Author: Huahua

// Runtime: 13 ms

class Solution {

public int maxArea(int[] height) {

int l = 0;

int r = height.length - 1;

int ans = 0;

while (l < r) {

int h = Math.min(height[l], height[r]);

ans = Math.max(ans, h * (r - l));

if (height[l] < height[r])

++l;

else

--r;

}

return ans;

}

Posts tagged as “two pointers”

花花酱 LeetCode 885. Boats to Save People

Problem

Solution: Greedy + Two Pointers

花花酱 LeetCode 345. Reverse Vowels of a String

Problem

Solution

花花酱 LeetCode 15. 3Sum

花花酱 LeetCode 11. Container With Most Water