鸡蛋掉落问题
你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。
你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
你的目标是确切地知道 F 的值是多少。
无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
思路：这个问题和智力题里，猜数字大小很像。遍历1-N层，计算在每一层扔鸡蛋的最小值，用递归的方式。假设在i层扔鸡蛋，对应鸡蛋碎了，没碎两种可能
public static int superEggDrop(int K, int N) {
if( N == 0 || N == 1 || K ==1){
return N;
}
int minimun = N;
for(int i = 1; i <= N; i++){ // 依次遍历从第1层到第N层开始扔第1个鸡蛋的情况
int tMin = Math.max(superEggDrop(K-1, i-1), superEggDrop(K, N-i));
minimun = Math.min(minimun, 1 + tMin);
}
return minimun;
}
// 以上是最简单的解法，改进的办法是加入中间表，减少重复的节点计算， 如下所示：
class Solution {
public int superEggDrop(int K, int N) {
int[][] middleResults = new int[K + 1][N + 1];
for (int i = 1; i <= N; i++) {
middleResults[1][i] = i; // only one egg
middleResults[0][i] = 0; // no egg
}
for (int i = 1; i <= K; i++) {
middleResults[i][0] = 0; // zero floor
}
for (int k = 2; k <= K; k++) { // start from two egg
for (int n = 1; n <= N; n++) {
int tMinDrop = N * N;
for (int x = 1; x <= n; x++) {
tMinDrop = Math.min(tMinDrop, 1 + Math.max(middleResults[k - 1][x - 1], middleResults[k][n - x]));
}
middleResults[k][n] = tMinDrop;
}
}
return middleResults[K][N];
}
}
最大正方形
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
思路：动态规划，如果是最大矩阵，就是dfs
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int m = matrix.size(), n = matrix[0].size(), res = 0;
vector<vector<int>> dp(m, vector<int>(n, 0));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 || j == 0) dp[i][j] = matrix[i][j] - '0';
else if (matrix[i][j] == '1') {
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;
}
res = max(res, dp[i][j]);
}
}
return res * res;
}
俄罗斯套娃
输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
思路：先对vector<pair>排序，然后动态规划
int maxEnvelopes(vector<pair<int, int>>& envelopes) {
vector<int> dp(envelopes.size(), 1);
sort(envelopes.begin(), envelopes.end());
int res = 0;
for (int i = 0; i < envelopes.size(); ++i){
for (int j = 0; j < i; ++j){
if (envelopes[i].first > envelopes[j].first && envelopes[i].second > envelopes[j].second)
dp[i] = max(dp[i], dp[j] + 1);
}
res = max(res, dp[i]);
}
return res;
}
岛屿的最大面积
示例 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。
示例 2:
[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。
解题思路：
此题与下面岛屿数量的思路类似，遍历二维数组，当遇到一个岛屿时进入岛屿将这个位置的置为0然后统计他周围陆地的1的个数，依次递归。
public int maxAreaOfIsland(int[][] grid) {
int max = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == 1) {
int num = depthSearch(grid,i,j);
max = Math.max(num, max);
}
}
}
return max;
}
public int depthSearch(int[][] grid, int i, int j) {
if (i >= 0 && i < grid.length && j >= 0 && j < grid[i].length && grid[i][j] == 1) {
grid[i][j] = 0;
int num = 1 + depthSearch(grid, i + 1, j) + depthSearch(grid, i - 1, j) + depthSearch(grid, i, j + 1) + depthSearch(grid, i, j - 1);
return num;
}
return 0;
}
岛屿数量
输入:
11000
11000
00100
00011
输出: 3
思路：这道求岛屿数量的题，本质是求矩阵中连续区域的个数，很容易想到需要用深度优先搜索 DFS 来解，我们需要建立一个 visited 数组用来记录某个位置是否被访问过，对于一个为 ‘1’ 且未被访问过的位置，我们递归进入其上下左右位置上为 ‘1’ 的数，将其 visited 对应值赋为 true，继续进入其所有相连的邻位置，这样可以将这个连通区域所有的数找出来，并将其对应的 visited 中的值赋 true，找完次区域后，我们将结果 res 自增 1，然后我们在继续找下一个为 ‘1’ 且未被访问过的位置，以此类推直至遍历完整个原数组即可得到最终结果。
public int numIslands(char[][] grid) {
if (grid.length == 0 || grid[0].length == 0) return 0;
int n = grid.length, m = grid[0].length;
boolean[][] visited = new boolean[n][m];
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '1' && !visited[i][j]) {
numIslandsDFS(grid, visited, i, j);
count++;
}
}
}
return count++;
}
void numIslandsDFS(char[][] grid, boolean[][] visited, int x, int y) {
if (x < 0 || x >= grid.length) return;
if (y < 0 || y >= grid[0].length) return;
if (grid[x][y] != '1' || visited[x][y]) return;
visited[x][y] = true;
numIslandsDFS(grid, visited, x - 1, y);
numIslandsDFS(grid, visited, x + 1, y);
numIslandsDFS(grid, visited, x, y - 1);
numIslandsDFS(grid, visited, x, y + 1);
}
岛屿的周长
输入:
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]
输出: 16
解释: 它的周长是下面图片中的 16 个黄色的边：
重点关注前面遍历过得方格，如果之前有相邻方格，就-2;
int islandPerimeter(vector<vector<int>>& grid) {
if (grid.size() == 0) {
return 0;
}
int rsp = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[i].size(); j++) {
if (grid[i][j] == 1) {
rsp += 4;
if (i > 0 && grid[i - 1][j] == 1) {
rsp -= 2;
}
if (j > 0 && grid[i][j - 1] == 1) {
rsp -= 2;
}
}
}
}
return rsp;
}
图像渲染，洪水泛滥
输入:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析:
在图像的正中间，(坐标(sr,sc)=(1,1)),
在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，
因为它不是在上下左右四个方向上与初始点相连的像素点。
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
int initColor=image[sr][sc];
if(newColor == initColor)return image;//原来的颜色和渲染后的颜色竟然一样？！
dfs(image ,sr,sc,newColor,initColor);
return image;
}
private void dfs(int[][] image, int sr, int sc, int newColor,int initColor){
image[sr][sc]=newColor;
if(sr>0&& image[sr - 1][sc] == initColor)
dfs(image ,sr-1,sc,newColor,initColor);
if(sr<image.length-1&& image[sr + 1][sc] == initColor)
dfs(image ,sr+1,sc,newColor,initColor);
if(sc>0&& image[sr][sc-1] == initColor)
dfs(image ,sr,sc-1,newColor,initColor);
if(sc<image[0].length-1&& image[sr][sc+1] == initColor)
dfs(image ,sr,sc+1,newColor,initColor);
}
