jasonlin

2.9万

jasonlin
3小时前

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


jasonlin
7小时前

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

}



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 】

#### 细节

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



/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
while (b) {
auto c = b->next;
b->next = a;
a = b, b = c;
}
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;
cur -> next = dummy -> next;
dummy -> next = cur;

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

return dummy -> next;
}
};



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


### 题目描述

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

#### 样例

示例 1:



### 算法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

#### 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'
-

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



### 贪心 切记

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


### 短除法 进制转换

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


### 题目描述

#### 样例

示例 1:

1
/ \
v   v
2-->3

5 <- 1 -> 2
^    |
|    v
4 <- 3



### 算法1

##### (并查集) $O(n)$

• 因此分为两种情况
• 构成环
• 入度为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};  // 返回构成环 或者是 考后的那条边
}
};