力扣刷题记录10.25

2024/10/25

（1）哈希表

1、最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

我的蹩脚解法：（时间复杂度O(nlogn)）（但是也过了。。）

int longestConsecutive(vector<int>& nums) {
    set<int> ans;
    int res=0,cnt=0;
    for(int i:nums){
        ans.insert(i);  //插入操作的时间复杂度为O(logn)
    }
    for(int i:ans){
        if(ans.count(i-1))
            cnt++;
        else
            cnt=1;
        res=max(cnt,res);
    }
    return res;
}

时间复杂度O(n)：

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> ans;  //基于哈希表实现，插入动作的时间复杂度是O(1)
    int res=0;
    for(int i:nums){
        ans.insert(i); //去重
    }
    for(int i:ans){//只要i-1存在就说明不是连续序列的开始，直接跳过
        if(!ans.count(i-1)){  //找到连续序列的开始
            int cnt=1,j=i;
            while(ans.count(j+1)){
                cnt++;
                j++;
            }
            res=max(res,cnt);
        }
    }
    return res;
}

（2）单调队列

1、滑动窗口最大值

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

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

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
       vector<int> ans;
       deque<int> res;  //单调队列，队首元素最大。（维护滑动窗口内的最大值，存储的是下标）
       for(int i=0;i<nums.size();i++){
          while(!res.empty()&&nums[res.back()]<nums[i]){
             res.pop_back();  //找到它应该在的位置。把小于它的元素都弹出
          }
          res.push_back(i);  //放置
          if(i-res.front>=k){
             res.pop_front();  //如果队首已经不在滑动窗口内，弹出
          }
          if(i>=k-1){
             ans.push_back(nums[res.front()]);  //放置该窗口内的最大值
          }
       }
       return ans;
    }
};

（3）多重组合计数

假设有编号 1到n 的扑克牌，每种编号的扑克牌各有四张。那么问题等价于从 4n 张牌中选取 m 张不同组合的数量，且每种编号最多只能选四张。

这道问题使用多重组合计数来解决。在多重组合计数中，可以通过动态规划或组合数学来计算方案

1、动态规划

定义一个二位动态规划数组dp[i][j]，表示在前i种牌（编号为1到i）种选出j张牌的组合数。

🎃状态转移方程：

对于每种编号的牌，可以选0-4张，因此状态转移方程为

🔺dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+dp[i-1][j-4]

dp[i-1][j-k]表示在不超过j张牌的情况下，从i-1编号种选择j-k张。

🎃初始化：

• dp[0][0]=1 表示不选任何牌的组合数为1；

🎃边界条件：

• 当j<k时，dp[i-1][j-k]为0（初始化为0）

class Solution {
public:
    const MOD=1e9+7;
    vector<int> PokerNumber(int n,int m) {
       vector<vector<int> > dp(n+1,vector<int>(m+1,0));
       dp[0][0]=1;
       for(int i=1;i<=n;i++){
          for(int j=0;j<=m;j++){
             for(int k=0;k<=4;k++){
                if(j>=k){
                   dp[i][j]+=dp[i-1][j-k];
                   dp%=MOD
                } 
             }
          }
       }
       return dp[n][m];
    }
};

2、组合数学

前面我是能看懂，怎么通过这个数学思路得到代码的，我是很迷惑的

int countCombinations(int n, int m) {
    vector<int> dp(m + 1, 0);
    dp[0] = 1;  // 初始条件，选择0张牌的组合数为1种

    for (int i = 1; i <= n; ++i) {  // 对每种牌进行循环
        for (int j = m; j >= 0; --j) {  // 倒序遍历总选择数量
            for (int k = 1; k <= 4; ++k) {  // 对每种牌最多选四张
                if (j >= k) {
                    dp[j] = (dp[j] + dp[j - k]) % MOD;
                }
            }
        }
    }

    return dp[m];  // 返回选择m张牌的组合数
}

（4）博弈论

牛牛和朵朵轮流从任意一堆石头中移走一颗石头，移动之前所有石头为零或者移完之后如果任意两堆石头的个数相等，当前玩家就会输掉比赛。

因此，可以考虑将石头数量的奇偶性和先手后手结合起来推理胜负。

我们可以利用 异或操作（Nim博弈的基本策略）来简化判断：

• 将每堆石头的数量进行异或，若结果为0，表示朵朵可以采取制胜策略，牛牛必输；
• 若异或结果非0，表示牛牛有必胜策略。

int n;
cin >> n;
int xor_sum = 0;  // 异或和
for (int i = 0; i < n; ++i) {
    cin >> tmp
    xor_sum ^= tmp;
}

// 根据异或和判断胜负
if (xor_sum == 0) {
    cout << "woman" << endl;  // 牛牛输
} else {
    cout << "man" << endl;    // 牛牛赢
}

（5）快速幂

long long fast_pow(long long a, long long b, long long p) {
    long long result = 1;
    a %= p;  // 防止初始的a大于p
    
    while (b > 0) {
        if (b & 1)  // 如果 b 是奇数
            result = (result * a) % p;  // 累乘当前的 a
        a = (a * a) % p;  // 平方 a
        b >>= 1;  // 右移 b，相当于 b = b / 2
    }
    return result;
}