Posts published in “Two pointers”

花花酱 LeetCode 948. Bag of Tokens

By zxi on November 29, 2018

Problem

You have an initial power P, an initial score of 0 points, and a bag of tokens.

Each token can be used at most once, has a value token[i], and has potentially two ways to use it.

If we have at least token[i] power, we may play the token face up, losing token[i] power, and gaining 1 point.
If we have at least 1 point, we may play the token face down, gaining token[i]power, and losing 1 point.

Return the largest number of points we can have after playing any number of tokens.

Example 1:

Input: tokens = [100], P = 50
Output: 0

Example 2:

Input: tokens = [100,200], P = 150
Output: 1

Example 3:

Input: tokens = [100,200,300,400], P = 200
Output: 2

Note:

tokens.length <= 1000
0 <= tokens[i] < 10000
0 <= P < 10000

Solution: Greedy + Two Pointers

Sort the tokens, gain points from the low end gain power from the high end.

Time complexity: O(nlogn)

Space complexity: O(1)

C++

// Author: Huahua, Running time: 8 ms

class Solution {

public:

int bagOfTokensScore(vector<int>& tokens, int P) {

sort(begin(tokens), end(tokens));

int points = 0;

int ans = 0;

int i = 0;

int j = tokens.size() - 1;

while (i <= j)

if (P >= tokens[i]) {

P -= tokens[i++];

ans = max(ans, ++points);

} else if (points > 0) {

P += tokens[j--];

--points;

} else {

break;

}

return ans;

}

};

花花酱 LeetCode 925. Long Pressed Name

By zxi on October 20, 2018

Problem

Your friend is typing his name into a keyboard. Sometimes, when typing a character c, the key might get long pressed, and the character will be typed 1 or more times.

You examine the typed characters of the keyboard. Return True if it is possible that it was your friends name, with some characters (possibly none) being long pressed.

Example 1:

Input: name = "alex", typed = "aaleex"
Output: true
Explanation: 'a' and 'e' in 'alex' were long pressed.

Example 2:

Input: name = "saeed", typed = "ssaaedd"
Output: false
Explanation: 'e' must have been pressed twice, but it wasn't in the typed output.

Example 3:

Input: name = "leelee", typed = "lleeelee" 
Output: true

Example 4:

Input: name = "laiden", typed = "laiden"
Output: true
Explanation: It's not necessary to long press any character.

Note:

name.length <= 1000
typed.length <= 1000
The characters of name and typed are lowercase letters.

Solution: Two Pointers

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua, 0 ms

class Solution {

public:

bool isLongPressedName(string name, string typed) {

int i = 0;

int j = 0;

while (i < name.size() && j < typed.size()) {

if (name[i] == typed[j]) {

++i;

++j;

} else if (j > 0 && typed[j] == typed[j - 1]) {

++j;

} else {

return false;

}

while (j < typed.size() && typed[j] == typed[j - 1]) ++j;

return i == name.size() && j == typed.size();

}

};

C++ / Iterator

// Author: Huahua

class Solution {

public:

bool isLongPressedName(string name, string typed) {

auto it1 = begin(name);

auto it2 = begin(typed);

while (it1 != end(name) && it2 != end(typed)) {

if (*it1 == *it2) {

++it1;

++it2;

} else if (it2 != begin(typed) && *it2 == *prev(it2)) {

++it2;

} else {

return false;

}

while (it2 != end(typed) && *it2 == *prev(it2)) ++it2;

return it1 == end(name) && it2 == end(typed);

}

};

花花酱 LeetCode 917. Reverse Only Letters

By zxi on October 6, 2018

Problem

Given a string S, return the “reversed” string where all characters that are not a letter stay in the same place, and all letters reverse their positions.

Example 1:

Input: "ab-cd"
Output: "dc-ba"

Example 2:

Input: "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"

Example 3:

Input: "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"

Note:

S.length <= 100
33 <= S[i].ASCIIcode <= 122
S doesn’t contain \ or "

Solution: Two Pointers

Time complexity: O(n)

Space complexity: O(1) – in place

C++/index

// Author: Huahua

class Solution {

public:

string reverseOnlyLetters(string S) {

int i = 0;

int j = S.length() - 1;

while (i < j) {

if (isalpha(S[i]) && isalpha(S[j])) {

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

} else {

if (!isalpha(S[i])) ++i;

if (!isalpha(S[j])) --j;

}

return S;

}

};

C++/iter

// Author: Huahua

class Solution {

public:

string reverseOnlyLetters(string S) {

auto it1 = begin(S);

auto it2 = prev(end(S));

while (it1 < it2) {

if (isalpha(*it1) && isalpha(*it2)) {

swap(*it1++, *it2--);

} else {

if (!isalpha(*it1)) ++it1;

if (!isalpha(*it2)) --it2;

}

return S;

}

};

花花酱 LeetCode 16. 3Sum Closest

By zxi on September 19, 2018

Problem

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Solution: Sorting + Two Pointers

Similar to 花花酱 LeetCode 15. 3Sum

Time complexity: O(n^2)

Space complexity: O(1)

C++

// Author: Huahua, 8 ms

class Solution {

public:

int threeSumClosest(vector<int> &num, int target) {

int n = num.size();

int d = INT_MAX;

int ans = target;

sort(num.begin(), num.end());

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

int s = i + 1, t = n - 1;

while (s < t) {

int sum = num[i] + num[s] + num[t];

if (sum == target)

return target;

int diff = abs(sum - target);

if (diff < d) {

d = diff;

ans = sum;

}

if (sum > target) --t;

else ++s;

}

return ans;

}

};

Java

// Author: Huahua

class Solution {

public int threeSumClosest(int[] nums, int target) {

Arrays.sort(nums);

int n = nums.length;

int ans = 0;

int d = Integer.MAX_VALUE;

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

int s = i + 1;

int t = n - 1;

while (s < t) {

int sum = nums[i] + nums[s] + nums[t];

if (sum == target) return target;

int diff = Math.abs(sum - target);

if (diff < d) {

d = diff;

ans = sum;

}

if (sum > target) --t;

else ++s;

}

return ans;

}

Python3

# Author: Huahua

class Solution:

def threeSumClosest(self, nums, target):

nums.sort()

n = len(nums)

d = 2**32

ans = 0

for i in range(n - 2):

s, t = i + 1, n - 1

while s < t:

sum3 = nums[i] + nums[s] + nums[t]

if sum3 == target: return target

diff = abs(sum3 - target)

if diff < d: ans, d = sum3, diff

if sum3 > target:

t -= 1

else:

s += 1

return ans

花花酱 LeetCode 455. Assign Cookies

By zxi on August 15, 2018

Problem

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor g_i, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s_j. If s_j >= g_i, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:
You may assume the greed factor is always positive.
You cannot assign more than one cookie to one child.

Example 1:

Input: [1,2,3], [1,1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

Example 2:

Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.

Solution: Greedy + Two Pointers

Time complexity: O(mlogm + nlogn)

Space complexity: O(1)

// Author: Huahua

// Running time: 28 ms

class Solution {

public:

int findContentChildren(vector<int>& g, vector<int>& s) {

sort(begin(g), end(g));

sort(begin(s), end(s));

int ans = 0;

int j = 0;

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

while (j < s.size() && s[j] < g[i]) {

++j;

}

if (j < s.size()) {

++ans;

++j;

continue;

}

return ans;

}

};