- 博客(37)
- 收藏
- 关注
原创 java算法day37 | 贪心算法 part06 ● 738.单调递增的数字 ● 968.监控二叉树
从后向前遍历,如果前一个数比后一个数大,则前一个数-1,后面的数都变成9.思路不难,但实现的代码还是有一点繁琐的。以下是用List实现的代码。
2024-03-29 00:15:10 75
原创 java算法day36 | 贪心算法 part05 ● 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间
重叠区间典型题目,先按照左边界排序,再从左到右判断相邻区间是否重叠,重叠则删除其中一个。时间复杂度:O(nlog n) ,有一个快排空间复杂度:O(n),有一个快排,最差情况(倒序)时,需要n次递归调用。因此确实需要O(n)的栈空间。
2024-03-27 17:12:16 239
原创 java算法day35 | 贪心算法 part04 ● 860.柠檬水找零 ● 406.根据身高重建队列 ● 452. 用最少数量的箭引爆气球
设定三个变量存储已有的三种面额的数量,只需要设想出每一种情况的找零方案,更新当前每种面额的数量。时间复杂度: O(n)空间复杂度: O(1)
2024-03-26 17:43:09 223
原创 java算法第34天 | 贪心算法 part03 ● 1005.K次取反后最大化的数组和 ● 134. 加油站 ● 135. 分发糖果
先将数组元素从小到大排列,从左向右处理,分两种情况讨论OnlognO1。
2024-03-25 17:26:29 426
原创 java算法第32天 | 贪心算法 part02 ● 122.买卖股票的最佳时机II ● 55. 跳跃游戏 ● 45.跳跃游戏II
本题中理解利润拆分是关键点!不要整块的去看,而是把整体利润拆为每天的利润。假如第 0 天买入,第 3 天卖出,那么利润为:prices[3] - prices[0]。相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。,最后稳稳的就是最大利润了。OnO1。
2024-03-23 11:26:07 1017
原创 java算法第31天 | 贪心算法 part01 ● 理论基础 ● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和
贪心算法没有固定的套路,贪心的本质是贪心算法一般分为如下四步:将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解这个四步其实过于理论化了,我们平时在做贪心类的题目 很难去按照这四步去思考,真是有点“鸡肋”。做题的时候,只要想清楚 局部最优 是什么,如果推导出全局最优,其实就够了。
2024-03-22 23:19:39 263
原创 java算法第29天 | * 491.递增子序列 * 46.全排列 * 47.全排列 II
本题和大家刚做过的 90.子集II 非常像,但又很不一样,很容易掉坑里。90.子集是可以对数组进行重新排序,再去重。但是这道题是要求子序列,如果对数组重排序会打乱顺序,无法获取子序列。因此491.递增子序列的去重思路是使用HashSet记录当前层处理过的节点,然后遇到已经处理过的节点直接跳过。(注意这里的跳过用的是continue,因为后面的节点还要继续处理)。时间复杂度: O(n * 2^n)空间复杂度: O(n)
2024-03-20 23:49:00 198
原创 java算法第28天 | 93.复原IP地址 78.子集 90.子集II
这里startIndex为插入‘.’的位置,使用回溯法遍历所有插入的位置,直接在原始字符串上操作。要注意的是开闭区间的规定(这里我规定的是左闭右闭区间)。还要明确什么时候能return。时间复杂度: O(3^4),IP地址最多包含4个数字,每个数字最多有3种可能的分割方式,则搜索树的最大深度为4,每个节点最多有3个子节点。空间复杂度: O(n)
2024-03-19 22:29:28 338
原创 java算法第27天 | ● 39. 组合总和 ● 40.组合总和II ● 131.分割回文串
本题是 集合里元素可以用无数次,那么和组合问题的差别 其实仅在于 startIndex上的控制。时间复杂度: O(n * 2^n),注意这只是复杂度的上界,因为剪枝的存在,真实的时间复杂度远小于此空间复杂度: O(target)
2024-03-18 23:14:05 370
原创 java算法第24天 | 回溯算法理论基础 77. 组合
回溯常用来解决一下问题:回溯算法并不高效,但他可以达到单纯暴力解法达不到的效果。因为当for循环的个数不能固定时,我们可以通过递归来动态实现循环的次数。
2024-03-15 21:16:39 392
原创 java算法第23天 | ● 669. 修剪二叉搜索树 ● 108.将有序数组转换为二叉搜索树 ● 538.把二叉搜索树转换为累加树
这道题和删除节点异曲同工。不过要注意避坑:当遍历到不在范围内的节点时,不要直接返回null或直接返回其左或右孩子,而是继续对其左或右孩子做递归。这道题是使用二分查找的思路递归构建二叉树。使用双指针的方法,右中左的顺序遍历数组。
2024-03-14 16:08:56 355
原创 java算法第22天 | ● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点
可以不考虑题目中提示所说的改变树的结构的插入方式。一定存在一个叶子节点,使val值作为它的左或右孩子是合理的。相对于上一题的插入操作,本题就有难度了,涉及到改树的结构。之前做过普通二叉树求共工作祖先的问题,有两种情况,可以不考虑题目中提示所说的改变树的结构的插入方式。
2024-03-13 15:57:21 399
原创 java算法第21天 | 530.二叉搜索树的最小绝对差 501.二叉搜索树中的众数 236. 二叉树的最近公共祖先
使用一个全局的动态数组result来存储当前出现次数最多的数(注意,可能后面还有出现次数更多的数),当遇到出现次数更多的数时,更新result中的数。情况一:如果找到一个节点,发现左子树出现结点p,右子树出现节点q,或者左子树出现结点q,右子树出现节点p,那么该节点就是节点p和q的最近公共祖先。**思路:**用pre节点记录当前节点cur的前一个结点,cur.val-pre.val就是差值。其实情况一 和 情况二 代码实现过程都是一样的,也可以说,实现情况一的逻辑,顺便包含了情况二。
2024-03-12 21:54:44 347
原创 java算法第20天 | ● 654.最大二叉树 ● 617.合并二叉树 ● 700.二叉搜索树中的搜索 ● 98.验证二叉搜索树
因此使用双指针优化的方法,假设当前遍历的节点是node,定义一个全局变量节点存储node中序遍历的上一个节点。这道题最直观的解法是直接用中序遍历得到一个数组,判断数组是否是由小到大的。和根据后/前中序遍历数组生成树结构的思路一样。首先要明确参数和返回值。同时遍历两个二叉树,可以不创建新的节点,直接在其中一个数的基础上操作。每次递归需要传入数组,和开始和结束的位置,返回的是二叉树的根节点。因为是二叉搜索树,不必左右子树都遍历。但是我试了这种解法超时。
2024-03-11 17:35:48 325
原创 java算法第十七天 | ● 513.找树左下角的值 ● 112. 路径总和 113.路径总和ii ● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树
注意,这道题的左下角值一定位于最后一层,因此不能单纯地向左下遍历。本题使用层序遍历更加易懂,也可以使用递归方法实现。
2024-03-09 23:19:53 354
原创 java算法第十八天 | ● 110.平衡二叉树 ● 257. 二叉树的所有路径 ● 404.左叶子之和
使用后序遍历分别求左右子树的高度,若高度只差大于一,则返回-1,否则返回当前节点的最大高度。
2024-03-09 14:45:49 391
原创 java算法第十六天 | ● 104.二叉树的最大深度 559.n叉树的最大深度 ● 111.二叉树的最小深度 ● 222.完全二叉树的节点个数
本题可以使用前序(中左右),也可以使用后序遍历(左右中),使用前序求的就是深度,使用后序求的是高度。
2024-03-07 16:40:20 316
原创 java算法第十五天 | ● 层序遍历 ● 226.翻转二叉树 ● 101.对称二叉树
需要借用一个辅助数据结构即来实现,队列先进先出,符合一层一层遍历的逻辑,而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。而这种层序遍历方式就是图论中的广度优先遍历,只不过我们应用在二叉树上。不要忽略root为空的情况,否则会报错。
2024-03-06 12:17:38 867
原创 java算法第十三天 | ● 239. 滑动窗口最大值 ● 347.前 K 个高频元素 ● 总结
堆是一棵完全二叉树,树中每个结点的值都不小于(或不大于)其左右孩子的值。如果父亲结点是大于等于左右孩子就是大顶堆,小于等于左右孩子就是小顶堆。
2024-03-04 13:07:41 387
原创 java算法第十一天 | ● 20. 有效的括号 ● 1047. 删除字符串中的所有相邻重复项 ● 150. 逆波兰表达式求值
要讲栈和队列,首先要讲Deque接口。Deque的含义是“double ended queue”,即双端队列,它既可以当作栈使用,也可以当作队列使用。下表列出了Deque与Stack相对应的接口:下表列出了Deque与Queue相对应的接口:上面两个表共定义了Deque的12个接口。添加,删除,取值都有两套接口,它们功能相同,区别是对失败情况的处理不同。一套接口遇到失败就会抛出异常,另一套遇到失败会返回特殊值(false或null)。除非某种实现对容量有限制,大多数情况下,添加操作是不会失败的。
2024-03-02 23:55:56 778 2
原创 java算法第十天 | ● 栈和队列理论基础 ● 232.用栈实现队列 ● 225. 用队列实现栈
再多说一些代码开发上的习惯问题,在工业级别代码开发中,最忌讳的就是 实现一个类似的函数,直接把代码粘过来改一改就完事了。可以看出peek()的实现,直接复用了pop(), 要不然,对stOut判空的逻辑又要重写一遍。获取队首元素 queue.peek()/element();弹出元素 queue.poll(x)/remove(x);追加元素 queue.add(x)/.offer(x);时间复杂度: pop为O(n),其他为O(1)时间复杂度: pop为O(n),其他为O(1)空间复杂度: O(n)
2024-03-01 13:27:33 941
原创 java算法第九天 | ●28. 实现 strStr() ●459.重复的子字符串
本题比较难懂建议多看几遍视频然后再去看一下本题我比较习惯理解不对next[]数组做右移和减一操作的版本。时间复杂度:O(n+m)空间复杂度:O(m)
2024-02-29 23:28:27 323
原创 java算法第八天 | 字符串part01 ● 344.反转字符串 ● 541. 反转字符串II ● 卡码网:54.替换数字 ● 151.翻转字符串里的单词 ● 卡码网:55.右旋转字符串
双指针的简单应用时间复杂度: O(n)空间复杂度: O(1)
2024-02-28 16:51:10 746
原创 java算法第七天 | ● 454.四数相加II ● 383. 赎金信 ● 15. 三数之和 ● 18. 四数之和
本题是 使用map 巧妙解决的问题,好好体会一下 哈希法 如何提高程序执行效率,降低时间复杂度,当然本题是使用哈希法的经典题目,而0015.三数之和 (opens new window),0018.四数之和 (opens new window)并不合适使用哈希法,因为三数之和和四数之和这两道题目使用哈希法在不超时的情况下做到对结果去重是很困难的,很有多细节需要处理。而这道题目是四个独立的数组,只要找到A[i] + B[j] + C[k] + D[l] = 0就可以,
2024-02-27 23:14:04 772
原创 java算法第六天 | ● 哈希表理论基础 ● 242.有效的字母异位词 ● 349. 两个数组的交集 ● 202. 快乐数 ● 1. 两数之和
哈希函数如下图所示,通过hashCode把名字转化为数值,一般hashcode是通过特定编码方式,可以将其他数据格式转化为不同的数值,这样就把学生名字映射为哈希表上的索引数字了。因为本题,我们不仅要知道元素有没有遍历过,还要知道这个元素对应的下标,需要使用 key value结构来存放,key来存元素,value来存下标,那么使用map正合适。我们需要依靠哈希表中的空位来解决碰撞问题。注意题目特意说明:输出结果中的每个元素一定是唯一的,也就是说输出的结果的去重的, 同时可以不考虑输出结果的顺序。
2024-02-26 16:11:52 776
原创 java算法打卡第五天|每周日复习日
把上一周的算法题重新做了一遍,有些细节还是会错,有的因为不认真,有的因为没理解透彻。看来还是要定期复习啊!删除链表的第n个节点和下标为n的节点,这个for循环的次数这里想了很久,CPU烧了。
2024-02-25 23:47:48 328
原创 java算法第四天 | ● 24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点 ● 面试题 02.07. 链表相交 ● 142.环形链表II
建议使用虚拟头结点,这样会方便很多,要不然每次针对头结点(没有前一个指针指向头结点),还要单独处理。接下来就是交换相邻两个元素了,此时一定要画图,不画图,操作多个指针很容易乱,而且要操作的先后顺序1、交换时需要使用两个temp指针暂存节点,防止丢失。2、while()中的&&两边的判断条件不能交换位置,否则会出现空指针异常。时间复杂度:O(n)空间复杂度:O(1)
2024-02-24 12:39:52 758
原创 java算法第三天 | 203.移除链表元素 、 707.设计链表 、206.反转链表
链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。
2024-02-23 15:34:23 397
原创 SSM学习前准备 01 | maven的作用、下载配置、使用idea创建maven项目的简单案例(jdk1.8)
按照教程一步一步来,就能安装配置成功。
2024-02-23 00:04:11 311
原创 SSM框架学习打卡day1 | Spring基本介绍
Spring Framework时Spring生态圈中最基础的项目,是其他项目的根基。Spring能做什么:Web开发、微服务开发、分布式系统的开发。Spring Boot:在简化开发的基础上加快开发速度。Spring Framework:底层的设计性的框架。Spring Cloud:分布式开发相关的技术。
2024-02-22 17:22:27 304
原创 java算法第二天 | 977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II
因为有序数组中包含负数,让left指针指向原数组的起始位置,right指针指向原数组的终止位置,交替比较两个位置上数据平方的大小,将更大的平方值放入新定义的数组new_nums中。Java中数组的定义方式时间复杂度:O(n)空间复杂度:O(n)
2024-02-22 14:51:58 365
原创 代码随想录java算法第一天打卡 | 704. 二分查找、27. 移除元素。
正是因为数组的在内存空间的地址是连续的,所以我们在删除或者增添元素的时候,就难免要移动其他元素的地址。Java是没有指针的,同时也不对程序员暴露其元素的地址,寻址操作完全交给虚拟机。所以看不到每个元素的地址情况,这里我们以Java为例,也做一个实验。这里的数值也是16进制,这不是真正的地址,而是经过处理过后的数值了,我们也可以看出,二维数组的每一行头结点的地址是没有规则的,更谈不上连续。
2024-02-21 13:38:54 673
原创 Anaconda在开始菜单找不到Anaconda prompt入口
Anaconda在开始菜单找不到Anaconda prompt入口如果在安装了Anaconda后,在开始栏下找不到 Anaconda prompt 怎么办?我在百度的评论里面找到了这个方法记录一下。1.win+r调出cmd窗口2.输入“conda install console_shortcut”,选择y。3.再烦开始栏,就会发现Anaconda prompt出现了...
2020-05-04 12:43:38 3003 3
原创 eclipse如何在控制台输出彩色字体
个人亲测有效!1.下载插件:点击安装(因为我已经安装完了,此处就只显示了更新和卸载)2.安装成功后会提示重启eclips.3.若如下显示,则说明安装成功。4.运行以下代码`package try_color;public class Color {public static void main(String[] args) {System.out.println("\033...
2020-04-16 01:37:00 2951 2
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人