Press "Enter" to skip to content

Posts published in “Search”

花花酱 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 17. Letter Combinations of a Phone Number

题目大意:给你一串电话号码,输出可以由这串电话号码打出的所有字符串。

Problem:

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Solution 1: DFS

C++

Java

Python3

Solution 2:  BFS

C++

Java

Python

 

花花酱 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++

花花酱 LeetCode 749. Contain Virus

题目大意:给你一个格子地图上面有一些病毒用1表示,未受感染的格子用0表示。带有病毒的格子每天会向四周的格子传播病毒。在每一天,你必须在最大的病毒(连通区域)的周围建造墙阻挡病毒传播。问你一共需要多少个墙才能阻挡所有病毒传播。

Problems:

A virus is spreading rapidly, and your task is to quarantine the infected area by installing walls.

The world is modeled as a 2-D array of cells, where 0 represents uninfected cells, and 1 represents cells contaminated with the virus. A wall (and only one wall) can be installed between any two 4-directionally adjacent cells, on the shared boundary.

Every night, the virus spreads to all neighboring cells in all four directions unless blocked by a wall. Resources are limited. Each day, you can install walls around only one region — the affected area (continuous block of infected cells) that threatens the most uninfected cells the following night. There will never be a tie.

Can you save the day? If so, what is the number of walls required? If not, and the world becomes fully infected, return the number of walls used.

Example 1:

Input: grid = 
[[0,1,0,0,0,0,0,1],
 [0,1,0,0,0,0,0,1],
 [0,0,0,0,0,0,0,1],
 [0,0,0,0,0,0,0,0]]
Output: 10
Explanation:
There are 2 contaminated regions.
On the first day, add 5 walls to quarantine the viral region on the left. The board after the virus spreads is:

[[0,1,0,0,0,0,1,1],
 [0,1,0,0,0,0,1,1],
 [0,0,0,0,0,0,1,1],
 [0,0,0,0,0,0,0,1]]

On the second day, add 5 walls to quarantine the viral region on the right. The virus is fully contained.

Example 2:

Input: grid = 
[[1,1,1],
 [1,0,1],
 [1,1,1]]
Output: 4
Explanation: Even though there is only one cell saved, there are 4 walls built.
Notice that walls are only built on the shared boundary of two different cells.

Example 3:

Input: grid = 
[[1,1,1,0,0,0,0,0,0],
 [1,0,1,0,1,1,1,1,1],
 [1,1,1,0,0,0,0,0,0]]
Output: 13
Explanation: The region on the left only builds two new walls.

Note:

  1. The number of rows and columns of grid will each be in the range [1, 50].
  2. Each grid[i][j] will be either 0 or 1.
  3. Throughout the described process, there is always a contiguous viral region that will infect strictly more uncontaminated squares in the next round.

 

Idea:

Use DFS to find virus regions, next affected regions and # of walls needed to block each virus region.

Simulate the virus expansion process.

Solution:

C++ / DFS

Time complexity: O(n^3)

Space complexity: O(n^2)

Related Problems: