Press "Enter" to skip to content

Posts published in “Two pointers”

花花酱 LeetCode 345. Reverse Vowels of a String

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

 

花花酱 LeetCode 15. 3Sum

题目大意:给你一个数组,让你找出3个数的和为0的所有组合。

Problem:

https://leetcode.com/problems/3sum/description/

Given an array S of n integers, are there elements abc 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.

Solution 1: Sorting + Two pointers

Time complexity: O(nlogn + n^2)

Space complexity: O(1)

C++

Related Problems:

花花酱 LeetCode 786. K-th Smallest Prime Fraction

题目大意:给你一些互质数字,求出它们组成的分数中第K小的分数。

A sorted list A contains 1, plus some number of primes.  Then, for every p < q in the list, we consider the fraction p/q.

What is the K-th smallest fraction considered?  Return your answer as an array of ints, where answer[0] = p and answer[1] = q.

Note:

  • A will have length between 2 and 2000.
  • Each A[i] will be between 1 and 30000.
  • K will be between 1 and A.length * (A.length + 1) / 2.

Solution 1: Binary Search

Binary search m, 0 < m < 1, such that there are exact k pairs of (i, j) that A[i] / A[j] < m

Time complexity: O(n*C) C <= 31

C++

Java

Python3

Related Problems:

花花酱 LeetCode 167. Two Sum II – Input array is sorted

题目大意:给你一个排过序的数组,让你输出两个数的index,他们的和等于target。

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Solution:

C++ / two pointers

Time complexity: O(n)

Space complexity: O(1)

 

C++ / Binary search

Related Problems:

 

花花酱 LeetCode 11. Container With Most Water

Problem:

Given n non-negative integers a1a2, …, an, where each represents a point at coordinate (iai). n vertical lines are drawn such that the two endpoints of line i is at (iai) 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

Java