题目序号 638、576、547、542、529、531、533、513、490¶
638. Shopping Offers¶
In LeetCode Store, there are some kinds of items to sell. Each item has a price.
However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.
You are given the each item’s price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers.
Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.
You could use any of special offers as many times as you want.
Example 1:
Input: [2,5], [[3,0,5],[1,2,10]], [3,2] Output: 14 Explanation: There are two kinds of items, A and B. Their prices are $2 and $5 respectively. In special offer 1, you can pay $5 for 3A and 0B In special offer 2, you can pay $10 for 1A and 2B. You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.
Example 2:
Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1] Output: 11 Explanation: The price of A is $2, and $3 for B, $4 for C. You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C. You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C. You cannot add more items, though only $9 for 2A ,2B and 1C.
Note:
- There are at most 6 kinds of items, 100 special offers.
- For each item, you need to buy at most 6 of them.
- You are not allowed to buy more items than you want, even if that would lower the overall price.
576. Out of Boundary Paths¶
There is an m by n grid with a ball. Given the start coordinate (i,j) of the ball, you can move the ball to adjacent cell or cross the grid boundary in four directions (up, down, left, right). However, you can at most move N times. Find out the number of paths to move the ball out of grid boundary. The answer may be very large, return it after mod 109 + 7.
Example 1:
Input:m = 2, n = 2, N = 2, i = 0, j = 0 Output: 6 Explanation: https://leetcode.com/static/images/problemset/out_of_boundary_paths_1.png Example 2:
Input:m = 1, n = 3, N = 3, i = 0, j = 1 Output: 12 Explanation: https://leetcode.com/static/images/problemset/out_of_boundary_paths_2.png Note:
- Once you move the ball out of boundary, you cannot move it back.
- The length and height of the grid is in range [1,50].
- N is in range [0,50].
547. Friend Circles¶
There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.
Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.
Example 1:
Input: [[1,1,0],
[1,1,0], [0,0,1]]
Output: 2 Explanation:The 0th and 1st students are direct friends, so they are in a friend circle. The 2nd student himself is in a friend circle. So return 2.
Example 2:
Input: [[1,1,0],
[1,1,1], [0,1,1]]
Output: 1 Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends, so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.
Note:
N is in range [1,200]. M[i][i] = 1 for all students. If M[i][j] = 1, then M[j][i] = 1.
542. 01 Matrix¶
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.
Example 1:
Input:
0 0 0
0 1 0
0 0 0
Output:
0 0 0
0 1 0
0 0 0
Example 2:
Input:
0 0 0
0 1 0
1 1 1
Output:
0 0 0
0 1 0
1 2 1
Note:
- The number of elements of the given matrix will not exceed 10,000.
- There are at least one 0 in the given matrix.
- The cells are adjacent in only four directions: up, down, left and right.
529. Minesweeper¶
扫雷游戏也他妈可以出一道算法题目，我还能说什么，这帮疯子
531. Lonely Pixel I¶
Given a picture consisting of black and white pixels, find the number of black lonely pixels.
The picture is represented by a 2D char array consisting of ‘B’ and ‘W’, which means black and white pixels respectively.
A black lonely pixel is character ‘B’ that located at a specific position where the same row and same column don’t have any other black pixels.
Example:
Input: [[‘W’, ‘W’, ‘B’],
[‘W’, ‘B’, ‘W’], [‘B’, ‘W’, ‘W’]]
Output: 3 Explanation: All the three ‘B’s are black lonely pixels.
Note:
The range of width and height of the input 2D array is [1,500].
题目大意：
给定一个包含字符’W’（白色）和’B’（黑色）的像素矩阵picture。
求所有同行同列有且仅有一个’B’像素的像素个数。
注意：
二维数组的宽度和高度在范围[1,500]之间。 解题思路：
利用数组rows，cols分别记录某行、某列’B’像素的个数。
然后遍历一次picture即可。
533. Lonely Pixel II¶
Given a picture consisting of black and white pixels, and a positive integer N, find the number of black pixels located at some specific row R and column C that align with all the following rules:
Row R and column C both contain exactly N black pixels. For all rows that have a black pixel at column C, they should be exactly the same as row R
The picture is represented by a 2D char array consisting of ‘B’ and ‘W’, which means black and white pixels respectively.
Example:
Input: [[‘W’, ‘B’, ‘W’, ‘B’, ‘B’, ‘W’],
[‘W’, ‘B’, ‘W’, ‘B’, ‘B’, ‘W’], [‘W’, ‘B’, ‘W’, ‘B’, ‘B’, ‘W’], [‘W’, ‘W’, ‘B’, ‘W’, ‘B’, ‘W’]]
N = 3 Output: 6 Explanation: All the bold ‘B’ are the black pixels we need (all ‘B’s at column 1 and 3).
0 1 2 3 4 5 column index
0 [[‘W’, ‘B’, ‘W’, ‘B’, ‘B’, ‘W’], 1 [‘W’, ‘B’, ‘W’, ‘B’, ‘B’, ‘W’], 2 [‘W’, ‘B’, ‘W’, ‘B’, ‘B’, ‘W’], 3 [‘W’, ‘W’, ‘B’, ‘W’, ‘B’, ‘W’]] row index
Take ‘B’ at row R = 0 and column C = 1 as an example: Rule 1, row R = 0 and column C = 1 both have exactly N = 3 black pixels. Rule 2, the rows have black pixel at column C = 1 are row 0, row 1 and row 2. They are exactly the same as row R = 0.
Note:
The range of width and height of the input 2D array is [1,200].
题目大意：
给定一个包含字符’W’（白色）和’B’（黑色）的像素矩阵picture，以及一个整数N。
求所有同行同列恰好有N个’B’像素，并且这N行均相同的像素个数。
注意：
二维数组的宽度和高度在范围[1,500]之间。 解题思路：
利用数组rows，cols分别记录某行、某列’B’像素的个数。
然后利用字典sdict统计每一行像素出现的个数。
最后遍历一次picture即可。
513. Find Bottom Left Tree Value¶
Given a binary tree, find the leftmost value in the last row of the tree.
Example 1:
Input:
2/
1 3
Output: 1
Example 2:
Input:
1/
2 3
/ /
- 4 5 6
7
Output: 7
Note: You may assume the tree (i.e., the given root node) is not NULL.
490. The Maze¶
迷宫一共有两道题目，描述特别多，估计也都是废话
There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the ball’s start position, the destination and the maze, find the shortest distance for the ball to stop at the destination. The distance is defined by the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included). If the ball cannot stop at the destination, return -1.
The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.
Example 1
Input 1: a maze represented by a 2D array
0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0
Input 2: start coordinate (rowStart, colStart) = (0, 4) Input 3: destination coordinate (rowDest, colDest) = (4, 4)
Output: 12 Explanation: One shortest way is : left -> down -> left -> down -> right -> down -> right.
The total distance is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.
https://leetcode.com/static/images/problemset/maze_1_example_1.png?_=6725380
Example 2
Input 1: a maze represented by a 2D array
0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0
Input 2: start coordinate (rowStart, colStart) = (0, 4) Input 3: destination coordinate (rowDest, colDest) = (3, 2)
Output: -1 Explanation: There is no way for the ball to stop at the destination.
Note:
There is only one ball and one destination in the maze. Both the ball and the destination exist on an empty space, and they will not be at the same position initially. The given maze does not contain border (like the red rectangle in the example pictures), but you could assume the border of the maze are all walls. The maze contains at least 2 empty spaces, and both the width and height of the maze won’t exceed 100.
这道题是之前那道The Maze的拓展，那道题只让我们判断能不能在终点位置停下，而这道题让我们求出到达终点的最少步数。其实本质都是一样的，难点还是在于对于一滚到底的实现方法，唯一不同的是，这里我们用一个二位数组dists，其中dists[i][j]表示到达(i,j)这个位置时需要的最小步数，我们都初始化为整型最大值，在后在遍历的过程中不断用较小值来更新每个位置的步数值，最后我们来看终点位置的步数值，如果还是整型最大值的话，说明没法在终点处停下来，返回-1，否则就返回步数值。注意在压入栈的时候，我们对x和y进行了判断，只有当其不是终点的时候才压入栈，这样是做了优化，因为如果小球已经滚到终点了，我们就不要让它再滚了，就不把终点位置压入栈，免得它还滚，参见代码如下：