春节临近,离过年还不到半个月了,很多大厂也都公布了今年春节的放假安排,大多数都是中规中矩,按照国家法定节假日放,今年的春节假国家规定是9天。
也有一些大厂会有10到12天的假期,其中最多的是58同城,假期多达17天,不过有不少网友评论说58的假是用年假换的。但不管怎么说,今年还算是比较满意,我工作十多年,之前一直都是7天,今年是第一次放9天,一般情况下年前都会请假的,春节在家待个十几天也够了,希望每年的春节也不要低于9天。
![]()
![]()
![]()
--------------下面是今天的算法题--------------
来看下今天的算法题,这题是LeetCode的第3637题:三段式数组 I,难度是简单。
给你一个长度为 n 的整数数组 nums。如果存在索引 0 < p < q < n − 1,使得数组满足以下条件,则称其为三段式数组(trionic):
1,nums[0...p] 严格 递增,
2,nums[p...q] 严格 递减,
3,nums[q...n − 1] 严格 递增。
如果 nums 是三段式数组,返回 true;否则,返回 false。
示例1:
输入: nums = [1,3,5,4,2,6] 输出: true 解释: 选择 p = 2, q = 4: nums[0...2] = [1, 3, 5] 严格递增 (1 < 3 < 5)。 nums[2...4] = [5, 4, 2] 严格递减 (5 > 4 > 2)。 nums[4...5] = [2, 6] 严格递增 (2 < 6)。
示例2:
输入: nums = [2,1,3] 输出: false 解释: 无法选出能使数组满足三段式要求的 p 和 q 。
3 <= n <= 100
-1000 <= nums[i] <= 1000
问题分析
这题说的是能否把数组分成3部分,第一部分是递增的,第二部分是递减的,第三部分是递增的。分的时候要注意,第一部分的最后一个元素是第二部分的第一个元素,第二部分的最后一个元素也是第三部分的第一个元素。
如果要判断数组是递增还是递减,至少需要2个元素,所以分成三部分(有重叠)最少也需要4个元素,如果低于4个元素,直接返回false即可。否则,我们直接判断,先找递增的,在找递减的,最后的都是递增的,如果不满足就返回false。
JAVA:
public boolean isTrionic(int[] nums) {
int n = nums.length;
if (n < 4) // 至少需要4个元素
returnfalse;
int i = 0;
// 递增
while (i + 1 < n && nums[i] < nums[i + 1])
i++;
if (i == 0 || i >= n - 2)
returnfalse;
// 递减
int start = i;
while (i + 1 < n && nums[i] > nums[i + 1])
i++;
if (i == start || i == n - 1)
returnfalse;
// 递增
while (i + 1 < n && nums[i] < nums[i + 1])
i++;
return i == n - 1;
}
C++:
public:
bool isTrionic(vector &nums) {
int n = nums.size();
if (n < 4) // 至少需要4个元素
returnfalse;
int i = 0;
// 递增
while (i + 1 < n && nums[i] < nums[i + 1])
i++;
if (i == 0 || i >= n - 2)
returnfalse;
// 递减
int start = i;
while (i + 1 < n && nums[i] > nums[i + 1])
i++;
if (i == start || i == n - 1)
returnfalse;
// 递增
while (i + 1 < n && nums[i] < nums[i + 1])
i++;
return i == n - 1;
}
笔者简介
博哥,真名:王一博,毕业十多年, 作者,专注于 数据结构和算法 的讲解,在全球30多个算法网站中累计做题2000多道,在公众号中写算法题解900多题,对算法题有自己独特的解题思路和解题技巧。
特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.