头像

jasonlin




离线:2小时前


活动打卡代码 LeetCode 174. 地下城游戏

jasonlin
3小时前

IMG_D079BA59350D-1.jpeg

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int n = dungeon.size(), m = dungeon[0].size();
        vector<vector<int>> f(n , vector<int>(m, 1e8));

        for(int i = n - 1; i >= 0 ;i --)
            for(int j = m - 1; j >= 0; j --)
            {
                int w = dungeon[i][j]; 
                if(i == n - 1 && j == m - 1) f[i][j] = max(1,1 - w);  // 很关键
                if(j < m - 1) f[i][j] = f[i][j + 1] - w;
                if(i < n - 1) f[i][j] = min(f[i][j], f[i + 1][j] - w); 
                f[i][j] = max(1, f[i][j]);  // 很关键
            }

        return f[0][0];
    }
};


活动打卡代码 AcWing 422. 校门外的树

jasonlin
7小时前

区间合并

排序 // 遍历维护区间 // 记得处理最后一个区间
IMG_CBB103CFB1F2-1.jpeg

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

using namespace std;


int n, m;
vector<vector<int>> intervals;

int main()
{
    cin >> n >> m;
    int st, ed;
    for(int i = 0; i < m; i ++)
    {
        cin >> st >> ed;
        intervals.push_back({st, ed});
    }
    sort(intervals.begin(), intervals.end());

    int cnt = n + 1;
    st = -2e9, ed = -2e9;
    for(auto &interval: intervals){
        if(ed < interval[0]){
            if(st != -2e9)  cnt -= ed - st + 1;
            st = interval[0], ed = interval[1];
        }
        else ed = max(ed, interval[1]);
    }

    cnt -= ed - st + 1; // 处理最后一个

    cout << cnt << endl;

    return 0;

}



活动打卡代码 AcWing 1227. 分巧克力

jasonlin
22小时前

整数二分

  • 分析题目
  • 确定区间分割
    • mid 属于左半边 【l, mid】 [mid + 1, r] 下取整 更新【r = mid // l = mid + 1】
    • mid 属于右半边 [l , mid - 1], [mid + 1, r] 上取整 更新【r = mid - 1 // l = mid 】

IMG_7B0DD158DAF8-1.jpeg

细节

乘法可能爆int

#include <iostream>

using namespace std;

typedef long long LL;  // 乘法可能会爆int

const int N = 100010;

int n, m;
int h[N], w[N];

bool check(int len){
    LL res = 0;
    for(int i = 0; i < n ; i ++){
        res += (LL)(h[i] / len) * (w[i] / len);
        if(res >= m) return true;
    }

    return false;
}
int main()
{
    cin >> n >> m;

    for(int i = 0; i < n; i ++)  cin >> h[i] >> w[i];

    int l = 1, r = 1e5;
    while(l < r){
        int mid =  l + r + 1 >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }

    cout << r << endl;

    return 0;
}


活动打卡代码 LeetCode 445. 两数相加 II

先逆序翻转
再相加,注意这里是头插


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverse(ListNode* head) {
        auto a = head, b = head->next;
        while (b) {
            auto c = b->next;
            b->next = a;
            a = b, b = c;
        }
        head->next = NULL;
        return a;
    }

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        l1 = reverse(l1), l2 = reverse(l2);
        auto dummy = new ListNode(-1);
        auto cur = dummy;
        int carry = 0;

        while (l1 || l2 || carry) {
            int a = l1 ? l1 -> val :0;

            int b = l2 ? l2 -> val :0;

            int sum = a + b + carry;
            auto cur = new ListNode(sum % 10);
            carry = sum / 10;
            // 采取头插 head 和 head -> next之间插入
            cur -> next = dummy -> next;
            dummy -> next = cur;

            if(l1) l1 = l1 -> next;
            if(l2) l2 = l2 -> next;
        }

        return dummy -> next;
    }
};




活动打卡代码 AcWing 680. 剪绳子

判定性问题

最优解 -> 浮点数二分

能不能二分的条件

  • check(mid)
#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N];

bool check(double length)   // 能不能分够m个
{
    int cnt = 0;
    for(int i = 0; i < n; i ++){
        cnt += a[i] / length;
        if(cnt >= m) return true;
    }

    return false;
}
int main()
{
    cin >> n >> m;   

    for(int i = 0 ; i < n; i ++)  cin >> a[i];

    double l = 0, r = 1e9;
    for(int i = 0 ; i < 100; i ++){. //  循环一个固定的次数 10^7  精度和时间都ok
        double mid = ( l + r ) / 2;
        if(check(mid))  l = mid;
        else r = mid;
    }

    printf("%.2lf\n", r); //  注意这里的输出格式控制
    return 0;
}



题目描述

给定一个非负整数 N,找出小于或等于 N 的最大的整数,同时这个整数需要满足其各个位数上的数字是单调递增。

(当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。)
说明: N 是在 [0, 10^9] 范围内的一个整数

样例

示例 1:

输入: N = 10
输出: 9
示例 2:

输入: N = 1234
输出: 1234
示例 3:

输入: N = 332
输出: 299

算法1

(贪心) $O(n)$ or $O(logN)$

要使得最大,尽可能的要求高位基本不变

  • 从高位到地位遍历,找到第一个下降沿(破坏了单调递增),该点减1,后面全部变为9

    • 若减1后,破坏了与前面的单调性,因此找到最前面与该点未减1的相等点,将其减1,后面全部变为9
    • 未减1时,前面时单调递增的,为了找到上述部分最前面与该点未减1的相等点, 也就是前缀中最早最大的点的下标
  • 总结

    • 高位到低位遍历,找到第一个下降沿,下标为i
    • s[o ~ i] 中最大值的下标为 idx
      • s[0 ~ idx -1] 不变
      • s[idx] = s[idx] -1
      • s[idx + 1 ~ n -1] = 9

IMG_48E4C05728FD-1.jpeg

时间复杂度

遍历一次,n为该数字转化为字符串形式的长度,$O(n)$ OR $O(logN)$

C++ 代码

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string num = to_string(N);
        char max_num = '0', idx = -1, n = num.size();

        for(int i = 0 ; i < n ; i ++){
            if(num[i] > max_num){
                max_num = num[i];
                idx = i;
            }
            if(i < n -1 && num[i] > num[i + 1]){
                num[idx] -= 1;
                for(int j = idx + 1; j < n; j ++) num[j] = '9';
                break;
            }
        }

        return stoi(num);
    }
};






**### 贪心
- 尽可能保证高位不变
- 遍历找到第一个破坏单调性的下标 i
- 找到以该位置为结尾的前缀中的最大值的下标 idx
- s[0- idx -1] 不变
- s[idx] - 1
- s[idx + 1 ~ n-1] = '9'
-
IMG_7E842DFBB6FD-1.jpeg

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string num = to_string(N);
        char max_num = '0', idx = -1, n = num.size();

        for(int i = 0 ; i < n ; i ++){
            if(num[i] > max_num){
                max_num = num[i];
                idx = i;
            }
            if(i < n -1 && num[i] > num[i + 1]){
                num[idx] -= 1;
                for(int j = idx + 1; j < n; j ++) num[j] = '9';
                break;
            }
        }

        return stoi(num);
    }
};




活动打卡代码 LeetCode 402. 移掉K位数字

贪心 切记

IMG_823E986CF094-1.jpeg

class Solution {
public:
    string removeKdigits(string num, int k) {
        k = min(k, (int)num.size());
        string res;
        for(auto c : num){
            while(k && res.size() && res.back() > c){
                k --;
                res.pop_back();
            }
            res += c;
        }

        while(k --) res.pop_back();  // 没删干净 删除后缀
        k = 0;   // 处理前导0
        while(k < res.size() && res[k] == '0') k++;
        if(k == res.size()) res += '0';  // 全空
        return res.substr(k);
    }
};


活动打卡代码 AcWing 1346. 回文平方

IMG_68AE4AC0B5B0-1.jpeg

短除法 进制转换

string base(int n, int b)
{
    string num;
    while (n) num += get(n % b), n /= b;
    reverse(num.begin(), num.end());
    return num;
}
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

char get(int x)  // 数字 -> 字符
{
    if(x <= 9) return x + '0';
    return x - 10 + 'A';
}

string base(int n, int b)
{
    string num;
    while(n) num += get(n % b), n /= b;
    reverse(num.begin(), num.end());
    return num;
}

bool check(string s)
{
    int n = s.size();
    for(int i = 0, j = n -1; i < j; i ++, j --)
        if(s[i] != s[j])  return false;

    return true;
}
int main(){
    int b; 
    cin >> b;

    for(int i = 1; i <= 300; i ++){
        auto num = base(i * i, b);
        if(check(num))
            cout << base(i, b) << ' ' << num << endl;
    }

    return 0;
}



题目描述

在本问题中,有根树指满足以下条件的有向图。该树只有一个根节点,所有其他节点都是该根节点的后继。
每一个节点只有一个父节点,除了根节点没有父节点。

输入一个有向图,该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。
附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。 每一个边 的元素是一对 [u, v],
用以表示有向图中连接顶点 u 和顶点 v 的边,其中 u 是 v 的一个父节点。

返回一条能删除的边,使得剩下的图是有N个节点的有根树
若有多个答案,返回最后出现在给定二维数组的答案

样例

示例 1:

输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的有向图如下:
  1
 / \
v   v
2-->3
示例 2:

输入: [[1,2], [2,3], [3,4], [4,1], [1,5]]
输出: [4,1]
解释: 给定的有向图如下:
5 <- 1 -> 2
     ^    |
     |    v
     4 <- 3
注意:

二维数组大小的在3到1000范围内。
二维数组中的每个整数在1到N之间,其中 N 是二维数组的大小。


算法1

(并查集) $O(n)$

首先树,不能有, 其次不能有两个父节点同时指向一个孩子节点,也就是不能有入度为2的节点
IMG_61860B543A84-1.jpeg

  • 因此分为两种情况
    • 构成
    • 入度为2的点, 去掉其中一条边,使其入度为变为1
      • 如果入度为2的点还参与形成了,那么就应该删除构成环的那一条
      • 否则,随便删除其中一条即可,按照题目要求,返回数组中的靠后的边

时间复杂度

  • 遍历数对$O(n)$
  • 并查集 ~$O(n)$

C++ 代码

class Solution {
public:
    vector<int> p;

    int find(int x ){
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    void merge(int x, int y){
        p[find(x)] = find(y);
    }

    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        p.resize(n + 1);
        for(int i = 1; i <= n; i++) p[i] = i;

        // 找入度为2的节点
        vector<int> in_degree(n + 1, 0);
        int k = -1;
        for(auto &e : edges){
            in_degree[e[1]] ++;
            if(in_degree[e[1]] == 2) k = e[1];
        }

        vector<int> in_degree_equal_2;
        for(auto &e : edges){
            int a = e[0], b = e[1];
            if(b == k){
                in_degree_equal_2.push_back(a);
                continue;
            }
            if(find(a) == find(b))  return e;
            else merge(a, b);
        }

        if(find(in_degree_equal_2[0]) == find(k)) return {in_degree_equal_2[0], k};
        else return {in_degree_equal_2[1], k};  // 返回构成环 或者是 考后的那条边
    }
};