美文网首页
4.数组(四)

4.数组(四)

作者: 今天柚稚了么 | 来源:发表于2020-04-16 22:23 被阅读0次

    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

    出处:https://leetcode-cn.com/problems/maximal-rectangle/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-1-8/

    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;
        }
    }
    

    相关文章

      网友评论

          本文标题:4.数组(四)

          本文链接:https://www.haomeiwen.com/subject/garbyhtx.html