Topic describes
You have a turntable lock with four round paddles. Each dial wheel has 10 Numbers: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’. Each dial wheel can rotate freely: for example, ‘9’ becomes ‘0’ and ‘0’ becomes ‘9’. Each rotation can only rotate one digit of one dial wheel.
The initial lock number is ‘0000’, a string representing the numbers of the four dial wheels.
The list deadends contains a set of death numbers. Once the number of the dial wheel matches any element in the list, the lock is permanently locked and cannot be rotated.
The string target represents the number that can be unlocked, you need to give the minimum number of rotations, and if it can’t be unlocked anyway, return -1.
Example 1:
Enter: deadends = ["0201"."0101"."0102"."1212"."2002"], target = "0202"
Output:6
Explanation:
The possible movement sequence is"0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Pay attention to"0000" -> "0001" -> "0002" -> "0102" -> "0202"Such sequences cannot be unlocked,
Because when the dial goes to"0102"", the lock will be locked.
Copy the codeExample 2:
Enter: deadends = ["8888"], target = "0009"
Output:1
Explanation:
Turn the last digit backwards once"0000" -> "0009".
Copy the codeExample 3:
Enter: deadends = ["8887"."8889"."8878"."8898"."8788"."8988"."7888"."9888"], target = "8888"
Output:- 1
Explanation:
Unable to rotate to target number and not locked.
Copy the codeExample 4:
Enter: deadends = ["0000"], target = "8888"
Output:- 1
Copy the codeTip:
- The length range of the death list deadends is [1, 500].
- Target numbers will not be in deadends.
- The number of strings in each deadends and target is generated in 10,000 possible cases ‘0000’ up to ‘9999’.
Source: LeetCode
Train of thought
This question is very interesting, there is a similar to the kind of combination lock our suitcase, can through turning up and turn out any password, there is a limit, however, is not through some deaths, is increased some difficulty to us, if you just look at the number of password is big or small, for example, is it from 0 to 3 > 1 – > 2 – > 3, If it’s 8, it’s 0->9->8.
We can think of 0, 0, 0, 0 as an origin, and then that one point can produce 8 different results, as shown below:
Then these 8 points can continue to change:
Notice in the figure above, there are 8 combinations that go back to 0, 0, 0, 0, and the blue ones all have coincidence terms.
So here’s the idea: we can use this change to go from 0, 0, 0, 0 to 8 points, and then continue to go from 0 to 8 points… Until we find the target code, we rotate it once for every change.
var openLock = function (deadends, target) {
// Store all origin, initially 0000
let nodes = new Set(a);
nodes.add('0000');
// Matched points, such as 0000, are not added to the origin set
const history = new Set(a);
// Initialize the number of rotations
let step = 0;
// Rotate up, for example from 0->1
const plus = function (nums, i) {
let array = nums.split(' ');
if (array[i] === '9') {
array[i] = '0';
} else {
array[i] = Number(array[i]) + 1;
}
return array.join(' ');
};
// Rotate down, for example from 0->9
const miuns = function (nums, i) {
let array = nums.split(' ');
if (array[i] === '0') {
array[i] = '9';
} else {
array[i] = Number(array[i]) - 1;
}
return array.join(' ');
};
// The origin has no destination password
while(! nodes.has(target)) {
// Add the origin set
const newNodes = new Set(a);
// The current origin set
for (const nums of nodes) {
// Jump over a blocked road
if (deadends.includes(nums)) {
continue;
}
// Iterate over the number, rotate up and down, respectively
for (let i = 0; i < nums.length; i++) {
// The result of the rotation, stores the origin of both the upward and downward rotation
let result = plus(nums, i);
// Exclude the selected origin
if(! history.has(result) && ! newNodes.has(result)) {
newNodes.add(result);
}
result = miuns(nums, i);
if(! history.has(result) && ! newNodes.has(result)) {
newNodes.add(result);
}
}
// Check the origin
history.add(nums);
}
step++;
// A newly generated set of origins that will be rotated in the next round
nodes = newNodes;
// This is critical, and the convergence may end up missing
if (nodes.size === 0) {
return - 1;
}
}
return step;
};
Copy the codeThe test results are as follows:
- 43/43 cases passed (652 ms)
- Your runtime beats 33.05 % of javascript submissions
- Each node in the linked list has 10000 entries in the linked list.
The result is correct, but it seems to be running for a long time. Where can I optimize it?
Our current idea is to slowly diffuse from one origin to the destination, which is the target code. It’s like throwing a stone into the water, creating a circle of ripples, and then the ripples eventually hit our target, so if I throw a stone at the target at the same time, and let the two ripples get close to each other, wouldn’t that be much faster? My gut tells me it’s going to be a lot faster, and besides, the ripples don’t have to be very big to find the target, so let’s try that
var openLock = function (deadends, target) {
// Store all origin, initially 0000
let nodes = new Set(a);
nodes.add('0000');
// The target is the origin
let targetNodes = new Set(a);
targetNodes.add(target);
// Matched points, such as 0000, are not added to the origin set
const history = new Set(a);
// Initialize the number of rotations
let step = 0;
// Rotate up, for example from 0->1
const plus = function (nums, i) {
let array = nums.split(' ');
if (array[i] === '9') {
array[i] = '0';
} else {
array[i] = Number(array[i]) + 1;
}
return array.join(' ');
};
// Rotate down, for example from 0->9
const miuns = function (nums, i) {
let array = nums.split(' ');
if (array[i] === '0') {
array[i] = '9';
} else {
array[i] = Number(array[i]) - 1;
}
return array.join(' ');
};
// The origin has no destination password
while (nodes.size > 0 && targetNodes.size > 0) {
// Add the origin set
const newNodes = new Set(a);
// The current origin set
for (const nums of nodes) {
// Jump over a blocked road
if (deadends.includes(nums)) {
continue;
}
/ / meet
if (targetNodes.has(nums)) {
return step;
}
// Iterate over the number, rotate up and down, respectively
for (let i = 0; i < nums.length; i++) {
// The result of the rotation, stores the origin of both the upward and downward rotation
let result = plus(nums, i);
// Exclude the selected origin
if(! history.has(result) && ! newNodes.has(result)) {
newNodes.add(result);
}
result = miuns(nums, i);
if(! history.has(result) && ! newNodes.has(result)) {
newNodes.add(result);
}
}
// Check the origin
history.add(nums);
}
step++;
// Swap the collection, and the targetNodes are checked in the next round
nodes = targetNodes;
// A newly generated set of origins that will be rotated in the next round
targetNodes = newNodes;
}
// No result
return - 1;
};
Copy the codeResults of minor code changes:
- 43/43 cases passed (208 ms)
- Your runtime beats 80 % of javascript submissions
- Each node in the linked list (10000 MB)
To borrow a phrase from Swain (hero of DOTA), “This is the big B”, running time and memory usage are up a notch
Recently in the algorithm to see the content, encountered interesting to share, thanks for support
Interesting algorithm “The best time to buy and sell stocks”
Interesting algorithm ‘climbing stairs’