头像

acw_zhw


访客:4126

离线:20小时前



acw_zhw
4天前
/*
区间合并dp @ 
-- attribute @ min
-- set @ f[i][j] @ 用[i, j]所有数组成的数的最小花费
-- subset & transition @ 
枚举root k
f[i][j] = min{max(f[i][k - 1], f[k + 1][j] + k)} k = i...j 

*/


class Solution {
public:
    int getMoneyAmount(int n) {
        int f[n + 1][n + 1]; 
        for (int i = 1; i <= n; i ++ ) f[i][i] = 0;

        for (int len = 2; len <= n; len ++ )
            for (int i = 1; i + len <= n + 1; i ++ )
            {
                int j = i + len - 1;
                f[i][j] = INT_MAX;
                for (int k = i; k <= j; k ++ )
                {
                    int a = k > i ? f[i][k - 1] : 0;
                    int b = k < j ? f[k + 1][j] : 0;
                    f[i][j] = min(f[i][j], max(a, b) + k);
                }
            }
        return f[1][n];
    }
};


活动打卡代码 LeetCode 376. 摆动序列

acw_zhw
4天前
/*
跟股票版本1号题差不多,找出单调变化线,线上除两端的点都可以删除
所以可以O(n)
*/

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return n;

        int i = 1, res = 1;
        while (i < n && nums[i] == nums[0]) i ++;
        if (i == n) return 1;

        int m = nums[i] > nums[0] ? 1 : -1;
        for ( ;i < n; m *= -1)
        {
            res ++;
            int t = i + 1;
            while (t < n && (nums[t] - nums[t - 1]) * m >= 0) t ++;
            i = t;
        }
        return res;
    }
};


活动打卡代码 LeetCode 374. 猜数字大小

acw_zhw
4天前
/*
二分
*/

class Solution {
public:
    int guessNumber(int n) {
        using LL = long long;
        LL l = 1, r = n;
        while (l < r)
        {
            LL mid = l + r >> 1;
            if (guess(mid) == 1) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};



acw_zhw
4天前
/*
多路归并 @ 
分别给数组1的每个数开个组,存进priority queue, 每次pop出最小的
然后加入下一个

e.g.
[1, 7, 11]
[2, 4, 6]

(3, 1, 0)
(9, 7, 0)
(13, 11, 0)

1. pop (3, 1, 0)
push (5, 1, 1)
2. pop (5, 1, 1)
push(7, 1, 2)
3. pop (7, 1, 2) 够三个数了

*/

class Solution {
    struct Item 
    {
        int sum, num1, idx2;
        bool operator > (const Item &rhs) const 
        {
            return sum > rhs.sum;
        }
    };
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {

        int n = nums1.size(), m = nums2.size();
        if (n == 0 || m == 0) return {};
        priority_queue<Item, vector<Item>, greater<Item>> pq;
        for (auto num1: nums1)
            pq.push({num1 + nums2[0], num1, 0});

        vector<vector<int>> res;
        while (pq.size() && k -- )
        {
            auto num1 = pq.top().num1, idx2 = pq.top().idx2; pq.pop();
            res.push_back({num1, nums2[idx2]});
            if (idx2 + 1 != m) pq.push({num1 + nums2[idx2 + 1], num1, idx2 + 1});
        }
        return res;
    }
};


活动打卡代码 AcWing 372. 超级次方

acw_zhw
4天前
/*
从左往右算, 每次算完之后, 结果的10次方表示b * 10了
*/

class Solution {
    static const int mod = 1337;
    using LL = long long;
public:
    int superPow(int a, vector<int>& b) {

        // 1.建表 a的0到9次方
        LL p[10]{1};
        for (int i = 1; i <= 9; i ++ ) 
            p[i] = a * p[i - 1] % mod;

        // 2.每次 * 10就是求10次方
        LL res = 1;
        for (int i = 0; i < b.size(); i ++ )
            res = pow10(res) * p[b[i]] % mod;
        return res;
    }
private:
    LL pow10(int x)
    {
        LL pow2 = x * x % mod;
        LL pow4 = pow2 * pow2 % mod;
        LL pow8 = pow4 * pow4 % mod;
        return pow2 * pow8 % mod;
    }
};


活动打卡代码 AcWing 371. 两整数之和

acw_zhw
4天前
/*
leetcode上有个位运算总结的非常好的帖子:
https://leetcode.com/problems/sum-of-two-integers/discuss/84278/A-summary%3A-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently

• Set union A | B
  Set intersection A & B
  Set subtraction A & ~B
  Set negation ALL_BITS ^ A or ~A
  Set bit A |= 1 << bit
  Clear bit A &= ~(1 << bit)

• Test bit (A & 1 << bit) != 0

• Extract last bit A&-A @ 就是lowbit,用于树状数组
  Remove last bit A&(A-1) @ 直接删除lowbit,可以用来数有多少个bit 1

先明白a ^ b, a & b << 1的作用
a ^ b @ 求的是没有进位的和
a & b @ 能够进位的bits
a & b << 1 @ 把所有carry_in放到一个数

然后通过递归不断合并a ^ b, a & b << 1直至没有进位为止
注意如果a & b < 0 的话, a & b << 1会overflow
我们可以手动把最高位的bit 1置0再shift
*/

class Solution {
public:
    int getSum(int a, int b) {
        int t = a & b;
        t &= ~(1 << 31);
        return b == 0 ? a : getSum(a ^ b, t << 1);
    }
};



acw_zhw
5天前
/*
1.排序
2.dp - LIS
-- set @ f[i], g[i]
---- f[i] @ 从前往后包含第i个数的最长序列长度

-- subset & transition
f[i] = max{f[j] + 1} if nums[i] % nums[j] == 0

因为需要重构答案,所以记录一个last数组 @ 记录上一个下标是多少
*/
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return {};
        sort(nums.begin(), nums.end());

        int maxv = 0, maxi;
        int f[n], last[n];
        for (int i = 0; i < n; i ++ )
        {
            f[i] = 1;
            int t;
            for (int j = 0; j < i; j ++ )
                if (nums[i] % nums[j] == 0)
                {
                    if (f[j] + 1 > f[i])
                        f[i] = f[j] + 1, t = j;
                }

            if (f[i] == 1) last[i] = -1;
            else last[i] = t;

            if (f[i] > maxv)
                maxv = f[i], maxi = i;
        }

        vector<int> res;
        while (maxi != -1)
        {
            res.push_back(nums[maxi]);
            maxi = last[maxi];
        }
        reverse(res.begin(), res.end());
        return res;
    }
};



acw_zhw
5天前
/*
二分
*/

class Solution {
public:
    bool isPerfectSquare(int num) {
        using LL = long long;
        LL l = 1, r = num;
        while (l < r)
        {
            LL mid = l + r >> 1;
            if (mid * mid < num) l = mid + 1;
            else r = mid;
        }
        return l * l == (LL) num;
    }
};


活动打卡代码 LeetCode 365. 水壶问题

acw_zhw
5天前
/*
数学题

acwing基础课的裴蜀定理 @ there always exists a, b
ax + by = gcd(x, y)
*/

class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        if (z == 0) return true;
        if (x == 0 && y == z) return true;
        if (y == 0 && x == z) return true;
        if (x == 0 && y == 0) return false;
        return z % std::gcd(x, y) == 0 
                && x + y >= z;
    }
};



acw_zhw
5天前
/*
目前知道的优化matrix的手段
1.dp @ f[i][j], 看f[i-1][j], f[i][j-1],f[i-1][j-1]
2.遍历每行,累计高度,然后单调栈
3.枚举两列,然后变成一维数组问题

这题属于第三种,跟lc1074是一类题,都是先考虑一维问题,能把O(n^2)压成O(n)的话就能
推广到二维来做
-- lc1074 @ 找出subarray的和 = k的个数  -> 找出submatrix的和=k的个数
-- lc365 @ 找出subarray的和 <=k 但最接近k的值 -> 找出submatrix的和 <=k 但最接近k的值

1.求出每行的prefix sum 
2.然后枚举两列作为区间 
3.问题就转换成了一维数组上,求有多少个subarray的和<= k @
满足sum[r] - sum[l] <= k
sum[r] - k <= sum[l]时
更新答案sum[l]越小越好
可以用set来二分解决

*/

class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return 0;

        int n = matrix.size(), m = matrix[0].size();
        // 1.求每行的prefix sum
        int psum[n][m + 1]; memset(psum, 0, sizeof psum);
        for (int i = 0; i < n; i ++ )
            for (int j = 1; j <= m; j ++ )
                psum[i][j] = psum[i][j - 1] + matrix[i][j - 1];

        // 2.枚举两列作为左右边界
        int res = INT_MIN;
        for (int l = 0; l < m; l ++ )
            for (int r = l; r < m ; r ++ )
                // 3.求一维的数组有多少个subarray的和<= k
                // 前缀和 + 哈希bst
                {
                    set<int> S{0};
                    int sum = 0;
                    for (int i = 0; i < n; i ++)
                    {
                        sum += psum[i][r + 1] - psum[i][l];
                        auto it = S.lower_bound(sum - k);
                        if (it != S.end()) res = max(res, sum - *it);
                        S.insert(sum);
                    }
                }

        return res;
    }
};