随想录专题
代码随想录冲冲冲 Day39 动态规划Part7
198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d
代码随想录训练营day37|52. 携带研究材料，518.零钱兑换II，377. 组合总和 Ⅳ，70. 爬楼梯
52. 携带研究材料 这是一个完全背包问题，就是每个物品可以无限放。 在一维滚动数组的时候规定了遍历顺序是要从后往前的，就是因为不能多次放物体。 所以这里能多次放物体只需要把遍历顺序改改就好了 # include<iostream># include<vector>using namespace std;int main(){int n,m;cin>>n>>m;std::vector<i
代码随想录打卡Day25
今天一整天都在教研室做实验，没时间刷题，就做了一题，剩下的明天补 491.递增子序列 这道题目和之前的子集问题很像，但是有一点要注意的，这个输入的数组不能进行排序，所以就不能沿用之前的去重逻辑，这道题要去重还是得借助额外的变量来维护元素使用情况，但是这题的used为集合，且不能为全局变量，只能为树层遍历前定义的一个局部变量，除了这个改动以外，其他地方都是高度相似的。 class Soluti
代码随想录刷题day25丨491.递增子序列 ，46.全排列 ，47.全排列 II
代码随想录刷题day25丨491.递增子序列 ，46.全排列 ，47.全排列 II 1.题目 1.1递增子序列 题目链接：491. 非递减子序列 - 力扣（LeetCode） 视频讲解：回溯算法精讲，树层去重与树枝去重 | LeetCode：491.递增子序列_哔哩哔哩_bilibili 文档讲解：https://programmercarl.com/0491.%E9%80%92%E
代码随想录算法训练营Day37|完全背包问题、518.零钱兑换II、377. 组合总和 Ⅳ、70. 爬楼梯（进阶版）
完全背包问题 和01背包最大区别就是一个物品可以重复放多次，因此遍历空间时可以从前往后。 import java.util.*;public class Main{public static void main (String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt
代码随想录刷题day24丨93.复原IP地址 ，78.子集 ， 90.子集II
代码随想录刷题day24丨93.复原IP地址 ，78.子集 ， 90.子集II 1.题目 1.1复原IP地址 题目链接：93. 复原 IP 地址 - 力扣（LeetCode） 视频讲解：回溯算法如何分割字符串并判断是合法IP？| LeetCode：93.复原IP地址_哔哩哔哩_bilibili 文档讲解：https://programmercarl.com/0093.%E5%A4%8
【代码随想录训练营第42期 续Day52打卡 - 图论Part3 - 卡码网 103. 水流问题 104. 建造最大岛屿
目录 一、做题心得 二、题目与题解 题目一：卡码网 103. 水流问题 题目链接 题解：DFS 题目二：卡码网 104. 建造最大岛屿 题目链接 题解：DFS 三、小结 一、做题心得 也是成功补上昨天的打卡了。 这里继续图论章节，还是选择使用 DFS 来解决这类搜索问题（单纯因为我更熟悉 DFS 一点），今天补卡的是水流问题和岛屿问题。个人感觉这一章节题对于刚
代码随想录八股训练营第三十七天| C++
前言 一、map和unorder_map的区别？ 1.1.内部实现: 1.2.排序: 1.3.查找效率： 1.4.内存使用: 1.5.迭代器: 1.6.键的唯一性： 1.7.使用场景: 二、C++11 新特性有哪些？ 2.1.std::map: 总结 前言 在现代软件开发中，选择合适的数据结构如 C++ 标准库中的 std::map 和 std::unordered_
代码随想录 -- 二叉树 -- 平衡二叉树
110. 平衡二叉树 - 力扣（LeetCode） 思路：仍然是递归调用 1. 定义一个递归函数 count 用来计算二叉树的层数 2. isBalanced 函数：如果传入根节点为空返回真；如果根节点 | 左子树的层数 - 右子树的层数 | 大于1，返回假；最后返回根节点左子树、右子树是否是平衡二叉树。 class Solution(object):def count(self,root
代码随想录Day 36|滑铁卢了,leetcode题目：1049.最后一块石头的重量、494.目标和、474.一和零
提示：DDU，供自己复习使用。欢迎大家前来讨论~ 文章目录 动态规划一、题目题目一：1049.最后一块石头的重量II解题思路： 题目二：494.目标和动态规划 （二维dp数组）#动态规划 （一维dp数组） 题目三： 474.一和零解题思路： 总结 动态规划 有点难了，之前差的有点多，找时间补 一、题目 题目一：1049.最后一块石头的重量II leetcode题目链接
图论篇--代码随想录算法训练营第五十二天打卡| 101. 孤岛的总面积，102. 沉没孤岛，103. 水流问题，104.建造最大岛屿
101. 孤岛的总面积 题目链接：101. 孤岛的总面积 题目描述： 给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。 现在你需要计算所有孤岛的总面积，岛屿面积的计算方式为组成岛屿的陆地的总数。 解题思路： 从周边找到陆地，然后通过 dfs或者bfs 将
代码随想录八股训练营第三十六天| C++
前言 一、push_back()和emplace_back()的区别？ 1.1.push_back(): 1.2.emplace_back(): 1.3.区别总结： 1.4.使用场景: 二、map dequeu list 的实现原理？ 2.1.std::map: 2.2. std::deque: 2.3. std::list: 2.4. 区别总结: 总结 前言 在C+
代码随想录冲冲冲 Day38 动态规划Part6
322. 零钱兑换 最大最小值的问题 这样的问题不需要考虑遍历顺序 但是这道题需要注意的是红线的两个部分 这两个部分的意思是一样的 首先dp[j]代表的是amount为j的时候 最小的硬币数量 如果说任何的dp[j]为INT_MAX也就是初始值，这就说明这哥mount的数量没有得到或者得不到 那么就不能继续更新了加入j =5 有可能 j=4根本得不到 那么由dp[4] +1就不合理了
代码随想录：322. 零钱兑换
322. 零钱兑换 class Solution {public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(10005,INT_MAX);//由于后面要取最小值，所以初始大一些dp[0]=0;//总金额为0个数一定为0for(int i=0;i<coins.size();i++){for(int j=coins
【代码随想录|回溯part04】
代码随想录|回溯part04 1、46.全排列2、47.全排列 II3.问题 总结 python 1、46.全排列 46.全排列 class Solution:def permute(self, nums):result = []self.backtracking
代码随想录算法训练营第十九天| 回溯理论、77. 组合、216. 组合总和Ⅲ、17. 电话号码的字母组合
今日内容 回溯的理论基础leetcode. 77 组合leetcode. 216 组合总和Ⅲleetcode. 17 电话号码的字母组合 回溯理论基础 回溯法也叫回溯搜索法，它是一种搜索的方式，而且只要有递归就会有回溯，回溯就是递归的副产品。 回溯说到底并不是什么非常高深的搜索方式，本质上仍然是穷举，穷举所有可能然后选择出我们要的答案。剪枝会使回溯法更加高效一点，但改变不了回溯本质就是穷举
【代码随想录|贪心part04以后——重叠区间】
代代码随想录|贪心part04以后——重叠区间 一、part041、452.用最少数量的箭引爆气球2、435. 无重叠区间2、763.划分字母区间3、56. 合并区间4、738.单调递增的数字 总结 python 一、part04 1、452.用最少数量的箭引爆气球 452. 用最少数量的箭引爆气球 class Solution:def findMinArrowShot
代码随想录 刷题记录-28 图论 (5)最短路径
一、dijkstra（朴素版）精讲 47. 参加科学大会 思路 本题就是求最短路，最短路是图论中的经典问题即：给出一个有向图，一个起点，一个终点，问起点到终点的最短路径。 接下来讲解最短路算法中的 dijkstra 算法。 dijkstra算法：在有权图（权值非负数）中求从起点到其他节点的最短路径算法。 需要注意两点： dijkstra 算法可以同时求 起点到所有节点的最短路径权值不
代码随想录算法训练营Day03 | 链表理论基础、203.移除链表元素 、707.设计链表、206.反转链表
提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档 文章目录 链表理论基础203.移除链表元素思路与重点 707.设计链表思路与重点 206.反转链表思路与重点 链表理论基础 C/C++的定义链表节点方式： // 单链表struct ListNode {int val; // 节点上存储的元素ListNode *next; // 指向下一个节点的指
图论篇--代码随想录算法训练营第五十一天打卡| 99. 岛屿数量（深搜版），99. 岛屿数量（广搜版），100. 岛屿的最大面积
99. 岛屿数量（深搜版） 题目链接：99. 岛屿数量 题目描述： 给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。 解题思路： 1、每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 2、遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都
代码随想录第八天|151.翻转字符串里的单词 卡码网：55.右旋转字符串 28. 实现 strStr() 459.重复的子字符串
反转字符串的单词 思路：刷过稍微忘记 class Solution {public://去除空格string remove(string s){//使用快慢指针int slow=0;int i=0;for(;i<s.size();i++){if(s[i]!=' '){if(slow!=0){s[slow++]=' ';}while(s[i]!=' '&&i<s.size()){s[slow+
代码随想录刷题day23丨39. 组合总和，40.组合总和II， 131.分割回文串
代码随想录刷题day23丨39. 组合总和，40.组合总和II， 131.分割回文串 1.题目 1.1组合总和 题目链接：39. 组合总和 - 力扣（LeetCode） 视频讲解：带你学透回溯算法-组合总和（对应「leetcode」力扣题目：39.组合总和）| 回溯法精讲！_哔哩哔哩_bilibili 文档讲解：https://programmercarl.com/0039.%E7%
代码随想录：343. 整数拆分
343. 整数拆分 class Solution {public:int integerBreak(int n) {int dp[100]={0};//拆分i的最大乘积为dp[i]dp[1]=1;//初始化，主要是为了dp[2]初始for(int i=2;i<=n;i++){for(int j=1;j<i;j++){ dp[i]=max(dp[i],max(j,dp[j])*ma
代码随想录算法训练营第五十天 | 98. 所有可达路径
目录 98. 所有可达路径 思路 图的存储 邻接矩阵 邻接表 深度优先搜索 1.确认递归函数，参数 2.确认终止条件 3.处理目前搜索节点出发的路径 方法一： 邻接矩阵写法 方法二：邻接表写法 98. 所有可达路径 题目链接：卡码网题目链接（ACM模式） 文章讲解：代码随想录 【题目描述】 给定一个有 n 个节点的有向无环图，节点编
图论篇--代码随想录算法训练营第五十天打卡| 深度优先搜索理论基础，98. 所有可达路径，广度优先搜索理论基础
深度优先搜索理论基础 DFS模板： void dfs(参数) {if (终止条件) {存放结果;return;}for (选择：本节点所连接的其他节点) {处理节点;dfs(图，选择的节点); // 递归回溯，撤销处理结果}} 98. 所有可达路径 题目链接：98. 所有可达路径 题目描述： 给定一个有 n 个节点的有向无环图，节点编号从 1 到 n。请编写一个函数，找出并返回所
【代码随想录训练营第42期 Day50打卡 - dfs入门 - 卡码网 98. 所有可达路径
目录 一、dfs基础 二、模板题 题目：98. 所有可达路径 题目链接 题解：dfs+邻接矩阵 三、小结 一、dfs基础 dfs是按照一个方向搜索到尽头再搜索其他方向。怎样实现对其他方向的搜索呢？我们可以通过回溯，撤销最后一步，再选择其他路线。 -- 回溯过程某种程度上也是递归的体现。所以，实现 dfs 的一个关键就是递归。 之前有了回溯的基础，其实可以发现回溯算法