- 博客(88)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 代码随想录算法训练营之JAVA｜第四十四天|198. 打家劫舍
因为有个i-2，因此i是从2开始遍历的，nums的取值是i-1 所以我们需要初始化 dp[1].在只有一个可以抢的情况下，最大值就是这一个的值，因此 dp[1] = nums[0];因此递推公式为：dp[i] = max( dp[i - 1], dp[i-2] + nums[i-1]假设抢了 i 位置上的，那么i-1位置上的就不能再抢了：dp[i-2] + nums[i-1]dp[i] 代表的含义是：在 0-i 可以抢的情况下，抢的最大值是dp[i]假设没有抢 i 位置上的，那么 dp[i - 1]
2023-09-03 20:44:13
255
原创 代码随想录算法训练营之JAVA｜第四十二天|70. 爬楼梯
我发现之前觉得很难理解的东西，在你理解之后他会变得很简单。那么如何快速去理解，我觉得这个就是拉开人和人之间的差距的地方。之后的步骤就是代入完全背包的公式。需要注意的一点是：这是一个排列组合，因为和顺序是相关的。这是一个动态规划的入门题目，在看完完全背包之后，感觉也是可以使用完全背包来实现的。
2023-08-28 23:12:24
514
原创 代码随想录算法训练营之JAVA｜第四十天|518. 零钱兑换 II
完全背包和0-1背包的区别在于遍历的顺序，因为可以无限使用，因此在一维数组中的0-1背包的遍历顺序中，先从遍历物品，然后遍历容量。但是容量的遍历必须得从大到小去遍历，因为每个物品只能使用一次的原因。还有一点需要注意的是，在0-1背包中，先遍历物品还是容量都是可以的，但是在完全背包中是有讲究的。先遍历物品在遍历容量是求的组合（重复的，但是顺序不同算一次），先遍历容量在遍历物品求的是排列（重复的，顺序不同算多次）。题目理解：相对于上一次做的零钱兑换，这一次的零钱是无数的，因此可以有更多的选择。
2023-08-28 22:20:04
139
原创 代码随想录算法训练营之JAVA｜第三十五天|343. 整数拆分
确定遍历顺序，先来看看递归公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));dp[i] 是依靠 dp[i - j]的状态，所以遍历i一定是从前向后遍历，先有dp[i - j]再有dp[i]。这里我只初始化dp[2] = 1，从dp[i]的定义来说，拆分数字2，得到的最大乘积是1，这个没有任何异议！严格从dp[i]的定义来说，dp[0] dp[1] 就不应该初始化，也就是没有意义的数值。dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。
2023-08-22 22:02:13
102
原创 代码随想录算法训练营之JAVA｜第三十五天|509. 斐波那契数
这个一般情况是不容易找到的，我一般是通过从比较小的数值去寻找规律，或者是根据题目的含义来找到递推的公式。因此在终点位置有两个入口可以到达终点，这两个入口的值相加就是这个终点的值。根据公式，我们会想确定一条边的值，当然确定一列的值也是可以的。初始化也是比较简单的，如果m=1 或者 n = 1 的情况下，都只会有一种路径，因此初始化也搞定了。这个是比较好理解的，dp(m,n) 表示的含义是：在M*N的棋盘中有多少种方式可以到达终点。遇到这种题目，会第一时间想起代码随想录的五个步骤，按照步骤一步一步的来。
2023-08-20 23:36:10
92
原创 代码随想录算法训练营之JAVA｜第三十四天|509. 斐波那契数
从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的。如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。dp[i]的定义为：第i个数的斐波那契数值是dp[i]简单的只是让你知道更多的信息，复杂是隐去了更多的信息。这是一道很简单的动态规划。
2023-08-20 22:56:04
128
原创 代码随想录算法训练营之JAVA｜第三十三天|738. 单调递增的数字
因为要求单调递增，因此可能会出现 类似 3799998 这种需要修改的值在在第一个九的位置的这种情况。代码随想录的方法是找到最大值出现的最后一位，然后通过减1的方式不断的回退idx的值，最后找到第一个idx的值，我感觉我的方法会更加简单和容易理解。如果符合条件 i的值比i+1的值更大，那么就会使用idx-1，然后后面填充9。有时候花掉一点点的空间，换取更加简单粗暴的方式，我认为是值得的。
2023-08-20 21:21:28
237
原创 代码随想录算法训练营之JAVA｜第三十二天|435. 无重叠区间
如果三个区间有重叠，那么我取一条就行，如果五个区间有重叠，我趣一条就行。题目理解：找出重叠的最小个数，反过来说就是找出不重叠的最大个数。你看如果多少个区间有重叠，我都是取一条。因此计算不重叠会更好算。当有重叠的时候，我们要跟新尾巴的值，取这两条线段的尾巴的最小值。为什么要计算不重叠的，而不是重叠的呢，因为不重叠的会更好算。如果尾巴大于头，说明有重叠，否则没有重叠。取前面线段的尾和后面线段的头去比较。
2023-08-17 23:48:56
110
原创 代码随想录算法训练营之JAVA｜第三十一天|860. 柠檬水找零
只需要在找零钱的时候符合这三种情况即可。题目理解：是否满足找零钱的需求。这个好像没有什么难度。860. 柠檬水找零。
2023-08-15 23:53:13
154
原创 代码随想录算法训练营之JAVA｜第三十天|134. 加油站
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。如果 curSum<0 说明 区间和1 + 区间和2 < 0， 那么 假设从上图中的位置开始计数curSum不会小于0的话，就是 区间和2>0。那么为什么一旦[0，i] 区间和为负数，起始位置就可以是i+1呢，i+1后面就不会出现更大的负数？当你得意的时候，往往就是你失败的时候。
2023-08-14 23:57:22
155
原创 代码随想录算法训练营之JAVA｜第二十九天|1005. K 次取反后最大化的数组和
思路也是比较容易理解：先将数组进行排序，尽可能的将数组中的负数都转化成正数。如果数组都是被转化成正数后，且还需x次取反，如果x是偶数，则不需要操作，如果x是奇数，将全部正数的数组再次排序后，将第一个转换成负数。在计算数组的累加和即可。题目理解：数组在进行K次取反后，求累加的最大值。1005. K 次取反后最大化的数组和。贪心算法的解题过程会更加的清晰易懂。取反操作可重复用于同一个数字。
2023-08-14 22:24:12
151
原创 代码随想录算法训练营之JAVA｜第二十五天| 491. 递增子序列
首先解决相同的两个在一起的情况，比如 4，6，7，7 会出现两个4，7的列表，这个时候我就判断当前元素不能和上一元素一样。如果列表中有重复的，1，2，3，1，1，就会出现1，1 这种重复的列表。然后又解决这个问题。1. 当陷入局部难题，并且难题越结越多的时候，应该跳出来观察问题，而不是继续纠结。回溯的原理是将每一次的选择当成一个分支来看，于是我们就可以画图。题目理解：在给定的一个数组中，找出全部的递增列表。
2023-08-10 00:36:33
186
原创 代码随想录算法训练营之JAVA｜第二十三天| 39. 组合总和
我认为回溯算法的核心是将组合的过程看成是一颗树，然后来回溯。那考虑第一个思路，如果遍历的时候只能选择当前或者往后的位置，那就可以杜绝重复现象的产生了。题目理解：根据给出的数组，从数组中选择n个数相加，记录相加结果为target的组合。做出来的答案可能是：[[2,2,3],[2,3,2],[3,2,2],[7]][2,2,3],[2,3,2],[3,2,2] 这个就是重复的。想法和思路是一致的。
2023-08-07 22:40:22
108
原创 代码随想录算法训练营之JAVA｜第二十二天| 216. 组合总和 III
看完代码随想录之后，发现暴力的回溯会遍历所有的可能，但是有一些可能是在开始或者中间的时候是可以判断出这条路径是走不通的，于是可以进行剪枝。在这道题目中，如果在进入递归的时候，列表中的值的和大于N了，那就没有必要往下回溯了。这道题和第二十一天做的题目很像，不过这道题目添加了一个条件，需要列表中的值等于N。剪枝就是将不必要的路径移除，那如何判断该路径是否必要呢？216. 组合总和 III。
2023-08-07 22:27:09
96
原创 代码随想录算法训练营之JAVA｜第二十天| 669. 修剪二叉搜索树
可以发现他一共找来三次，先找头节点，找处于区间的最小值，找处于区间的最大值。寻找的方式都是一样的：使用二叉搜索树的特性，左边节点 < 中间节点 < 右边节点。可以递归的操作都是可以迭代来完成的，我想了一下如何使用迭代来完成，但是没有想出来。2.1 如果当前节点小于区间最小值，则往当前节点的右节点寻找下一个节点。2.2 如果当前节点大于区间最大值，则往当前节点的左节点寻找下一个节点。要确定一棵树，得先确定他的根节点，如果不确定那是不能确定这棵树的。先找到头节点，然后修剪左树枝，最后修剪右树枝。
2023-08-03 23:20:48
85
原创 代码随想录算法训练营之JAVA｜第十九天| 235. 二叉搜索树的最近公共祖先
因此代码就很好写了，只要这个两个节点都大于该节点，就往该节点的右边遍历，如果这个两个节点都小于该节点，就往该节点的左边遍历。直到找到一个节点不满足都大于或者小于这两个节点的节点，返回该节点。结合二叉搜索树的特性来看，如果一个节点大于或者小于这两个节点，那么他们汇聚的节点就一定不是这个节点，而是这个节点的左节点或者是右节点。想法是一致的，还有一种是递归的方法，想法都是一样的。如果两个节点分别是5，7，那么他们会在节点6汇聚。如果两个节点分别是0，5，那么他们会在2汇聚。235. 二叉搜索树的最近公共祖先。
2023-08-02 22:29:05
305
原创 代码随想录算法训练营之JAVA｜第十六天| 513. 找树左下角的值
第一想法就是使用层序遍历，每一次遍历的时候会将这一层的最左边的拿出来就行。题目理解：找到最后一层的最左边的节点的值。相差不大，另外提供了递归的做法。无，只是将之前层序遍历在写了一遍。
2023-07-29 23:35:48
131
原创 代码随想录算法训练营之JAVA｜第十一天| 239. 滑动窗口最大值
梳理的过程使用的是工程的思维，单调队列有三个操作，那就从一个操作入手。要实现这个数据结构也是比较简单的。第一个想法是暴力循环，我只需要对窗口的值进行排序，然后取出最大值就行。实现单调队列的时候是比较不能理解的，但是慢慢梳理后发现还是可以理解的。单调队列就是记录窗口内值的单调性。题目理解：找到滑动窗口中最大的值，写入数组中，返回该数组即可。代码随想录的做法是使用单调队列来完成的。只需要保证队列是递减的即可。
2023-07-25 00:52:37
130
原创 代码随想录算法训练营之JAVA｜第七天| 344. 反转字符串
理解题目：将一个字符串数组反转，也就是将第一个和最后一个调换位置，第二个和倒数第二调换位置，以此类推。如此，那么我们使用一个双指针，一个指向头，一个指向尾，然后将指针的两个调换位置即可。位运算的交换没有搞懂，后面了解了一下位运算的基础知识后，就恍然大悟了。思路是一致的，但是他提供了另一种交换位置的写法，我觉得挺有意思的。在基础知识的运用下我们可以来分析一下。344. 反转字符串。
2023-07-19 23:56:58
61
struts2+hibernate实现简单的仿论坛功能
2017-12-03
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人