Press "Enter" to skip to content

Posts published in “Algorithms”

花花酱 LeetCode 239. Sliding Window Maximum

题目大意:给你一个数组,让你输出移动窗口的最大值。

Problem:

https://leetcode.com/problems/sliding-window-maximum/

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note: 
You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.

Follow up:
Could you solve it in linear time?

 

Idea:

 

Solution 1: Brute Force

Time complexity: O((n – k + 1) * k)

Space complexity: O(1)

C++

Java

Python

Solution 2: BST

Time complexity: O((n – k + 1) * logk)

Space complexity: O(k)

C++

Solution 3: Monotonic Queue

Time complexity: O(n)

Space complexity: O(k)

C++

C++ V2

C++ V3

Java

Python3

Python3 V2

花花酱 LeetCode. 69 Sqrt(x)

题目大意:让你实现开根号函数,只需要返回整数部分。

Problem:

Implement int sqrt(int x).

Compute and return the square root of x.

x is guaranteed to be a non-negative integer.

Example 1:

Example 2:

 

 

Solution 1: Brute force

Time complexity: sqrt(x)

C++

C++ div

Java

Python3 TLE

Solution 2: Binary search

Time complexity: O(logn)

C++

Java

Python3

Solution 3: Newton’s method

C++ / float

C++ / int

Java

Python3

花花酱 LeetCode 760. Find Anagram Mappings

题目大意:输出数组A中每个元素在数组B中的索引。

Given two lists Aand B, and B is an anagram of AB is an anagram of A means B is made by randomizing the order of the elements in A.

We want to find an index mapping P, from A to B. A mapping P[i] = j means the ith element in A appears in B at index j.

These lists A and B may contain duplicates. If there are multiple answers, output any of them.

For example, given

We should return

as P[0] = 1 because the 0th element of A appears at B[1], and P[1] = 4 because the 1st element of Aappears at B[4], and so on.

Solution:

C++

Time complexity: O(nlogn)

Space complexity: O(n)

C++ / No duplication

 

花花酱 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 315. Count of Smaller Numbers After Self

题目大意:给你一个数组,对于数组中的每个元素,返回一共有多少在它之后的元素比它小。

Problem:

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Return the array [2, 1, 1, 0].

Idea:

Fenwick Tree / Binary Indexed Tree

BST

Solution 1: Binary Indexed Tree (Fenwick Tree)

C++

Java

Solution 2: BST

C++

Java