头像

jyu_zwy




在线 


最近来访(33)
用户头像
不拿NOI金牌不改名
用户头像
acwing_1867
用户头像
蜉蝣
用户头像
Amor_Fati
用户头像
只吃虾仁大雪菜
用户头像
yxc
用户头像
直言不
用户头像
Kinpow
用户头像
算法先和初中生同步
用户头像
CodePrince
用户头像
诺亚方舟.
用户头像
cklsyw
用户头像
RyanMoriarty
用户头像
MyUniverse
用户头像
internationalization
用户头像
不容客
用户头像
acwing_4143
用户头像
bu_nai_lii
用户头像
挪威森林
用户头像
星逐月丶

活动打卡代码 AcWing 23. 矩阵中的路径

jyu_zwy
8天前
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); i ++ ) {
            for (int j = 0; j < board[i].size(); j ++ ) {
                if (dfs(board, word, 0, i, j)) return true;
            }
        }
        return false;
    }

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    bool dfs(vector<vector<char>>& board, string& word, int u, int x, int y) {
        if (board[x][y] != word[u]) return false;
        if (u == word.size() - 1) return true;

        char t = board[x][y];
        board[x][y] = '.';
        for (int i = 0; i < 4; i ++ ) {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= board.size() || b < 0 || b >= board[0].size() || board[a][b] == '.') continue;
            if (dfs(board, word, u + 1, a, b)) return true;
        }
        board[x][y] = t;
        return false;
    }
};



jyu_zwy
8天前

思路:
1. 从矩阵 matrix 左下角元素(索引设为 (i, j) )开始遍历,并与目标值对比:
- 当 matrix[i][j] > target时,执行 i-- ,即消去第 i 行元素;
- 当 matrix[i][j] < target时,执行 j ++ ,即消去第 j 列元素;
- 当 matrix[i][j] = target 时,返回 true ,代表找到目标值。
2. 若行索引或列索引越界,则代表矩阵中无目标值,返回 false
时间复杂度 O(M+N) :其中,NM 分别为矩阵行数和列数,此算法最多循环 M+N 次。

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int i = matrix.size() - 1, j = 0;
        while (i >= 0 && j <matrix[0].size()) {
            if (matrix[i][j] > target) i --;
            else if (matrix[i][j] < target) j ++;
            else return true;
        }
        return false;
    }
};



jyu_zwy
8天前

思路分析

方法一:哈希表
思路:定义一个哈希表,遍历一次数组,利用哈希表对每个元素进行标记。若当前元素被标记过了,则该元素重复。
时间复杂度:O(n)

方法二:原地交换
主要思想是把每个数放到对应的位置上,即让 nums[i] = i
前往后遍历数组中的所有数,假设当前遍历到的数是 nums[i]=x,那么:
- 如果x != i && nums[x] == x,则说明 x出现了多次,直接返回 x即可;
- 如果nums[x] != x,那我们就把 x 交换到正确的位置上,即 swap(nums[x], nums[i]),交换完之后如果nums[i] != i,则重复进行该操作。由于每次交换都会将一个数放在正确的位置上,所以swap操作最多会进行 n 次,不会发生死循环。
循环结束后,如果没有找到任何重复的数,则返回-1。
时间复杂度:
每次swap操作都会将一个数放在正确的位置上,最后一次swap会将两个数同时放到正确位置上,一共只有 n 个数和 n 个位置,所以swap最多会进行 n−1 次。所以总时间复杂度是 O(n)

代码实现

方法一:

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int, bool> mp;
        for (int num : nums) {
            if (mp[num]) return num;
            mp[num] = true;
        }
        return  -1;
    }
};

方法二:

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int, bool> mp;
        for (int num : nums) {
            if (mp[num]) return num;
            mp[num] = true;
        }
        return  -1;
    }
};


活动打卡代码 AcWing 3302. 表达式求值

jyu_zwy
8天前
#include <bits/stdc++.h>

using namespace std;

stack<int> num;
stack<char> op;

void eval()
{
    auto b = num.top(); num.pop();
    auto a = num.top(); num.pop();
    auto c = op.top(); op.pop();
    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    num.push(x);
}

int main()
{
    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i ++ )
    {
        auto c = str[i];
        if (isdigit(c))
        {
            int x = 0, j = i;
            while (j < str.size() && isdigit(str[j]))
                x = x * 10 + str[j ++] - '0';
            i = j - 1;
            num.push(x);
        }
        else if (c == '(') op.push(c);
        else if (c == ')')
        {
            while (op.top() != '(') eval();
            op.pop();
        }
        else
        {
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
            op.push(c);
        }
    }
    while (op.size()) eval();
    cout << num.top() << endl;
    return 0;
}



jyu_zwy
8天前
typedef long long LL;

class Solution {
public:
    long long minimumReplacement(vector<int>& nums) {
        int n = nums.size();
        LL res = 0;
        for (int i = n - 2, last = nums.back(); i >= 0; i -- ) {
            if (nums[i] < last) last = nums[i];
            else {
                int k = (nums[i] + last - 1) / last;
                res += k - 1;
                last = nums[i] / k;
            }
        }
        return res;
    }
};



jyu_zwy
8天前

思路分析

解法:贪心
从倒数第二个数开始往前考虑。设当前考虑的数为x,它的后一个数为y
1. 若x <= y,根据贪心,我们不应拆分x
2. 若x > y,我们需要拆分 x 使得拆分后的最大值不超过 y,且根据贪心,拆分后的最小值要尽量大。根据数学知识,拆的次数越少,且拆得尽量平均才能让最小值尽量大。因此我们对 x 进行 (k - 1) 次拆分把它变成 kk 个数,其中的最小值就是$\lfloor x/k \rfloor$。

C++ 代码

```
typedef long long LL;

class Solution {
public:
long long minimumReplacement(vector[HTML_REMOVED]& nums) {
int n = nums.size();
LL res = 0;
for (int i = n - 2, last = nums.back(); i >= 0; i – ) {
if (nums[i] < last) last = nums[i];
else {
int k = (nums[i] + last - 1) / last;
res += k - 1;
last = nums[i] / k;
}
}
return res;
}
};```




jyu_zwy
8天前

思路分析

解法:模拟
维护一个unordered_map<int, int> mp,mp[x]表示类型x的任务最近一次的结束时间。按顺序枚举所有任务,设当前任务类型为x,执行当前任务之前已经经过了t的时间,那么:
1. 若t - mp[x] >= space,说明冷却时间已经结束,可以直接执行任务。t +=,并更新mp[x] = t.
2. 若t - mp[x] < space,说明冷却时间还未结束。根据题意,此时最早能执行类型 x 任务的时间是 mp[x] + space + 1。因此,t = mp[x] + space + 1,并更新mp[x] = t

C++ 代码

typedef long long LL;

class Solution {
public:
    long long taskSchedulerII(vector<int>& tasks, int space) {
        int n = tasks.size();
        unordered_map<int, LL> mp;
        for (int x : tasks) mp[x] = -1e8;
        LL ans = 0;
        for (int i = 0; i < n; i ++ ) {
            LL &last = mp[tasks[i]];
            if (ans - last >= space) ans ++, last = ans;
            else ans = last + space + 1, last = ans;
        }
        return ans;
    }
};



jyu_zwy
9天前
typedef long long LL;

class Solution {
public:
    long long taskSchedulerII(vector<int>& tasks, int space) {
        int n = tasks.size();
        unordered_map<int, LL> mp;
        for (int x : tasks) mp[x] = -1e8;
        LL ans = 0;
        for (int i = 0; i < n; i ++ ) {
            LL &last = mp[tasks[i]];
            if (ans - last >= space) ans ++, last = ans;
            else ans = last + space + 1, last = ans;
        }
        return ans;
    }
};



jyu_zwy
9天前

思路

解法:枚举
坏数对的数量=所有数对的数量-满足i < jj - i == nums[j] - nums[i]的数对数目。
把等式两边移项,变为nums[i] - i == nums[j] - j。因此只需要维护一个unordered_map<int, int> mp,mp[i]表示目前为止满足nums[i] - i == xi有几个。我们枚举j,并从答案中减去mp[nums[j] - j]的值即可。
时间复杂度为O(n)

C++ 代码

typedef long long LL;

class Solution {
public:
    long long countBadPairs(vector<int>& nums) {
        int n = nums.size();
        LL ans = n * (n - 1ll) / 2;
        unordered_map<int, int> mp;
        for (int i = 0; i < n; i ++ ) {
            int t = nums[i] - i;
            ans -= mp[t];
            mp[t] ++;
        }
        return ans;
    }
};



jyu_zwy
9天前
typedef long long LL;

class Solution {
public:
    long long countBadPairs(vector<int>& nums) {
        int n = nums.size();
        LL ans = n * (n - 1ll) / 2;
        unordered_map<int, int> mp;
        for (int i = 0; i < n; i ++ ) {
            int t = nums[i] - i;
            ans -= mp[t];
            mp[t] ++;
        }
        return ans;
    }
};