力扣爆刷第165天之TOP100五连刷91-95(岛屿DFS、打家劫舍、堆排)
文章目录
一、226. 翻转二叉树
题目链接:https://leetcode.cn/problems/invert-binary-tree/description/
思路:翻转二叉树,只需要前序遍历交换左右子树,然后递归遍历左右子树即可。
class Solution {
public TreeNode invertTree(TreeNode root) {
traverse(root);
return root;
}
void traverse(TreeNode root) {
if(root == null) return;
TreeNode t = root.left;
root.left = root.right;
root.right = t;
traverse(root.left);
traverse(root.right);
}
}
二、695. 岛屿的最大面积
题目链接:https://leetcode.cn/problems/max-area-of-island/description/
思路:求最大的岛屿面积,典型的深度优先解题,通过DFS遍历岛屿每次开始遍历一个岛屿时 ,记录岛屿中陆地的数量,遍历完成后进行最大值的记录。
class Solution {
int max = 0, sum = 0;
public int maxAreaOfIsland(int[][] grid) {
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[0].length; j++) {
if(grid[i][j] == 1) {
dfs(grid, i, j);
max = Math.max(max, sum);
sum = 0;
}
}
}
return max;
}
void dfs(int[][] grid, int x, int y) {
if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0) return;
sum++;
grid[x][y] = 0;
dfs(grid, x-1, y);
dfs(grid, x, y-1);
dfs(grid, x+1, y);
dfs(grid, x, y+1);
}
}
三、152. 乘积最大子数组
题目链接:https://leetcode.cn/problems/maximum-product-subarray/description/
思路:本题让求最大子数组的乘积,但是数组元素有正有负,这样就有可能出现正数乘着乘着变成负数,负数乘着乘着变成正数的问题,所以为了防止这样的两极问题的出现,可以专门 维护两个数组,一个是最大数值的数组,一个是最小数组的数组,这样对于每一个位置来说既可以只使用当前元素,也可以与前一个位置的最大乘积或者最小乘积相乘,以此进行比较。
class Solution {
public int maxProduct(int[] nums) {
double[] dpMax = new double[nums.length];
double[] dpMin = new double[nums.length];
dpMax[0] = nums[0];
dpMin[0] = nums[0];
double max = nums[0];
for(int i = 1; i < nums.length; i++) {
dpMax[i] = Math.max(nums[i], Math.max(nums[i] * dpMax[i-1], nums[i] * dpMin[i-1]));
dpMin[i] = Math.min(nums[i], Math.min(nums[i] * dpMax[i-1], nums[i] * dpMin[i-1]));
}
for(double i : dpMax) {
max = Math.max(max, i);
}
return (int)max;
}
}
四、198. 打家劫舍
题目链接:https://leetcode.cn/problems/house-robber/description/
思路:打家劫舍是经典的动态规划问题,本题要求不能连续的打劫两家,否则就会被报警,所以,对于每一家来说,他偷不偷当前这家取决于前两家的状态,如果偷当前这家,前一家就不能偷,如果不偷当前这家,那么前前加就可以偷。
class Solution {
public int rob(int[] nums) {
if(nums.length == 1) return nums[0];
int a = nums[0], b = Math.max(nums[0], nums[1]), c = 0;
for(int i = 2; i < nums.length; i++) {
c = Math.max(nums[i]+a, b);
a = b;
b = c;
}
return b;
}
}
五、912. 排序数组
题目链接:https://leetcode.cn/problems/sort-an-array/
思路:排列算法有很多,一般掌握快排,堆排,归并。堆排的话,只需要先从最后一个非叶子节点开始建立一个大根堆,然后不断的把数组头元素与数组尾元素交换即可。
class Solution {
public int[] sortArray(int[] nums) {
heapSort(nums);
return nums;
}
void heapSort(int[] nums) {
int len = nums.length;
for(int i = len / 2 -1; i >= 0; i--) bulidMaxHeap(nums, i, len);
for(int i = len-1; i > 0; i--) {
int t = nums[0];
nums[0] = nums[i];
nums[i] = t;
bulidMaxHeap(nums, 0, i);
}
}
void bulidMaxHeap(int[] nums, int start, int end) {
int k = start, t = nums[start];
for(int i = start*2+1; i < end; i = i*2+1) {
if(i+1 < end && nums[i] < nums[i+1]) i = i+1;
if(t < nums[i]) {
nums[k] = nums[i];
k = i;
}else break;
}
nums[k] = t;
}
}