echomingzhu

echomingzhu
3小时前
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
if(nums1.size() == 0 || nums2.size() == 0){
return ;
}
if((m + n) != nums1.size() || n != (nums2.size())){
return ;
}

int i = m - 1, j = n - 1;
int k = m + n - 1;
while(i >= 0 && j >= 0){
if(nums1[i] >= nums2[j]){
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}

while (j >= 0){
nums1[k--] = nums2[j--];
}

return ;
}
};


class Solution {
public:
string minWindow(string s, string t) {
if(s.size() == 0 || t.size() == 0){
return "";
}

unordered_map<char, int> ht, hs;
for(auto &c: t){
ht[c]++;
}

//区间【l, r）
int l = 0, r = 0;
int dis = 0;
int res = INT_MAX;
int left = 0, right = 0;
string ans = "";
while(r < s.size()){

char c = s[r];
hs[c]++;
r++;
if(ht.count(c) > 0){
if(hs[c] == ht[c]){
dis ++;
}
}

//cout << "debug: l=" << l << ", r=" << r << ", dis=" << dis << endl;

while(dis == ht.size()){

char d = s[l];
if(r - l < res){
res = r - l;
left = l, right = r;
}

if(ht.count(d) > 0){
if(hs[d] == ht[d]){
dis--;
}
}

hs[d]--;
l++;
}
}

if(res != INT_MAX){
ans = s.substr(left, res);
}

return ans;
}
};


### 题目描述

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

#### 样例1

输入：word1 = "horse", word2 = "ros"

horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')


#### 样例2

输入：word1 = "intention", word2 = "execution"

intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')


### 算法

##### (DP) $O(mn)$

1. word1 [1,i] 添加一个字符 word1[i+1] 得到 word2 [1, j], 则 f[i, j] = f[i, j-1] + 1
2. word1 [1,i] 删除一个字符 word1[i] 得到 word2 [1,j], 则 f[i, j] = f[i-1, j] + 1
3. word1 [1,i] 修改一个字符 word1[i] 得到 word2 [1,j], 则 f[i,j] = f[i-1, j-1] + 1/0(word1[i]是否等于word[j])

#### C++ 代码

class Solution {
public:
int minDistance(string word1, string word2) {
if(word1.size() == 0 || word2.size() == 0){
return max(word1.size(), word2.size());
}

int m = word1.size(), n = word2.size();
word1 = ' ' + word1;
word2 = ' ' + word2;

vector<vector<int>> f(m + 1, vector<int>(n + 1));
for(int j = 0; j <= n; j++) f[0][j] = j;
for(int i = 0; i <= m; i++) f[i][0] = i;

for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
f[i][j] = min(f[i][j-1], f[i-1][j]) + 1;
int t = 0;
if(word1[i] != word2[j]){
t = 1;
}
f[i][j] = min(f[i][j], f[i-1][j-1] + t);
}
}

return f[m][n];
}
};


class Solution {
public:
int minDistance(string word1, string word2) {
if(word1.size() == 0 || word2.size() == 0){
return max(word1.size(), word2.size());
}

int m = word1.size(), n = word2.size();
word1 = ' ' + word1;
word2 = ' ' + word2;

vector<vector<int>> f(m + 1, vector<int>(n + 1));
for(int j = 0; j <= n; j++) f[0][j] = j;
for(int i = 0; i <= m; i++) f[i][0] = i;

for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
f[i][j] = min(f[i][j-1], f[i-1][j]) + 1;
int t = 0;
if(word1[i] != word2[j]){
t = 1;
}
f[i][j] = min(f[i][j], f[i-1][j-1] + t);
}
}

return f[m][n];
}
};


class Solution {
public:
void sortColors(vector<int>& nums) {
if(nums.size() == 1 || nums.size() == 1){
return ;
}

int p0 = 0, p2 = nums.size() - 1;
int cnt1 = 0;
for(int i = 0; i <= p2; i++){
if(nums[i] == 0) nums[p0++] = 0;
else if(nums[i] == 1) cnt1++;
else if(nums[i] == 2){
while(p2 > i && nums[p2] == 2) p2--;
if(p2 == i) break;
else {
swap(nums[i], nums[p2]);
i--;
}
}
}

for(int i = p0; i <= p0 + cnt1 - 1; i++){
nums[i] = 1;
}

return ;
}
};


class Solution {
public:

vector<vector<int>> ans;
vector<int> path;
vector<bool> vst;
vector<vector<int>> combine(int n, int k) {
if(n == 0 || k == 0 || k > n){
return ans;
}

vst = vector<bool>(n + 1, false);
path = vector<int>(k);

dfs(n, 0, k, 0);

return ans;
}

void dfs(int n, int u, int k, int prev){
if(u == k){
ans.push_back(path);
return ;
}

for(int i = 1; i <= n; i++){
if(vst[i] == false && i > prev){
vst[i] = true;
path[u] = i;
dfs(n, u + 1, k, i);
vst[i] = false;
}
}
}
};


class Solution {
public:

vector<vector<int>> ans;
vector<int> path;

vector<vector<int>> subsets(vector<int>& nums) {
if(nums.size() == 0){
return ans;
}

int n = nums.size();
dfs(n, 0, nums);
return ans;
}

void dfs(int n, int u, vector<int>& nums){
if(u == n){
ans.push_back(path);
return ;
}

// 当前位置不选
dfs(n, u + 1, nums);

//选择
path.push_back(nums[u]);
dfs(n, u + 1, nums);
path.pop_back();
}
};


class Solution {
public:

vector<vector<bool>> vst;
bool exist(vector<vector<char>>& board, string word) {
if(board.size() == 0 || board[0].size() == 0){
return false;
}

int m = board.size(), n = board[0].size();
vst = vector<vector<bool>>(m, vector<bool>(n, false));

for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
//vst = vector<vector<bool>>(m, vector<bool>(n, false));
if(board[i][j] == word[0]){
vst[i][j] = true;
if(dfs(board, 1, i, j, word)){
return true;
}
vst[i][j] = false;
}
}
}

return false;
}

bool dfs(vector<vector<char>>& board, int u, int x, int y, string& word){
if(u == word.size()){
return true;
}

int m = board.size(), n = board[0].size();
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

for(int i = 0; i < 4; i++){
int nx = x + dx[i], ny = y + dy[i];
if(nx >= 0 && nx < m && ny >= 0 && ny < n && vst[nx][ny] == false && board[nx][ny] == word[u]){
vst[nx][ny] = true;
if(dfs(board, u + 1, nx, ny, word) == true){
return true;
}
vst[nx][ny] = false;
}
}

return false;
}
};


class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size() == 0 || nums.size() == 1){
return nums.size();
}

int k = 0;
int n = nums.size();
for(int i = 0; i < n; i++){

int j = i + 1;
while(j < n && nums[j] == nums[i]) j++;
// j第一个不等于nums[i]的位置
int cnt = j - i;
if(cnt > 2){
cnt = 2;
}
while(cnt--){
nums[k++] = nums[i];
}
i = j - 1;
}

return k;
}
};


# 一. 不等式贪心

## 1. 问题模型

n个人排队打水，每个人打水的时间为 t[i], 如何设置打水顺序使得所有人的排队等待时间最短？

## 3. 代码模板

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef long long LL;

int main()
{
int n;
cin >> n;

vector<int> t = vector<int>(n, 0);
for(int i = 0; i < n; i++){
cin >> t[i];
}

sort(t.begin(), t.end());

LL ans = 0;
for(int i= 0; i < n; i++){
ans += (t[i] * (n - i - 1));
}

cout << ans << endl;

return 0;
}


# 二. 绝对值不等式

## 1. 问题模型

n个村庄位置，如何设置超市位置，可以使得超市到所有村庄的距离最小

## 3. 代码模板

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

using namespace std;

int main()
{
int n;
cin >> n;

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

sort(a.begin(), a.end());
int x = a[a.size() / 2];

long long ans = 0;
for(int i = 0; i < n; i++){
ans += abs(x - a[i]);
}

cout << ans << endl;
return 0;
}


# 三 推公式贪心

## 1. 问题模型

n个人叠罗汉，每个人有属性重量 w和强壮 s

## 3. 代码模板

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

using namespace std;

struct Node{
int all;
int w, s;

bool operator<(const struct Node& b)
{
return all < b.all;
}
};

int main()
{
int n;
cin >> n;

vector<struct Node> zoo(n);

for(int i = 0; i < n; i++){
int w, s;
cin >> w >> s;
zoo[i] = {w+s, w, s};
}

sort(zoo.begin(), zoo.end());

int ans = INT_MIN;
long long prev = 0;
for(int i = 0; i < n; i++){
int tmp = prev - zoo[i].s;
ans = max(ans, tmp);
prev += zoo[i].w;
}

cout << ans << endl;
return 0;
}