头像

echomingzhu


访客:9849

在线 



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


活动打卡代码 LeetCode 76. 最小覆盖子串

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



题目描述

给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:
1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

样例1

输入:word1 = "horse", word2 = "ros"
输出:3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

样例2

输入:word1 = "intention", word2 = "execution"
输出:5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

算法

(DP) $O(mn)$

典型的字符串状态转换问题,注意题目的关键字“最小”、 word1转换成 word2三种方法
同时关键的一点是状态转换和顺序没有关系, 比如“abc”转换成 "c",
可以先删掉 a,再删掉 b得到 c
也可以先删掉 b, 再删掉 a得到 c
定义:f[i, j]: 所有 word1[1-i]个字符转换成word2[1-j]所有方案的集合,所有集合的最小值
那么: f[i,j]由题意可知,word2 [1,j]可以由 word1 [1,i]通过添加一个字符/删除一个字符/修改一个字符三种方式转换而来
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])
综合上面三种情况,
状态转移方程: f[i,j] = min(min(f[i,j-1], f[i-1, j]) + 1, f[i-1,j-1] + 1/0)

时间复杂度

参考文献

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


活动打卡代码 LeetCode 72. 编辑距离

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


活动打卡代码 LeetCode 75. 颜色分类

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


活动打卡代码 LeetCode 77. 组合

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


活动打卡代码 LeetCode 78. 子集

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


活动打卡代码 LeetCode 79. 单词搜索

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], 如何设置打水顺序使得所有人的排队等待时间最短?

2. 贪心思想,打水最慢最墨迹的排最后,不要耽误别人时间

按照打水时间从小到大的顺序打水,总的打水时间最小

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个村庄位置,如何设置超市位置,可以使得超市到所有村庄的距离最小

2. 贪心思想

坐标按照从小达到位置排序,中间的位置(奇数中间的那个数位置/偶数中间两个数围成的闭区间任意位置)
放置超市位置可以使得总距离最小

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
定义一个人的危险系数等于所有在这个人上层重量 w 之和减去这个人自身的强壮 s
问如何能够让所有人当中危险系数最大的人危险系数数值最小?

2. 贪心思想

按照所有人的 重量和强壮属性之和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;
}