当前位置: 首页 > article >正文

LeetCode--缺失的第一个正数(41)和 接雨水(42)

目录

缺失的第一个正数

接雨水

0ms,100% 代码


缺失的第一个正数

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/first-missing-positive


题目:给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1:

输入:nums = [1,2,0]
输出:3

示例 2:

输入:nums = [3,4,-1,1]
输出:2

示例 3:

输入:nums = [7,8,9,11,12]
输出:1

提示:

    1 <= nums.length <= 5 * 105
    -231 <= nums[i] <= 231 - 1

思路:

(1)映射一个关系为数组 a[i] 存的值为 i+1,所以当 a[i] = x时,x的下标就位 x-1

(2)0 -> a.length 循环,将 a[i] 放到 a[i] - 1 位置,如果a[a[i] - 1] != a[i] 就将两个数位置调整

(3)循环判断缺失了的数,如果a[i] != i + 1,缺失的数就是 i+1,循环完后还没有找到那就是返回a.length+1

class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {
                //当 nums[i]大于零 且 nums[i]小于nums的长度 且 nums[nums[i - 1]]不等于nums[i] 的时候循环
                //nums[nums[i - 1]]和nums[i]进行交换
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }

        //判断缺失的数
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) return i + 1;
        }
        return nums.length + 1;
    }
}


接雨水

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/trapping-rain-water
 

题目:给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

示例 1:

输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6


解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。

 

示例 2:

输入:height = [4,2,0,3,2,5]
输出:9

提示:

    n == height.length
    1 <= n <= 2 * 104
    0 <= height[i] <= 105

思路:

(1)需要先找到第一个大于0的柱子当做U型的左边

(2)左边固定下来后去找右边的柱子,右边的柱子有两种可能性

1)右边找到的第一个柱子>=左边的柱子

2)右边找到的第一个柱子<左边的柱子,但不能为0

(3)求出左边柱子与右边柱子中间的空隙,这里我使用了穷举的方法尝试所有的可能性

class Solution {
    public int trap(int[] height) {
        int ans = 0;//存放接水的数量
        int left = 0;//存放左边柱子的高度,默认为0
        for(int i = 0; i < height.length; i++) {
            if(height[i] >= 1) {//左侧的柱子必须大于等于一才可以接水
                left = i++;//左侧柱子高度等于i
                int now = 0;
                while(i < height.length && height[i] < height[left]) {//右边小于左边才可以存储
                    now += height[left] - height[i++];//左边减去右边
                }
                if(i < height.length) {
                    ans += now;
                    i--;//for后会有i++,所以要--来抵消++,右边的柱子可以当做下一个U型的左侧柱子
                } else {//右边柱子都比左边的低
                    i = left - 1;//回到左边的左边,i++抵消,重新回到left
                    height[left]--;//每次减去1去匹配右边更低的柱子
                }
            }
        }
        return ans;
    }
}

0ms,100% 代码

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int maxL = height[left], maxR = height[right];
        int res = 0;
        while (left < right) {
            maxL = Math.max(maxL, height[left]);
            maxR = Math.max(maxR, height[right]);
            res += maxR > maxL ? maxL - height[left++] : maxR - height[right--];
        }
        return res;
    }
}

 

 


http://www.kler.cn/a/2034.html

相关文章:

  • 高效准确的PDF解析工具,赋能企业非结构化数据治理
  • 【Spring事务】深入浅出Spring事务从原理到源码
  • 在安卓Android应用中实现二维码图像的保存与条形码文本合并
  • OpenResty、Lua介绍认识
  • Java操作Xml
  • 【QSS样式表 - ⑤】:QLineEdit控件样式
  • Elastic 之 elasticsearch 基本操作
  • 【数据结构】千字深入浅出讲解队列(附原码 | 超详解)
  • 【设计模式】UML、RUP、元素、关系、视图
  • 二分查找法
  • 经典七大比较排序算法 · 下 + 附计数和基数排序
  • 如何用matlab工具箱训练一个SOM神经网络
  • synchronized 加锁 this 和 class 的区别
  • QT | 编写一个简单的上位机
  • GEC6818开发板JPG图像显示,科大讯飞离线语音识别包Linux_aitalk_exp1227_1398d7c6运行demo程序,开发板实现录音
  • 思维导图模板怎么制作?提供几种思路
  • chatgpt3.5和chatgpt4的区别
  • GPT4论文翻译 by GPT4 and Human
  • 网络安全之防火墙
  • Vue2项目总结-电商后台管理系统
  • 软件测试拿了几个20K offer,分享一波面经
  • “工作三年,跳槽要求涨薪50%”,合理吗?
  • LeetCode:35. 搜索插入位置
  • 【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(4)
  • 100天精通Python(可视化篇)——第80天:matplotlib绘制不同种类炫酷柱状图代码实战(簇状、堆积、横向、百分比、3D柱状图)
  • python网上选课系统django-PyCharm