Algorithm-leetcode

算法

 2025/04/07 

lc的输入传引用，并且无需自己设计输入输出格式，只需要实现核心函数即可

考虑在每个方向上都做1-2道题。

数组操作

1-3：数组操作，双指针为主，C++上学期考完csp已经手生了，不会用vec了。需要利用有序信息。保留连续两个重复元素，有序数组，不额外开空间：

双指针一个用于遍历搜索，另一个用于标记修改位置，通用思路

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        // 试一下上一题的快慢指针
        // 数组有序，如果有需要删除的元素，那么在首次遍历到这个元素之后+2肯定不会漏
        // 不让开新数组？
        int n=nums.size();
        if(n<=2) return n;
        int fast=2,slow=2;// 0,1直接保留不用看
        while(fast < n){
            if(nums[fast]!=nums[slow-2])//无
                nums[slow++]=nums[fast];
            fast++;
        }
        return slow;
    }
};

4 多数元素数组统计

统计指标相关的问题最暴力的就是hashmap一对一，比如找多数元素。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counts;
        int majority = 0, cnt = 0;
        for (int num: nums) {
            ++counts[num];
            if (counts[num] > cnt) {
                majority = num;
                cnt = counts[num];
            }
        }
        return majority;
    }
};

多数元素的问题：hashmap，摩尔投票（新鲜），排序取中间，随机摩尔投票是一个专门解决绝对众数的算法。具有On的时间复杂度和O1的空间复杂度，效率比较高。

初始化：票数统计 votes = 0 ，众数 x。循环：遍历数组 nums 中的每个数字 num 。当票数 votes 等于 0 ，则假设当前数字 num 是众数。当 num = x 时，票数 votes 自增 1 ；当 num != x 时，票数 votes 自减 1 。返回值：返回 x 即可。正确性略

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int x = 0, votes = 0;
        for (int num : nums){
            if (votes == 0) x = num;
            votes += (num == x ? 1 : -1);
        }
        return x;
    }
};

5 轮转数组

额外空间略，关注原地算法。

// 方法一：交换。比较符合直觉的O1思路。不过需要遍历的轮数gcd(k,n)是推导的结果
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        int count = gcd(k, n);
        for (int start = 0; start < count; ++start) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % n;
                swap(nums[next], prev);
                current = next;
            } while (start != current);
        }
    }
};
// 方法2: 巧妙的思路，最后的k%n个元素会变到开头
// 联想到翻转操作的数组原语
// 我们只需要先翻转整个数组，再分别翻转前k%n个和其余的，翻转三次即可
class Solution {
public:
    void reverse(vector<int>& nums, int start, int end) {
        while (start < end) {
            swap(nums[start], nums[end]);
            start += 1;
            end -= 1;
        }
    }

    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }
};

简单的贪心

买卖股票：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 用一个结构数组打包然后直接排序
        // 贪心
        int cost = INT_MAX, profit = 0;
        for (int price : prices) {
            cost = min(cost, price);
            profit = max(profit, price - cost);
        }
        return profit;
    }
};

135 分糖果

开始没憋出来，题解没看懂但是看了一点一下想出来了。中途数组排序状态变化会影响结果的，或者说对”部分区间排序“或者所谓的”极大值“/“极小值”有要求的，可以考虑这个思路。我们先从左到右遍历一遍，只关注增幅度，不是增加的不管。然后反向重新遍历一遍，也是一样的思路，最终结果在两次中取最大就行了。

class Solution {
public:
    int candy(vector<int>& ratings) {
    // 两次遍历取最大
        int n=ratings.size();
        int sum=0;
        vector<int> v(n);
        v[0]=1;
        for(int i=1;i<n;i++){
            if(ratings[i]>ratings[i-1]){
                v[i]=v[i-1]+1;
            }
            else v[i]=1;
        }
        for(int i=n-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){
                v[i]=max(v[i+1]+1,v[i]);
            }
            else v[i]=max(1,v[i]);
        }

        for(int e : v){
            sum += e;
        }
        return sum;
    }
};

滑动窗口

最小字串问题

“in”，存在于而不关心具体位置 => unordered_map
如果是英文字符或者数字的话完全可以用数组下标做一一映射，快速随机存取而无需hashmap

128长数组相当于是ascii字符的哈希表
不要太复杂的算法，用好基本的数据结构就行，觉得要更多信息就开空间存不要怕

class Solution {
public:
    unordered_map <char, int> ori, cnt;

    bool check() {
        for (const auto &p: ori) {
            if (cnt[p.first] < p.second) {
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t) {
        for (const auto &c: t) {
            ++ori[c];
        }

        int l = 0, r = -1;
        int len = INT_MAX, ansL = -1, ansR = -1;

        while (r < int(s.size())) {
            if (ori.find(s[++r]) != ori.end()) {
                ++cnt[s[r]];
            }
            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                }
                if (ori.find(s[l]) != ori.end()) {
                    --cnt[s[l]];
                }
                ++l;
            }
        }

        return ansL == -1 ? string() : s.substr(ansL, len);
    }
};

Next Post

DefCon33 Qual
Previous Post

漏洞挖掘入门（持续更新）

CATALOG

1. 数组操作
2. 滑动窗口
3.