Press "Enter" to skip to content

Posts published in “Search”

花花酱 LeetCode 773. Sliding Puzzle

题目大意:给你一个2×3的棋盘,放着0-5。每一步0可以和上下左右的一个数交换。问需要多少步可以构成123450的棋盘状态。

Problem:

On a 2×3 board, there are 5 tiles represented by the integers 1 through 5, and an empty square represented by 0.

A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.

The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]].

Given a puzzle board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.

Examples:

Solution: BFS

Time complexity: O(6!)

Space complexity: O(6!)

C++

Simplified, only works on 3×2 board

 

 

花花酱 LeetCode 464. Can I Win

题目大意:两个人从1到M中每次取出一个数加到当前的总和上,第一个达到或超过T的人获胜。问你第一个玩家能不能获胜。

In the “100 game,” two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.

Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.

You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.

Example

 

 

Solution: Recursion with memoization 

Time complexity: O(2^M)

Space complexity: O(2^M)

C++

Java

Python3

 

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