头像

itdef

https://space.bilibili.com/18508846 && http://www.cnblogs.com/itdef




离线:13小时前


最近来访(1429)
用户头像
October003
用户头像
iic
用户头像
卡一哦
用户头像
LNN
用户头像
𝑬𝒑𝒊𝒑𝒉𝒂𝒏𝒊𝒆𝒅
用户头像
WangJY
用户头像
wby0124
用户头像
acwing_95426
用户头像
记着别人的好
用户头像
Vacant
用户头像
代健坤
用户头像
lihua777
用户头像
yxy.
用户头像
OLIVEIRA
用户头像
芒果黄桃冰
用户头像
小陈要努力
用户头像
AuroraY
用户头像
CyanFishhh
用户头像
jkz_
用户头像
黑夜最相似


itdef
2天前

地址 https://leetcode.cn/problems/maximal-rectangle/

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。
示例 1:

sample1.jpg

输入:matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出:6
解释:最大矩形如上图所示。


示例 2:
输入:matrix = []
输出:0


示例 3:
输入:matrix = [["0"]]
输出:0


示例 4:
输入:matrix = [["1"]]
输出:1


示例 5:
输入:matrix = [["0","0"]]
输出:0


提示:
rows == matrix.length
cols == matrix[0].length
1 <= row, cols <= 200
matrix[i][j] 为 '0' 或 '1'

本题解答使用到084 的单调栈代码
或者说就是084的二维加强数据版本
我们逐层扫描,每层使用084的代码记性最大矩形求解。
85.png
调用一次单调栈求柱状图矩形的时间复杂度为O(n)
逐层调用 ,共有m层,总的复杂度就是O(nm)

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int len = heights.size();
        vector<int> leftmin(len, -1);  vector<int> rightmin(len, len);
        stack<int> st;
        for (int i = 0; i < len; i++) {
            while (!st.empty() && heights[i] <= heights[st.top()]) { st.pop(); }
            if (!st.empty()) { leftmin[i] = st.top(); }
            st.push(i);
        }
        while (!st.empty()) { st.pop(); }
        for (int i = len - 1; i >= 0; i--) {
            while (!st.empty() && heights[i] <= heights[st.top()]) { st.pop(); }
            if (!st.empty()) { rightmin[i] = st.top(); }
            st.push(i);
        }
        int ans = 0;
        for (int i = 0; i < len; i++) {
            int left = leftmin[i];   int right = rightmin[i];
            ans = max(ans, (right - left - 1) * heights[i]);
        }
        return ans;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix.size(); int m = matrix[0].size();
        if (n == 0 || m == 0) return 0;
        vector<int> heights(m, 0);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == '1') {  heights[j]++;   }
                else {  heights[j] = 0;  }
            }
            ans = max(ans, largestRectangleArea(heights));
        }
        return ans;
    }
};

我的视频题解空间



新鲜事 原文

itdef
3天前
图片


活动打卡代码 AcWing 1883. 删减

itdef
5天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int main()
{
    string s, t, res;
    cin >> s >> t;
    for(int i = 0; i < s.size(); i ++)
    {
        res += s[i];
        if(res.size() >= t.size() && res.substr(res.size() - t.size(), t.size()) == t)
            res.erase(res.size() - t.size());
    }
    cout << res << endl;
    return 0;
}




活动打卡代码 AcWing 1874. 哞加密

itdef
5天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 55;

int n, m;
string g[N];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> g[i];

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

    unordered_map<string, int> hash;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            for (int k = 0; k < 8; k ++ )
            {
                int x = i, y = j;
                string s(1, g[x][y]);

                bool flag = true;
                for (int u = 0; u < 2; u ++ )
                {
                    x += dx[k], y += dy[k];
                    if (x < 0 || x >= n || y < 0 || y >= m)
                    {
                        flag = false;
                        break;
                    }
                    s += g[x][y];
                }

                if (flag && s[0] != s[1] && s[1] == s[2] && s[0] != 'M' && s[1] != 'O')
                    hash[s] ++ ;
            }

    int res = 0;
    for (auto& [k, v]: hash) res = max(res, v);

    cout << res << endl;
    return 0;
}





itdef
16天前

地址 https://leetcode.cn/problems/jump-game/?favorite=2cktkvj

给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。


示例 1:
输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2:
输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。
 
提示:
1 <= nums.length <= 3 * 104
0 <= nums[i] <= 105

注意题目是可以在当前位置选择可以跳跃最大长度内的任意长度,也就是在自己能达到的最远格子内,任一格子都是可以达到的,那么我们选择哪个格子呢?


1.png

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int currPos = 0;
        int canreach = currPos + nums[0];

        for (; currPos <= canreach; currPos++) {
            if (canreach >= nums.size() - 1) { break; }
            canreach = max(canreach, currPos + nums[currPos]);
        }

        return canreach >= nums.size()-1;

    }
};

我的视频题解空间




itdef
18天前

例子说明
7 =
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+2+2
1+2+2+2
1+2+4
1+1+1+4

一种方法是观察找规律
所有的n都有可以由上一个数的所有组合方案+1得到自己的一种组合方案
假设dp[x]表示x的2次幂数的组合方案数
那么dp[x]一部分可以由dp[x-1]转化而来
当x为偶数的时候 x的2次幂组合可以从 x/2的2次幂组合所有元素乘以2转化,而且和dp[x-1]的方案不重合
综上所述
当x为偶数的时候 dp[x] = dp[x/2]+dp[x-1]
当x为奇数的时候 dp[x]=dp[x-1]

#include <iostream>

using  namespace std;

const int N = 1000010;
long long dp[N];
int n;

void solve() {
    dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 2; dp[4] = 4;

    for (int i = 5; i <= n; i++) {
        if (i % 2 == 0) {
            dp[i] = dp[i - 1] + dp[i / 2];
        }
        else {
            dp[i] = dp[i - 1];
        }
        dp[i] = dp[i] % 1000000000;
    }

    cout << dp[n] << endl;

}

int main()
{
    cin >> n;

    solve();

    return 0;
}

另一种解法从背包的角度来看待

dp[x][y]表示在可选取(2^0,2^1,...2^x)的多个元素下 组合成y的方案数
那么可得dp[x][y] = dp[x-1][y-2^x]+dp[x-1][y-2*2^x]+...+dp[x-1][y-z*2^x]

还可以优化成1维数组,代码如下

#include <iostream>

using  namespace std;

const int N = 1000010;
long long dp[N];
int n;
const int MOD = 1000000000;

int main() {
    cin >> n;
    dp[0] = 1;

    for (int i = 1; i <= n; i <<= 1) {
        for (int j = 1; j <= n; j++) {
            if (j >= i) {
                dp[j] += dp[j - i];
                dp[j] %= MOD;
            }
        }
    }

    cout << dp[n] << endl;

    return 0;
}

我的视频题解空间




itdef
22天前

Google Codejam 2009, Round 1 problem C

一个监狱里有 P 个并排着的牢房, 从左到右依次编号为 1,2,...P
最初所有的牢房里都住着一个囚犯。相邻的两个牢房之间有一个窗户, 可以通过它与相邻的牢房里的囚犯对话。
现在要释放一批囚犯, 如果释放某个牢房的囚犯, 其相邻的牢房里的囚犯就会知道, 因而发怒暴动。
所以释放某个牢房的囚犯时, 必须要贿赂两旁相邻的囚犯一枚金币。
另外为了防止释放的消息在相邻牢房传开, 不仅两旁直接相邻的牢房, 所有可能听到消息的囚犯, 
即直到空牢房或者到监狱两端为止, 此间的所有囚犯都必须给一枚金币。
现在要释放 a_1,a_2...a_Q牢房里的 Q 名囚犯, 释放的顺序还未确定。
如果选择所需金币数尽量少的顺序释放, 最少需要多少金币?

输入
第一行整数 T(1≤T≤100),表示有多少组测试数据
每组测试数据有 2 行:
第一行有两个整数 P 和 Q
第二行有 Q 个整数,表示 a_1,a_2...a_Q
1≤P≤10000,1≤Q≤100
输出
输出 T 行,每行格式:Case #{第几组测试数据}: {答案},表示第几组测试数据,答案是多少
样例 1
输入
1
20 3
3 6 14
输出
Case #1: 35

如图
1.png
假如我们释放14号牢房囚犯,那么计算当前需要的花费 ,再加上释放1到13号房间中的3号和6号的囚犯的最小花费,就可以得到答案1
假如我们释放3号牢房囚犯,那么计算当前需要的花费 ,再加上释放4到20号房间中的14号和6号的囚犯的最小花费,就可以得到答案2
假如我们释放6号牢房囚犯,那么计算当前需要的花费 ,再加上释放1到5号房间中的3号囚犯的最小花费,再加上释放7到20号房间中的14号囚犯的最小花费,就可以得到答案3
答案123中的最小花费就是最后的实际答案。
我们可以使用递归来计算 使用dp[x][y]记录 释放x到y之间所有囚犯的最小开销。 但是由于P的范围太大,数组内存过大,这里使用哈希表记录释放x到y之间所有囚犯的最小开销。
用来避免重复计算.
代码

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <unordered_map>

using namespace std;

int t, p, q;
const int N = 10010;
int arr[N];
unordered_map<long long, int > dp;

int dfs(int rooml, int roomr, int arrl, int arrr) {
    if (roomr < rooml) return 0;
    if (arrr < arrl) return 0;
    long long key = rooml + roomr * 100000;
    if (dp.count(key) != 0) return dp[key];
    //if (dp[rooml][roomr] != 0x3f3f3f3f) return dp[rooml][roomr];

    int ans  = 0x3f3f3f3f;
    for (int i = arrl; i <= arrr; i++) {
        int selRoom = arr[i];
        int c = (selRoom - rooml);
        int d = (roomr - selRoom);
        int a = dfs(rooml, selRoom - 1, arrl, i - 1);
        int b = dfs(selRoom + 1, roomr, i + 1, arrr);
        ans = min(ans, a + b + c + d);
    }
    dp[key] = ans;
    return ans;
}


void solve(int curr) {
    dp.clear();
    cin >> p >> q;
    for (int i = 1; i <= q; i++) {
        cin >> arr[i];
    }
    sort(arr + 1, arr + 1 + q);
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= q; i++) {
        int selRoom = arr[i];
        int c = (selRoom - 1);
        int d = (p - selRoom);
        int a = dfs(1, selRoom - 1, 1, i - 1);
        int b = dfs(selRoom + 1, p, i + 1, q);
        ans = min(ans, a + b + c + d);
    }

    cout << "Case #" << curr << ": " << ans << endl;
}


int main()
{
    cin >> t;
    for (int i = 1; i <= t; i++) {
        solve(i);
    }

    return 0;
}

下面再来一个dp数组优化内存版本的方案
使用dp[x][y]记录 释放x到y房间之间的所有囚犯的最小开销。 但是由于P的范围太大,数组内存过大.无法使用这个数组.
使用arr[N]的数组记录要释放的囚犯号码, 可以考虑dp[x][y]表示释放arr[x]~~arr[y]之间的所有囚犯的最小开销。
dp[x][y] = min(dp[x][x+1]+dp[x+1][y] , dp[x][x+2],dp[x+2][y] … ,dp[x][y-1]+dp[y-1][y]);
2.png

#include <iostream>
#include <memory.h>
#include <algorithm>

using namespace std;

const int N = 110;
int arr[N];
int dp[N][N];
int t, n, l;


int dpFunc(int l, int r) {
    if ( r <=l+1) {
        dp[l][r] = 0;
    }

    if (dp[l][r] != -1) return dp[l][r];
    int ans = 0x3f3f3f3f;
    for (int i = l + 1; i < r; i++) {
        ans = min(ans, (arr[r] - arr[i]-1)   + (arr[i]-arr[l]-1) + dpFunc(l, i) + dpFunc(i, r));
    }

    dp[l][r] = ans;
    return ans;
}

void solve(int currIdx) {
    cin >> l >> n;
    memset(arr, 0, sizeof arr);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    //sort(&arr[1],&arr[1]+n);
    arr[0] = 0; arr[n + 1] = l + 1;
    memset(dp, -1, sizeof dp);

    int ans = dpFunc(0, n + 1);

    cout << "Case #" << currIdx << ": " << ans << endl;
    return ;
}

int main() {
    cin >> t;
    for (int i = 1; i <= t; i++) {
        solve(i);
    }

    return 0;
}

我的视频题解空间




itdef
1个月前

题目描述

你需要驾驶一辆汽车行驶 L 单位距离。

最开始时, 卡车上有 P 单位的汽油。

汽车每开 1 单位距离需要消耗 1 单位的汽油。

如果在途中车上的汽油耗尽, 车就无法继续前行, 因而无法达到终点。

在途中一共有 N 个加油站。第ii 个加油站在距离 终点 A_i单位距离的地方, 最多可以给汽车加 B_i单位汽油。

假设卡车的燃油箱的容量是无限大的。问最少加多少次汽油可以达到终点 ?

无法达到请输出-1。

输入
第一行是 N,表示有多少个加油站
接下来 N 行,每行两个整数 A_i, B_i,表示每个加油站距离 终点 的位置,以及最多可以加多少油
最后一行是 L, P
1≤N≤2∗10^4
1≤L≤10^6
1≤P≤10^6
1≤Ai≤L
1≤Bi≤100
输出
一个整数,表示最少加多少次油
样例 1
输入
4
4 4
5 2
11 5
15 10
25 10
输出
2

解答
本题目使用贪心算法,首先在已有的油的情况下,尽可能走远。如果油不足以达到终点或者 下一个点。从已经经过的点中选取一个加油。 由于要求加油次数最小,那么在可选择的加油站中选择可加油最多的站点加油。(同样是加一次油,贪心选择加油最多的站点,这样可以将加油次数的可能降低到最低)
1.png


算法1

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using  namespace std;

priority_queue<pair<int, int>, vector<pair<int, int>>> q;

int n;
const int N = 20010;
pair<int, int> dat[N];
int l, p;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> dat[i].first >> dat[i].second;
    }
    cin >> l >> p;

    sort(dat,dat+n);

    int currpos = l - p;   
    int ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (currpos <= 0) { break; }
        if (currpos <= dat[i].first) {
            q.push({ dat[i].second,dat[i].first });
        }
        else {
            while (currpos > dat[i].first && !q.empty()) {
                currpos -= q.top().first; q.pop(); ans++;
            }
            if (currpos > dat[i].first) { break; }
            else{ q.push({ dat[i].second,dat[i].first }); }
        }
    }


    while (currpos > 0 && !q.empty()) {
        currpos -= q.top().first; q.pop(); ans++;
    }

    if (currpos <= 0) {
        cout << ans<< endl;
    }
    else {
        cout << -1 << endl;
    }

    return 0;
}

我的视频题解空间



新鲜事 原文

itdef
2个月前
每个几天就有些乱七八糟的什么互相关注,谁谁的访客量大增,Y总来看我之类的发言。 就问一句,你们来acwing是玩朋友圈的么 ? 玩朋友圈去微信新浪 不香吗?


活动打卡代码 AcWing 1854. 晋升计数

itdef
3个月前
#include<iostream>
using namespace std;
int b[4], a[4];//before after
int main()
{
    for(int i=0; i<4; i++) cin>>b[i]>>a[i];
    cout<<a[1]+a[2]+a[3]-b[1]-b[2]-b[3]<<endl;
    cout<<a[2]+a[3]-b[2]-b[3]<<endl;
    cout<<a[3]-b[3]<<endl;
    return 0;
}