acw_zhw

acw_zhw
4天前
/*

-- attribute @ min
-- set @ f[i][j] @ 用[i, j]所有数组成的数的最小花费
-- subset & transition @

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];
}
};


acw_zhw
4天前
/*

*/

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;
}
};


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天前
/*

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;
}
};


acw_zhw
4天前
/*

*/

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;
}
};


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 @ 能够进位的bits
a & b << 1 @ 把所有carry_in放到一个数

*/

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

*/
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;
}
};


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天前
/*

1.dp @ f[i][j], 看f[i-1][j], f[i][j-1],f[i-1][j-1]
2.遍历每行，累计高度，然后单调栈
3.枚举两列，然后变成一维数组问题

-- lc1074 @ 找出subarray的和 = k的个数  -> 找出submatrix的和=k的个数
-- lc365 @ 找出subarray的和 <=k 但最接近k的值 -> 找出submatrix的和 <=k 但最接近k的值

1.求出每行的prefix sum
2.然后枚举两列作为区间
3.问题就转换成了一维数组上，求有多少个subarray的和<= k @

sum[r] - k <= sum[l]时

*/

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;
}
};