Press "Enter" to skip to content

Huahua's Tech Road

花花酱 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 121. Best Time to Buy and Sell Stock

题目大意: 给你一只股票每天的价格,如果只能做一次交易(一次买进一次卖出)问你最多能赚多少钱。

Problem:

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Example 2:

 

Idea:

DP

Solution 1:

C++

C++ / reduce to maximum subarray

Related Problems:

花花酱 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 748. Shortest Completing Word

题目大意: 给你一个由字母和数字组成车牌。另外给你一些单词,让你找一个最短的单词能够覆盖住车牌中的字母(不考虑大小写)。如果有多个解,输出第一个解。

Problem:

Find the minimum length word from a given dictionary words, which has all the letters from the string licensePlate. Such a word is said to complete the given string licensePlate

Here, for letters we ignore case. For example, "P" on the licensePlate still matches "p" on the word.

It is guaranteed an answer exists. If there are multiple answers, return the one that occurs first in the array.

The license plate might have the same letter occurring multiple times. For example, given a licensePlate of "PP", the word "pair" does not complete the licensePlate, but the word "supper" does.

Example 1:

Example 2:

Note:

  1. licensePlate will be a string with length in range [1, 7].
  2. licensePlate will contain digits, spaces, or letters (uppercase or lowercase).
  3. words will have a length in the range [10, 1000].
  4. Every words[i] will consist of lowercase letters, and have length in range [1, 15].

Idea:

Hashtable

Solution:

C++

Time complexity: 时间复杂度 O(N*26), N is number of words.

Space complexity: 空间复杂度 O(26) = O(1)

 

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