【LeetCode 热题 HOT 100】题解笔记 —— Day03

2023-12-23 17:59:18

? 作者主页:欢迎来到我的技术博客😎
? 个人介绍:大家好,本人热衷于Java后端开发,欢迎来交流学习哦!( ̄▽ ̄)~*
🍊 如果文章对您有帮助,记得关注点赞收藏评论??????
📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉

一、全排列

1. 题目描述

在这里插入图片描述

2. 思路分析

在这里插入图片描述
算法流程:

  • p a t h path path 数组来保存排序,当排序长度为 n 时,是一个排序方案,输出该方案;
  • s t a t e state state 数组表示数字是否使用过。当 s t a t e [ i ] state[i] state[i] 为 1 时表示 i i i已经被使用过, s t a t e [ i ] state[i] state[i] 为 0 时表示 i i i没有被使用过;
  • d f s ( i ) dfs(i) dfs(i) 表示的含义是:在 p a t h [ i ] path[i] path[i] 处填写数字,然后递归的在下一个位置填写数字;
  • 回溯:第 i 个位置填写某个数字的所有情况都遍历后, 第 i 个位置填写下一个数字。

3. 代码实现

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> st;

    vector<vector<int>> permute(vector<int>& nums) {
        path = vector<int>(nums.size());
        st = vector<bool>(nums.size());

        dfs(nums, 0);
        return ans;
    }

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

        for (int i = 0; i < nums.size(); i ++) {
            if (!st[i]) {
                path[u] = nums[i];
                st[i] = true;
                dfs(nums, u + 1);
                st[i] = false;
            }
        }
    }
};

二、旋转图像

1. 题目描述

在这里插入图片描述


2. 思路分析

(操作分解) O( n 2 n^2 n2)
直接操作旋转 9 0 o 90^o 90o比较困难,我们可以将它分解成两个操作:

  1. 先以左上-右下对角线为轴做翻转;
  2. 再以中心的竖线为轴做翻转;

在这里插入图片描述


3. 代码实现

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n; i ++) 
            for (int j = i + 1; j < n; j ++)
                swap(matrix[i][j], matrix[j][i]);
        
        for (int i = 0; i < n; i ++)        
            for (int j = 0, k = n - 1; j < k; j ++, k --) 
                swap(matrix[i][j], matrix[i][k]);
    }
};

三、字母异位词分组

1.题目描述

在这里插入图片描述


2. 思路分析

由于互为字母异位词的两个字符串包含的字母相同,因此对两个字符串分别进行排序之后得到的字符串一定是相同的,故可以将排序之后的字符串作为哈希表的键。

定义从 string 映射到vector<string>的哈希表: unordered_map<string, vector<string>>
我们将每个字符串的所有字符从小到大排序,将排好序的字符串作为key,然后将原字符串插入key对应的vector<string>>


3. 代码实现

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hash;
        for (auto& str : strs) {
            string nstr = str;
            sort(nstr.begin(), nstr.end());
            hash[nstr].push_back(str);
        }

        vector<vector<string>> res;
        for (auto& item : hash) res.push_back(item.second);

        return res;
    }
};

四、最大子数组和

1. 题目描述

在这里插入图片描述


2. 思路分析

动态规划 O ( n ) O(n) O(n)

  1. f(i)f(i) 表示以第 i i i 个数字为结尾的最大连续子序列的 总和 是多少。
  2. 初始化: f(0)=nums[0]
  3. 转移方程 f(i)=max(f(i?1)+nums[i],nums[i])。可以理解为当前有两种决策,一种是将第 i i i 个数字和前边的数字拼接起来;另一种是第 i i i 个数字单独作为一个新的子序列的开始。
  4. 最终答案为 a n s = m a x ( f ( k ) ) , 0 ≤ k < n ans=max(f(k)),0≤k<n ans=max(f(k)),0k<n

3. 代码实现

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size(), res = nums[0];
        vector<int> f(n);
        f[0] = nums[0];

        for (int i = 1; i < n; i ++) {
            f[i] = max(f[i - 1] + nums[i], nums[i]);
            res = max(res, f[i]);
        }
        return res;
    }
};

五、跳跃游戏

1. 题目描述

在这里插入图片描述


2. 思路分析

核心思想:尽可能跳到更远的位置。

  1. 若往后的位置能跳到,则前面的位置一定可以跳到, l a s t last last 表示的是从前 i ? 1 i - 1 i?1 个位置中跳,能跳到最远的位置是 l a s t last last
  2. 若前 i ? 1 i - 1 i?1 个位置中跳,跳到最远的位置是 l a s t last last i i i 小,表示从前 i ? 1 i - 1 i?1 个位置中跳,跳不到 i i i 的位置,因此一定不能跳到最后一个的位置;
  3. 若前 i ? 1 i - 1 i?1 个位置中跳,能跳到 i i i,则继续尝试从 i i i 位置跳,可能会跳得更远,更新 l a s t last last 的值。

3. 代码实现

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int last = 0;
        for (int i = 0; i <nums.size(); i ++) {
            if (last < i) return false;
            last = max(last, i + nums[i]);
        }
        return true;
    }
};

六、合并区间

1. 题目描述

在这里插入图片描述


2. 思路分析

贪心思想:

  1. 首先对各区间进行排序;
  2. 定义当前区间的左右端点为第一个区间的左右端点;
  3. 从前往后遍历每一个区间,如果当前区间与上一个区间有交集,则更新右端点;否则将上一个区间加入集合,然后更新当前区间。

3. 代码实现

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& a) {
        vector<vector<int>> res;
        if (a.empty()) return res;

        sort(a.begin(), a.end());
        int l = a[0][0], r = a[0][1];
        for (int i = 1; i < a.size(); i ++) {
            if (a[i][0] > r) {
                res.push_back({l, r});
                l = a[i][0], r = a[i][1];
            } else r = max(r, a[i][1]);
        }
        res.push_back({l, r});
        return res;
    }
};

七、不同路径

1. 题目描述

在这里插入图片描述


2. 思路分析

动态规划

  1. 状态表示: f[i][j] 表示从起点到 ( i , j ) (i,j) (i,j) 的路径总和;
  2. 状态转移方程: f[i][j] = f[i - 1][j] + f[i][j - 1];
  3. 初始化: 对于第一行f[0][j] 或者第一列 f[j][0],由于都是在边界,所有只能为1。

3. 代码实现

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> f(m, vector<int>(n));

       for (int i = 0; i < m; i ++)
            for (int j = 0; j < n; j ++) {
                if (!i || !j) f[i][j] = 1; //f[i][0] 和 f[0][j]单独初始化为1
                else f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        return f[m - 1][n - 1];
    }
};

八、最小路径和

1. 题目描述

在这里插入图片描述


2. 思路分析

状态表示: f[i][j] 表示从起点到 ( i , j ) (i,j) (i,j) 的最小路径和。
很显然,f[0][0] = grid[0][0],对于 f f f 中的其余元素值,通过以下状态转移方程计算元素值:

  • i > 0 i > 0 i>0 j = 0 j = 0 j=0 时(即第一行),f[i][0] = f[i - 1][0] + grid[i][0];
  • i = 0 i = 0 i=0 j > 0 j > 0 j>0 时(即第一列),f[0][j] = f[0][j - 1] + grid[0][j];
  • i > 0 i > 0 i>0 j > 0 j > 0 j>0 时,f[i][j] = min(f[i - 1][j], f[i][j - 1] + grid[i][j];

3. 代码实现

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();

        vector<vector<int>> f(n, vector<int>(m));
        f[0][0] = grid[0][0]; //起点

        //第一行,只能从左边来
        for (int i = 1; i < n; i ++) {
            f[i][0] = f[i - 1][0] + grid[i][0];
        }
        
        //第一列,只能从上面来
        for (int j = 1; j < m; j ++) {
            f[0][j] = f[0][j - 1] + grid[0][j];
        }

        //其他的则可以从左边或者上面来
        for (int i = 1; i < n; i ++) 
            for (int j = 1; j < m; j ++) {
                f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
            }
        
        return f[n - 1][m - 1];
    }
};

九、爬楼梯

1. 题目描述

在这里插入图片描述


2. 思路分析

定义数组 f [ i ] f[i] f[i] 表示上 i i i 级台阶的方案数,则枚举最后一步是上1级台阶,还是上2级台阶,所以有:f[i] = f[i ? 1] + f[i ? 2]


3. 代码实现

class Solution {
public:
    int climbStairs(int n) {
        vector<int> f(n + 1);
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i <= n; i ++) 
            f[i] = f[i - 1] + f[i - 2];
        
        return f[n];
    }
};

十、编辑距离

1. 题目描述

在这里插入图片描述


2. 思路分析

动态规划
状态表示: f[i][j] 表示 w o r d 1 word1 word1 i i i 位置转化成 w o r d 2 word2 word2 j j j 位置需要的最小步数。

状态转移方程:

  • word1[i] == word2[j]f[i][j] = f[i - 1][j - 1];
  • word1[i] != word2[j][i][j] = min(f[i - 1][j - 1] + 1, min(f[i][j - 1] + 1, f[i - 1][j] + 1));

其中,f[i - 1][j - 1] 表示替换操作, f[i - 1][j] 表示删除操作,f[i][j - 1] 表示插入操作。

注意:针对第一行和第一列到单独考虑,我们引入 '' 如下图所示:
在这里插入图片描述


3. 代码实现

class Solution {
public:
    int minDistance(string a, string b) {
        int n = a.size(), m = b.size();
        a = ' ' + a, b = ' ' + b;
        vector<vector<int>> f(n + 1, vector<int>(m + 1));

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

        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++) {
                if (a[i] == b[j]) 
                    f[i][j] = f[i - 1][j - 1];
                else
                    f[i][j] = min(f[i - 1][j - 1] + 1, min(f[i][j - 1] + 1, f[i - 1][j] + 1));
            }
        return f[n][m];
    }
};

?
非常感谢您阅读到这里,如果这篇文章对您有帮助,希望能留下您的点赞👍 关注💖 分享👥 留言💬thanks!!!

文章来源:https://blog.csdn.net/m0_52691962/article/details/135164754
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。