字节3面真题,LeetCode上hard难度,极具启发性题解

2024-02-08 21:04

本文主要是介绍字节3面真题,LeetCode上hard难度,极具启发性题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

请添加图片描述

文章目录

  • 🚀前言
  • 🚀LeetCode:41. 缺失的第一个正整数
  • 🚀思路
  • 🚀整个代码思路串一下
  • 🚀Code

🚀前言

铁子们好啊!阿辉来讲道题,这道题据说是23年字节3面真题,LeetCode上面hard难度,而且是很多难题的基础模板,今天阿辉就带你拿下它!!!

🚀LeetCode:41. 缺失的第一个正整数

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

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

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

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

🚀思路

首先这道题要求时间复杂度在O(n),空间复杂度在O(1)
很明显可以想到二分或者有限次的遍历数组

  1. 对于本题,这道题让我们找到数组中缺失的第一个正整数,我们很容易想到排序然后便利数组,看看数组里面最先缺了谁,这道题就解决了,但是很遗憾时间复杂度限制在了O(n)空间复杂度O(1)不能用排序
  2. 不过上述的思考并非毫无意义,对于本题并非不能排序,因为我们要找的是缺失的第一个正整数,只要我们能够做到将数组中从1~x的数字排好即可,x+1即为所求,而排好这部分数我们仅需遍历一遍数组即可
  3. 铁子们是不是要问为何如此,因为1~x这些数字本身就决定了他们的位置,1本身就是他自己的索引,比如:1填在数组中0位置,2填在1位置,数字n填在n-1位置
  4. 对于一个长度为n的数组num,不一定整个数组都是1~n的数字,对于负数就属于垃圾,大于n的数也是垃圾,重复的数也是垃圾,为什么这么说,因为我们的目的是排1~x不间断连续的数字,其他的都没用,1~x排好了,这题也就拿下了
  5. 到这里兄弟们还觉得有难度吗?这不就是快拍的partition划分过程吗?拿下!!!!

🚀整个代码思路串一下

请添加图片描述

首先,我们准备两个数组偏移量left = 0right = n(n代表数组的长度),left的位置表示待排序的位置,right首先是垃圾区的边界,其次right还表示能够排完整个连续不间断正整数数列的长度,所以一开始,rightn

  • left当前位置的数字为left+1时,++left
  • left当前位置的数字处于left+1right之间且它本该在的位置也空出来的时候时,left位置的数与这个数本该在的位置交换,也就是num[left]num[num[left]-1]的数交换
  • 当上面两种情况都不成立时,left当前位置的数就是垃圾数,与r-1位置的数交换,并且--r垃圾区扩充

🚀Code

class Solution {
public:int firstMissingPositive(vector<int>& nums) {int left = 0;//左边界int right = nums.size();//右边界while (left < right) {//当left来到right时跳出循环if (nums[left] == left + 1) {//当left当前位置的数字为left+1时,++left++left;}//垃圾区else if (nums[left] <= left || nums[left] > right || nums[left] == nums[nums[left] - 1]) {swap(nums[left], nums[--right]);}//当`left`当前位置的数字处于`left+1`到`right`之间//且它本该在的位置也空出来的时候时else {swap(nums[left], nums[nums[left] - 1]);}}return left + 1;//要加1,因为1在0位置,n就在n-1位置}
};

复杂度

时间复杂度:

O ( n ) O(n) O(n)

空间复杂度:

O ( 1 ) O(1) O(1)

请添加图片描述

这篇关于字节3面真题,LeetCode上hard难度,极具启发性题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/692199

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

字节面试 | 如何测试RocketMQ、RocketMQ?

字节面试:RocketMQ是怎么测试的呢? 答: 首先保证消息的消费正确、设计逆向用例,在验证消息内容为空等情况时的消费正确性; 推送大批量MQ,通过Admin控制台查看MQ消费的情况,是否出现消费假死、TPS是否正常等等问题。(上述都是临场发挥,但是RocketMQ真正的测试点,还真的需要探讨) 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说,就是一个分

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样

LeetCode:64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵,找出只包含 1 的最大正方形,并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划