Press "Enter" to skip to content

Posts published in April 2019

花花酱 8 Puzzles – Bidirectional A* vs Bidirectional BFS

8 Puzzles # nodes expended of 1000 solvable instances

Conclusion:

Nodes expended: BiDirectional A* << A* (Manhattan) <= Bidirectional BFS < A* Hamming << BFS
Running time: BiDirectional A* < Bidirectional BFS <= A* (Manhattan) < A* Hamming << BFS

Code:

C++ Version

花花酱 LeetCode 853. Car Fleet

N cars are going to the same destination along a one lane road.  The destination is target miles away.

Each car i has a constant speed speed[i] (in miles per hour), and initial position position[i] miles towards the target along the road.

A car can never pass another car ahead of it, but it can catch up to it, and drive bumper to bumper at the same speed.

The distance between these two cars is ignored – they are assumed to have the same position.

car fleet is some non-empty set of cars driving at the same position and same speed.  Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.


How many car fleets will arrive at the destination?

Example 1:

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
The cars starting at 10 and 8 become a fleet, meeting each other at 12.
The car starting at 0 doesn't catch up to any other car, so it is a fleet by itself.
The cars starting at 5 and 3 become a fleet, meeting each other at 6.
Note that no other cars meet these fleets before the destination, so the answer is 3.


Note:

  1. 0 <= N <= 10 ^ 4
  2. 0 < target <= 10 ^ 6
  3. 0 < speed[i] <= 10 ^ 6
  4. 0 <= position[i] < target
  5. All initial positions are different.

Solution: Greedy

  1. Compute the time when each car can reach target.
  2. Sort cars by position DESC

Answer will be number slow cars in the time array.

Ex 1: 
target = 12
p = [10,8,0,5,3] 
v = [2,4,1,1,3]


p     t
10    1  <- slow -- ^
 8    1             |
 5    7  <- slow -- ^
 3    3             |
 0   12  <- slow -- ^

Ex 2
target = 10
p = [5, 4, 3, 2, 1]
v = [1, 2, 3, 4, 5]

p     t
5     5  <- slow -- ^
4     3             |
3     2.33          |
2     2             |
1     1.8           |

Time complexity: O(nlogn)
Space complexity: O(n)

C++

Python3

花花酱 LeetCode 45. Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

You can assume that you can always reach the last index.

Solution: Greedy

Jump as far as possible but lazily.

[2, 3, 1, 1, 4]
i    nums[i]   steps   near   far
-      -         0       0     0
0      2         0       0     2
1      3         1       2     4
2      1         1       2     4
3      1         2       4     4
4      4         2       4     8

Time complexity: O(n)
Space complexity: O(1)

C++

花花酱 LeetCode Weekly Contest 134 (1033,1034,1035,1036)

1033. Moving Stones Until Consecutive

Solution: Math

Time complexity: O(1)
Space complexity: O(1)

C++

1034. Coloring A Border

Solution: DFS

Time complexity: O(mn)
Space complexity: O(mn)

C++

1035. Uncrossed Lines

Solution: LCS

Time complexity: O(nm)
Space complexity: O(mn)

C++

1036. Escape a Large Maze

Solution: limited search

Time complexity: O(b^2)
Space complexity: O(b^2)

C++

// Author: Huahua, running time: 168 ms, 49.7 MB class Solution { public: bool isEscapePossible(vector>& blocked, vector& source, vector& target) { for (const auto& p : blocked) b.insert(static_cast(p[0]) << 32 | p[1]); seen = 0; t = target; bool first = dfs(source[0], source[1]); t = source; bool second = dfs(target[0], target[1]); return first && second; } private: const static int kMaxN = 1000000; const static int kMaxSeen = 20000; unordered_set b; vector t; int seen; int tx; int ty; bool dfs(int x, int y) { if (x < 0 || y < 0 || x >= kMaxN || y >= kMaxN) return false; if (x == t[0] && y == t[1]) return true; long key = static_cast(x) << 32 | y; if (b.find(key) != b.end()) return false; b.insert(key); if (++seen > kMaxSeen) return true; return dfs(x + 1, y) || dfs(x – 1, y) || dfs(x, y + 1) || dfs(x, y – 1); } };

花花酱 LeetCode 831. Masking Personal Information

We are given a personal information string S, which may represent either an email address or a phone number.

We would like to mask this personal information according to the following rules:


1. Email address:

We define a name to be a string of length ≥ 2 consisting of only lowercase letters a-z or uppercase letters A-Z.

An email address starts with a name, followed by the symbol '@', followed by a name, followed by the dot '.' and followed by a name. 

All email addresses are guaranteed to be valid and in the format of "name1@name2.name3".

To mask an email, all names must be converted to lowercase and all letters between the first and last letter of the first name must be replaced by 5 asterisks '*'.


2. Phone number:

A phone number is a string consisting of only the digits 0-9 or the characters from the set {'+', '-', '(', ')', ' '}. You may assume a phone number contains 10 to 13 digits.

The last 10 digits make up the local number, while the digits before those make up the country code. Note that the country code is optional. We want to expose only the last 4 digits and mask all other digits.

The local number should be formatted and masked as "***-***-1111", where 1 represents the exposed digits.

To mask a phone number with country code like "+111 111 111 1111", we write it in the form "+***-***-***-1111".  The '+' sign and the first '-' sign before the local number should only exist if there is a country code.  For example, a 12 digit phone number mask should start with "+**-".

Note that extraneous characters like "(", ")", " ", as well as extra dashes or plus signs not part of the above formatting scheme should be removed.

Return the correct “mask” of the information provided.

Example 1:

Input: "LeetCode@LeetCode.com"
Output: "l*****e@leetcode.com"
Explanation: All names are converted to lowercase, and the letters between the
             first and last letter of the first name is replaced by 5 asterisks.
             Therefore, "leetcode" -> "l*****e".

Example 2:

Input: "AB@qq.com"
Output: "a*****b@qq.com"
Explanation: There must be 5 asterisks between the first and last letter 
             of the first name "ab". Therefore, "ab" -> "a*****b".

Example 3:

Input: "1(234)567-890"
Output: "***-***-7890"
Explanation: 10 digits in the phone number, which means all digits make up the local number.

Example 4:

Input: "86-(10)12345678"
Output: "+**-***-***-5678"
Explanation: 12 digits, 2 digits for country code and 10 digits for local number. 

Notes:

  1. S.length <= 40.
  2. Emails have length at least 8.
  3. Phone numbers have length at least 10.

Solution: String

Time complexity: O(n)
Space complexity: O(n)

C++