LC675 Cut Off Trees for Golf Event

Problem

You are asked to cut off trees in a forest for a golf event. The forest is represented as a non-negative 2D map, in this map:

  1. 0 represents the obstacle can’t be reached.
  2. 1 represents the ground can be walked through.
  3. The place with number bigger than 1 represents a tree can be walked through, and this positive number represents the tree’s height.

In one step you can walk in any of the four directions top, bottom, left and right also when standing in a point which is a tree you can decide whether or not to cut off the tree.

You are asked to cut off all the trees in this forest in the order of tree’s height - always cut off the tree with lowest height first. And after cutting, the original place has the tree will become a grass (value 1).

You will start from the point (0, 0) and you should output the minimum steps you need to walk to cut off all the trees. If you can’t cut off all the trees, output -1 in that situation.

You are guaranteed that no two trees have the same height and there is at least one tree needs to be cut off.

Example 1:

1
2
3
4
5
6
7
Input: 
[
 [1,2,3],
 [0,0,4],
 [7,6,5]
]
Output: 6

Example 2:

1
2
3
4
5
6
7
Input: 
[
 [1,2,3],
 [0,0,0],
 [7,6,5]
]
Output: -1

Example 3:

1
2
3
4
5
6
7
8
Input: 
[
 [2,3,4],
 [0,0,5],
 [8,7,6]
]
Output: 6
Explanation: You started from the point (0,0) and you can cut off the tree in (0,0) directly without walking.

Constraints:

  • 1 <= forest.length <= 50
  • 1 <= forest[i].length <= 50
  • 0 <= forest[i][j] <= 10^9
Think

首先获得所有的树，然后排序，从最矮的开始，每次从当前树的位置bfs到后一棵树。

Code 
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
int cutOffTree(vector<vector<int>>& forest) {
    int m = forest.size(), n = forest[0].size();
    int res = 0, row = 0, col = 0;
    vector<vector<int>> trees;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (forest[i][j] > 1) trees.push_back({forest[i][j], i, j});
        }
    }
    sort(trees.begin(), trees.end());
    for(int i = 0; i < trees.size(); i++){
        int cnt = helper(forest, row, col, trees[i][1], trees[i][2]);
        if(cnt == -1) return -1;
        res += cnt;
        row = trees[i][1];
        col = trees[i][2];
    }
    return res;
}

int helper(vector<vector<int>>& forest, int row, int col, int treeRow, int treeCol) {
    if(row == treeRow && col == treeCol) return 0;
    int m = forest.size(), n = forest[0].size();
    queue<int> q;
    q.push(row * n + col);
    vector<vector<int>> visited(m, vector<int>(n));
    vector<int> dir{-1, 0, 1, 0, -1};
    int cnt = 0;
    while(!q.empty()){
        cnt++;
        int len = q.size();
        for(int i = 0; i < len; i++){
            int r = q.front() / n, c = q.front() % n;
            q.pop();
            for(int j = 0; j < 4; j++){
                int x = r + dir[j], y = c + dir[j + 1];
                if(x < 0 || x >= m || y < 0 || y >= n || visited[x][y] == 1 || forest[x][y] == 0) continue;
                if(x == treeRow && y == treeCol) return cnt;
                visited[x][y] = 1;
                q.push(x * n + y);
            }
        }
    }
    return -1;
}

LC690 Employee Importance

Problem

You are given a data structure of employee information, which includes the employee’s unique id, their importance value and their direct subordinates’ id.

For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is not direct.

Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all their subordinates.

Example 1:

1
2
3
4
Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
Output: 11
Explanation:
Employee 1 has importance value 5, and he has two direct subordinates: employee 2 and employee 3. They both have importance value 3. So the total importance value of employee 1 is 5 + 3 + 3 = 11.

Note:

  1. One employee has at most one direct leader and may have several subordinates.
  2. The maximum number of employees won’t exceed 2000.
Think

BFS, p.s. 可以不使用visited数组，因为一个人只有一个领导。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int getImportance(vector<Employee*> employees, int id) {
        unordered_map<int, Employee*> map;
        unordered_set<int> visited;
        for(auto e: employees) map[e->id] = e;
        int res = 0;
        queue<int> q;
        q.push(id);
        visited.insert(id);
        while(!q.empty()){
            int len = q.size();
            for(int i = 0; i < len; i++){
                Employee *cur = map[q.front()];
                q.pop();
                res += cur->importance;
                for(int next: cur->subordinates){
                    if(!visited.count(next)){
                        q.push(next);
                        visited.insert(next);
                    }
                }
            }
        }
        return res;
    }

LC744 Find Smallest Letter Greater Than Target

Problem

Given a list of sorted characters letters containing only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.

Letters also wrap around. For example, if the target is target = 'z' and letters = ['a', 'b'], the answer is 'a'.

Examples:

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
Input:
letters = ["c", "f", "j"]
target = "a"
Output: "c"

Input:
letters = ["c", "f", "j"]
target = "c"
Output: "f"

Input:
letters = ["c", "f", "j"]
target = "d"
Output: "f"

Input:
letters = ["c", "f", "j"]
target = "g"
Output: "j"

Input:
letters = ["c", "f", "j"]
target = "j"
Output: "c"

Input:
letters = ["c", "f", "j"]
target = "k"
Output: "c"

Note:

  1. letters has a length in range [2, 10000].
  2. letters consists of lowercase letters, and contains at least 2 unique letters.
  3. target is a lowercase letter.
Think

Upper_bound

Code 
1
2
3
4
5
char nextGreatestLetter(vector<char>& letters, char target) {
    auto it = upper_bound(letters.begin(), letters.end(), target);
    if(it == letters.end()) return letters[0];
    return *it;
}

LC753 Cracking the Safe

Problem

There is a box protected by a password. The password is a sequence of n digits where each digit can be one of the first k digits 0, 1, ..., k-1.

While entering a password, the last n digits entered will automatically be matched against the correct password.

For example, assuming the correct password is "345", if you type "012345", the box will open because the correct password matches the suffix of the entered password.

Return any password of minimum length that is guaranteed to open the box at some point of entering it.

Example 1:

1
2
3
Input: n = 1, k = 2
Output: "01"
Note: "10" will be accepted too.

Example 2:

1
2
3
Input: n = 2, k = 2
Output: "00110"
Note: "01100", "10011", "11001" will be accepted too.

Note:

  1. n will be in the range [1, 4].
  2. k will be in the range [1, 10].
  3. k^n will be at most 4096.
Think

贪心算法，每次修改最后一位数字，注意内层要反向遍历

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
string crackSafe(int n, int k) {
    string res = string(n, '0');
    unordered_set<string> visited;
    visited.insert(res);
    for(int i = 0; i < pow(k, n); i++)
    {
        string pre = res.substr(res.size() - n + 1, n - 1);
        for(int j = k - 1; j >= 0; j--){
            string cur = pre + to_string(j);
            if(!visited.count(cur)){
                visited.insert(cur);
                res += to_string(j);
                break;
            }
        }
    }
    return res;
}

LC764 Largest Plus Sign

Problem

In a 2D grid from (0, 0) to (N-1, N-1), every cell contains a 1, except those cells in the given list mines which are 0. What is the largest axis-aligned plus sign of 1s contained in the grid? Return the order of the plus sign. If there is none, return 0.

An “axis-aligned plus sign of 1s of order k” has some center grid[x][y] = 1 along with 4 arms of length k-1 going up, down, left, and right, and made of 1s. This is demonstrated in the diagrams below. Note that there could be 0s or 1s beyond the arms of the plus sign, only the relevant area of the plus sign is checked for 1s.

Examples of Axis-Aligned Plus Signs of Order k:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Order 1:
000
010
000

Order 2:
00000
00100
01110
00100
00000

Order 3:
0000000
0001000
0001000
0111110
0001000
0001000
0000000

Example 1:

1
2
3
4
5
6
7
8
9
Input: N = 5, mines = [[4, 2]]
Output: 2
Explanation:
11111
11111
11111
11111
11011
In the above grid, the largest plus sign can only be order 2.  One of them is marked in bold.

Example 2:

1
2
3
4
Input: N = 2, mines = []
Output: 1
Explanation:
There is no plus sign of order 2, but there is of order 1.

Example 3:

1
2
3
4
Input: N = 1, mines = [[0, 0]]
Output: 0
Explanation:
There is no plus sign, so return 0.

Note:

  1. N will be an integer in the range [1, 500].
  2. mines will have length at most 5000.
  3. mines[i] will be length 2 and consist of integers in the range [0, N-1].
  4. (Additionally, programs submitted in C, C++, or C# will be judged with a slightly smaller time limit.)
Think

分别建立上下左右四个方向上的dp数组，然后取四个当中的最小值即可。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) {
    int res = 0;
    vector<vector<int>> dp(N, vector<int>(N, N));
    for(auto mine: mines) dp[mine[0]][mine[1]] = 0;
    for(int i = 0; i < N; i++){
        int l = 0, r = 0, u = 0, d = 0;
        for(int j = 0, k = N - 1; j < N; j++, k--){
            l = dp[i][j] ? l + 1: 0;
            r = dp[j][i] ? r + 1: 0;
            u = dp[i][k] ? u + 1: 0;
            d = dp[k][i] ? d + 1: 0;
            dp[i][j] = min(dp[i][j], l);
            dp[j][i] = min(dp[j][i], r);
            dp[i][k] = min(dp[i][k], u);
            dp[k][i] = min(dp[k][i], d);
        }
    }

    for (int k = 0; k < N * N; ++k) res = max(res, dp[k / N][k % N]);
    return res;
}

LC787 Cheapest Flights Within K Stops

Problem

There are n cities connected by m flights. Each flight starts from city u and arrives at v with a price w.

Now given all the cities and flights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Example 1:
Input: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
Output: 200
Explanation: 
The graph looks like this:


The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.
Example 2:
Input: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
Output: 500
Explanation: 
The graph looks like this:


The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.

Constraints:

  • The number of nodes n will be in range [1, 100], with nodes labeled from 0 to n`` - 1.
  • The size of flights will be in range [0, n * (n - 1) / 2].
  • The format of each flight will be (src, ``dst``, price).
  • The price of each flight will be in the range [1, 10000].
  • k is in the range of [0, n - 1].
  • There will not be any duplicated flights or self cycles.
Think
Code

LC

Problem
Think
Code

LC

Problem
Think
Code

LC

Problem
Think
Code

LC

Problem
Think
Code

LC

Problem
Think
Code

LC

Problem
Think
Code

LC

Problem
Think
Code

LC

Problem
Think
Code

LC

Problem
Think
Code