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

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

文章目录

  • 一、全排列
    • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 二、旋转图像
    • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 三、字母异位词分组
    • 1.题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 四、最大子数组和
    • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 五、跳跃游戏
    • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 六、合并区间
    • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 七、不同路径
    • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 八、最小路径和
    • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 九、爬楼梯
    • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 十、编辑距离
    • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现

一、全排列

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)),0≤k<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！！！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/264931.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

职场利器-软考高级、PMP、CKA/CKS/CKAD备考

职场利器-软考高级、PMP、CKA/CKS/CKAD备考

1、【软考高级】信息系统项目管理师 全国计算机技术与软件专业技术资格(水平)考试网上报名平台http://bm.ruankao.org.cn/sign/welcome 模拟作答系统230747 第一次裸考 考试成绩查询 三科均未通过 软考考试多少分通过? ​​​​​​​ 软考高级&#xff0c;它的考试科目是《…
阅读更多...
黄鼠狼目标检测数据集VOC+YOLO格式400张

黄鼠狼目标检测数据集VOC+YOLO格式400张

黄鼠狼是一种小型哺乳动物&#xff0c;通常分布在亚洲和欧洲的森林和草原地区。它们的身体长度约为30-50厘米&#xff0c;体重约为0.5-1.5千克。黄鼠狼的身体呈灰黄色&#xff0c;背部有黑色条纹&#xff0c;尾巴短而毛茸茸的。 黄鼠狼是一种夜行性动物&#xff0c;主要以小型…
阅读更多...
网络通信--深入理解网络和TCP / IP协议

网络通信--深入理解网络和TCP / IP协议

计算机网络体系结构 TCP/IP协议族 TCP / IP 网络传输中的数据术语 网络通信中的地址和端口 window端查看IP地址和MAC地址&#xff1a;ipconfig -all MAC层地址是在数据链路层的&#xff1b;IP工作在网络层的 MAC是48个字节&#xff0c;IP是32个字节 在子网&#xff08;局域…
阅读更多...
TIA博途Wincc_通过VBS脚本实现电机风扇或水泵旋转动画的具体方法

TIA博途Wincc_通过VBS脚本实现电机风扇或水泵旋转动画的具体方法

TIA博途Wincc_通过VBS脚本实现电机风扇或水泵旋转动画的具体方法 前面和大家介绍了通过在PLC中编程，结合HMI的图形IO域实现电机风扇或水泵旋转动画的具体方法，详细内容可参考以下链接： TIA博途Wincc中制作电机风扇或水泵旋转动画的具体方法示例 本次和大家分享通过VBS脚本实…
阅读更多...
智能图像编辑软件Luminar Neo mac提供多种调整和滤镜选项

智能图像编辑软件Luminar Neo mac提供多种调整和滤镜选项

Luminar Neo mac是一款由Skylum公司开发的AI技术图像编辑软件&#xff0c;旨在为摄影师和视觉艺术家提供创意图像编辑解决方案。Luminar Neo拥有强大的AI技术和丰富的后期处理工具&#xff0c;可帮助用户快速轻松地实现从基本到高级的图像编辑需求。 Luminar Neo提供了多种调整…
阅读更多...
什么是Vue.js ? Vue相关介绍

什么是Vue.js ? Vue相关介绍

vue介绍 vue官网&#xff1a;Vue.js (vuejs.org) a) Vue.js目前最流行的一个前端框架&#xff0c;三大主流前端框架之一。 b) AngularJS是Vue早期开发的灵感来源。然而&#xff0c;AngularJS 中存在的许多问题&#xff0c;在 Vue 中已经得到解决。 c) Vue.js是一套构…
阅读更多...
idea 注入mapper报错报红的几种解决方案

idea 注入mapper报错报红的几种解决方案

文章目录 前言方法1&#xff1a;为 Autowired 注解设置required false方法2&#xff1a;用 Resource 替换 Autowired方法3&#xff1a;在Mapper接口上加上Repository注解方法4&#xff1a;用Lombok方法5&#xff1a;把IDEA的警告关闭掉方法6&#xff1a;不用管他 前言 相信大…
阅读更多...
Linux系统LVS+Keepalived群集

Linux系统LVS+Keepalived群集

目录 一、概述 &#xff08;一&#xff09;群集特性 1.负载均衡 2.健康检查&#xff08;探针&#xff09; 3.故障转移 &#xff08;二&#xff09;Keepalived 1.作用 &#xff08;1&#xff09;支持故障自动转移 &#xff08;2&#xff09;支持节点健康状态检…
阅读更多...
WebGL开发三维解剖学应用

WebGL开发三维解剖学应用

开发基于 WebGL 的三维解剖学应用通常涉及以下步骤。这些步骤包括创建三维模型、整合交互性、优化性能等&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xff0c;欢迎交流合作。 1.三维模型创建&#xff1a; 首先&#xff0…
阅读更多...
Pytorch项目，肺癌检测项目之二

Pytorch项目，肺癌检测项目之二

diameter_dict{} with open(/xunlian/annotations.csv &#xff0c;‘r’) as f: for row in list(csv.reader(f)[1:]): series_uid row[0] annotationCenter_xyz tuple([float(x) for x in row[1:4]]) annotationDiameter_mm float(row[4]) diameter_dict.setdefault(seri…
阅读更多...
【GIS前言技术】甘肃积石山6.2级地震烈度图

【GIS前言技术】甘肃积石山6.2级地震烈度图

12月18日23时59分&#xff0c;甘肃临夏州积石山县发生6.2级地震。地震发生后&#xff0c;应急管理部组织中国地震局派出地震现场工作队&#xff0c;依照《地震现场工作&#xff1a;调查规范》&#xff08;GB/T 18208.3-2011&#xff09;、《中国地震烈度表》(GB/T 17742-2020)&…
阅读更多...
josef约瑟 电流继电器 RL-D1 电压AC220V 整定范围0-9.99AAC

josef约瑟 电流继电器 RL-D1 电压AC220V 整定范围0-9.99AAC

系列型号 RL-D1型电流继电器&#xff1b; RL-D2型电流继电器&#xff1b; 基本参数 RL-D系列电流继电器用于发电机、变压器和输电线的过负荷和短路保护装置中作为启动元件。本继电器为集成电路型继电器&#xff0c;精度高、功耗小、动作时间快&#xff0c; 返回系数高、整定…
阅读更多...
0.618算法和基于Armijo准则的线搜索回退法

0.618算法和基于Armijo准则的线搜索回退法

0.618代码如下&#xff1a; import math # 定义函数h(t) t^3 - 2t 1 def h(t): return t**3 - 2*t 1 # 0.618算法 def golden_section_search(a, b, epsilon): ratio 0.618 while (b - a) > epsilon: x1 b - ratio * (b - a) x2 a ratio * (b - a) h_…
阅读更多...
九：爬虫-MongoDB基础

九：爬虫-MongoDB基础

MongoDB介绍 MongoDB是一个介于关系数据库和非关系数据库之间的产品&#xff0c;是非关系数据库当中功能最丰富&#xff0c;最像关系数据库的。它支持的数据结构非常松散&#xff0c;因此可以存储比较复杂的数据类型。Mongo最大的特点是它支持的查询语言非常强大&#xff0c;其…
阅读更多...
Java设计模式-原型模式

Java设计模式-原型模式

目录 一、克隆羊问题 二、传统方式解决 三、基本介绍 四、浅拷贝和深拷贝 &#xff08;一&#xff09;浅拷贝介绍 &#xff08;二&#xff09;深拷贝 五、原型模式深拷贝 &#xff08;一&#xff09;重写clone方法 &#xff08;二&#xff09;对象序列化 六、注意事项…
阅读更多...
法线贴图实现地形模型皱褶、凹凸不平的纹理效果

法线贴图实现地形模型皱褶、凹凸不平的纹理效果

在线工具推荐&#xff1a; 3D数字孪生场景编辑器 - GLTF/GLB材质纹理编辑器 - 3D模型在线转换 - Three.js AI自动纹理开发包 - YOLO 虚幻合成数据生成器 - 三维模型预览图生成器 - 3D模型语义搜索引擎 法线贴图在3D建模中扮演着重要的角色&#xff0c;它通过模拟表面的微…
阅读更多...
es倒排索引以及分词

es倒排索引以及分词

单词词典(Term Dictionary)是倒排索引的重要组成记录所有文档的单词&#xff0c;一般都比较大 记录单词到倒排排列表的关联信息 倒排列表(Posting List)记录了单词对应的文档集合&#xff0c;由倒排索项( Posting )组成倒排索项( Posting)主要包含如下信息: 文档Id&#xff0c…
阅读更多...
前端基础location的使用

前端基础location的使用

概念 获取当前页面的地址信息&#xff0c;还可以修改某些属性&#xff0c;实现页面跳转和刷新等。 样例展示 window.location 含义.originURL 基础地址&#xff0c;包括协议名、域名和端口号.protocol协议 (http: 或 https:).host域名端口号.hostname域名.port端口号.pathname路…
阅读更多...
postMessage——不同源的网页直接通过localStorage/sessionStorage/Cookies——技能提升

postMessage——不同源的网页直接通过localStorage/sessionStorage/Cookies——技能提升

最近遇到一个问题&#xff0c;就是不同源的两个网页之间进行localstorage或者cookie的共享。 上周其实遇到过一次&#xff0c;觉得麻烦就让后端换了种方式处理了&#xff0c;昨天又遇到了同样的问题。 使用场景 比如从网页A通过iframe跳转到网页B&#xff0c;而且这两个网页…
阅读更多...
[C语言]程序练习（一）

[C语言]程序练习（一）

你好&#xff0c;这里是争做图书馆扫地僧的小白。 个人主页&#xff1a;争做图书馆扫地僧的小白_-CSDN博客 目标&#xff1a;希望通过学习技术&#xff0c;期待着改变世界。 目录 前言 一、常量练习 &#xff08;一&#xff09;整型常量 &#xff08;二&#xff09;浮点型常…
阅读更多...
最新文章

Copyright @ 2022~2023