力扣刷题记录10.9

开始刷100题。

2024/10/9

（1）双指针

1、移动零-283. 移动零 - 力扣（LeetCode）

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。

public void moveZeroes(int[] nums)  {
    int length;
    if (nums == null || (length = nums.length) == 0) {
        return;
    }
    int j = 0;
    for (int i = 0; i < length; i++) {
        if (nums[i] != 0) {
            if (i > j) {// #1
                nums[j] = nums[i];
                nums[i] = 0;
            }
            j++;
        }
    }
}

• j 是一个指针，用来跟踪非零元素应该放置的位置，初始化为 0。

i 是遍历数组的索引，逐个检查数组中的元素。

• 当 nums[i] 不为 0 时，我们需要将其放到正确的位置，即 nums[j]。

通过 if (i > j) 这一步，检查是否当前元素和目标位置是相同的。如果 i == j，意味着当前元素已经在正确的位置，不需要交换；如果 i > j，则表示当前非零元素需要移动到 j 位置，然后将 nums[i] 置为 0。

时间复杂度O(n)，空间复杂度O(1)。

2、盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0, j = height.size() - 1, res = 0;
        while(i < j) {
            res = height[i] < height[j] ? 
                max(res, (j - i) * height[i++]): 
                max(res, (j - i) * height[j--]); 
        }
        return res;
    }
};

在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽 底边宽度 −1 变短：

若向内移动短板，水槽的短板 min(h[i],h[j]) 可能变大，因此下个水槽的面积 可能增大 。

若向内移动长板，水槽的短板 min(h[i],h[j]) 不变或变小，因此下个水槽的面积 一定变小 。

3、三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        if (nums[0] > 0 || nums[nums.size() - 1] < 0) {
       		return {};
    	  }
        int l = 0, r = nums.size() - 1;
        vector<vector<int> > ans;
        for (int i = 0; i < nums.size() - 2; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 跳过重复的元素
            int l = i + 1, r = nums.size() - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    ans.push_back({nums[i], nums[l], nums[r]});
                    while (l < r && nums[l] == nums[l + 1]) ++l; // 跳过重复的元素
                    while (l < r && nums[r] == nums[r - 1]) --r; // 跳过重复的元素
                    ++l; --r;
                } else if (sum < 0) {
                    ++l;
                } else {
                    --r;
                }
            }
        }
        return ans;
    }
};

首先对数组进行排序，这样就可以通过双指针的方式从两端开始收缩，寻找满足条件的三元组；有利于后续避免重复的元素。

外层从第一个元素开始循环，直到倒数第三个；若与前一个数相等则跳过。

初始化两个指针l,r分别从左右两端开始遍历。在两个指针未相遇前，寻找满足条件的三个数，并继续跳过重复的元素。不满足条件时则做相应的调整。

时间复杂度：O(N^2)

（2）滑动窗口

1、无重复字符的最长子串c++（做完就忘，烦死我了😩😩😩）

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(!s.size()) return 0;   //先判断一手
        int maxSize=0,left=0;
        unordered_set <int> ans;
        for(int i=0;i<s.size();i++){
            while(ans.find(s[i])!=ans.end()){
                ans.erase(s[left]);
                left++;
            }
            maxSize=max(maxSize,i-left+1);
            ans.insert(s[i]);
        }
        return maxSize;
    }
};

使用unordered_set是为了提高查找效率

维护窗口最左边的坐标：left。

如果最右边的值不在ans中，说明窗口可以增加。否则需要将窗口左边坐标向右，直到最右边的值不在ans中。每次循环都维护一个窗口的最大长度。

2、找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int sLen=s.length(),pLen=p.length();
        if(sLen<pLen) return vector<int> ();
        vector <int> ans;
        vector <int> sCount(26),pCount(26);
        for(int i=0;i<pLen;i++){
            sCount[s[i]-'a']++;
            pCount[p[i]-'a']++;
        }
        if(sCount==pCount) ans.push_back(0);
        for(int i=0;i<sLen-pLen;i++){
            sCount[s[i]-'a']--;
            sCount[s[i+pLen]-'a']++;
            if(sCount == pCount)
                ans.push_back(i+1);
        }
        return ans;
    }
};

（3）前缀和

1、和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        mp[0] = 1;  //可能有前几个数字加在一起等于k的情况。
        int count = 0, pre = 0;
        for (auto& x:nums) {
            pre += x;
            if (mp.find(pre - k) != mp.end()) {
                count += mp[pre - k];
            }
            mp[pre]++;
        }
        return count;
    }
};

遍历计算前缀和，并用哈希表存储前缀和的值出现的次数。

计算时，查找哈希表中是否存在pre-k的值，如果有，就说明某个位置到这里的字串的和加起来等于k，于是可以加上相应的个数。

（4）优先队列

1、滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();  // 数组长度
        priority_queue<pair<int, int>> q;  // 优先队列，存储 (元素值, 索引) 对

        // 初始化前 k 个元素到优先队列
        for (int i = 0; i < k; ++i) {
            q.emplace(nums[i], i);  // 将前 k 个元素加入到队列中
        }

        vector<int> ans = {q.top().first};  // 当前最大值即是队列的堆顶元素（值最大）
        
        // 开始滑动窗口
        for (int i = k; i < n; ++i) {
            q.emplace(nums[i], i);  // 将新元素加入队列
            // 检查队列堆顶元素的索引是否已经超出滑动窗口的范围
            while (q.top().second <= i - k) {
                q.pop();  // 如果堆顶元素已不在窗口内，则将其移除
            }
            // 队列中的堆顶元素为当前窗口的最大值
            ans.push_back(q.top().first);
        }

        return ans;  // 返回滑动窗口中的所有最大值
    }
};

（5）二分查找

1、搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。nums 为 无重复元素 的 升序 排列数组

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l=0,r=nums.size()-1;
        while(l<=r){
            int mid=(l+r)/2;
            if(target>nums[mid])
                l=mid+1;
            else
                r=mid-1;   
        }
        return l;
    }
};

2、搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false; // 如果矩阵为空，直接返回 false
        
        int m = matrix.size();    // 行数
        int n = matrix[0].size(); // 列数
        int left = 0, right = m * n - 1; // 二维数组扁平化后的索引范围
        
        // 二分查找
        while (left <= right) {
            int mid = left + (right - left) / 2; // 防止溢出
            int row = mid / n;  // 计算出 mid 对应的行号
            int col = mid % n;  // 计算出 mid 对应的列号
            int midVal = matrix[row][col]; // 获取当前元素
            
            if (midVal == target) {
                return true; // 找到目标值
            } else if (midVal < target) {
                left = mid + 1; // 在右半部分查找
            } else {
                right = mid - 1; // 在左半部分查找
            }
        }
        
        return false; // 未找到目标值
    }
};

（6）栈

1、有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

不看答案做不出系列。。。。

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) {
            return false;
        }

        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        stack<char> stk;
        for (char ch: s) {
            if (pairs.count(ch)) {  //右括号
                if (stk.empty() || stk.top() != pairs[ch]) {
                    return false;   //不匹配
                }
                stk.pop();  //匹配，弹出栈顶元素
            }
            else { 
                stk.push(ch);   //压入左括号
            }
        }
        return stk.empty();
    }
};

2、最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

class MinStack {
    stack <int> x;
    stack <int> min;
public:
    MinStack() {
        min.push(INT_MAX)
    }
    
    void push(int val) {
        x.push(val);
        min.push(min(min.top(),val));
    }
    
    void pop() {
        x.pop();
        min.pop();
    }
    
    int top() {
        return x.top();
    }
    
    int getMin() {
        return min.top();
    }
};