On the sea represented by a cartesian plane, each ship is located at an integer point, and each integer point may contain at most 1 ship.
You have a function Sea.hasShips(topRight, bottomLeft) which takes two points as arguments and returns true if and only if there is at least one ship in the rectangle represented by the two points, including on the boundary.
Given two points, which are the top right and bottom left corners of a rectangle, return the number of ships present in that rectangle. It is guaranteed that there are at most 10 ships in that rectangle.
Submissions making more than 400 calls to hasShips will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.
Example :
Input:
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3
Explanation: From [0,0] to [4,4] we can count 3 ships within the range.
Constraints:
On the input ships is only given to initialize the map internally. You must solve this problem “blindfolded”. In other words, you must find the answer using the given hasShips API, without knowing the ships position.
0 <= bottomLeft[0] <= topRight[0] <= 1000
0 <= bottomLeft[1] <= topRight[1] <= 1000
Solution: Divide and Conquer
If the current rectangle contains ships, subdivide it into 4 smaller ones until 1) no ships contained 2) the current rectangle is a single point (e.g. topRight == bottomRight)
Time complexity: O(logn) Space complexity: O(logn)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Author: Huahua
classSolution{
public:
// Modify the interface to pass sea as a reference.
A decimal number can be converted to its Hexspeak representation by first converting it to an uppercase hexadecimal string, then replacing all occurrences of the digit 0 with the letter O, and the digit 1 with the letter I. Such a representation is valid if and only if it consists only of the letters in the set {"A", "B", "C", "D", "E", "F", "I", "O"}.
Given a string num representing a decimal integer N, return the Hexspeak representation of N if it is valid, otherwise return "ERROR".
Example 1:
Input: num = "257"
Output: "IOI"
Explanation: 257 is 101 in hexadecimal.
Example 2:
Input: num = "3"
Output: "ERROR"
Constraints:
1 <= N <= 10^12
There are no leading zeros in the given string.
All answers must be in uppercase letters.
Solution: Simulation
Time complexity: O(logn) Space complexity: O(logn)
Storekeeper is a game in which the player pushes boxes around in a warehouse trying to get them to target locations.
The game is represented by a grid of size n*m, where each element is a wall, floor, or a box.
Your task is move the box 'B' to the target position 'T' under the following rules:
Player is represented by character 'S' and can move up, down, left, right in the grid if it is a floor (empy cell).
Floor is represented by character '.' that means free cell to walk.
Wall is represented by character '#' that means obstacle (impossible to walk there).
There is only one box 'B' and one target cell 'T' in the grid.
The box can be moved to an adjacent free cell by standing next to the box and then moving in the direction of the box. This is a push.
The player cannot walk through the box.
Return the minimum number of pushes to move the box to the target. If there is no way to reach the target, return -1.
Example 1:
Input: grid = [["#","#","#","#","#","#"],
["#","T","#","#","#","#"],
["#",".",".","B",".","#"],
["#",".","#","#",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
Output: 3
Explanation: We return only the number of times the box is pushed.
grid contains only characters '.', '#', 'S' , 'T', or 'B'.
There is only one character 'S', 'B' and 'T' in the grid.
Solution: BFS + DFS
BFS to search by push steps to find miminal number of pushes. Each time we move from the previous position (initial position or last push position) to a new push position. Use DFS to check that whether that path exist or not.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// Author: Huahua
structNode{
intbx;
intby;
intpx;
intpy;
intkey()const{return((by*20+bx)<<16)|(py*20+px);}
};
classSolution{
public:
intminPushBox(vector<vector<char>>& grid) {
const int n = grid.size();
constintm=grid[0].size();
Node start;
Node end;
for(inty=0;y<n;++y)
for(intx=0;x<m;++x)
if(grid[y][x]=='B'){
start.bx=x;
start.by=y;
}elseif(grid[y][x]=='S'){
start.px=x;
start.py=y;
}elseif(grid[y][x]=='T'){
end.bx=x;
end.by=y;
}
auto hasPath=[&](const Node& cur, int tx, int ty) {
vector<int> seen(m*n);
function<bool(int,int)>dfs=[&](int x, int y) {
if (x < 0 || x >= m || y < 0 || y >= n || grid[y][x] == '#')