Press "Enter" to skip to content

Posts published in “Hard”

花花酱 LeetCode 282. Expression Add Operators

题目大意:给你一个字符串,让你在数字之间加上+,-,*使得等式的值等于target。让你输出所有满足条件的表达式。

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +-, or * between the digits so they evaluate to the target value.

Examples:

Slides:

 

Solution 1: DFS

Time complexity: O(4^n)

Space complexity: O(n^2) -> O(n)

C++

C++ / SC O(n)

Java

花花酱 LeetCode 480. Sliding Window Median

题目大意:让你求移动窗口的中位数。

Problem:

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:

[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

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. Your job is to output the median array for each window in the original array.

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

Therefore, return the median sliding window as [1,-1,-1,3,5,6].

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

 

Solution 0: Brute Force

Time complexity: O(n*klogk) TLE 32/42 test cases passed

Solution 1: Insertion Sort

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

Space complexity: O(k)

C++ / vector

C++ / vector + binary_search for deletion.

Java

Java / Binary Search

 

Python

Solution 2: BST

 

Related Problems:

花花酱 LeetCode 759. Employee Free Time

题目大意:给你每个员工的日历,让你找出所有员工都有空的时间段。

Problem:

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

Example 1:

Example 2:

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined.)

Also, we wouldn’t include intervals like [5, 5] in our answer, as they have zero length.

Note:

  1. schedule and schedule[i] are lists with lengths in range [1, 50].
  2. 0 <= schedule[i].start < schedule[i].end <= 10^8.


Idea:

Merge Intervals (virtually)

Solution:

C++

Time complexity: O(nlogn)

Space complexity: O(n)

n is the total number of intervals, n <= 2500

Related Problems:

花花酱 LeetCode 752. Open the Lock

Problem:

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Example 1:

Example 2:

Example 3:

Example 4:

Note:

  1. The length of deadends will be in the range [1, 500].
  2. target will not be in the list deadends.
  3. Every string in deadends and the string target will be a string of 4 digits from the 10,000 possibilities '0000' to '9999'.


题目大意:

给你一个4位密码锁,0可以转到1和9,1可以转到0和2,。。。,9可以转到0和8。

另外给你一些死锁的密码,比如1234,一但转到任何一个死锁的密码,锁就无法再转动了。

给你一个目标密码,问你最少要转多少次才能从0000转到目标密码。

Solution:

C++

C++ / Bidirectional BFS

C++ / Bidirectional BFS / int state / Array

Java

Python

Python / Int state

 

花花酱 LeetCode 301. Remove Invalid Parentheses

Problem:

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:

 

题目大意:给你一个字符串,由”(” “)”和其他字符构成。让你删除数量最少的括号使得表达式合法(括号都匹配)。输出所有的合法表达式。

 

Idea:

Search 

Solution: DFS

C++