【题解】—— LeetCode一周小结28

🌟欢迎来到 我的博客 —— 探索技术的无限可能!


🌟博客的简介(文章目录)


【题解】—— 每日一道题目栏


上接:【题解】—— LeetCode一周小结27

8.寻找数组的中心下标

题目链接:724. 寻找数组的中心下标

给你一个整数数组 nums ,请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端,那么左侧数之和视为 0 ,因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标,应该返回 最靠近左边 的那一个。如果数组不存在中心下标,返回 -1 。

示例 1:

输入:nums = [1, 7, 3, 6, 5, 6]

输出:3

解释:

中心下标是 3 。

左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ,

右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ,二者相等。

示例 2:

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

输出:-1

解释:

数组中不存在满足此条件的中心下标。

示例 3:

输入:nums = [2, 1, -1]

输出:0

解释:

中心下标是 0 。

左侧数之和 sum = 0 ,(下标 0 左侧不存在元素),

右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

提示:

1 <= nums.length <= 104

-1000 <= nums[i] <= 1000

题解:
方法:遍历数组
        

class Solution {
    public int pivotIndex(int[] nums) {
        int s = 0;
        for (int num : nums) {
            s += num;
        }
        int leftS = 0;
        for (int i = 0; i < nums.length; i++) {
            if (leftS * 2 == s - nums[i]) {
                return i;
            }
            leftS += nums[i];
        }
        return -1;
    }
}


9.最小化曼哈顿距离

题目链接:3102. 最小化曼哈顿距离

给你一个下标从 0 开始的数组 points ,它表示二维平面上一些点的整数坐标,其中 points[i] = [xi, yi] 。

两点之间的距离定义为它们的
曼哈顿距离

请你恰好移除一个点,返回移除后任意两点之间的 最大 距离可能的 最小 值。

示例 1:

输入:points = [[3,10],[5,15],[10,2],[4,4]]

输出:12

解释:移除每个点后的最大距离如下所示:

  • 移除第 0 个点后,最大距离在点 (5, 15) 和 (10, 2) 之间,为 |5 - 10| + |15 - 2| = 18 。
  • 移除第 1 个点后,最大距离在点 (3, 10) 和 (10, 2) 之间,为 |3 - 10| + |10 - 2| = 15 。
  • 移除第 2 个点后,最大距离在点 (5, 15) 和 (4, 4) 之间,为 |5 - 4| + |15 - 4| = 12 。
  • 移除第 3 个点后,最大距离在点 (5, 15) 和 (10, 2) 之间的,为 |5 - 10| + |15 - 2| = 18 。

在恰好移除一个点后,任意两点之间的最大距离可能的最小值是 12 。

示例 2:

输入:points = [[1,1],[1,1],[1,1]]

输出:0

解释:移除任一点后,任意两点之间的最大距离都是 0 。

提示:

3 <= points.length <= 105

points[i].length == 2

1 <= points[i][0], points[i][1] <= 108

题解:
方法:维护最大次大、最小次小
        
参考:【图解】曼哈顿距离转切比雪夫距离

class Solution {
    public int minimumDistance(int[][] points) {
        final int INF = Integer.MAX_VALUE;
        int maxX1 = -INF, maxX2 = -INF, maxY1 = -INF, maxY2 = -INF;
        int minX1 = INF, minX2 = INF, minY1 = INF, minY2 = INF;

        for (int[] p : points) {
            int x = p[0] + p[1];
            int y = p[1] - p[0];

            // x 最大次大
            if (x > maxX1) {
                maxX2 = maxX1;
                maxX1 = x;
            } else if (x > maxX2) {
                maxX2 = x;
            }

            // x 最小次小
            if (x < minX1) {
                minX2 = minX1;
                minX1 = x;
            } else if (x < minX2) {
                minX2 = x;
            }

            // y 最大次大
            if (y > maxY1) {
                maxY2 = maxY1;
                maxY1 = y;
            } else if (y > maxY2) {
                maxY2 = y;
            }

            // y 最小次小
            if (y < minY1) {
                minY2 = minY1;
                minY1 = y;
            } else if (y < minY2) {
                minY2 = y;
            }
        }

        int ans = INF;
        for (int[] p : points) {
            int x = p[0] + p[1];
            int y = p[1] - p[0];
            int dx = (x == maxX1 ? maxX2 : maxX1) - (x == minX1 ? minX2 : minX1);
            int dy = (y == maxY1 ? maxY2 : maxY1) - (y == minY1 ? minY2 : minY1);
            ans = Math.min(ans, Math.max(dx, dy));
        }
        return ans;
    }
}

10.统计移除递增子数组的数目 I

题目链接:2970. 统计移除递增子数组的数目 I

给你一个下标从 0 开始的 正 整数数组 nums 。

如果 nums 的一个子数组满足:移除这个子数组后剩余元素 严格递增 ,那么我们称这个子数组为 移除递增 子数组。比方说,[5, 3, 4, 6, 7] 中的 [3, 4] 是一个移除递增子数组,因为移除该子数组后,[5, 3, 4, 6, 7] 变为 [5, 6, 7] ,是严格递增的。

请你返回 nums 中 移除递增 子数组的总数目。

注意 ,剩余元素为空的数组也视为是递增的。

子数组 指的是一个数组中一段非空且连续的元素序列。

示例 1:

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

输出:10

解释:10 个移除递增子数组分别为:[1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3],
[2,3,4] 和 [1,2,3,4]。移

除任意一个子数组后,剩余元素都是递增的。注意,空数组不是移除递增子数组。

示例 2:

输入:nums = [6,5,7,8]

输出:7

解释:7 个移除递增子数组分别为:[5], [6], [5,7], [6,5], [5,7,8], [6,5,7] 和 [6,5,7,8]

nums 中只有这 7 个移除递增子数组。

示例 3:

输入:nums = [8,7,6,6]

输出:3

解释:3 个移除递增子数组分别为:[8,7,6], [7,6,6] 和 [8,7,6,6] 。注意 [8,7] 不是移除递增子数组因为

移除 [8,7] 后 nums 变为 [6,6] ,它不是严格递增的。

提示:

1 <= nums.length <= 50

1 <= nums[i] <= 50

题解:
方法:双指针
        

class Solution {
    public int incremovableSubarrayCount(int[] nums) {
        int i = 0, n = nums.length;
        while (i + 1 < n && nums[i] < nums[i + 1]) {
            ++i;
        }
        if (i == n - 1) {
            return n * (n + 1) / 2;
        }
        int ans = i + 2;
        for (int j = n - 1; j > 0; --j) {
            while (i >= 0 && nums[i] >= nums[j]) {
                --i;
            }
            ans += i + 2;
            if (nums[j - 1] >= nums[j]) {
                break;
            }
        }
        return ans;
    }
}

11.统计移除递增子数组的数目 II

题目链接:2972. 统计移除递增子数组的数目 II

给你一个下标从 0 开始的 正 整数数组 nums 。

如果 nums 的一个子数组满足:移除这个子数组后剩余元素 严格递增 ,那么我们称这个子数组为 移除递增 子数组。比方说,[5, 3, 4, 6, 7] 中的 [3, 4] 是一个移除递增子数组,因为移除该子数组后,[5, 3, 4, 6, 7] 变为 [5, 6, 7] ,是严格递增的。

请你返回 nums 中 移除递增 子数组的总数目。

注意 ,剩余元素为空的数组也视为是递增的。

子数组 指的是一个数组中一段连续的元素序列。

示例 1:

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

输出:10

解释:10 个移除递增子数组分别为:[1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3],
[2,3,4] 和 [1,2,3,4]。移 除任意一个子数组后,剩余元素都是递增的。注意,空数组不是移除递增子数组。

示例 2:

输入:nums = [6,5,7,8]

输出:7

解释:7 个移除递增子数组分别为:[5], [6], [5,7], [6,5], [5,7,8], [6,5,7] 和 [6,5,7,8]

nums 中只有这 7 个移除递增子数组。

示例 3:

输入:nums = [8,7,6,6]

输出:3

解释:3 个移除递增子数组分别为:[8,7,6], [7,6,6] 和 [8,7,6,6] 。注意 [8,7] 不是移除递增子数组因为移除 [8,7] 后 nums 变为 [6,6] ,它不是严格递增的。

提示:

1 <= nums.length <= 105

1 <= nums[i] <= 109

题解:
方法:双指针
        

class Solution {
    public long incremovableSubarrayCount(int[] a) {
        int n = a.length;
        int i = 0;
        while (i < n - 1 && a[i] < a[i + 1]) {
            i++;
        }
        if (i == n - 1) { // 每个非空子数组都可以移除
            return (long) n * (n + 1) / 2;
        }

        long ans = i + 2; // 不保留后缀的情况,一共 i+2 个
        // 枚举保留的后缀为 a[j:]
        for (int j = n - 1; j == n - 1 || a[j] < a[j + 1]; j--) {
            while (i >= 0 && a[i] >= a[j]) {
                i--;
            }
            // 可以保留前缀 a[:i+1], a[:i], ..., a[:0] 一共 i+2 个
            ans += i + 2;
        }
        return ans;
    }
}


12.最小数字游戏

题目链接:2974. 最小数字游戏

你有一个下标从 0 开始、长度为 偶数 的整数数组 nums ,同时还有一个空数组 arr 。Alice 和 Bob 决定玩一个游戏,游戏中每一轮 Alice 和 Bob 都会各自执行一次操作。游戏规则如下:

每一轮,Alice 先从 nums 中移除一个 最小 元素,然后 Bob 执行同样的操作。
接着,Bob 会将移除的元素添加到数组 arr 中,然后 Alice 也执行同样的操作。
游戏持续进行,直到 nums 变为空。
返回结果数组 arr 。

示例 1:

输入:nums = [5,4,2,3]

输出:[3,2,5,4]

解释:第一轮,Alice 先移除 2 ,然后 Bob 移除 3 。然后 Bob 先将 3 添加到 arr 中,接着 Alice 再将 2
添加到 arr 中。于是 arr = [3,2] 。

第二轮开始时,nums = [5,4] 。Alice 先移除 4 ,然后 Bob 移除 5 。接着他们都将元素添加到 arr 中,arr
变为 [3,2,5,4] 。

示例 2:

输入:nums = [2,5]

输出:[5,2]

解释:第一轮,Alice 先移除 2 ,然后 Bob 移除 5 。然后 Bob 先将 5 添加到 arr 中,接着 Alice 再将 2
添加到 arr 中。于是 arr = [5,2] 。

提示:

1 <= nums.length <= 100

1 <= nums[i] <= 100

nums.length % 2 == 0

题解:
方法:模拟 + 优先队列
        

class Solution {
    public int[] numberGame(int[] nums) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int x : nums) {
            pq.offer(x);
        }
        int[] ans = new int[nums.length];
        int i = 0;
        while (!pq.isEmpty()) {
            int a = pq.poll();
            ans[i++] = pq.poll();
            ans[i++] = a;
        }
        return ans;
    }
}

13.判断一个数组是否可以变为有序

题目链接:3011. 判断一个数组是否可以变为有序

给你一个下标从 0 开始且全是 正 整数的数组 nums 。

一次 操作 中,如果两个 相邻 元素在二进制下数位为 1 的数目 相同 ,那么你可以将这两个元素交换。你可以执行这个操作 任意次 (也可以 0 次)。

如果你可以使数组变有序,请你返回 true ,否则返回 false 。

示例 1:

输入:nums = [8,4,2,30,15]

输出:true

解释:我们先观察每个元素的二进制表示。 2 ,4 和 8 分别都只有一个数位为 1 ,分别为 “10” ,“100” 和 “1000”
。15 和 30 分别有 4 个数位为 1 :“1111” 和 “11110” 。

我们可以通过 4 个操作使数组有序:

  • 交换 nums[0] 和 nums[1] 。8 和 4 分别只有 1 个数位为 1 。数组变为 [4,8,2,30,15] 。
  • 交换 nums[1] 和 nums[2] 。8 和 2 分别只有 1 个数位为 1 。数组变为 [4,2,8,30,15] 。
  • 交换 nums[0] 和 nums[1] 。4 和 2 分别只有 1 个数位为 1 。数组变为 [2,4,8,30,15] 。
  • 交换 nums[3] 和 nums[4] 。30 和 15 分别有 4 个数位为 1 ,数组变为 [2,4,8,15,30] 。

数组变成有序的,所以我们返回 true 。

注意我们还可以通过其他的操作序列使数组变得有序。

示例 2:

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

输出:true

解释:数组已经是有序的,所以我们返回 true 。

示例 3:

输入:nums = [3,16,8,4,2]

输出:false

解释:无法通过操作使数组变为有序。

提示:

1 <= nums.length <= 100

1 <= nums[i] <= 28

题解:
方法:排序
        

class Solution {
    public boolean canSortArray(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n;) {
            int start = i;
            int ones = Integer.bitCount(nums[i++]);
            while (i < n && Integer.bitCount(nums[i]) == ones) {
                i++;
            }
            Arrays.sort(nums, start, i);
        }
        for (int i = 1; i < n; i++) {
            if (nums[i] < nums[i - 1]) {
                return false;
            }
        }
        return true;
    }
}

14.保持城市天际线

题目链接:807. 保持城市天际线

给你一座由 n x n 个街区组成的城市,每个街区都包含一座立方体建筑。给你一个下标从 0 开始的 n x n 整数矩阵 grid ,其中 grid[r][c] 表示坐落于 r 行 c 列的建筑物的 高度 。

城市的 天际线 是从远处观察城市时,所有建筑物形成的外部轮廓。从东、南、西、北四个主要方向观测到的 天际线 可能不同。

我们被允许为 任意数量的建筑物 的高度增加 任意增量(不同建筑物的增量可能不同) 。 高度为 0 的建筑物的高度也可以增加。然而,增加的建筑物高度 不能影响 从任何主要方向观察城市得到的 天际线 。

在 不改变 从任何主要方向观测到的城市 天际线 的前提下,返回建筑物可以增加的 最大高度增量总和 。

示例 1:

在这里插入图片描述

输入:grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]

输出:35

解释:建筑物的高度如上图中心所示。

用红色绘制从不同方向观看得到的天际线。

在不影响天际线的情况下,增加建筑物的高度:

gridNew = [ [8, 4, 8, 7],

        [7, 4, 7, 7],

        [9, 4, 8, 7],

        [3, 3, 3, 3] ]

示例 2:

输入:grid = [[0,0,0],[0,0,0],[0,0,0]]

输出:0

解释:增加任何建筑物的高度都会导致天际线的变化。

提示:

n == grid.length

n == grid[r].length

2 <= n <= 50

0 <= grid[r][c] <= 100

题解:
方法:贪心
        

class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int[] rowMax = new int[n];
        int[] colMax = new int[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                rowMax[i] = Math.max(rowMax[i], grid[i][j]);
                colMax[j] = Math.max(colMax[j], grid[i][j]);
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans += Math.min(rowMax[i], colMax[j]) - grid[i][j];
            }
        }
        return ans;
    }
}


下接:【题解】—— LeetCode一周小结29


本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/798724.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【CICID】GitHub-Actions-SpringBoot项目部署

[TOC] 【CICID】GitHub-Actions-SpringBoot项目部署 0 流程图 1 创建SprinBoot项目 ​ IDEA创建本地项目&#xff0c;然后推送到 Github 1.1 项目结构 1.2 Dockerfile文件 根据自身项目&#xff0c;修改 CMD ["java","-jar","/app/target/Spri…

docker部署canal 并监听mysql

1.部署mysql 需要开启mysql的binlong&#xff0c;和创建好用户等 可以参考这个 Docker部署Mysql数据库详解-CSDN博客 2.部署canal 参考这一篇&#xff1a; docker安装Canal&#xff0c;开启MySQL binlog &#xff0c;连接Java&#xff0c;监控MySQL变化_docker canal-CSD…

简单搭建卷积神经网络实现手写数字10分类

搭建卷积神经网络实现手写数字10分类 1.思路流程 1.导入minest数据集 2.对数据进行预处理 3.构建卷积神经网络模型 4.训练模型&#xff0c;评估模型 5.用模型进行训练预测 一.导入minest数据集 MNIST--->raw--->test-->(0,1,2...) 10个文件夹 MNIST--->raw-…

【Linux】基于环形队列RingQueue的生产消费者模型

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 目录 前言 环形队列的概念及定义 POSIX信号量 RingQueue的实现方式 RingQueue.hpp的构建 Thread.hpp Main.cc主函数的编写 Task.hpp function包装器的使用 总结 前言…

《Python数据科学之一:初见数据科学与环境》

《Python数据科学之一&#xff1a;初见数据科学与环境》 欢迎来到“Python数据科学”系列的第一篇文章。在这个系列中&#xff0c;我们将通过Python的镜头&#xff0c;深入探索数据科学的丰富世界。首先&#xff0c;让我们设置和理解数据科学的基本概念以及在开始任何数据科学项…

《C专家编程》 C++

抽象 就是观察一群数据&#xff0c;忽略不重要的区别&#xff0c;只记录关注的事务特征的关键数据项。比如有一群学生&#xff0c;关键数据项就是学号&#xff0c;身份证号&#xff0c;姓名等。 class student {int stu_num;int id_num;char name[10]; } 访问控制 this关键字…

安全防御:防火墙概述

目录 一、信息安全 1.1 恶意程序一般会具备一下多个或全部特点 1.2 信息安全五要素&#xff1a; 二、了解防火墙 2.1 防火墙的核心任务 2.2 防火墙的分类 2.3 防火墙的发展历程 2.3.1 包过滤防火墙 2.3.2 应用代理防火墙 2.3.3 状态检测防火墙 补充防御设备 三、防…

Torch-Pruning 库入门级使用介绍

项目地址&#xff1a;https://github.com/VainF/Torch-Pruning Torch-Pruning 是一个专用于torch的模型剪枝库&#xff0c;其基于DepGraph 技术分析出模型layer中的依赖关系。DepGraph 与现有的修剪方法&#xff08;如 Magnitude Pruning 或 Taylor Pruning&#xff09;相结合…

uniapp实现水印相机

uniapp实现水印相机-livePusher 水印相机 背景 前两天拿到了一个需求&#xff0c;要求在内部的oaApp中增加一个卫生检查模块&#xff0c;这个模块中的核心诉求就是要求拍照的照片添加水印。对于这个需求&#xff0c;我首先想到的是直接去插件市场&#xff0c;下一个水印相机…

《Python数据科学之五:模型评估与调优深入解析》

《Python数据科学之五&#xff1a;模型评估与调优深入解析》 在数据科学项目中&#xff0c;精确的模型评估和细致的调优过程是确保模型质量、提高预测准确性的关键步骤。本文将详细探讨如何利用 Python 及其强大的库进行模型评估和调优&#xff0c;确保您的模型能够达到最佳性能…

docker中1个nginx容器搭配多个django项目中设置uwsgi.ini的django项目路径

docker中&#xff0c;1个nginx容器搭配多个django项目容器&#xff0c;设置各个uwsgi.ini的django项目路径 被这个卡了一下&#xff0c;真是&#xff0c;哎 各个uwsgi配置应该怎样设置项目路径 django项目1中创建的django项目名为 web 那么uwsgi.ini中要设置为 chdir …

【Vue3 ts】echars图表展示统计的月份数据

图片展示 此处内容为展示24年各个月份产品的创建数量。在后端统计24年各个月份产品数量后&#xff0c;以数组的格式发送给前端&#xff0c;前端负责展示。 后端 entity层&#xff1a; Data Schema(description "月份统计")public class MonthCount {private Stri…

得物六宫格验证码分析

声明(lianxi a15018601872) 本文章中所有内容仅供学习交流使用&#xff0c;不用于其他任何目的&#xff0c;抓包内容、敏感网址、数据接口等均已做脱敏处理&#xff0c;严禁用于商业用途和非法用途&#xff0c;否则由此产生的一切后果均与作者无关&#xff01; 前言(lianxi a…

算法的时间复杂度和空间复杂度-例题

一、消失的数字 . - 力扣&#xff08;LeetCode&#xff09; 本题要求的时间复杂度是O(n) &#xff0c;所以我们不能用循环嵌套&#xff1b; 解法一&#xff1a; int missingNumber(int* nums, int numsSize){int sum10;for(int i0;i<numsSize;i){sum1i;}int sum20;for(i…

C到C嘎嘎的衔接篇

本篇文章&#xff0c;是帮助大家从C向C嘎嘎的过渡&#xff0c;那么我们直接开始吧 不知道大家是否有这样一个问题&#xff0c;学完C的时候感觉还能听懂&#xff0c;但是听C嘎嘎感觉就有点难度或者说很难听懂&#xff0c;那么本篇文章就是帮助大家从C过渡到C嘎嘎。 C嘎嘎与C的区…

MPC轨迹跟踪控制器推导及Simulink验证

文章目录 MPC轨迹跟踪控制器推导及Simulink验证MPC的特点MPC轨迹跟踪控制器推导一 系统离散化二 预测区间状态和变量推导三 代价函数推导四 优化求解 <center> 基于MPC的倒立摆控制系统相关资料Reference&#xff1a; MPC轨迹跟踪控制器推导及Simulink验证 MPC的特点 多…

SAP 消息输出 - Adobe Form

目录 1 安装链接 2 前台配置 - Fiori app 2.1 维护表单模板 (maintain form templates) 2.2 管理微标 (manage logos) 2.3 管理文本 (manage texts) 3 后台配置 3.1 定义表单输出规则 3.2 分配表单模板 SAP 消息输出&#xff0c;不仅是企业内部用来记录关键业务操作也是…

Win11任务栏当中对 STM32CubeMX 的堆叠问题

当打开多个 CubeMX 程序的时候&#xff0c;Win11 自动将其进行了堆叠&#xff0c;这时候就无法进行预览与打开。 问题分析&#xff1a;大部分ST的工具都是基于 JDK 来进行开发的&#xff0c;Win11 将其识别成了同一个 Binary 但是实际上他们并不是同一个&#xff0c;通过配置…

基于conda包的环境创建、激活、管理与删除

Anaconda是一个免费、易于安装的包管理器、环境管理器和 Python 发行版&#xff0c;支持平台包括Windows、macOS 和 Linux。下载安装地址&#xff1a;Download Anaconda Distribution | Anaconda 很多不同的项目可能需要使用不同的环境。例如某个项目需要使用pytorch1.6&#x…