林重笑

时长：6h 链表理论基础链表：一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域，一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。 链表类型单链表单链表中的指针域只能指向节点的下一个节点 双链表每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点 既可以向前查询，也可以向后查询 循环链表链表首尾相连 可解决约瑟夫环问题 【故事讲述了一群罗马士兵在被围困的要塞中，面临被敌军俘虏的命运。为了避免被俘，他们决定集体自杀。但是，他们希望通过某种方式来决定自己的死亡顺序，以避免出现任何争斗。 于是，他们决定围成一个圆圈，从某个固定的位置开始，按照一定的规则进行计数，每计到一个特定的数字，对应的士兵就会被处决，直到只剩下最后一个人幸存。 这个问题的数学形式可以描述为：给定n个人围成一个圆圈，并从编号为1的人开始报数，每次数到第m个人，就将该人处决。然后从下一个人重新开始报数，直到只剩下最后一个人。】 链表的存储方式数组在内存中是连续分布的，但是链表在内存中不是连续分布的。 链表的定义 Java定义 123456789101 ...

997.有序数组的平方文章：4. 有序数组的平方 题目：977. 有序数组的平方 【思路】 双指针 Java 12345678910111213141516class Solution { public int[] sortedSquares(int[] nums) { int[]res = new int[nums.length]; int k =nums.length-1; for(int i = 0,j=nums.length-1;i <= j;){ if(nums[i]*nums[i] > nums[j] * nums[j]){ res[k--] = nums[i] *nums[i]; i++; }else{ res[k--] = nums[j] * nums[j]; j--; ...

数组理论基础数组是存放在连续内存空间上的相同类型数据的集合。 数组下标都是从0开始的 数组内存空间的地址是连续的 数组的元素不能删，只能覆盖 704.二分查找文章：2. 二分查找 题目：704. 二分查找 【思路】 左闭右闭区间 Go 12345678910111213141516171819func search(nums []int, target int) int { //左闭右闭区间 left,right := 0,len(nums)-1 //!! //(left + right) / 2 = left/2 + right/2 //left + ((right - left)/2) //left + right/2 - left/2 = right/2 + left/2 for ;left <= right ; { mid := left + (right - left)/2 if nums[mid] == target{ return mid ...

回家躺的太舒服了的说 -><- 300.最长递增子序列文章：41. 最长上升子序列 题目：300. 最长递增子序列 【思路】 子序列：由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序 1.确定dp及其下标的定义 dp[i]：表示i之前包括 i 的以nums[i]结尾的最长递增子序列的长度 2.状态转移方程 位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列+1的最大值 =》 if(nums[i] > nums[i-1]) dp[i] = max(dp[i],dp[j+1]) (j=0; j< i ;j++) 不是要dp[i]与dp[j] + 1进行比较，而是要去dp[j] +1 的最大值 3.dp[i] 的初始化 每一个i，对应的dp[i] 的起始大小都至少为1 4.确认遍历顺序 每个dp[i] 都是从0到i-1各个位置的最长递增子序列推导而来的，那么遍历i一定是从前向后遍历 Java实现 1234567891011121314151617class Solution { ...

309.最佳买卖股票时机含冷冻期文章：37. 最佳买卖股票时机含冷冻期 题目：309. 买卖股票的最佳时机含冷冻期 【思路】 在昨天的题目的基础上，本题加上了一个冷冻期(无法在第二天买入股票) 1.确定dp数组及其下标含义 dp[i] [j]：第i天状态为j，所剩的最多现金为dp[i] [j] 具体可以区分为四个状态 1：持有股票状态（今天买入股票，或者是之前就买入了股票然后没有操作，一直持有） 2：保持卖出股票的状态（两天前就卖出了股票，度过了一天冷冻期，或者是前一天就是卖出股票的状态，一直没买入） 3：今天卖出股票 4：今天为冷冻期，但冷冻期状态不可持续，只有一天 2.确定递推公式 达到买入股票状态（状态1）即：dp[i] [0]： 操作一：前一天就是持有股票状态（状态一）,dp[i] [0] = dp[i-1] [0] 操作二：今天买入了，有两种情况 前一天是冷冻期（状态四）,dp[i-1] [3] - prices[i] 前一天是保持卖出股票的状态（状态二）：dp[i-1] [1] -prices[i] dp[i] [0] = max(dp[i-1] ...

123.买卖股票的最佳时机III文章：35. 买卖股票的最佳时机III 题目：123. 买卖股票的最佳时机 III 【思路】 本题关键在于：至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖 1.确定数组及其下标含义 0：没有操作 1：第一次持有股票 2：第一次不持有股票 3：第二次持有股票 4：第二次不持有股票 dp[i] [j]：i表示第 i 天，j为[0-4]五个状态，dp[i] [j] 表示第i天状态 j 所剩最大现金。 需要注意：dp[i] [1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，这是很多同学容易陷入的误区。 例如 dp[i] [1] ，并不是说 第i天一定买入股票，有可能 第 i-1天 就买入了，那么 dp[i] [1] 延续买入股票的这个状态。 2.确定递推公式 达到dp[i] [1]的两种情况： 第i天买入股票，那么dp[i] [1] = dp[i-1] [0] - prices[i] 第i天没有操作，而是沿用前一天买入的状态，即：dp[i] [1] = dp[i-1] [1] 因此我们可以选取这两个前置 ...

买卖股票的最佳时机文章：32. 买卖股票的最佳时机 题目：121. 买卖股票的最佳时机 【思路】 暴力找最大间距 Go实现（不出意外的超时了哈哈） 123456789func maxProfit(prices []int) int { res :=0 for i:=0;i < len(prices);i++{ for j :=i+1; j < len(prices);j++{ res = max(res,prices[j] - prices[i]) } } return res} 贪心找左边最小值和右边最大值即可。 Go实现 123456789func maxProfit(prices []int) int { leftMin := math.MaxInt rightMax :=0 for i :=0 ;i<len(prices);i++{ leftMin = min(lef ...

198.打家劫舍文章;29. 打家劫舍 题目：198. 打家劫舍 【思路】 题目的特点：相邻的房屋装有相互连通的防盗系统。 1.确认数组及其下标含义 dp[i]：考虑下标（包括i）以内的房屋，最多可以偷窃的金额为dp[i] 2.确认递推公式 决定dp[i]的因素是第i房间偷还是不偷。 如果偷第i房间，那么dp[i] = dp[i-2] + nums[i]，即：第i-1房是一定不考虑的，找出下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2]加上第i房间偷盗的钱。 如果不偷第i房间，那么dp[i] = dp[i-1]，即考虑i-1房，（注意这里是考虑，不是一定要偷i-1房） dp[i] = max(dp[i-2] + nums[i],dp[i-1]) 3.dp数组如何初始化 从递推公式dp[i] = max(dp[i-2]+nums[i],dp[i-1])可以看出，递推公式的基础就是dp[0]和dp[1] 从dp[i]的定义上来讲，dp[0]一定是nums[0]，dp[1]则是nums[0]和nums[1]的最大值：dp[1] & ...

139.单词拆分文章：26. 单词拆分 题目：139. 单词拆分 【思路】 单词就是物品，字符串就是背包，单词能否组成字符串，即问物品能不能把背包装满。 拆分时可以重复使用字典中的单词，说明是一个完全背包。 1.确定dp数组及其下标的含义 dp[i]：字符串长度为 i，dp[i] 为true，表示可以拆分为一个或多个在字典中出现的单词。 2.确定递推公式 如果dp[j] 为true，且[ j , i ]这个区间的子串出现在字典里，那么dp[i]就一定是true。 递推公式为： if([j , i] 这个区间的子串出现在字典中 && dp[j] 是true) dp[i] = true 3.初始化数组 递推公式中可以看出，dp[i]的状态是依靠dp[j]是否为true，那么dp[0]就是递推的根基，dp[0]一定要为true。 非零下标初始化为false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。 4.确定遍历顺序 单词有排列顺序，求的是某一段序列，也就是排列数。 因此，先遍历背包，再遍历物品。 5.举例推导。。 Java实现 123456 ...

动态规划理论基础动规五部曲： 1.确定dp数组及其下标含义 2.确定递推公式 3.dp数组如何初始化 4.确定遍历顺序 5.举例推导dp数组 斐波那契数列状态转移方程：dp[i] = dp[i-1] + dp[i-2] 爬楼梯状态转移方程：dp[i] = dp[i-1] + dp[i-2] 初始化dp数组的时候，dp[0]的初始化其实是没有含义的。 正确的思路是：dp[1] = 1,dp[2]=2，从3开始遍历。 使用最小花费爬楼梯推导现在的状态怎么出现的：（爬上当前楼梯不需要花费，在前一阶已经花了） 状态转移方程：dp[i] = min(dp[[i-1]+costs[i] , dp[i-2] + costs[i-2]) 不同路径从出发点到终点有几种路径。 dp[i] [j] = 从左边+从上面来的路径 = dp[i-1] [j] + dp[i] [j-1] 需要注意数组初始化！最左、最上的边框都需要初始化为1，因为只有一条路径能都到达。 不同路径（添加障碍版）从出发点到终点有几种路径。 （ ( i , j )没有障 ...