LeetCode hot 100 day2

最长连续序列

题目链接

用排序

class Solution {
public:int longestConsecutive(vector<int>& nums) {sort(nums.begin(),nums.end());if(nums.size()<=1) return nums.size();int ans=0;int res=1;for(int i=0;i<nums.size()-1;i++){if(nums[i+1]==nums[i]+1){res++;}else if(nums[i+1]==nums[i]) continue;else{ans=max(ans,res);res=1;}}ans=max(ans,res);return ans;}
};

O(n)

class Solution {
public:int longestConsecutive(vector<int>& nums) {// 如果数组为空或只有一个元素，最长连续序列长度就是数组长度if(nums.size() <= 1) return nums.size();int ans = 0;   // 记录最长连续序列的长度int res = 1;   // 当前连续序列的长度// 使用 unordered_set 存储所有元素，去重并支持 O(1) 时间查找unordered_set<int> mp(nums.begin(), nums.end());// 遍历集合中的每个元素for(auto& it : mp) {// 如果它的前一个数不存在，说明这个数是某个连续序列的起点if(mp.find(it - 1) == mp.end()) {int x = it + 1;  // 从当前数的下一个开始查找// 向后查找连续的数while(mp.find(x) != mp.end()) {res++;  // 找到一个连续的数就增加长度x++;}// 更新最长连续序列的长度ans = max(res, ans);res = 1;  // 重置当前长度计数器}}return ans;}
};

移动零

题目链接

借助栈

class Solution {
public:void moveZeroes(vector<int>& nums) {int cnt = 0;  // 计数器，用来记录非零元素的个数stack<int> stk;  // 使用栈来存储所有非零元素// 第一遍遍历，将所有非零的数字压入栈中for(int num : nums) {if(num != 0) {stk.push(num);  // 非零数字压入栈}}// 如果栈为空，则说明没有非零元素，直接返回if(stk.empty()) return;// 第二遍遍历，从后往前填充数组for(int i = nums.size() - 1; i >= 0; i--) {// 如果栈还有元素，则从栈中取出一个数字并赋值给当前数组位置if(i <= stk.size() - 1) {nums[i] = stk.top();  // 从栈中获取非零数字stk.pop();  // 弹出栈顶元素} else {// 如果栈已经没有非零数字了，当前数组位置填充0nums[i] = 0;}}}
};

双指针

class Solution {
public:void moveZeroes(vector<int>& nums) {int j = 1;  // 用于寻找当前零元素后面非零元素的位置// 遍历数组for (int i = 0; i < nums.size(); i++) {// 如果当前元素是 0if (nums[i] == 0) {// 从当前位置 i 后开始寻找第一个非零元素int j = i + 1;// 查找下一个非零元素的位置while (j < nums.size() && nums[j] == 0) {j++;  // 如果是零，继续向后查找}// 如果 j 在数组范围内，找到一个非零元素if (j < nums.size()) {nums[i] = nums[j];  // 将非零元素移到当前零的位置nums[j] = 0;  // 把当前位置变为零}}}}
};