一刷专题
一刷代码随想录（图论9）
dijkstra（堆优化版）精讲 题目即小明参会题 解法：若遇到稀疏图可以考虑处理边而非处理节点，使用邻接表来存储边，使用小顶堆对边进行排序，直接取出最小的边即可，然后从当前点出发遍历剩余数组，更新min数组，在将更新后的数组与路径长度加入小顶堆，相当于用一条新边代替了原来的边，并在小顶堆里自动排序得到最短路径 #include <iostream>#include <vector>#i
一刷代码随想录（图论7）
题目引入： 题目描述： 在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。 不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将 所有岛屿联通起来。 给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。 输入描述： 第一行包含两个整数V
一刷代码随想录（图论4）
110. 字符串接龙 题意： 题目描述 字典 strList 中从字符串 beginStr 和 endStr 的转换序列是一个按下述规格形成的序列： 序列中第一个字符串是 beginStr。 序列中最后一个字符串是 endStr。 每次转换只能改变一个字符。 转换过程中的中间字符串必须是字典 strList 中的字符串。 给你两个字符串 beginStr 和 endStr 和一
【一刷《剑指Offer》】面试题 28：字符串的排列
牛客对应题目链接：字符串的排列_牛客题霸_牛客网 (nowcoder.com) 力扣对应题目链接：LCR 157. 套餐内商品的排列顺序 - 力扣（LeetCode） 核心考点 ：全排列问题， DFS。 一、《剑指Offer》对应内容 二、分析题目 全排列问题，可以看做如下多叉树形态： 很明显，我们想要得到合适的排列组合，一定是深度优
【一刷《剑指Offer》】面试题 29：数组中出现次数超过一半的数字
力扣对应题目链接：169. 多数元素 - 力扣（LeetCode） 牛客对应题目链接：数组中出现次数超过一半的数字_牛客题霸_牛客网 (nowcoder.com) 核心考点 ： 数组使用，简单算法的设计。 一、《剑指Offer》对应内容 二、分析题目 这里找到的题目链接所对应的数据都满足数组是非空的，并且给定的数组总是存在多数元素。所
【一刷《剑指Offer》】面试题 30：最小的 k 个数
牛客对应题目链接：最小的K个数_牛客题霸_牛客网 (nowcoder.com) 力扣对应题目链接：LCR 159. 库存管理 III - 力扣（LeetCode） 核心考点 ： topK 问题。 一、《剑指Offer》内容 二、分析题目 1、排序（O(NlogN)） 直对原数组从小到大排序后，取出前 k 个数即可。 2
【一刷《剑指Offer》】面试题 31：连续子数组的最大和
牛客对应题目链接：连续子数组最大和_牛客题霸_牛客网 (nowcoder.com) 力扣对应题目链接：53. 最大子数组和 - 力扣（LeetCode） 核心考点 ：简单动归问题。 一、《剑指Offer》对应内容 二、分析题目 1、贪心 从前往后迭代，一个个数字加过去，如果 sum<res，则重新开始找子序串。 2、动态规
【一刷《剑指Offer》】面试题 25：二叉树中和为某一值的路径
力扣对应题目链接：113. 路径总和 II - 力扣（LeetCode） 核心考点 ：简单回溯法的使用。 一、《剑指Offer》对应内容 二、分析题目 这是一个典型的 DFS 回溯的算法，回溯法本质是一个基于 DFS 的穷举的过程。 先添加值（待选结果）在判定现有结果是否满足条件（待选结果是否符合条件，是的话就添加结果集）DFS（深
代码随想录|跟着训练营一刷结束
今天是在代码随想录训练营的第63天， 在决定参加训练营的那天我就下定了决心， 一定要坚持打卡 You can do it! 而今天便是我达成目标全勤打卡结束一刷的日子。 开始 参加训练营其实对于我这个大三学生来说还是有点贵的，大几百块钱。所以交钱那一刻我还是挺心痛的。接触代码随想录是我大二的时候，在一个学长的推荐下知道的，然后看了一下，那个时候我还没学完数据结构，几乎不怎么看得懂。然后去
【力扣一刷】代码随想录day44（动态规划part6 - 背包问题专题： 完全背包理论基础、卡码网52、518. 零钱兑换 II、377. 组合总和 Ⅳ ）
【完全背包理论基础】 与01背包问题的区别： 1、物品的可取次数：完全背包和01背包问题唯一不同的地方就是，01背包问题的每种物品只能取0次或1次，而完全背包问题的每种物品可以取无限次。 2、遍历滚动数组的顺序：01背包问题每件物品最多取一次，前面取了后面就不能取，所以要逆向遍历书包容量。而完全背包问题可以取无限次，因此是正向遍历，即使前面的书包容量放过物品 i 也可以。遍历第 i 个物品
【一刷《剑指Offer》】面试题 13：在 O(1) 时间删除链表结点
力扣对应题目链接：LCR 136. 删除链表的节点 - 力扣（LeetCode） 一、《剑指 Offer》内容 二、分析题目 1、信息交换法 《剑指Offer》上给的这段代码，我把它称为信息交换法。 这道题其实考察了我们对链表的操作和时间复杂度的理解。 一般来讲，正常的解法时间复杂度都是 O(N)，因为我们要找到待删除节点，不得不牺牲 O(N) 的时间复杂
【一刷《剑指Offer》】面试题 11：数值的整数次方
力扣对应题目链接：50. Pow(x, n) - 力扣（LeetCode） 牛客对应题目链接：数值的整数次方_牛客题霸_牛客网 (nowcoder.com) 一、《剑指Offer》内容 二、分析题目 【快速幂 + 递归】 当指数 n 为负数时，我们可以计算 x^(−n) 再取倒数得到结果，因此我们只需要考虑 n 为自然数的情况。 假设我们需要
【一刷《剑指Offer》】面试题 9：斐波那契数列（扩展：青蛙跳台阶、矩阵覆盖）
力扣对应链接：LCR 126. 斐波那契数 - 力扣（LeetCode） 牛客对应链接：斐波那契数列_牛客题霸_牛客网 (nowcoder.com) 核心考点：空间复杂度，fib 理解，剪枝重复计算。 一、《剑指Offer》内容 二、分析问题 斐波那契数列是：0 1 1 2 3 5 8 13 21 ... 解题方式很多，有递归方式，也
Day22.一刷数据结构算法(C语言版) 216组合总和III；17电话号码的字母组合
一、216组合总和III 如果把昨天的组合问题理解了，本题就容易一些了。 题目链接：组合总和III 文章讲解：代码随想录 视频讲解：和组合问题有啥区别？回溯算法如何剪枝？| 216.组合总和III 1.思路分析 相对于77. 组合，无非就是多了一个限制，本题是要找到和为n的k个数的组合，而整个集合
【一刷《剑指Offer》】面试题 7：用两个栈实现队列
力扣对应题目链接：232. 用栈实现队列 - 力扣（LeetCode） 一、《剑指 Offer》内容 二、分析题目 这道题就是在考察对栈和队列的理解，需要我们熟悉栈（先入后出）和队列（先入先出）的特性。详情可见： 【数据结构】栈（Stack）的实现 -- 详解_栈的程序功能及算法实现-CSDN博客 【数据结构】队列（Queue）的实现 -- 详解_队列实现-
Day17.一刷数据结构算法(C语言版) 654最大二叉树；617合并二叉树；700二叉搜索树中的搜索；98验证二叉搜索树
又是破防的一天...... 一.654最大二叉树 又是构造二叉树，昨天大家刚刚做完 中序后序确定二叉树，今天做这个 应该会容易一些， 先看视频，好好体会一下 为什么构造二叉树都是 前序遍历 题目链接：最大二叉树 文章讲解：代码随想录 视频讲解：又是构造二叉树，又有很多坑！| LeetCode：654.最
【一刷《剑指Offer》】面试题 5：从尾到头打印链表
力扣对应链接：LCR 123. 图书整理 I - 力扣（LeetCode） 牛客对应连接：从尾到头打印链表_牛客题霸_牛客网 核心考点 ：链表相关，多结构混合使用，递归。 一、《剑指Offer》内容 二、分析问题 这道题整体的解决思路很多，可以使用 stack，也可以将数据保存数组，再逆序数组，还可以递归。 三、代码 1、方法一（
代码随想录系统性一刷总结
代码随想录系统性一刷总结 数组 指针思想很重要 day01 二分查找+移除元素 day02 数组平方+长度最小子数组+螺旋矩阵II 链表 链表结点的增删改查，头结点的运用，灵活运用指针 day03 移除链表元素+设计链表+翻转链表 day04 交换结点+删除结点+链表相交+环形列表 哈希表 灵活使用hashset，几数之和指针再次出马，理解去重和剪枝操作 day
代码随想录刷题｜一刷总结
文章目录 一刷总结一、 成果汇报1、leetcode提交记录2、博客更新记录 二、 经验总结2.1.刷过的所有题型2.1.1、数组2.1.2、链表2.1.3、哈希表2.1.4、字符串2.1.5、栈与队列2.1.6、二叉树2.1.7、回溯2.1.8、贪心2.1.9、动态规划2.1.10、单调栈 2.2、做得好的2.3、做得不好的2.4、其他的碎碎念 三、 为什么要刷题3.1、面向大厂 四、 未
【力扣一刷】代码随想录day42（动态规划part4 - 背包问题专题：卡码网46.携带研究材料、416.分割等和子集 ）
目录 【卡码网46. 携带研究材料】 方法一 01背包问题 - 二维数组 方法二 01背包问题 - 一维数组 【416. 分割等和子集】 方法一 暴力回溯 -> 超时 方法二 动态规划（01背包问题） 【卡码网46. 携带研究材料】 方法一 01背包问题 - 二维数组 思路： 1、确定 dp[i][j] 的含义 dp[i][j] 是指从 0 ~ i 件物品中选部分物
【一刷《剑指Offer》】面试题 3：二维数组中的查找
力扣对应题目链接：240. 搜索二维矩阵 II - 力扣（LeetCode） 核心考点：数组相关，特性观察，时间复杂度把握。 一、《剑指Offer》对应内容 二、分析题目 正常查找的过程本质就是排除的过程，谁排除的效率更高，谁对应查找的效率也就更高。如果双循环查找，本质是一次排除一个，效率过低。但采取从右上角 / 左下角进行比较，这样就
【力扣一刷】代码随想录day39（动态规划part2：62.不同路径、63. 不同路径 II ）
目录 【62.不同路径】中等题 方法一 只初始化start位置 方法二 初始化第一行和第一列 【63. 不同路径 II】中等题 【62.不同路径】中等题 思路： 1、前提：只能向右或向下移动一步，当前格子只能由左边（向右移）或上边（向下移）到达 2、递推关系：到达当前格子的路径数 = 到达左边格子的路径数 + 到达上边格子的路径数 方法一 只初始化start位置 思路：
【力扣一刷】代码随想录day38（动态规划part1：509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼）
目录 【动态规划理论基础】 【509. 斐波那契数】简单题 方法一 用额外的数组存储每个状态 方法二 用2个遍历存储前两个状态（减小空间复杂度） 【70. 爬楼梯】简单题 【746. 使用最小花费爬楼】简单题 【动态规划理论基础】 1、定义：英文为Dynamic Programming，简称DP 2、步骤： 确定变量 f(i) 的含义确定递推公式：如 f(i) 和 f
【力扣一刷】代码随想录day35（贪心算法part4：860.柠檬水找零、406.根据身高重建队列、452. 用最少数量的箭引爆气球 ）
目录 【860.柠檬水找零】简单题(很简单) 【406.根据身高重建队列】中等题（掌握思路后简单） 【452. 用最少数量的箭引爆气球】中等题 【860.柠檬水找零】简单题(很简单) 思路： 5元的直接收，不需要找钱10元的只需要找5元20元的优先找10元，没有10元再全部找5元 class Solution {public boolean lemonadeChange(int[
【力扣一刷】代码随想录day32（贪心算法part2：122.买卖股票的最佳时机II、55. 跳跃游戏、45.跳跃游戏II ）
目录 【122.买卖股票的最佳时机II】中等题 方法一 贪心算法 方法二 动态规划 【55. 跳跃游戏】中等题 【尝试】 递归 （超时） 方法 贪心算法 【45.跳跃游戏II】中等题 方法 贪心算法 【122.买卖股票的最佳时机II】中等题（偏简单） 方法一 贪心算法 思路： 1、局部最优：截止到当天能赚到的最大利润 2、全局最优：截止到最后一天能赚到的最大利润就是全局
【力扣一刷】代码随想录day29（回溯算法part5：491.递增子序列、46.全排列、47.全排列 II）
目录 【491.递增子序列】中等题 【46.全排列】中等题 【47.全排列 II】中等题 【491.递增子序列】中等题 思路： 1、处理当前节点 如果到当前节点的路径长度为1或者为0，直接遍历访问子节点即可如果到当前节点的路径长度大于/等于2，则判断是否递增 如果递增，则记录路径如果不是递增，则不记录路径，不访问子节点，直接返回 2、遍历子节点 在for循环遍历前，定义Set对