4.数组（四）
https://leetcode-cn.com/tag/array/
题目汇总
75. 颜色分类中等
78. 子集中等
79. 单词搜索中等
80. 删除排序数组中的重复项 II中等
81. 搜索旋转排序数组 II中等
84. 柱状图中最大的矩形困难※※※
85. 最大矩形困难※※※
88. 合并两个有序数组简单
90. 子集 II中等
105. 从前序与中序遍历序列构造二叉树中等
75. 颜色分类中等
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:：不能使用代码库中的排序函数来解决这道题。
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？
思路一：迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
class Solution {
public void sortColors(int[] nums) {
int red = 0;
int white = 0;
int blue = 0;
for(int i=0;i<nums.length;i++){
if(nums[i]==0){
red++;
}else if(nums[i]==1){
white++;
}else{
blue++;
}
}
for(int i=0;i<red;i++){
nums[i]=0;
}
for(int i=red;i<white+red;i++){
nums[i]=1;
}
for(int i=white+red;i<blue+white+red;i++){
nums[i]=2;
}
}
}
思路二：双指针
class Solution {
public void sortColors(int[] nums) {
int left = 0;
int right = nums.length-1;
int i=0;
while(i<=right){
if(nums[i]==0&&i>left){
int temp = nums[i];
nums[i] = nums[left];
nums[left] = temp;
left++;
}else if(nums[i]==2&&i<right){
int temp = nums[i];
nums[i] = nums[right];
nums[right] = temp;
right--;
}
else{
i++;
}
}
}
}
78. 子集中等
给定一组不含重复元素的整数数组
nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
思路一：枚举法
直接遍历，遇到一个数就把所有子集加上该数组成新的子集，遍历完毕即是所有子集
class Solution {
public List<List<Integer>> subsets(int[] nums) {//执行用时：1 ms
List<List<Integer>> res = new ArrayList<>();
res.add(new ArrayList<>());
for(int i=0;i<nums.length;i++){
int size = res.size();
for(int j=0;j<size;j++){
List<Integer> temp = new ArrayList<>(res.get(j));
temp.add(nums[i]);
res.add(temp);
}
}
return res;
}
}
思路二：递归回溯
class Solution {
public List<List<Integer>> subsets(int[] nums) {//执行用时：2 ms在所有 Java 提交中击败了32.96%的用户
List<List<Integer>> res = new ArrayList<>();
backtrack(0, nums, res, new ArrayList<Integer>());
return res;
}
private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> tmp) {
res.add(new ArrayList<>(tmp));
for (int j = i; j < nums.length; j++) {
tmp.add(nums[j]);
backtrack(j + 1, nums, res, tmp);
tmp.remove(tmp.size() - 1);
}
}
}
79. 单词搜索中等
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
思路：回溯
此路不通则返回上一状态并继续尝试
出处https://blog.csdn.net/death05/article/details/103726619
class Solution {
int row;// 总行数
int col;// 总列数
char[][] board;// 原数组
char[] wordArray;// 需要寻找的字符数组
public boolean exist(char[][] board, String word) {
this.board = board;
this.row = board.length;
this.col = board[0].length;
this.wordArray = word.toCharArray();
boolean[][] used = new boolean[row][col];// 标记每一格是否用过的二维数组
// 以每一格为起点开始搜索
for (int i = 0; i<row; i++) {
for (int j = 0; j<col; j++) {
if (dfs(i, j, 0, used)) {
return true;
}
}
}
return false;
}
public boolean dfs(int x, int y, int index, boolean[][] used) {
if (x < 0 || x >= row || y < 0 || y >= col || used[x][y]) {// 当前位置不存在或者使用过，则返回失败
return false;
}
if (board[x][y] != wordArray[index]) {// 当前位的字母不相等，不符合条件，此路不通
return false;
}
if (index == wordArray.length - 1) {// 最后一个字母也相等, 返回成功
return true;
}
used[x][y] = true;// 设置当前格使用过了
// 寻找上下左右是否有符合下一个的情况
boolean flag = dfs(x - 1, y, index + 1, used) || dfs(x + 1, y, index + 1, used) ||
dfs(x, y - 1, index + 1, used) || dfs(x, y + 1, index + 1, used);
// 上下左右的情况都走完了，因此回退，设置当前格没有使用过
used[x][y] = false;
return flag;
}
}
80. 删除排序数组中的重复项 II中等
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
给定 nums = [1,1,1,2,2,3],
函数应返回新长度 length =5, 并且原数组的前五个元素被修改为1, 1, 2, 2, 3
你不需要考虑数组中超出新长度后面的元素。
与26. 删除排序数组中的重复项类似
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成
思路：双指针
class Solution {
public int removeDuplicates(int[] nums) {
if(nums == null || nums.length == 0)
return 0;
if(nums.length < 3)
return nums.length;
int j = 1;//慢指针来记录可以覆写数据的位置
for (int i = 2; i < nums.length; i++)//快指针来遍历整个数组
{
if (nums[i] != nums[j-1])
{
j++;//慢指针后移一位
nums[j] = nums[i];//快指针指向的元素覆写入慢指针指向的单元
}
}
return j+1;
}
}
81. 搜索旋转排序数组 II中等
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组[0,0,1,2,2,5,6]可能变为[2,5,6,0,0,1,2])。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回true，否则返回false。
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
与 33. 搜索旋转排序数组类似
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
思路：二分查找
分为三种情况进行讨论：
(1)1 0 1 1 1，此时nums[left] == nums[mid]，分不清到底是前面有序还是后面有序，此时 start++ 即可，相当于去掉一个重复的干扰项，这是自己没有考虑到的
(2)4 5 6 7 0 1 2，此时nums[left]<=nums[mid]，若nums[left]<=target<nums[mid]，在前半部分进行查找
(3)5 6 7 0 1 2 4，此时nums[left]>nums[mid]，若nums[mid]<target<=nums[right]，在后半部分进行查找
class Solution {
public boolean search(int[] nums, int target) {
if(nums == null || nums.length == 0){
return false;
}
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = (right - left)/2 + left;
if(target == nums[mid])
return true;
//去掉一个重复的干扰项，这步自己没有考虑到
if (nums[left] == nums[mid]){
left++;
continue;
}
else if(nums[left] > nums[mid]){
if(target > nums[mid]&&target <= nums[right]){//在后半部分进行查找
left = mid + 1;
}else{
right = mid - 1;
}
}else{//前半部分有序
if(target >= nums[left]&&target < nums[mid]){
right = mid - 1;
}else{
left = mid + 1;
}
}
}
return false;
}
}
84. 柱状图中最大的矩形困难※※※
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为[2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为10个单位。
输入: [2,1,5,6,2,3]
输出: 10
思路：单调栈
看了以下几篇文章
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/84-by-ikaruga/很好的解释了为什么使用单调栈
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/xiang-jie-dan-diao-zhan-bi-xu-miao-dong-by-sweetie/
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/zhao-liang-bian-di-yi-ge-xiao-yu-ta-de-zhi-by-powc/
遍历每根柱子，以当前柱子 i 的高度作为矩形的高，那么矩形的宽度边界即为向左找到第一个高度小于当前柱体 i 的柱体，向右找到第一个高度小于当前柱体 i 的柱体。
对于每个柱子我们都如上计算一遍以当前柱子作为高的矩形面积，最终比较出最大的矩形面积即可。
class Solution {//执行用时 :15 ms, 在所有 Java 提交中击败了53.09%的用户
public int largestRectangleArea(int[] heights) {
int[] tmp = new int[heights.length + 2];
//在柱体数组的头和尾加了两个高度为 0 的柱体
//将height中从0开始的，长度为height.length的元素复制到temp从1开始的位置上
System.arraycopy(heights, 0, tmp, 1, heights.length);
Stack<Integer> stack = new Stack <>();
stack.push(-1);
int maxarea = 0;
for (int i = 0; i < tmp.length; ++i) {
while (stack.peek() != -1 && tmp[stack.peek()] >= tmp[i]){
maxarea = Math.max(maxarea,tmp[stack.pop()]*(i-stack.peek()-1));
}
stack.push(i);
}
return maxarea;
}
}
85. 最大矩形困难※※※
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6
class Solution {
public int maximalRectangle(char[][] matrix) {//执行用时 :10 ms, 在所有 Java 提交中击败了66.16%的用户
if (matrix.length == 0) {
return 0;
}
int[] heights = new int[matrix[0].length];
int maxArea = 0;
for (int row = 0; row < matrix.length; row++) {
//遍历每一列，更新高度
for (int col = 0; col < matrix[0].length; col++) {
if (matrix[row][col] == '1') {
heights[col] += 1;
} else {
heights[col] = 0;
}
}
//调用上一题的解法，更新函数
maxArea = Math.max(maxArea, largestRectangleArea(heights));
}
return maxArea;
}
public int largestRectangleArea(int[] heights) {
int maxArea = 0;
Stack<Integer> stack = new Stack<>();
int p = 0;
while (p < heights.length) {
//栈空入栈
if (stack.isEmpty()) {
stack.push(p);
p++;
} else {
int top = stack.peek();
//当前高度大于栈顶，入栈
if (heights[p] >= heights[top]) {
stack.push(p);
p++;
} else {
//保存栈顶高度
int height = heights[stack.pop()];
//左边第一个小于当前柱子的下标
int leftLessMin = stack.isEmpty() ? -1 : stack.peek();
//右边第一个小于当前柱子的下标
int RightLessMin = p;
//计算面积
int area = (RightLessMin - leftLessMin - 1) * height;
maxArea = Math.max(area, maxArea);
}
}
}
while (!stack.isEmpty()) {
//保存栈顶高度
int height = heights[stack.pop()];
//左边第一个小于当前柱子的下标
int leftLessMin = stack.isEmpty() ? -1 : stack.peek();
//右边没有小于当前高度的柱子，所以赋值为数组的长度便于计算
int RightLessMin = heights.length;
int area = (RightLessMin - leftLessMin - 1) * height;
maxArea = Math.max(area, maxArea);
}
return maxArea;
}
}
88. 合并两个有序数组简单
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 num1 成为一个有序数组。
说明：
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
思路：双指针，时间复杂度 : O(m + n)
从后往前每次比较两个数组的最后一个数，将大的放入末尾指针后再进行比较，假如有nums2有剩余，再放入开头
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1;
int p2 = n - 1;
int p = m + n - 1;
while(p1 >= 0 && p2 >= 0){
if(nums1[p1]>nums2[p2]){
nums1[p] = nums1[p1];
p1--;
}else{
nums1[p] = nums2[p2];
p2--;
}
p--;
}
if(p2 >= 0){
//参数src，srcPos，dest，destPos，length: 原数组
//原数组，从元数据的起始位置开始，目标数组，目标数组的开始起始位置，要copy的数组的长度
System.arraycopy(nums2, 0, nums1, 0, p2+1);
}
}
}
90. 子集 II中等
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
输入: [1,2,2]
输出:
[[2],[1],[1,2,2],[2,2],[1,2],[]]
与 78. 子集相比，只是增加了去重的步骤
思路：递归回溯
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {//执行用时 :1 ms, 在所有 Java 提交中击败了100.00%的用户
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
backtrack(0, nums, res, new ArrayList<Integer>());
return res;
}
private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> tmp) {
res.add(new ArrayList<>(tmp));
for (int j = i; j < nums.length; j++) {
if (j > i && nums[j] == nums[j - 1]) //去重
continue;
tmp.add(nums[j]);
backtrack(j + 1, nums, res, tmp);
tmp.remove(tmp.size() - 1);
}
}
}
105. 从前序与中序遍历序列构造二叉树中等，与剑指Offer重建二叉树相同
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:你可以假设树中没有重复的元素。
例如，给出前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
思路：递归
根据中序遍历和前序遍历可以确定二叉树，具体过程为：
根据前序序列第一个结点确定根结点
根据根结点在中序序列中的位置分割出左右两个子序列
对左子树和右子树分别递归使用同样的方法继续分解
/**
* Definition for a binary tree node.
* public class TreeNode {//执行用时 :14 ms
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length==0||inorder.length==0)
return null;
TreeNode root = new TreeNode(preorder[0]);
//for(int i = preorder.length-1; i >=0; i--)，从后开始遍历执行用时：9ms
for(int i=0;i<preorder.length;i++){//执行用时 :14 ms
if(inorder[i]==preorder[0]){
root.left = buildTree(Arrays.copyOfRange(preorder,1,i+1),Arrays.copyOfRange(inorder,0,i));
root.right = buildTree(Arrays.copyOfRange(preorder,i+1,preorder.length),
Arrays.copyOfRange(inorder,i+1,inorder.length));
break;
}
}
return root;
}
}
