两数之和(1)
题目
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
我的思路
- 先排序
- 排除比target大的数
- 从最靠近target的数开始遍历
- 记录找到的数的下标输出即可
我的代码(未AC)
1 | import java.util.Arrays; |
正确思路
利用 HashMap 记录数组元素值和对应的下标,对于一个数 nums[i],判断 target - nums[i] 是否存在 HashMap 中,存在的话,返回两个下标组成的数组。注意,已存在的元素下标在前,当前元素下标在后。
正确代码
1 | class Solution { |
涉及的知识点
数组内容
一维和二维数组
一维数组:int[] a = new int[4];
二维数组:1
2
3
4//第一行4个元素,第二行5个元素
int[][] a = new int[2][];
a[0] = new int[4];
a[1] = new int[5];Arrays类
java.util.Arrays类能够方便的操作数组,提供的所有方法都是静态的:
1 | import java.util.Arrays; |
总共5个方法,分别是copyOf,fill,binarySearch,equals,sort。第一个用来复制原始数组,方便后续排序的操作,fill是用来初始化数组比较方便,可以将所有数组中的值全部初始化为同一个值,binarySearch是二分查找,返回的是该数的索引值,sort是用来排序的。
binarySearch()
自己写代码的时候用到了这个方法,首先该方法需要数组排好序才能调用,其次很特别的是,如果要找的值在数组中,则会返回搜索键的索引,但是,注意:值不存在于数组的话会返回-1或者是目标值需要插入的位置,从1开始数起,不是0哦!!!
这个写的贼好哈哈哈哈:
数组查询Arrays类的binarySearch()方法详解map.containsKey和map.get()区别
hashmap判断是否存在key时,使用get(key)==null判断还是containsKey?
key值可能为null,若此时Map集合值对象为null,并且没有个数限制,所以当get()方法的返回值为null时,可能有两种情况,一种是在集合中没有该键对象,另一种是该键对象没有映射任何值对象,即值对象为null。因此,在Map集合中不应该利用get(Object key)方法来判断是否存在某个键,而应该利用containsKey()方法来判断,containsKey方法用来判断Map集合对象中是否包含指定的键名。
一句话概括:get()如果得到null,可能这是键对应的值对象为null也可能是不存在该键,而containsKey则是false或true,不存在这种疑问。扩充:map.containsKey()、map.containsValue()、map.get()
- get的过程是先计算hash,然后通过hash与table.length取摸计算index值,然后遍历table[index]上的链表,直到找到key,然后返回;
1 | public V get(Object key) { |
- containsKey方法也是先计算hash,然后使用hash和table.length取摸得到index值,遍历table[index]元素查找是否包含key相同的值;
1 | public boolean containsKey(Object key) { |
看代码能看到区别,一个是返回key对应的value值,一个是返回是否有该key的boolean变量。
* containsValue方法就比较粗暴了,就是直接遍历所有元素直到找到value,由此可见HashMap的containsValue方法本质上和普通数组和list的contains方法没什么区别,你别指望它会像containsKey那么高效。
1 | public boolean containsValue(Object value) { |
知识缺陷
- 压根没想到用Map去做
- 自己只考虑到了全是正数的情况,所以用了排序和跟0判断,如果含有负数的话就做不了了……
收获
在遇到数组问题时,可以考虑用map,因为索引和数值就是一个天生的map集合,如果我知道数值,我就可以通过map找到其索引,本题思路就是这样,当已知一个值是我所需要的,直接从map中拿出就行。
插入知识点
既然复习到了map,那就给list、set和map来一个全部的复习吧!!!
嘿嘿开始吧!!!
先来上个链接,主要是看的这个写的:Java集合中List,Set以及Map等集合体系详解(史上最全)
collection
先上个图:这个图画的好啊哈哈哈哈哈哈哈
不瞎的都看得到,Collection这个接口下有三个接口继承,分别是Set、List、Queue(我他妈好像没怎么用过Queue啊,以后要多用点了),Set有三个实现类,分别是HashSet、LinkedHashSet、TreeSet,List有三个实现类,分别是ArrayList、Vector(感觉现在是不是用的比较少啊…)、LinkedList,咦这个LinkedList牛逼啊,竟然还是Queue的实现类,不过看别人博客好像是说继承Queue部分的LinkedList是被阉割了的实现类,也就是Queue不能访问到LinkedList的所有方法(管它呢我都没用过…),还有一个PriorityQueue,看名字就知道是优先级队列啦!
(妈呀看的资料太多,想单独开一篇来总结集合源码和Map源码了…算了先这样写着吧)
####先列个提纲:
- 1.先综述一下collection中三个儿子接口得各个实现类的特点,比如底层实现,优缺点等等;
还有要考虑的就是base case,由于是最短递归子序列至少为1,所以base case为1,所以dp数组全部初始化为1即可。
3.面试常问到的点
综述
— List 有序,可重复
ArrayList
优点: 底层数据结构是数组,查询快,增删慢。
缺点: 线程不安全,效率高
特点: 允许null,不同步
Vector
优点: 底层数据结构是数组,查询快,增删慢。
缺点: 线程安全,效率低
tips:所谓的线程安全,是相对的,在vector内部内部内部,其所有方法不会被多线程所访问,单个方法的原子性(注:原子性,程序的原子性即不会被线程调度机制打断),并不能保证复合操作也具有原子性,所以如果是复合操作,同样线程不安全!!如果要保证真正的线程安全,还需要以vector对象为锁,来进行操作,但这样就跟ArrayList没啥区别了…———–> Vector是线程安全吗
特点:允许null,不同步
LinkedList
优点: 底层数据结构是双向链表,查询慢,增删快。故既可以做Queue,又可以做Stack。
缺点: 线程不安全,效率高
特点:允许null,不同步
—Set 无序,唯一
HashSet(不同步,允许null)
底层数据结构是哈希表(无序,唯一),其实就是HashMap的实例,只不过值是key,value是一个固定的对象。
如何来保证元素唯一性?
1.依赖两个方法:hashCode()和equals()
LinkedHashSet(不同步,允许null)
底层数据结构是双向链表和哈希表。(FIFO插入有序,唯一),实际上依旧是LinkedHashMap的实例,待会源码分析看看
1.由链表保证元素有序
2.由哈希表保证元素唯一
TreeSet(允许null,不同步)
底层数据结构是红黑树。(唯一,有序,这里的有序指的是排序好的,不是说FIFO之类的),实际上依旧是TreeMap的实例
- 如何保证元素排序的呢?
自然排序(重写):1.Student类中实现 Comparable接口 2.重写Comparable接口中的Comparetor方法
比较器排序:1.单独创建一个比较类,这里以MyComparator为例,并且要让其继承Comparator接口 2.重写Comparator接口中的Compare方法
2.如何保证元素唯一性的呢?
根据比较的返回值是否是0来决定
-Queue
PriorityQueue:优先级队列,按照大小排序好了的队列,并不遵循先进先出,不允许null元素,头部是最小元素,底层采用的数组和堆。
- PriorityQueue不是线程安全的。如果多个线程中的任意线程从结构上修改了列表, 则这些线程不应同时访问PriorityQueue 实例,这时请使用线程安全的PriorityBlockingQueue 类。
- 不允许插入 null 元素。
- PriorityQueue实现插入方法(offer、poll、remove() 和 add 方法) 的时间复杂度是O(log(n)) ;实现 remove(Object) 和 contains(Object) 方法的时间复杂度是O(n) ;实现检索方法(peek、element 和 size)的时间复杂度是O(1)。所以在遍历时,若不需要删除元素,则以peek的方式遍历每个元素。
- 方法iterator()中提供的迭代器并不保证以有序的方式遍历PriorityQueue中的元素。
剩余有关Queue队列看—–> Java集合(七) Queue详解
- 方法iterator()中提供的迭代器并不保证以有序的方式遍历PriorityQueue中的元素。
分别阐述
这个还是另开一篇吧…内容太多了…够写两星期了!!还是不放在这喧宾夺主了!!
map
具体展开见另一篇博客:Map源码分析
三数之和(15)
题目
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例:
1 | 给定数组 nums = [-1, 0, 1, 2, -1, -4], |
思路
固定住一个数,然后就剩另外两个数相加等于一个值
代码
1 | class Solution { |
两数相加(2)
题目
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例
1 | 输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) |
我的思路
- 先讲输入输出。要输入两个链表,首先就要构造Node实体类,注意构造函数有多个,根据参数的不同进行选择,输出同输入,将组合好的链表的头结点(有数据的)返回后,就可以循环将整个链表打印出来了;
- 再讲实现。见代码注释。
我的代码(AC)
1 | package 链表实现_java.leecode第二题; |
1 | package 链表实现_java.leecode第二题; |
正确思路
同时遍历两个链表,对应值相加(还有 quotient)求余数得到值并赋给新创建的结点。而商则用quotient存储,供下次相加。
正确代码
1 | //复杂版 |
1 | //简化版 |
涉及的知识点
java中的单链表
见我写的另外一篇博文 ——> Java实现单向链表
无重复字符的最长子串(3)
题目
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例
示例 1:
1 | 输入: "abcabcbb" |
示例 2:
1 | 输入: "bbbbb" |
示例 3:
1 | 输入: "pwwkew" |
我的思路
要找到一个最长子串,就必须有一头一尾,所以就必须有两个指针,然后又是字符串对应索引值,所以肯定是需要用map来操作的,key为索引值,value为索引所在位置的值。于是设定两个指针p、q,最开始同时指定在最开始的位置,然后q向后移动,每移动一次,只要q对应的值没有在map中,就将其值放入map,并且记录下串的大小,当碰到了map中相同的值时,就将p向后移到map中出现该值的索引后一位,同时注意!!!此时p可能会回溯,所以此时要用max函数判断一下,然后继续判断串的大小和继续遍历的最长子串的长度,最后返回最长子串长度即可。
我的代码(AC)
1 | package 第三题; |
正确思路
利用指针 p
, q
,初始指向字符串开头。遍历字符串,q
向右移动,若指向的字符在 map 中,说明出现了重复字符,此时,p
要在出现重复字符的下一个位置 map.get(chars[q]) + 1
和当前位置 p
之间取较大值,防止 p
指针回溯。循环的过程中,要将 chars[q] 及对应位置放入 map 中,也需要不断计算出max
与 q - p + 1
的较大值,赋给 max
。最后输出 max
即可。
正确代码
1 | class Solution { |
涉及的知识点
好像并没有啥新知识点,其实就是用map代替指针的作用。
删除链表中的节点(237)
题目
请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。
示例
示例 1
1 | 输入: head = [4,5,1,9], node = 5 |
示例 2:
1 | 输入: head = [4,5,1,9], node = 1 |
说明:
- 链表至少包含两个节点。
- 链表中所有节点的值都是唯一的。
- 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
- 不要从你的函数中返回任何结果。
我的思路
本题题干个人觉得没有交代的很清楚,让人感觉有点摸不着头脑,正常来说应该是给定两个参数,但是要写的函数只有一个参数,所以最开始会让人感觉很突兀,但是实际上这道题设计的很巧妙,不需要给定头结点,可以采用替身攻击,给定的node其实就可以当做头结点来处理,因为不可能是最后一个节点,所以后面一定有节点,故可以将node后节点牺牲掉,这样就相当于将node本身干掉了。
个人遇到的困难主要是在输入输出,尤其是构造单链表的过程花费了比较长的时间,总而言之还是对单链表的操作不够熟练,接下来会重点攻克单链表这一块的知识点!
##我的代码(AC)
1 | package 第237题_删除链表中的节点; |
1 | package 第237题_删除链表中的节点; |
正确思路
只提供 node 依然可以解决此题。只要把下个结点的 值 & next 赋给当前 node,然后删除下个结点,就可以搞定。
正确代码
1 | /** |
涉及的知识点
- 链表的构建
- 链表删除
不足
对链表操作还不是很驾轻就熟,接下来会重点训练链表操作。
删除链表的倒数第N个节点(19)
题目
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例
1 | 给定一个链表: 1->2->3->4->5, 和 n = 2. |
说明:
给定的 n 保证是有效的。
我的思路
删除倒数第n个节点,这个思路比较简单,就是运用两个指针 fast 和 slow ,一个指针比另外一个多n-1步,这样的话当fast指针到最后一个节点的时候,slow指针刚好到达要删除的节点的位置,此时就可以用上题用过的替身牺牲法,牺牲掉要删除节点的下一个节点,只需要将下一个节点的值赋值给当前节点并且将slow.next = slow.next.next即可。但是,有特殊情况 :
- 当要删除的节点是最后一个时,无法做到用下一个节点替换,这个时候就要提前预判,不能等到slow到了最后一个节点才考虑删除,要在slow.next.next == null时就考虑!!!
我的代码(AC)
1 | package 第19题; |
1 | package 第19题; |
正确思路
快指针 fast 先走 n 步,接着快指针 fast 与慢指针 slow 同时前进,等到快指针指向链表最后一个结点时,停止前进。然后将 slow 的 next 指向 slow.next.next,即删除了第 n 个结点。最后返回头指针。
这里设置了 pre 虚拟结点(指向 head )是为了方便处理只有一个结点的情况。
正确代码
1 | /** |
涉及的知识点
单链表的删除…比较简单啦
不足
个人感觉其实答案的解法还是要比我的好一些,它是通过直接找到删除节点的前一个,这样就非常好处理了,而且还没有特殊情况…我就很笨了,还自以为是的用了一个替身攻击的方法…学到了!!!要记得用到删除节点的前一个节点,这才是单链表的关键。
合并两个有序链表(21)
题目
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例
1 | 输入:1->2->4, 1->3->4 |
我的思路
创建一个新链表,然后比较两个链表,哪个小就让新链表的next指向他,如果有一个提前结束了,剩下的链表接上新链表的后半部分。
我的代码(AC)
1 | public static ListNode merge(ListNode l1, ListNode l2){ |
1 | package 第21题; |
正确思路
利用链表天然的递归性。如果 l1 为空,返回 l2;如果 l2 为空,返回 l1。如果 l1.val < l2.val
,返回 l1->mergeTwoLists(l1.next, l2);否则返回 l2->mergeTwoLists(l1, l2.next)。
正确代码
1 | /** |
涉及的知识点
链表算法题面试必看必看必看!!!!!!!合并K个排序链表(23)
题目
合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
示例
1 | 输入: |
我的思路
我没做出来,然后看了下讨论区,大概总结出三种思路:
- 运用优先级队列,将整个链表扔到优先级队列中,然后一个个取出来就可以了,这种思路代码实现比较简单,但是用了人家封装好的东西,总感觉有点投机取巧的感觉…
- 运用分治归并的思想,K个链表两两进行归并。
- 强行归并,两个归并完直接放到后者,然后后者再跟后面的排序,这样复杂度很高。
我的代码
1 | /** |
正确思路
第一种,优先级队列,20ms,
复杂度
- 时间复杂度: O(Nlogk) ,其中 k 是链表的数目。弹出操作时,比较操作的代价会被优化到 O(logk) 。同时,找到最小值节点的时间开销仅仅为 O(1)。最后的链表中总共有 N 个节点。
- 空间复杂度:O(n) 。创造一个新的链表需要 O(n) 的开销。O(k) 。以上代码采用了重复利用原有节点,所以只要 O(1) 的空间。同时优先队列(通常用堆实现)需要 O(k) 的空间(远比大多数情况的 N要小)。
- 过程:
- 1.因为链表有序,所以用每个链表的首元素构建初试堆(小顶堆) – 的队列
- 2.首元素出队,该元素next指向元素入队
第二种,归并分治,典型的归并分治思想,自底向上,依次合并(可结合归并排序理解,将每个链表理解成排序的值)。
复杂度分析
时间复杂度: O(Nlogk) ,其中 k 是链表的数目。
空间复杂度:O(1),我们可以用 O(1) 的空间实现两个有序链表的合并。
第三种,强行做。见我的代码,170ms
- 用第一个链依次和后面的所有链进行双链合并,利用021的双顺序链合并,秒杀!但是效率极低,
- 时间复杂度是O(x(a+b) + (x-1)(a+b+c) + … + 1 * (a+b+…+z);[a-z]是各链表长度,x表示链表个数-1,可见时间复杂度是极大的。
正确代码
- 优先级队列
1 | public ListNode mergeKLists(ListNode[] lists) { |
- 归并分治
1 | class Solution { |
涉及的知识点
包括了优先级队列、最小堆、归并以及 分治的思想
- 优先级队列。java中的优先级队列是PriorityQueue,是通过最小堆实现的
- 最小堆
- 归并
- 分治
判断一个数是否是回文数
题目
判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
示例 1:
1 | 输入: 121 |
示例 2:
1 | 输入: -121 |
示例 3:
1 | 输入: 10 |
思路
将数字直接转成字符串,然后用双指针判断即可;
直接将数字翻转,但是要考虑到给的数字可能会产生溢出,所以改成翻转一半的数字,如果该数字是回文,其后半部分反转后应该与原始数字的前半部分相同。
首先需要处理一些临界条件:
- 负数不可能是回文数字;
- 所有个位数是 0 的也不可能是回文数字。
翻转的话比较简单,通过将原来的数字进行取余得到对应的值,然后将当前值除10,与新形成的数进行比较大小,当原始数字小于或等于反转后的数字时,就意味着我们已经处理了一半位数的数字了。
代码
1 | class Solution { |
最长回文子串(5)
题目
给定一个字符串 s
,找到 s
中最长的回文子串。你可以假设 s
的最大长度为 1000。
示例
示例 1:
1 | 输入: "babad" |
示例 2:
1 | 输入: "cbbd" |
我的思路
- 最开始的想法是将源字符串翻转,然后判断翻转后的字符串和源字符串的最长公共子序列,但是貌似有点问题,例如
accbbdcca
翻转后变为accdbbcca
,最长公共子序列为acc
,但是最长回文子串为bb
。 - 但是上面的思路有可取之处,其实遇到回文子串最核心的问题是从中间开始依次比较左右是否相等,直到不相等,返回左右相等的子串,当然还有一个问题,就是该回文子串可能是单数,也可能是双数,单数的话,直接比较该数的左右即可,双数则需要先判断最开始两数是否相等。
- 时间复杂度是O(n²),空间复杂度O(1)
我的代码(AC)
美其名曰 中心扩展算法
1 | package Dynamic_Programming.最长回文子串; |
正确思路和代码
dp
1 | class Solution { |
关键就是暴力法: res[i][j] = (j <= i + 2) ? s1[i] == s1[j] : res[i+1][j-1] && s1[i] == s1[j];
上面就是dp最为关键的状态转移递推式,为什么在dp中不用考虑回文串长度的奇偶呢,因为我的方法中是从中间扩散,那么就必然需要分类,而dp是从两边向中间靠,要是回文串首尾必须相同,而当回文串小于等于3时,只要比较的首尾相等,则无需再比较,这样回文串的奇偶就不需要再考虑了。
细细想来,其实dp就是中心扩展方法的逆,一个是从中间向两边发散,一个是两边向中间靠拢!!
Tips:
注意边界处理,因为 str.substring 这个是不允许字符串为 null 的
时间复杂度为O(n²),空间复杂度为O(n²)
注意二维数组的维度分别是代表首和尾,子串是否为回文串取决于子子串和首尾是否相等,要注意base case是子串为1个字符时,它必为回文子串
最核心的就是状态转移的条件,是分为两种小情况,一种是当源字符串长度<=3时
- 当源字符串元素个数为3个,若左右边界相等,则去掉他们,只剩一个字符,必为回文串
- 当源字符串元素个数为2个,若左右边界相等,则必为回文串
此时该串是否为回文串就取决于首尾,另一种情况是当源字符串长度>3时,则需要判断首尾是否相等并且去除首尾后的子串是否为回文串
当发现有回文串时,则判断一下长度是否比之前发现的长,如果是,则记录长度,并且将最长回文串的起始位置拿到,最后全部循环完一遍后截取最长回文串即可
部分知识点补充
暂无
编辑距离(72)
题目描述
给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1:
1 | 输入:word1 = "horse", word2 = "ros" |
示例 2:
1 | 输入:word1 = "intention", word2 = "execution" |
代码
1 | class Solution { |
会议室 II(253)
题目描述
给定一个会议时间安排的数组,每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],…] (si < ei),为避免会议冲突,同时要考虑充分利用会议室资源,请你计算至少需要多少间会议室,才能满足这些会议安排。
示例 1:
1 | 输入: [[0, 30],[5, 10],[15, 20]] |
示例 2:
1 | 输入: [[7,10],[2,4]] |
思路
- 先将会议时间按照会议开始时间排序
- 将会议结束时间加入到优先级队列中
- 首先将最先开始的会议,其结束时间加入到优先级队列中
- 获取优先级队列中的队头数据,判断该结束时间是否早于下一个会议的开始时间
- 如果早于,则将该会议结束时间踢出队列,将下一个会议的结束时间加入队列中
- 如果不早于,说明存在重叠,优先级队列需要加入下一个会议的结束时间
- 优先级队列按照结束时间先后排序
- 优先级队列的数量就是会议室的个数
代码
1 | class Solution { |
不同的二叉搜索树(96)
题目描述
给定一个整数 n
,求以 1 ... n
为节点组成的二叉搜索树有多少种?
示例:
1 | 输入: 3 |
解法
原问题可拆解为子问题的求解。
二叉搜索树,可以分别以 1/2/3..n
做为根节点。所有情况累加起来,也就得到了最终结果。
res[n] 表示整数n组成的二叉搜索树个数。它的左子树可以有0/1/2...n-1
个节点,右子树可以有n-1/n-2...0
个节点。res[n] 是所有这些情况的加和。
时间复杂度分析:状态总共有 n
个,状态转移的复杂度是 O(n)
,所以总时间复杂度是 O(n²)
。
- 普通的dp
1 | class Solution { |
- 上面的解法明显还可以得到改进,因为左-右子树的节点个数为0,n-1,和左右子树节点个数为n-1,0。这两者的二叉搜索树的结果肯定是一致的,所以我们就没有必要算两遍。但是同时要考虑到奇偶的问题。
- 如果n=4,那么G(4) = G(0) G(3) + G(1) G(2) + G(2) G(1) + G(3) G(0) = 2[G(0) G(3) + G(1) G(2)]
- 如果n=5,那么G(5) = G(0) G(4) + G(1) G(3) + G(2) G(2) + G(3) G(1) + G(4) G(0) = 2[G(0) G(4) + G(1) G(3) ] + G(2) G(2)
1 | class Solution { |
知识点补充
- LeetCode二叉树专题——>DFS和BFS
不同的二叉搜索树II(95)
题目描述
给定一个整数 n,生成所有由 1 … n 为节点所组成的二叉搜索树。
示例
1 | 输入: 3 |
解释
1 | 以上的输出对应以下 5 种不同结构的二叉搜索树: |
解法
这题就是典型的运用递归去做,明确三个点:
- 递归出口
- 递归返回值
- 一级递归需要做什么
递归出口
当树没有节点了,递归结束,怎么表示树没有节点呢,所以就需新建一个函数,参数包括节点的起始和终止。
递归返回值
返回值很明显就是符合条件
的各种二叉树,是一个含根节点的列表(根据题目最终需要得到的)。
一级递归需要做什么
这个是比较难的地方,我们来缕缕现在有什么,我们现在有三个节点,根节点,左子树根节点,右子树根节点,这三个节点我们可以随意将任意一个节点当做根节点,然后去组合得到新的搜索二叉树。注意!!!我们只需要关注一级递归就可以了,无需关注太多,我们现在手上假设就三个节点分别是1,2,3,首先要做的就是遍历1,2,3,分别将其作为根节点,假设以2为根节点,1代表就是左子树返回的根节点列表,3代表的是右子树返回的根节点列表,我们要做的就是遍历左右子树的根节点列表,分别将其添加到根节点的左右子树,然后将该根节点添加至列表,返回列表即可。
代码
1 | /** |
部分知识点补充
明天继续进军二叉树部分 同时复习并且捡回来原先要完成的集合那部分的源码分析!(2020.1.1)
杨辉三角(118)
Tip:今天第一次写题解,还是非常开心的!!!!!
今天重点就是掌握了一下递归的思想,最重要的三点!!!!!
递归思想
- 找整个递归的终止条件
- 找返回值
- 本地递归需要如何操作
主要参考:递归
题目描述
给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。
在杨辉三角中,每个数是它左上方和右上方的数的和。
示例:
1 | 输入: 5 |
思路
方法一:递归
递归方法总而言之就是抓住三点:
- 找整个递归的终止条件
- 找返回值
- 一次递归需要如何操作
找整个递归的终止条件
咱来分析一下题目,递归到numRows = 0
时或者numRows = 1
时都可以终止,因为第一行比较特殊,只有一个1
,所以我们可以将其当成整个递归的终止条件,当numRows = 1
时,我们就可以终止递归向下返回值了。
找返回值
找返回值,我们也需要分析下,题目要我们求的是整个杨辉三角的所有数,那最后递归得到的应该就是 List<List<Integer>>
(题目给定),也就是每递归完一层,我们就更新完List并返回即可,最后递归完成就是我们要的答案。
一次递归需要如何操作
递归的难点就在这里,很多童靴刚学递归时,总是在这里搞晕,其实我们只需要关注一次递归即可,因为每一层递归的过程都是一样的,我们只需要找到最上层的递归的规律,就可以了。
如图所示,我们只需要分析第二行到第三行这级递归即可!先上代码!
递归 代码
1 | class Solution { |
方法二:动态规划
思路其实差不多,只是一个递归,一个变成了迭代而,仅此而已!
1 | class Solution { |
单词拆分(139)
题目
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明:
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
示例
示例 1:
1 | 输入: s = "leetcode", wordDict = ["leet", "code"] |
示例 2:
1 | 输入: s = "applepenapple", wordDict = ["apple", "pen"] |
1 | 示例 3: |
代码
1 | class Solution { |
解码方法(91)
题目描述
1 | 一条包含字母 A-Z 的消息通过以下方式进行了编码: |
示例
1 | 示例 1: |
思路
所有可以用dp的,基本都有三个方法:
递归 ——-> 带备忘录的自顶向下 ——-> dp
递归
1 | class Solution { |
带备忘录的自顶向下
1 | class Solution { |
dp
注意:难点在处理'0'
,'00'
等边界问题!尤其是在dp[n]、dp[n-1]的赋值问题上有一点难度,而且,这个由于是倒序的,跟平时处理的dp问题略微有些许不同,以前是dp[1]对应第一个字符,而这里是dp[0]对应第一个字符。
1 | class Solution { |
1 | class Solution { |
零钱兑换(322)
题目
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。
示例 1:
1 | 输入: coins = [1, 2, 5], amount = 11 |
示例 2:
1 | 输入: coins = [2], amount = 3 |
思路
一维dp数组,简单的一批…
代码
1 | // import java.util.Arrays; |
回文子串(647)
题目
给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。
思路
思路同第5题!!!!“最长回文子串”
代码
1 | class Solution { |
环形链表I(141)
题目
给定一个链表,判断链表中是否有环。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
思路
- 方法一:使用
Set集合
存储已经出现过的节点,如果再次出现,则直接返回true,如果没有再出现,则一定会有null节点的出现。 - 方法二:运用快慢指针的方法,快指针走得快,如果遍历到null节点,则说明不存在环,如果快指针和慢指针会相遇,则说明存在环。
代码
- 方法一
1 | public class Solution { |
- 方法二
1 | public class Solution { |
环形链表 II(142)
这个题翻译的一坨屎…题目整来整去不知道在说什么,真的是服了耶!
其实题目就一个意思,给定一个有环链表,要你返回环的入口!
思路
这种思路都要讲烂了吧..就是使用快慢指针,第一次相遇后,快指针继续走,慢指针回到起点,第二次相遇的地方就是环的起点。
代码
1 | /** |
寻找两个有序数组的中位数(4)
题目
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
1 | nums1 = [1, 3] |
示例 2:
1 | nums1 = [1, 2] |
思路
- 如果没有时间复杂度的话,那这道题有非常多的思路可以做,可以先排序再取中位数,可以采用两个有序数组进行
归并排序
,这样的时间复杂度为O(m+n)
,达不到O(log(m+n))
- 看到
log(m+n)
,就应该想到二分查找,这道题也的确可以用二分去做。首先我们明确一下这里的中位数是什么意思?这里说的是求两个有序数组(m + n)的中位数,如果 m + n 为奇数,则中位数的下标为 (m + n + 1)/2 [下标从1开始!],如果 m + n 为偶数,则中位数的值为下标为 (m + n + 1)/2 、(m + n + 2)/2的数的平均值,所以其实可以统一一下,也就是不论奇数还是偶数,中位数的值 = 下标为 (m + n + 1)/2 、(m + n + 2)/2的数的平均值!!!所以问题就转换为求第 (m + n + 1)/2、 (m + n + 2)/2大的数了,至于求第K大的数问题,这个方法就很多了,从远古的快排到堆排序,待会会拓展一下!回到正题,如何在两个有序数组中间取到第K大的数还必须是log
级别的时间复杂度,那只能选择二分了,这里的二分比较特殊,是对两个数组取第K/2大的数,有人会问了,为何是这样取呢?因为在每次划分的时候,我们都要确保第K大的数未被去除,所以两个数组分别取K/2,这样能确保有 m + n - k个数是一定大于我们要取的数的,也就是说,我们的二分,就是一步步去除比中位数小的数,直到遍历到中位数为止,而什么时候能遍历到中位数呢?难点就在于边界比较复杂,比如:数组长度过短导致取不到K/2、K如果为1的话是不能取K/2的(下标从1开始,这样会越界)、单个数组可能已经遍历完另外一个还没遍历完等等。
代码实现
方法一
方法二
1 | /** |
电话号码的字母组合(17)
题目
给定一个仅包含数字 2-9
的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例:
1 | 输入:"23" |
思路
队列
先定义一个String字符串数组,然后遍历输入的数字,拿到每一个数字,然后利用队列,先将前一次循环的字符串遍历(这里非常巧妙,因为 i 从 0 开始,那么第 n 次循环的 i 为 n-1 ,即是前一次循环的字符串的长度),每次遍历前一次循环的字符串,就将其出队列,然后将新的字符串拼接好直接放入队列,类似于树的层序遍历,只是这里非常巧妙地运用了队头元素的长度和 i 的关系。
回溯
回溯是一种通过穷举所有可能情况来找到所有解的算法。如果一个候选解最后被发现并不是可行解,回溯算法会舍弃它,并在前面的一些步骤做出一些修改,并重新尝试找到可行解。
给出如下回溯函数 backtrack(combination, next_digits)
,它将一个目前已经产生的组合 combination
和接下来准备要输入的数字 next_digits
作为参数。
如果没有更多的数字需要被输入,那意味着当前的组合已经产生好了。
如果还有数字需要被输入:
遍历下一个数字所对应的所有映射的字母。
将当前的字母添加到组合最后,也就是 combination = combination + letter
。
重复这个过程,输入剩下的数字: backtrack(combination + letter, next_digits[1:])
。
代码实现
队列实现
1 | class Solution { |
回溯实现
1 | class Solution { |
有效的括号(20)
题目
给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
思路
使用栈,这里可以将期望的字符串压栈。
代码
1 | class Solution { |
括号生成(22)
题目
给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。
例如,给出 n = 3,生成结果为:
1 | [ |
思路
dp
简单来说,在求N个括号的排列组合时,把第N种情况(也就是N个括号排列组合)视为单独拿一个括号E出来,剩下的N-1个括号分为两部分,P个括号和Q个括号,P+Q=N-1,然后这两部分分别处于括号E内和括号E的右边,各自进行括号的排列组合。由于我们是一步步计算得到N个括号的情况的,所以小于等于N-1个括号的排列组合方式我们是已知的(用合适的数据结构存储,方便后续调用,且在存储时可利用特定数据结构实现题目某些要求,如排序,去重等),且P+Q=N-1,P和Q是小于等于N-1的,所以我们能直接得到P个和Q个括号的情况,进而得到N个括号的结果!
这个算法主要的基点就是将排列组合的情况分为了括号内和括号外这两种情况,且仅存在两种情况!至于为什么,原因在于楼主的算法的前提是单独拿出来的括号E的左边在N个括号所有排列组合情况中都是处于最左边,所以不存在括号位于括号E的左边的情况。因此,N-1个括号(拿出了括号E)仅可能分布于括号E内和括号E外,分为两种子情况讨论! 这种思想还可以应用于其他类似的题的求解中,即怎样合理高效的利用前面步骤的计算结果得出当前步骤结果,从而得出最终结果。
递归
只有在我们知道序列仍然保持有效时才添加 ‘(‘ or ‘)’,我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点,如果我们还剩一个位置,我们可以开始放一个左括号。 如果它不超过左括号的数量,我们可以放一个右括号。
代码实现
dp
1 | class Solution { |
递归
1 | /** |
下一个排列(31)
题目
实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须 原地
修改,只允许使用额外常数空间。
以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
1 | 1,2,3 → 1,3,2 |
思路
- 从右向左,找到第一个非倒序的数字,例如上面的
158476531
,从右向左的第一个非倒序的数字是4
- 然后再从右向左遍历一次,找到第一个比4大的数,这里是右边数第三个
5
,交换4
和5
,数字变为158576431
,这显然不是我们要的答案 - 然后将
5
后面的数字翻转,也就是将76431
翻转,于是数字变为158513467
代码实现
1 | class Solution { |
最长有效括号(32)
题目
给定一个只包含 ‘(‘ 和 ‘)’ 的字符串,找出最长的包含有效括号的子串的长度。
示例 1:
1 | 输入: "(()" |
示例 2:
1 | 输入: ")()())" |
思路
思路一:栈 + dp
前文第20题
有效的括号
,就是采用栈
去做的,那么这个很自然的也同样是采用栈去做,凡是碰到了括号,基本都是用栈去做处理,因为符合后进先出的原则。然后又是寻找子串长度,那自然是要用到dp,故采用的方法很明显就是栈 + dp。
思路二:栈
与找到每个可能的子字符串后再判断它的有效性不同,我们可以用栈在遍历给定字符串的过程中去判断到目前为止扫描的子字符串的有效性,同时都是最长有效字符串的长度。我们首先将 −1 放入栈顶。对于遇到的每个 ‘(’ ,我们将它的下标放入栈中。对于遇到的每个 ‘)’ ,我们弹出栈顶的元素并将当前元素的下标与弹出元素下标作差,得出当前有效括号字符串的长度。通过这种方法,我们继续计算有效子字符串的长度,并最终返回最长有效子字符串的长度
我认为这种思路最精妙的地方在于他提前压栈了-1,这是这个方法最妙的地方,而在遍历元素时,每次都会有压栈或者弹栈的操作,这样就能知道最长有效字符串的长度,因为一旦不是有效字符串了,栈就会变空,下一个填入的一定是有效字符串的前一位…不过我还是觉得我的方法更容易让人理解,这个方法只能欣赏了。
作者:LeetCode
链接:https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
代码
- 思路一
1 | class Solution { |
- 思路二 【精妙无比,适当记忆】
1 | public class Solution { |
将矩阵按对角线排序(5152)
题目
给你一个 m * n 的整数矩阵 mat ,请你将同一条对角线上的元素(从左上到右下)按升序排序后,返回排好序的矩阵。
示例 1:
1 | 输入:mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]] |
思路
- 使用的是 N皇后 问题的编码技巧:主对角线上元素的特点是:纵坐标 - 横坐标 = 定值 【难点】
- 为了能够放进数组中,加上偏移 m - 1 。【难点】
- 两次遍历:第一次遍历把数据拷贝到对角线数组中,然后排序;第二次遍历把对角线数组写回原始数组(或者新开一个数组)均可。
作者:liweiwei1419
链接:https://leetcode-cn.com/problems/sort-the-matrix-diagonally/solution/bao-li-jie-fa-by-liweiwei1419/
来源:力扣(LeetCode)
代码
1 | import java.util.ArrayList; |
作者:liweiwei1419
链接:https://leetcode-cn.com/problems/sort-the-matrix-diagonally/solution/bao-li-jie-fa-by-liweiwei1419/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
N皇后(51)
回溯算法
这篇文章是很久之前的一篇《回溯算法详解》的进阶版,之前那篇不够清楚,就不必看了,看这篇就行。把框架给你讲清楚,你会发现回溯算法问题都是一个套路。
废话不多说,直接上回溯算法框架。解决一个回溯问题,实际上就是一个决策树的遍历过程。你只需要思考 3 个问题:
1、路径:也就是已经做出的选择。 2、选择列表:也就是你当前可以做的选择。 3、结束条件:也就是到达决策树底层,无法再做选择的条件。如果你不理解这三个词语的解释,没关系,我们后面会用「全排列」和「N 皇后问题」这两个经典的回溯算法问题来帮你理解这些词语是什么意思,现在你先留着印象。
代码方面,回溯算法的框架:
1 | result = [] |
其核心就是 for 循环里面的递归,在递归调用之前「做选择」,在递归调用之后「撤销选择」,特别简单。
什么叫做选择和撤销选择呢,这个框架的底层原理是什么呢?下面我们就通过「全排列」这个问题来解开之前的疑惑,详细探究一下其中的奥妙!
一、全排列问题
我们在高中的时候就做过排列组合的数学题,我们也知道 n 个不重复的数,全排列共有 n! 个。
PS:为了简单清晰起见,我们这次讨论的全排列问题不包含重复的数字。
那么我们当时是怎么穷举全排列的呢?比方说给三个数 [1,2,3],你肯定不会无规律地乱穷举,一般是这样:
先固定第一位为 1,然后第二位可以是 2,那么第三位只能是 3;然后可以把第二位变成 3,第三位就只能是 2 了;然后就只能变化第一位,变成 2,然后再穷举后两位……
其实这就是回溯算法,我们高中无师自通就会用,或者有的同学直接画出如下这棵回溯树:
只要从根遍历这棵树,记录路径上的数字,其实就是所有的全排列。我们不妨把这棵树称为回溯算法的「决策树」。
为啥说这是决策树呢,因为你在每个节点上其实都在做决策。比如说你站在下图的红色节点上:
你现在就在做决策,可以选择 1 那条树枝,也可以选择 3 那条树枝。为啥只能在 1 和 3 之中选择呢?因为 2 这个树枝在你身后,这个选择你之前做过了,而全排列是不允许重复使用数字的。
现在可以解答开头的几个名词:[2] 就是「路径」,记录你已经做过的选择;[1,3] 就是「选择列表」,表示你当前可以做出的选择;「结束条件」就是遍历到树的底层,在这里就是选择列表为空的时候。如果明白了这几个名词,可以把「路径」和「选择」列表作为决策树上每个节点的属性,比如下图列出了几个节点的属性:
我们定义的 backtrack 函数其实就像一个指针,在这棵树上游走,同时要正确维护每个节点的属性,每当走到树的底层,其「路径」就是一个全排列。
再进一步,如何遍历一棵树?这个应该不难吧。回忆一下之前「学习数据结构的框架思维」写过,各种搜索问题其实都是树的遍历问题,而多叉树的遍历框架就是这样:
1 | void traverse(TreeNode root) { |
而所谓的前序遍历和后序遍历,他们只是两个很有用的时间点,我给你画张图你就明白了:
前序遍历的代码在进入某一个节点之前的那个时间点执行,后序遍历代码在离开某个节点之后的那个时间点执行。
回想我们刚才说的,「路径」和「选择」是每个节点的属性,函数在树上游走要正确维护节点的属性,那么就要在这两个特殊时间点搞点动作:
现在,你是否理解了回溯算法的这段核心框架?
1 | for 选择 in 选择列表: |
我们只要在递归之前做出选择,在递归之后撤销刚才的选择,就能正确得到每个节点的选择列表和路径。
下面,直接看全排列代码:
1 | List<List<Integer>> res = new LinkedList<>(); |
我们这里稍微做了些变通,没有显式记录「选择列表」,而是通过 nums 和 track 推导出当前的选择列表:
至此,我们就通过全排列问题详解了回溯算法的底层原理。当然,这个算法解决全排列不是很高效,应为对链表使用 contains 方法需要 O(N) 的时间复杂度。有更好的方法通过交换元素达到目的,但是难理解一些,这里就不写了,有兴趣可以自行搜索一下。
但是必须说明的是,不管怎么优化,都符合回溯框架,而且时间复杂度都不可能低于 O(N!),因为穷举整棵决策树是无法避免的。这也是回溯算法的一个特点,不像动态规划存在重叠子问题可以优化,回溯算法就是纯暴力穷举,复杂度一般都很高。
明白了全排列问题,就可以直接套回溯算法框架了,下面简单看看 N 皇后问题。
二、N 皇后问题
这个问题很经典了,简单解释一下:给你一个 N×N 的棋盘,让你放置 N 个皇后,使得它们不能互相攻击。
PS:皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。
这个问题本质上跟全排列问题差不多,决策树的每一层表示棋盘上的每一行;每个节点可以做出的选择是,在该行的任意一列放置一个皇后。
直接套用框架:
1 | vector<vector<string>> res; |
这部分主要代码,其实跟全排列问题差不多,isValid 函数的实现也很简单:
1 | /* 是否可以在 board[row][col] 放置皇后? */ |
函数 backtrack 依然像个在决策树上游走的指针,通过 row 和 col 就可以表示函数遍历到的位置,通过 isValid 函数可以将不符合条件的情况剪枝:
如果直接给你这么一大段解法代码,可能是懵逼的。但是现在明白了回溯算法的框架套路,还有啥难理解的呢?无非是改改做选择的方式,排除不合法选择的方式而已,只要框架存于心,你面对的只剩下小问题了。
当 N = 8 时,就是八皇后问题,数学大佬高斯穷尽一生都没有数清楚八皇后问题到底有几种可能的放置方法,但是我们的算法只需要一秒就可以算出来所有可能的结果。
不过真的不怪高斯。这个问题的复杂度确实非常高,看看我们的决策树,虽然有 isValid 函数剪枝,但是最坏时间复杂度仍然是 O(N^(N+1)),而且无法优化。如果 N = 10 的时候,计算就已经很耗时了。
有的时候,我们并不想得到所有合法的答案,只想要一个答案,怎么办呢?比如解数独的算法,找所有解法复杂度太高,只要找到一种解法就可以。
其实特别简单,只要稍微修改一下回溯算法的代码即可:
1 | // 函数找到一个答案后就返回 true |
这样修改后,只要找到一个答案,for 循环的后续递归穷举都会被阻断。也许你可以在 N 皇后问题的代码框架上,稍加修改,写一个解数独的算法?
三、最后总结
回溯算法就是个多叉树的遍历问题,关键就是在前序遍历和后序遍历的位置做一些操作,算法框架如下:
1 | def backtrack(...): |
写 backtrack 函数时,需要维护走过的「路径」和当前可以做的「选择列表」,当触发「结束条件」时,将「路径」记入结果集。
其实想想看,回溯算法和动态规划是不是有点像呢?我们在动态规划系列文章中多次强调,动态规划的三个需要明确的点就是「状态」「选择」和「base case」,是不是就对应着走过的「路径」,当前的「选择列表」和「结束条件」?
某种程度上说,动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质,可以用 dp table 或者备忘录优化,将递归树大幅剪枝,这就变成了动态规划。而今天的两个问题,都没有重叠子问题,也就是回溯算法问题了,复杂度非常高是不可避免的。
作者:labuladong
链接:https://leetcode-cn.com/problems/n-queens/solution/hui-su-suan-fa-xiang-jie-by-labuladong/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
Tip: Java写法 【N皇后】
1 | class Solution { |
代码来自:
接雨水(42)
题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例:
1 | 输入: [0,1,0,2,1,0,1,3,2,1,2,1] |
思路
见代码
代码
1 | /** |
搜索旋转排序数组(33)
题目
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
1 | 示例 1: |
思路
题目要求 O(logN) 的时间复杂度,基本可以断定本题是需要使用二分查找,怎么分是关键。
由于题目说数字了无重复,举个例子:1 2 3 4 5 6 7
可以大致分为两类,
第一类 2 3 4 5 6 7 1
这种,也就是 nums[start] <= nums[mid]。此例子中就是 2 <= 5
。
这种情况下,前半部分有序。因此如果 nums[start] <=target<nums[mid],则在前半部分找,否则去后半部分找。
第二类 6 7 1 2 3 4 5
这种,也就是 nums[start] > nums[mid]。此例子中就是 6 > 2
。
这种情况下,后半部分有序。因此如果 nums[mid] <target<=nums[end],则在后半部分找,否则去前半部分找。
此题有个存在重复数字的变形题,可参考 此题解 。
作者:reedfan
链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/ji-bai-liao-9983de-javayong-hu-by-reedfan/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
代码实现
1 | class Solution { |
1 | class Solution { |
Tip: 81题思路一样
1 | class Solution { |
在排序数组中查找元素的第一个和最后一个位置(34)
题目
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值,返回 [-1, -1]。
1 | 示例 1: |
思路
见 labuladong 公众号笔记
实现代码
1 | class Solution { |
组合总和(39)
题目
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
- 所有数字(包括
target
)都是正整数。 - 解集不能包含重复的组合。
示例 1:
1 | 输入: candidates = [2,3,6,7], target = 7, |
示例 2:
1 | 输入: candidates = [2,3,5], target = 8, |
思路
直接上回溯算法框架。解决一个回溯问题,实际上就是一个决策树的遍历过程。你只需要思考 3 个问题:
1、路径:也就是已经做出的选择。 2、选择列表:也就是你当前可以做的选择。 3、结束条件:也就是到达决策树底层,无法再做选择的条件。代码方面,回溯算法的框架:
1 | result = [] |
其核心就是 for 循环里面的递归,在递归调用之前「做选择」,在递归调用之后「撤销选择」,特别简单。
labuladong 回溯框架!!!老哥写的文章真是干净利落!
demo(全排列)
1 | List<List<Integer>> res = new LinkedList<>(); |
代码实现
先按照demo写一个差不多的,这个暂时无法做到去重!
1 | public class combinationSum_39 { |
1 | 输出:[[2, 2, 3], [2, 3, 2], [3, 2, 2], [7]] |
去重之后的代码:
1 | public class combinationSum_39 { |
1 | 输出:[[2, 2, 3], [7]] |
LRU缓存机制(146)
题目
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。
相信如果有认真看过 LinkedHashMap 源码的小伙伴,一定会很快的跟官方题解写的一模一样!
简单介绍LinkedHashMap(跟题目有关的知识点)
HashMap 大家都清楚,底层是 数组 + 红黑树 + 链表 (不清楚也没有关系),同时其是无序的,而 LinkedHashMap 刚好就比 HashMap 多这一个功能,就是其提供 有序,并且,LinkedHashMap的有序可以按两种顺序排列,一种是按照插入的顺序,一种是按照读取的顺序(这个题目的示例就是告诉我们要按照读取的顺序进行排序),而其内部是靠 建立一个双向链表 来维护这个顺序的,在每次插入、删除后,都会调用一个函数来进行 双向链表的维护 ,准备的来说,是有三个函数来做这件事,这三个函数都统称为 回调函数 ,这三个函数分别是:
void afterNodeAccess(Node p) { }
其作用就是在访问元素之后,将该元素放到双向链表的尾巴处(所以这个函数只有在按照读取的顺序的时候才会执行),之所以提这个,是建议大家去看看,如何优美的实现在双向链表中将指定元素放入链尾!
void afterNodeRemoval(Node p) { }
其作用就是在删除元素之后,将元素从双向链表中删除,还是非常建议大家去看看这个函数的,很优美的方式在双向链表中删除节点!
void afterNodeInsertion(boolean evict) { }
这个才是我们题目中会用到的,在插入新元素之后,需要回调函数判断是否需要移除一直不用的某些元素!
其次,我再介绍一下 LinkedHashMap 的构造函数!
其主要是两个构造方法,一个是继承 HashMap ,一个是可以选择 accessOrder 的值(默认 false,代表按照插入顺序排序)来确定是按插入顺序还是读取顺序排序。
1 | /** |
思路 & 代码
下面是我自己在分析 LinkedHashMap 源码时做的一些笔记,应该是比较清楚的,主体意思就是我们要继承 LinkedHashMap,然后复写 removeEldestEntry()函数,就能拥有我们自己的缓存策略!
1 | // 在插入一个新元素之后,如果是按插入顺序排序,即调用newNode()中的linkNodeLast()完成 |
通过上述代码,我们就已经知道了只要复写 removeEldestEntry() 即可,而条件就是 map 的大小不超过 给定的容量,超过了就得使用 LRU 了!然后根据题目给定的语句构造和调用:
1 |
|
很明显我们只需要直接继承父类的put函数即可,因为题目没有特殊要求,故可以不写!至于 get() 函数,题目是有要求的!
获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
所以我们可以调用 LinkedHashMap 中的 getOrDefault(),完美符合这个要求,即当key不存在时会返回默认值 -1。
至此,我们就基本完成了本题的要求,只要写一个构造函数即可,答案的 super(capacity, 0.75F, true);
,没看过源码的小伙伴可能不太清楚这个构造函数,这就是我上文讲的 LinkedHashMap 中的常用的第二个构造方法,具体大家可以看我上面代码的注释!
至此,大功告成!
1 |
|
Tip: 自己实现:
1 | class LRUCache { |
最大频率栈(895)
题目
设计一个类似堆栈的数据结构,将元素推入堆栈,并从堆栈中弹出出现频率最高的元素。
实现 FreqStack 类:
- FreqStack() 构造一个空的堆栈。
- void push(int val) 将一个整数 val 压入栈顶。
- int pop() 删除并返回堆栈中出现频率最高的元素。
- 如果出现频率最高的元素不只一个,则移除并返回最接近栈顶的元素。
示例 1:
1 | 输入: |
思路
- 思路一:使用两个哈希表,一个哈希表存数值对应出现的次数,另外一个则存储当前所有数据中,出现次数为 n 所对应的元素有哪些
- 思路二:与上述思想类似,用一个哈希表和栈来解决,其中用哈希表 freq 来记录每个元素出现的次数,设当前最大频率为 maxFreq,再将 1 ~ maxFreq 的每种频率单独设置一个栈,为了方便描述,设置 freq[x] 为 x 的频率,group[i] 为频率为 i 的栈
代码
思路一:
1 | class FreqStack { |
思路2:
1 | class FreqStack { |
LFU缓存(460)
题目
请你为 最不经常使用(LFU)缓存算法设计并实现数据结构。
实现 LFUCache 类:
- LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
- int get(int key) - 如果键 key 存在于缓存中,则获取键的值,否则返回 -1 。
- void put(int key, int value) - 如果键 key 已存在,则变更其值;如果键不存在,请插入键值对。当缓存达到其容量 capacity 时,则应该在插入新项之前,移除最不经常使用的项。在此问题中,当存在平局(即两个或更多个键具有相同使用频率)时,应该去除 最近最久未使用 的键。
为了确定最不常使用的键,可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。
当一个键首次插入到缓存中时,它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作,使用计数器的值将会递增。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
思路
见题解:https://leetcode.cn/problems/lfu-cache/solution/chao-xiang-xi-tu-jie-dong-tu-yan-shi-460-lfuhuan-c/
代码
1 | import java.util.HashMap; |
排序链表(148)
题目
在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。
示例 1:
1 | 输入: 4->2->1->3 |
示例 2:
1 | 输入: -1->5->3->4->0 |
思路
题目要求时间空间复杂度分别为 O(nlogn) 和 O(1),根据时间复杂度我们自然想到二分法,从而联想到归并排序;
对数组做归并排序的空间复杂度为 O(n) ,分别由新开辟数组 O(n) 和递归函数调用 O(logn) 组成,而根据链表特性:
- 数组额外空间:链表可以通过修改引用来更改节点顺序,无需像数组一样开辟额外空间;
- 递归额外空间:递归调用函数将带来 O(logn) 的空间复杂度,因此若希望达到 O(1) 空间复杂度,则不能使用递归。 【这里咱还是用下递归,降低难度!】
通过递归实现链表归并排序,有以下两个环节:
- 分割 cut 环节: 找到当前链表中点,并从中点将链表断开(以便在下次递归 cut 时,链表片段拥有正确边界);
- 我们使用 fast,slow 快慢双指针法,奇数个节点找到中点,偶数个节点找到中心左边的节点。
- 找到中点 slow 后,执行 slow.next = None 将链表切断。
- 递归分割时,输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp(因为链表是从 slow 切断的)。
- cut 递归终止条件: 当head.next == None时,说明只有一个节点了,直接返回此节点。
- 合并 merge 环节: 将两个排序链表合并,转化为一个排序链表。
- 双指针法合并,建立辅助ListNode h 作为头部。
- 设置两指针 left, right 分别指向两链表头部,比较两指针处节点值大小,由小到大加入合并链表头部,指针交替前进,直至添加完两个链表。
- 返回辅助ListNode h 作为头部的下个节点 h.next。
- 时间复杂度 O(l + r),l, r 分别代表两个链表长度。
- 当题目输入的 head == None 时,直接返回None。
- 分割 cut 环节: 找到当前链表中点,并从中点将链表断开(以便在下次递归 cut 时,链表片段拥有正确边界);
代码
1 | class Solution { |
作者:jyd
链接:https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
不符合时间复杂度的路过一下:
1 | public ListNode sortList(ListNode head) { |
路径总和 III(437)
题目
给定一个二叉树,它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。
示例:
1 | root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 |
思路
回溯,只不过这里的选择条件,比较特殊,并且 做选择 和 撤销选择 得稍微注意一下,这里可以直接用 if else。
代码
1 | /** |
二叉树中的最大路径和(124)
题目
给定一个非空二叉树,返回其最大路径和。
本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。
示例 1:
1 | 输入: [1,2,3] |
示例 2:
1 | 输入: [-10,9,20,null,null,15,7] |
思路
这题还是挺难的,要求最大路径和,可以采用递归,递归就是三部曲:
1、确定递归出口,这个简单,root == null 即退出
2、确定返回值,这个是本题最难的,返回的是以该节点结尾的最大路径和!!!
3、一级递归需要做的事,其实就是去算最大的路径和,这个很简单,在二叉树中,一级递归其实也就是三个节点,分别是根节点,左子树节点,右子树节点,既然每个节点返回的是 以该节点结尾的最大路径和,则我们可以在每级递归时去更新一下最大的路径和,即 左子树节点返回来的以其节点结尾的最大路径和 + 根节点的值 + 右子树节点返回的以该节点结尾的最大路径和。
代码
1 | class Solution { |
旋转图像(48)
题目
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明:
你必须在原地旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例 1:
1 | 给定 matrix = |
示例 2:
1 | 给定 matrix = |
思路
翻转 + 转置
代码
1 | //1.先转置再翻转,注意这里翻转是 行 翻转,比如 第一行 1 2 3,行翻转变为 3 2 1 |
螺旋矩阵—回形打印二维数组(54)
题目
给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。
示例 1:
1 | 输入: |
示例 2:
1 | 输入: |
思路
这里的方法不需要记录已经走过的路径,所以执行用时和内存消耗都相对较小
- 首先设定上下左右边界
- 其次向右移动到最右,此时第一行因为已经使用过了,可以将其从图中删去,体现在代码中就是重新定义上边界
- 判断若重新定义后,上下边界交错,表明螺旋矩阵遍历结束,跳出循环,返回答案
- 若上下边界不交错,则遍历还未结束,接着向下向左向上移动,操作过程与第一,二步同理
- 不断循环以上步骤,直到某两条边界交错,跳出循环,返回答案
作者:youlookdeliciousc
链接:https://leetcode-cn.com/problems/spiral-matrix/solution/cxiang-xi-ti-jie-by-youlookdeliciousc-3/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
代码
1 | class Solution { |
螺旋矩阵 II(59)
题目
给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
1 | 输入: 3 |
思路
跟 螺旋矩阵
思路一模一样,只是上面是按回形读取数组元素,这里是按照回形放置元素到数组中,一模一样。
代码
1 | class Solution { |
字母异位词分组(49)
题目
给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。
示例:
1 | 输入: ["eat", "tea", "tan", "ate", "nat", "bat"], |
说明:
- 所有输入均为小写字母。
- 不考虑答案输出的顺序。
思路
- 每个单词进行字母排序,排完序后存入map中,key相同的存入同一个list中即可。
- 每个单词都是由 26 个字母组成的,这个方法无需对每个单词的字母进行排序,类似于桶的概念,每个单词不同的字符放入 26 个桶中,字母异位词对应的桶中的数值应该是一样的,将桶中数据相同的字母当成一个key,存入map中,然后key相同的存入同一个list中,我个人认为这种方法对字母很多很多的单词是非常有用的,时间复杂度上更小。
代码
思路一
1 | class Solution { |
思路二
1 | class Solution { |
只出现一次的数字(136)
题目
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
1 | 输入: [2,2,1] |
示例 2:
1 | 输入: [4,1,2,1,2] |
思路
- 拿到手,要求时间复杂度在 O( n ),第一反应是使用哈希表 HashMap 来完成,遍历一遍数组,然后找到 value == 1的即可,时间复杂度 O(n),空间复杂度为O(n)。
- 但是题目要求不使用额外空间,即空间复杂度 O(1),这个就很难了,只能暴力法,就是每查一个数字,我们就去剩下的数字中去找,如果找不到,即使我们需要的,但是这个时间复杂度是O(n²)。
- 最后一个是最骚的,直接异或就行了…
代码
1 | class Solution { |
跳跃游戏(55)
题目
给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
1 | 输入: [2,3,1,1,4] |
示例 2:
1 | 输入: [3,2,1,0,4] |
思路
- 回溯
- 贪心算法,每次都找到能跳到的最远距离,然后在原地到最远距离之间遍历,看能否继续跳到更远,如果可以,就更新最远距离值,如果最远距离值能够不小于最后一个位置,说明可以跳到,否则不行。
- 评论区看到的,其实跟贪心算法思想类似,但是又有点不一样,就是记录每个节点能跳到的最远距离,不断更新最远距离,如果有某个节点的下标比k值大,说明到不了该节点,即有个挡板挡在了这个节点之前,过不来,此时就是无法到达最后一个节点,如果全程都没有被挡板挡住,且挡板的值过了最后一个位置,即可以到达最后一个位置。
代码
- 回溯【超出时间限制】
1 | class Solution { |
- 贪心
1 | class Solution { |
- 评论区神仙
1 | class Solution { |
合并区间(56)
题目
给出一个区间的集合,请合并所有重叠的区间。
示例 1:
1 | 输入: [[1,3],[2,6],[8,10],[15,18]] |
示例 2:
1 | 输入: [[1,4],[4,5]] |
思路
先按首位置进行排序;
接下来,如何判断两个区间是否重叠呢?比如 a = [1,4],b = [2,3]
当 a[1] >= b[0] 说明两个区间有重叠
但是如何把这个区间找出来呢?
左边位置一定是确定,就是 a[0],而右边位置是 max(a[1], b[1])
所以,我们就能找出整个区间为:[1,4]
代码
1 | class Solution { |
颜色分类(75)
题目
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
1 | 输入: [2,0,2,1,1,0] |
进阶:
- 一个直观的解决方案是使用计数排序的两趟扫描算法。首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。
- 你能想出一个仅使用常数空间的一趟扫描算法吗?
思路
三路归并,其实也是 Arrays.sort() 这里采用的方法,也是三色旗的解决方案。
三个指针,分别是 left、cur、right。left指向数组最左侧,right指向数组最右侧,cur代表当前正在遍历的数组元素,当 cur 遍历的元素是 0 时,将 cur 指向的元素 与 p0 指向的元素交换,然后 cur++,p0++。当 cur 遍历的元素是 1 时,cur++。当 cur 遍历的元素是 2 时,将 cur 指向的元素与 p2 指向的元素交换,然后 p2–,cur不动!!!直到 cur > p2 ,循环结束(即全部扫描完毕)。
对于以上,有一个难点!
- 为何 cur 在与 p0 交换时需要 p0++,cur++;而在 cur 与 p2 交换时,却只需要 p2–?
对于上面这个问题,有两种解释思路:1.cur 与 p0 交换需要自加,是因为其左边已经扫描过了,交换过来的值也是之前就扫描过了的,而右边不是, p2 d交换过来的值 cur 并没有扫描过;2.当 cur 与 p0 不是一个指向同一个索引值时,那 cur 指向的索引值如果发生交换,那交换过来的一定是 1(原因是只有当遍历过的节点有1,p0 和 cur 才不会同步),而 如果索引是 1 刚好也就不用有任何操作,所以可以直接继续向右扫描,当 cur 和 p0 指向的是同一个索引,那交换就等于没交换,故也是直接可以向右扫描,右边的就不行。
代码
1 | class Solution { |
子集(78)
题目
给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
1 | 输入: nums = [1,2,3] |
思路
很明显,一看就是回溯,思路跟 全排列、N 皇后问题一样
代码
1 | class Solution { |
单词搜索(79)
题目
给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
1 | board = |
思路
依旧是… 回溯
代码
1 | class Solution { |
柱状图中最大的矩形(84)
题目
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为 [2,1,5,6,2,3]
。
思路
暴力法,每个高度都计算一遍最长的连续的底,然后取最大值。
其实这道题的本质就是转化为求每个高度对应的最长的连续的底,即对两边分别找第一个小于遍历的数的高度的索引值(即求矩形的最长的底),这点和
接雨水
有点相似,同时,采用单调递增栈的方法 跟求最大有效括号
这道题有异曲同工之处,都是采用了栈存取数组索引值的方法!- 为何说单调递增栈(严格递增)能非常轻松的找到 height[i] 的 两边刚好比它的高度小的第一个数 呢?
- 这里我们先假设所有的高度都是不会相同的。 首先由于栈是递增的,当 height[i] 比栈顶的索引值对应的高度 大时,直接压入栈即可,否则说明 height[i] 比栈顶的索引值对应的高度小,则栈顶对应的右边第一个小于它的高度的数找到了,就是 height[i],然后把栈顶元素弹出,新栈顶的元素即是刚才弹栈元素左边第一个小于它的高度的数,这样就很轻松的找到了两边分别小于 栈顶元素的数,这样取更新最大值就行了。
- 所以,我们现在来考虑一下取消开始那个前提条件,现在有的高度是会相同的,这个条件我们怎么处理呢?当面临栈顶元素和遍历的元素对应的高度相同时,我们只需要更新栈顶元素的值(即将其存入的索引变为新的我们正在遍历的元素的索引值),我举个例子,比如说 2 5 6 7 5 6 3,当遍历到最后一个数 5 时,此时栈顶值为 1(索引 1 对应的高度是 5 ),我们只要把栈顶值变为 4 即可。
- 当然这样还有一个问题,就是假如是 2 5 6 7,高度一直递增,四个值全部入栈了,此时最后一个元素 7 的 右边第一个小于它的高度其实没有,我们可以令其为 height.length。
代码
- 暴力法
1 | class Solution { |
作者:windliang
链接:https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-1-7/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
- 单调递增栈法
1 | class Solution { |
最大矩形(85)
题目
给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。
示例:
1 | 输入: |
思路
思路同84题,每一行都调用84题的算法即可。
代码
1 | class Solution { |
买卖股票的最佳时机(121)
题目
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
1 | 输入: [7,1,5,3,6,4] |
示例 2:
1 | 输入: [7,6,4,3,1] |
思路
假设当前在第 i 天,令 minPrice 表示前 i-1 天的最低价格;令 maxProfit 表示前 i-1 天的最大收益。那么考虑第 i 天的收益时,存在两种情况:
- 在第 i 天卖出。很显然,想要获得最大收益,应该在前 i-1 天中价格最低的时候买入,即此时的收益为:prices[i] - minPrice。(可能会出现负数,但是没关系)
- 不在第 i 天卖出。那么第 i 天的最大收益就等于前 i -1 天中的最大收益
状态转移方程为:第 i 天最大收益 = max( 在第 i 天卖出的所得收益 , 前 i-1 天的最大收益)
代码
1 | class Solution { |
买卖股票的最佳时机 II(122)
题目
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)
示例 1:
1 | 输入: [7,1,5,3,6,4] |
示例 2:
1 | 输入: [1,2,3,4,5] |
示例 3:
1 | 输入: [7,6,4,3,1] |
思路
扫描一遍,只要后一天比前一天大,就把这两天的差值加一下。
代码
1 | class Solution { |
买卖股票的最佳时机 III(123)
题目
给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
1 | 输入: [3,3,5,0,0,3,1,4] |
示例 2:
1 | 输入: [1,2,3,4,5] |
示例 3:
1 | 输入: [7,6,4,3,1] |
思路
代码
1 | class Solution { |
买卖股票的最佳时机 IV(188)
题目
给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
1 | 输入: [2,4,1], k = 2 |
示例 2:
1 | 输入: [3,2,6,5,0,3], k = 2 |
思路
思路跟上题一样,这里最多可以有 k 笔交易,所以就存在 s(2k+1) 个状态,思路一模一样,但是注意有个坑,就是这里的 k 如果超过数组长度的一半,就说明可以随便交易了,就是股票 II 一样的贪心思想就可以了。
代码
1 | class Solution { |
最佳买卖股票时机含冷冻期(309)
题目
给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
- 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
- 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
1 | 输入: [1,2,3,0,2] |
思路
代码
1 | class Solution { |
买卖股票的最佳时机含手续费(714)
题目
给定一个整数数组 prices,其中第 i 个元素代表了第 i 天的股票价格 ;非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。
示例 1:
1 | 输入: prices = [1, 3, 2, 8, 4, 9], fee = 2 |
思路
只有两个状态机,持股和不持股
代码
1 | class Solution { |
最长连续序列(128)
题目
给定一个未排序的整数数组,找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
1 | 输入: [100, 4, 200, 1, 3, 2] |
思路
- 暴力法。从头到尾遍历每个数,然后对每个数去找数组中是否存在下一个数,如果存在,就找是否存在下一个再下一个的数,以此类推。
- 排序之后再进行判断,这个很简单…不讲了。
- 用 Set 存储数组,这样查询是否有该数的时候,直接就是 O(1) 的复杂度,同时不需要数组从头到尾遍历,只有在(遍历的元素值 - 1) 不在 Set 中,才开始判断其下一个是否在 Set 中,这样就可以减少遍历的次数。
代码
- 暴力
1 | class Solution { |
- 排序
1 | class Solution { |
- Set
1 | class Solution { |
Tip:
假如要求打印出连续序列的首尾:
1 | import java.util.*; |
乘积最大子数组(152)
题目
给定一个整数数组 nums
,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。
示例 1:
1 | 输入: [2,3,-2,4] |
示例 2:
1 | 输入: [-2,0,-1] |
思路
这其实说白了就是子串的题目,所以必须使用动态规划去做。做 dp 的题目,我觉得首先最重要的不是状态转移方程,而是dp数组的含义是什么,只有这个确定对了,状态方程才能很好的列出来!!!
这里的 dp 数组指的是以第 i 个数 结尾的 连续子序列,由于存在负数,所以必须维护两个 dp 数组,其实这里根本用不到数组,但是为了更加清晰的看到 dp 的思想,我还是用数组来表达吧。
- 我们先考虑都是正数的情况。dp_max[i] 的含义我们已经讲过了,
dp_max[i] = Math.max(nums[i-1],dp_max[i-1]*nums[i-1])
,即 dp_max[i] 这个值只会在这两者产生,要么 乘上之前的会更大,要么 舍弃前面的。 - 接下来考虑负数的情况,所以我们有必要维护一个 dp_min,思路是一模一样的,当遍历的元素为负数时,我们只需要把 dp_max[i-1],dp_min[i-1]交换即可。
- 最后,只要找到所有dp_max中的数值最大的那个,就是我们需要的值了。
代码
1 | class Solution { |
1 | class Solution { |
最大子数组和
题目
给你一个整数数组 nums
,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。
示例 1:
1 | 输入:nums = [-2,1,-3,4,-1,2,1,-5,4] |
示例 2:
1 | 输入:nums = [1] |
示例 3:
1 | 输入:nums = [5,4,-1,7,8] |
思路
dp[i]
:表示以 nums[i]
结尾 的 连续 子数组的最大和。
dp[i]=max{nums[i], dp[i-1]+nums[i]}
代码
1 | class Solution { |
优化:
1 | public class Solution { |
最长递增子序列(300)
题目
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1:
1 | 输入:nums = [10,9,2,5,3,7,101,18] |
示例 2:
1 | 输入:nums = [0,1,0,3,2,3] |
示例 3:
1 | 输入:nums = [7,7,7,7,7,7,7] |
进阶:
- 你能将算法的时间复杂度降低到
O(n log(n))
吗?
思路
- dp
dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]
- 二分
代码
1 | class Solution { |
二分
1 | class Solution { |
最小栈(155)
题目
设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。
- push(x) – 将元素 x 推入栈中。
- pop() – 删除栈顶的元素。
- top() – 获取栈顶元素。
- getMin() – 检索栈中的最小元素。
示例:
1 | MinStack minStack = new MinStack(); |
思路
用两个栈,一个栈专门存最小值,主要就是入栈和出栈做到同步就行。存最小值的栈的具体操作流程如下:
将第一个元素入栈。
新加入的元素如果大于栈顶元素,那么新加入的元素就不处理。
新加入的元素如果小于等于栈顶元素,那么就将新元素入栈。
出栈元素不等于栈顶元素,不操作。
出栈元素等于栈顶元素,那么就将栈顶元素出栈。
用一个栈,当有更小的值来的时候,我们只需要把之前的最小值入栈,当前更小的值再入栈即可。当这个最小值要出栈的时候,下一个值便是之前的最小值了。
栈中存储链表,其中设定一个节点包括其 val,和当前最小值。
代码
- 两个栈
1 | class MinStack { |
- 单个栈
1 | class MinStack { |
- 存储链表
1 | class MinStack { |
分裂二叉树的最大乘积(1339)
题目
给你一棵二叉树,它的根为 root 。请你删除 1 条边,使二叉树分裂成两棵子树,且它们子树和的乘积尽可能大。
由于答案可能会很大,请你将结果对 10^9 + 7 取模后再返回。
示例 1:
1 | 输入:root = [1,2,3,4,5,6] |
示例 2:
1 | 输入:root = [1,null,2,3,4,null,null,5,6] |
代码
1 | /** |
反转链表(206)
题目
反转一个单链表。
示例:
1 | 输入: 1->2->3->4->5->NULL |
思路
迭代
设置三个节点pre
、cur
、next
- (1)每次查看
cur
节点是否为NULL
,如果是,则结束循环,获得结果 - (2)如果
cur
节点不是为NULL
,则先设置临时变量next
为cur
的下一个节点 - (3)让
cur
的下一个节点变成指向pre
,而后pre
移动cur
,cur
移动到next
- (4)重复(1)(2)(3)
递归
拿到手之后,是直接使用的递归的做法,看评论区大家好像对递归的过程都觉得很绕,其实我个人觉得大家把这个想复杂了,下面我来试着帮大家一起理解一下!
递归,就是三部曲:
- 1、找到递归出口
- 2、确定返回值
- 3、分析单次递归需要做的事情
下面,我们来具体分析一下:
- 首先,找到递归出口,这个还是非常简单的,就是当前即将反转的节点为 null 或者是 反转链表 为 null 时(一轮递归其实就只有两个节点,后面会讲),说明已经全部反转完毕了,即递归出口;
- 其次,确定返回值,我们只需要返回反转链表的头结点即可;
- 最后,分析单次递归需要做的事情,我觉得大家觉得递归比较难理解的地方就是在这,其实是大家把递归复杂化了,递归其实每一轮做的事情都是一样的,我们不需要去重复考虑,这样反而会很乱,只需要考虑单轮递归需要做什么就可以了。在这里,我们就只有两个节点,一个是即将反转的节点元素,一个是已经反转完毕的链表头结点。 我们要做的一轮递归只是 将当前节点加入到反转链表中,仅此而已。
代码
- 迭代
1 | /** |
- 递归
1 | /** |
相交链表(160)
题目
编写一个程序,找到两个单链表相交的起始节点。
【注意:这里相交节点并不是看链表的值相等就代表相交,得是两个节点直接相等才代表相交,指向同一块内存。】
如下面的两个链表:
在节点 c1 开始相交。
示例 1:
1 | 输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 |
示例 2:
1 | 输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 |
示例 3:
1 | 输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 |
注意:
- 如果两个链表没有交点,返回 null。
- 在返回结果后,两个链表仍须保持原有的结构。
- 可假定整个链表结构中没有循环。
- 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。
思路
- 最开始的思路就是,找到
长链表和短链表的长度差 c
,这样第二次遍历的时候,长链表从第c+1
个节点出发,短链表从第一个节点出发,这样最后二者必是同时到达终点的,而二者如果有相交,则在遍历的时候节点必相等,第一个相等的节点就是相交的起始节点。 - 还有一个思路可以找到相交的起始节点,我们无需去计算长链表和短链表的长度差 c,只需要让两个指针 p1、p2 同时从链表头结点处出发,假设 长链表长度为 a,短链表的长度为 b,当短链表指针p2遍历到 null,即遍历完了短链表,将其移到长链表头结点继续遍历,同时p1也继续向前遍历,当p1遍历到 null 时,将其移到短链表头节点继续遍历,这样 如果长链表和短链表相交,则 p1 和 p2 必会在相交起始处相遇,如果两个链表不相交,p1 和 p2 会在 null 处相遇。
代码
- Code I
1 | /** |
- Code II
1 | public ListNode getIntersectionNode(ListNode headA, ListNode headB) { |
回文链表(234)
题目
请判断一个链表是否为回文链表。
示例 1:
1 | 输入: 1->2 |
示例 2:
1 | 输入: 1->2->2->1 |
思路
- 链表转列表
- 1.快慢指针找到链表的中点
2.翻转链表前半部分
3.回文校验 - 一边翻转一边快慢指针遍历
代码
- Case I
1 | class Solution { |
- Case II
1 | public boolean isPalindrome(ListNode head) { |
- Case III
1 | public boolean isPalindrome(ListNode head) { |
多数元素(169)
题目
给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
1 | 输入: [3,2,3] |
示例 2:
1 | 输入: [2,2,1,1,1,2,2] |
思路
哈希表存储。
投票算法,如果我们把众数记为 +1 ,把其他数记为 −1 ,将它们全部加起来,显然和大于 0 ,从结果本身我们可以看出众数比其他数多。本质上, Boyer-Moore 算法就是找 nums 的一个后缀 suf ,其中 suf[0] 就是后缀中的众数。我们维护一个计数器,如果遇到一个我们目前的候选众数,就将计数器加一,否则减一。只要计数器等于 0 ,我们就将 nums 中之前访问的数字全部忘记 ,并把下一个数字当做候选的众数。
- 分治,如果数 a 是数组 nums 的众数,如果我们将 nums 分成两部分,那么 a 必定是至少一部分的众数。
我们可以使用反证法来证明这个结论。假设 a 既不是左半部分的众数,也不是右半部分的众数,那么 a 出现的次数少于 l / 2 + r / 2 次,其中 l 和 r 分别是左半部分和右半部分的长度。由于 l / 2 + r / 2 <= (l + r) / 2,说明 a 也不是数组 nums 的众数,因此出现了矛盾。所以这个结论是正确的。
这样以来,我们就可以使用分治法解决这个问题:将数组分成左右两部分,分别求出左半部分的众数 a1 以及右半部分的众数 a2,随后在 a1 和 a2 中选出正确的众数。
代码
- Case I
1 | class Solution { |
- Case II 投票算法
1 | class Solution { |
- Case III 分治
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47class Solution {
private int countInRange(int[] nums, int num, int lo, int hi) {
int count = 0;
for (int i = lo; i <= hi; i++) {
if (nums[i] == num) {
count++;
}
}
return count;
}
private int majorityElementRec(int[] nums, int lo, int hi) {
// base case; the only element in an array of size 1 is the majority
// element.
if (lo == hi) {
return nums[lo];
}
// recurse on left and right halves of this slice.
int mid = (hi-lo)/2 + lo;
int left = majorityElementRec(nums, lo, mid);
int right = majorityElementRec(nums, mid+1, hi);
// if the two halves agree on the majority element, return it.
if (left == right) {
return left;
}
// otherwise, count each element and return the "winner".
int leftCount = countInRange(nums, left, lo, hi);
int rightCount = countInRange(nums, right, lo, hi);
return leftCount > rightCount ? left : right;
}
public int majorityElement(int[] nums) {
return majorityElementRec(nums, 0, nums.length-1);
}
}
作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
时间复杂度: T(n) = 2T(n/2) + 2n,master定理可知,logba = 1,所以 f(x) = n的logba,故时间复杂度为O(nlogn)
空间复杂度:栈的空间,O(logn)
岛屿数量(200)
题目
给定一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
1 | 输入: |
示例 2:
1 | 输入: |
思路
思路一:深度优先遍历DFS
- 目标是找到矩阵中 “岛屿的数量” ,上下左右相连的 1 都被认为是连续岛屿。
- dfs方法: 设目前指针指向一个岛屿中的某一点 (i, j),寻找包括此点的岛屿边界。
- 从 (i, j) 向此点的上下左右 (i+1,j),(i-1,j),(i,j+1),(i,j-1) 做深度搜索。
- 终止条件:
- (i, j) 越过矩阵边界;
- grid[i][j]== 0,代表此分支已越过岛屿边界。
- 搜索岛屿的同时,执行 grid[i][j] = ‘0’,即将岛屿所有节点删除,以免之后重复搜索相同岛屿。
主循环:
- 遍历整个矩阵,当遇到 grid[i][j] == ‘1’ 时,从此点开始做深度优先搜索 dfs,岛屿数 count + 1 且在深度优先搜索中删除此岛屿。
- 最终返回岛屿数 count 即可。
思路二:广度优先遍历BFS
- 主循环和思路一类似,不同点是在于搜索某岛屿边界的方法不同。
- bfs 方法:
- 借用一个队列 queue,判断队列首部节点 (i, j) 是否未越界且为 1:
- 若是则置零(删除岛屿节点),并将此节点上下左右节点 (i+1,j),(i-1,j),(i,j+1),(i,j-1) 加入队列;
- 若不是则跳过此节点;
- 循环 pop 队列首节点,直到整个队列为空,此时已经遍历完此岛屿。
- 借用一个队列 queue,判断队列首部节点 (i, j) 是否未越界且为 1:
代码
- Case I
1 | class Solution { |
- Case II
1 | class Solution { |
作者:jyd
链接:https://leetcode-cn.com/problems/number-of-islands/solution/number-of-islands-shen-du-you-xian-bian-li-dfs-or-/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
- 并查集
1 | class Solution { |
最大正方形(221)
题目
在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。
示例:
1 | 输入: |
思路
前面做了一题求 最大长方形的题目,当时的思路是用的第 84 题 柱状图中最大的矩形
,分别求每一行的最大矩形,最后得到 整个的最大长方形。这里求正方形,就不能用那种方法了,必须得另辟蹊径。
这里采用的是 dp,既然是找最大正方形,其实找对 dp数组代表什么 和 状态转移方程 如何写,就完成了,这里的 dp 数组代表以 该元素为右下角的正方形边长,故 dp(i, j)=min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1))+1
代码
1 | public class Solution { |
由于当前 dp[i][j] 只用到了左上、左边、上边三个元素,所以不需要建立一个二维数组去操作,只需要用一个一维的数组去存每一行对应的列的数就行了,可以复用,至于 左上角 的数,可以用一个变量单独记录一下(这个是真的牛皮)
1 | public class Solution { |
课程表(207)
题目
现在你总共有 n 门课需要选,记为 0
到 n-1
。
在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件,判断是否可能完成所有课程的学习?
示例 1:
1 | 输入: 2, [[1,0]] |
示例 2:
1 | 输入: 2, [[1,0],[0,1]] |
思路
这题本质就是拓扑排序,解决拓扑排序,一般就是两个方法:BFS 和 DFS。其核心都是能拓扑排序的都是有向无环图。BFS 主要是从入度出度考虑,而 DFS 主要从有无环考虑。
详细思路见:
代码
- BFS
1 | class Solution { |
- DFS
1 | class Solution { |
实现 Trie (前缀树)(208)
题目
实现一个 Trie (前缀树),包含 insert
, search
, 和 startsWith
这三个操作。
示例:
1 | Trie trie = new Trie(); |
说明:
- 你可以假设所有的输入都是由小写字母
a-z
构成的。 - 保证所有输入均为非空字符串。
思路
https://blog.csdn.net/qq_43152052/article/details/101109415 大佬对 leetcode 前缀树的习题总结
代码
1 | package LeetCode_100_hotest; |
每日温度(739)
题目
根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。
例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示:气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数。
思路
很明显是采用单调栈的方法,具体见
https://labuladong.gitbook.io/algo/shu-ju-jie-gou-xi-lie/dan-tiao-zhan
模板:
1 | vector<int> nextGreaterElement(vector<int>& nums) { |
代码
1 | class Solution { |
下一个更大元素 I(496)
题目
给定两个没有重复元素 的数组 nums1 和 nums2 ,其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在,对应位置输出 -1 。
示例 1:
1 | 输入: nums1 = [4,1,2], nums2 = [1,3,4,2]. |
示例 2:
1 | 输入: nums1 = [2,4], nums2 = [1,2,3,4]. |
思路
我们可以忽略数组 nums1,先对将 nums2 中的每一个元素,求出其下一个更大的元素。随后对于将这些答案放入哈希映射(HashMap)中,再遍历数组 nums1,并直接找出答案。对于 nums2,我们可以使用单调栈来解决这个问题。
我们首先把第一个元素 nums2[1] 放入栈,随后对于第二个元素 nums2[2],如果 nums2[2] > nums2[1],那么我们就找到了 nums2[1] 的下一个更大元素 nums2[2],此时就可以把 nums2[1] 出栈并把 nums2[2] 入栈;如果 nums2[2] <= nums2[1],我们就仅把 nums2[2] 入栈。对于第三个元素 nums2[3],此时栈中有若干个元素,那么所有比 nums2[3] 小的元素都找到了下一个更大元素(即 nums2[3]),因此可以出栈,在这之后,我们将 nums2[3] 入栈,以此类推。
可以发现,我们维护了一个单调栈,栈中的元素从栈顶到栈底是单调不降的。当我们遇到一个新的元素 nums2[i] 时,我们判断栈顶元素是否小于 nums2[i],如果是,那么栈顶元素的下一个更大元素即为 nums2[i],我们将栈顶元素出栈。重复这一操作,直到栈为空或者栈顶元素大于 nums2[i]。此时我们将 nums2[i] 入栈,保持栈的单调性,并对接下来的 nums2[i + 1], nums2[i + 2] … 执行同样的操作。
单调栈写法就是上面的模板:
1 | vector<int> nextGreaterElement(vector<int>& nums) { |
代码
1 | class Solution { |
任务调度器(621)
题目
给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行,并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务,或者在待命状态。
然而,两个相同种类的任务之间必须有长度为 n 的冷却时间,因此至少有连续 n 个单位时间内 CPU 在执行不同的任务,或者在待命状态。
你需要计算完成所有任务所需要的最短时间。
示例 1
1 | 输入: tasks = ["A","A","A","B","B","B"], n = 2 |
思路
- 桶思想,每个桶固定大小为 n+1(除最后一个桶之外),这样可以确保相同的任务可以分在不同的桶中
- 当然,每个任务在桶中的次序是固定的,比如说 A 在桶底,那么在每个桶中 A 都在底部,这样可以确保相同任务的间隔时间都不小于 n
- 桶的数量由 拥有最多任务数的那个任务决定,只要他保证了冷却时间,其他的一定可以
- 结果就是 (n+1) \ (count - 1) + 最后一个桶的大小*,count 为桶的数量,因为最后一个桶无需固定大小
- count 很好求,那最后一个桶大小如何求呢,很明显就是 拥有最多数任务的个数,比如AAABBBCCCDDEE,那最后一个桶的大小就是 3,因为 A B C 都是拥有 3 个任务数
- 如果冷却时间过短,任务数过多,也就是说桶不够用了,比如说 AAABBBCCCDDEE 且 n = 2 这种情况,此时 桶的大小为 3,桶的数量为 3。第一个桶 ABC ,第二个 ABC,第三个 ABC,此时的 D 和 E 我们可以理解为按照
一定次序
放在桶之上
就行 ,也就是不用放到桶中,这样不会影响桶内元素 - 由于 D 和 E 的出现次数是一定小于桶的数量的,所以最多每个桶上放一个相同任务,这样 D 和 E 按次序排布是一定符合要求的
- 此时的答案就是 任务总数 了,因为所有的桶都满了,并且多出来的也是任务,没有待命时间
- 故答案就是 两个时间 的最大值
代码
1 | class Solution { |
最短无序连续子数组(581)
题目
给定一个整数数组,你需要寻找一个连续的子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。
你找到的子数组应是最短的,请输出它的长度。
示例 1:
1 | 输入: [2, 6, 4, 8, 10, 9, 15] |
思路
我采用的是排序
代码
1 | class Solution { |
和为K的子数组(560)
题目
给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
1 | 输入:nums = [1,1,1], k = 2 |
思路
- 暴力法,两次 for 循环,首先是 start,然后 end 从第一个数开始,当碰到 sum = k 时 count 就 + 1
- dp。dp[i] 表示从0到第 i 个数的总和,则 dp[j] - dp[i] = k,这个 dp[i] 的个数就是 连续子数组的个数,这里可以用 HashMap 直接存储 和 以及 和 出现的次数,这样就可以非常方便的求得 dp[i] 的个数。
代码
- 暴力法
1 | public class Solution { |
- dp
1 | import java.util.HashMap; |
- dp 优化
1 | public class Solution { |
除自身以外数组的乘积(238)
题目
给定长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
1 | 输入: [1,2,3,4] |
说明: 请不要使用除法,且在 O(n) 时间复杂度内完成此题。
进阶:
你可以在常数空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组不被视为额外空间。)
思路
- 左边乘积 右边乘积,题目中要求使用 O(1) 的空间复杂度,但是 输出数组 不被视为额外空间,于是可以用左边乘积 右边乘积,具体见代码!
代码
1 | class Solution { |
滑动窗口最大值(239)
题目
给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例:
1 | 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 |
提示:
1 | 你可以假设 k 总是有效的,在输入数组不为空的情况下,1 ≤ k ≤ 输入数组的大小。 |
进阶:
1 | 你能在线性时间复杂度内解决此题吗? |
思路
暴力法
双端队列法。遍历数组,将数存放在双向队列中,并用L,R来标记窗口的左边界和右边界。队列中保存的并不是真的数,而是该数值对应的数组下标位置,并且数组中的数要从大到小排序。如果当前遍历的数比队尾的值大,则需要弹出队尾值,直到队列重新满足从大到小的要求。刚开始遍历时,L和R都为0,有一个形成窗口的过程,此过程没有最大值,L不动,R向右移。当窗口大小形成时,L和R一起向右移,每次移动时,判断队首的值的数组下标是否在[L,R]中,如果不在则需要弹出队首的值,当前窗口的最大值即为队首的数。
【有点难,适当记忆步骤】
作者:hanyuhuang
链接:https://leetcode-cn.com/problems/sliding-window-maximum/solution/shuang-xiang-dui-lie-jie-jue-hua-dong-chuang-kou-2/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。dp。这个就更骚了…见官方题解方法三
代码
- 暴力法
1 | class Solution { |
- 双端队列法
1 | class Solution { |
- dp
1 | class Solution { |
搜索二维矩阵 II(240)
题目
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性:
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例:
现有矩阵 matrix 如下:
1 | [ |
给定 target = 5
,返回 true
。
给定 target = 20
,返回 false
。
思路
暴力法
直接先行后列遍历,遍历到了 target 退出。
二分查找法
以对角线为界限,对角线之上的进行 行二分查找,对角线之下的进行 列二分查找。
减治法
其实就是选定一个特殊的出发点。
- 选左上角,往右走和往下走都增大,不能选
- 选右下角,往上走和往左走都减小,不能选
- 选左下角,往右走增大,往上走减小,可选
- 选右上角,往下走增大,往左走减小,可选
这里我们选定左下角元素!!具体操作如下:
* 设矩阵左下角元素 matrix\[i][j] ,它是第 i 行最小值,同时也是第 j 列最大值
- 若 target < matrix[i][j] (小于第 i 行最小值),则排除第 i 行,令 i–
- 若 target > matrix[i][j] (大于第 j 列最大值),则排除第 j 列,令 j++
- 循环 2~3 直到找到 target,或所有行列均被排除
代码
- 暴力法
1 | class Solution { |
- 二分
1 | class Solution { |
- 减治法
1 | class Solution { |
完全平方数(279)
题目
给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...
)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
1 | 输入: n = 12 |
示例 2:
1 | 输入: n = 13 |
思路
dp
代码
1 | class Solution { |
移动零(283)
题目
给定一个数组 nums
,编写一个函数将所有 0
移动到数组的末尾,同时保持非零元素的相对顺序。
示例:
1 | 输入: [0,1,0,3,12] |
说明:
- 必须在原数组上操作,不能拷贝额外的数组。
- 尽量减少操作次数。
思路
先复制后补0
代码
1 | class Solution { |
寻找重复数(287)
题目
给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。
示例 1:
1 | 输入: [1,3,4,2,2] |
示例 2:
1 | 输入: [3,1,3,4,2] |
说明:
- 不能更改原数组(假设数组是只读的)。
- 只能使用额外的 O(1) 的空间。
- 时间复杂度小于 O(n2) 。
- 数组中只有一个重复的数字,但它可能不止重复出现一次。
思路
排序后,相邻元素如果相等,则 return
用 set 存储,一旦发现 key 已经存在,直接返回,否则存入 map 中
其实这是一个链表中非常常见的问题,就是寻找环的入口问题,n 个不同的数,相同的那个数其实就是形成一个环。即元素索引下标为节点 node,而 node 的 next 指针则是 元素值 所对应的索引下标值。
Tip: 例如[2,1,2,3,4],这个是符合题目要求且符合自循环的情况,在nums[2]处,索引值和元素值相等,在这里的确,快慢指针会在2的位置不停指向自己,但是只要发生这种自循环的情况,那么重复的数字就是这个,我们依旧可以使用快慢指针的方法去做,因为我们的做法就是先求一次相遇,然后慢指针回到原点,第二次相遇就是环的起点,在这里,既然是自循环的,那么当然最后第二次相遇还是在这里,答案是一样的。
二分法
代码
- 排序
1 | class Solution { |
- Set 存储
1 | class Solution { |
- 快慢指针
1 | class Solution { |
- 二分
1 | class Solution { |
删除无效的括号(301)
(暂时未做哈~ 先把代码贴一下 第二遍写)
题目
删除最小数量的无效括号,使得输入的字符串有效,返回所有可能的结果。
说明: 输入可能包含了除 (
和 )
以外的字符。
示例 1:
1 | 输入: "()())()" |
示例 2:
1 | 输入: "(a)())()" |
示例 3:
1 | 输入: ")(" |
思路
代码
1 | class Solution { |
戳气球(312)
【跟上面一样,这两题没做呢!】
题目
有 n
个气球,编号为0
到 n-1
,每个气球上都标有一个数字,这些数字存在数组 nums
中。
现在要求你戳破所有的气球。每当你戳破一个气球 i
时,你可以获得 nums[left] * nums[i] * nums[right]
个硬币。 这里的 left
和 right
代表和 i
相邻的两个气球的序号。注意当你戳破了气球 i
后,气球 left
和气球 right
就变成了相邻的气球
思路
代码
1 | class Solution { |
比特位计数(338)
题目
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
1 | 输入: 2 |
示例 2:
1 | 输入: 5 |
进阶:
- 给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗?
- 要求算法的空间复杂度为O(n)。
- 你能进一步完善解法吗?要求在C++或任何其他语言中不使用任何内置函数来执行此操作。
思路
- 从 191. 位1的个数 中启发而来,n &(n-1)这种秀的一批的操作
- 对上述方法有一个改进版,动态规划版本的
代码
- Case I
1 | class Solution { |
- Case II
1 | class Solution { |
前 K 个高频元素(347)
题目
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
示例 1:
1 | 输入: nums = [1,1,1,2,2,3], k = 2 |
示例 2:
1 | 输入: nums = [1], k = 1 |
说明:
- 你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
思路
借助 2020-02-02 周赛的一道题的思路,将其存入 map,然后用 list 存储 map,然后利用集合的排序方法,对其进行排序,再转成 map,然后用 iterator 遍历即可。
思路基本一致,但是其实这里排序之后根本用不到 value 了,所以根本没必要再转成 map,所以可以不用 list 去存储 entry 对象,直接用 PriorityQueue 去对 value 排序,然后存储 key 值就可以了,因为 PriorityQueue 是最小堆实现的,时间复杂度只有 O(nlogn)
- 这个方法不用排序,用 map 存储完之后,直接放到桶中(value值作为桶的序号),存入 key。
代码
- Case I
1 | class Solution { |
- Case II
1 | class Solution { |
- Case III
1 | //基于桶排序求解「前 K 个高频元素」 |
字符串解码(394)
题目
给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。
示例:
1 | s = "3[a]2[bc]", 返回 "aaabcbc". |
思路
- 栈
- 递归
代码
- 栈
1 | public String decodeString(String s) { |
- 递归
1 | class Solution { |
找到所有数组中消失的数字(448)
题目
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例:
1 | 输入: |
思路
就是用正负号去维护一个简易的 map,标记是否出现该数。题目限制是数是在 1 ~ n 之间的,而一共有 n 个数,我们这么想,用数组元素的值代表数组中出现的数的索引,比如说[4,3,2,7,8,2,3,1],第一个数是 4,就代表了第 4个数,也就是 7,将其标志位 -1,以此类推,通过这种方式数组变为 [-4,-3,-2,-7,8,2,-3,-1],故再遍历一遍,为正数的即未出现的数字。
用这种思路还可以解决 442. 数组中重复的数据 ,思路一模一样,当遍历时发现元素(代表数组下标)所指向的数是负数,说明那个数已经出现了一次,此时此数就出现了两次,记录下来即可。
代码
1 | class Solution { |
442题代码
1 | public List<Integer> findDuplicates(int[] nums) { |
除法求值(399)
【图论知识,暂时不太会,从 leetcode英文版的 高分区 溜了几个高赞答案过来,以后欣赏一下】
题目
给出方程式 A / B = k, 其中 A 和 B 均为代表字符串的变量, k 是一个浮点型数字。根据已知方程式求解问题,并返回计算结果。如果结果不存在,则返回 -1.0。
示例 :
1 | 给定 a / b = 2.0, b / c = 3.0 |
1 | 给定 a / b = 2.0, b / c = 3.0 |
思路
- dfs
- 并查集
代码
- dfs 第一个版本
1 | class Solution { |
- dfs 第二个版本
1 | class Solution { |
- Dfs 第三个版本
1 | class Solution { |
- 并查集 I
1 | class Solution { |
- 并查集 ——> 大佬的并查集和DFS
1 | class Solution { |
根据身高重建队列(406)
题目
假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示,其中h是这个人的身高,k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。
示例
1 | 输入: |
思路
官方题解讲的不错,高个子的眼中,矮个子相当于不存在,所以高个子先按规矩站好,后面矮个子的插入不会影响其顺序,所以我们先把高个子安排完,矮个子可以直接按 k 值从小到大插入,k 值即他们当时插入的下标值。
代码
1 | public static void main(String[] args) { |
分割等和子集(416)
题目
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
注意:
- 每个数组中的元素不会超过 100
- 数组的大小不会超过 200
示例 1:
1 | 输入: [1, 5, 11, 5] |
示例 2:
1 | 输入: [1, 2, 3, 5] |
思路
见 liwei大佬思路,这个优化的套路,值得学习。
代码
1 | public class Solution { |
找到字符串中所有字母异位词(438)
题目
给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。
字符串只包含小写英文字母,并且字符串 s 和 p 的长度都不超过 20100
示例 1:
1 | 输入: |
示例 2:
1 | 输入: |
思路
滑动窗口算法,见 另外一篇文章:滑动窗口技巧总结(假装有链接)
代码
1 | class Solution { |
- 用数组代替 map
1 | class Solution { |
目标和(494)
题目
给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例 1:
1 | 输入: nums: [1, 1, 1, 1, 1], S: 3 |
注意:
- 数组非空,且长度不会超过20。
- 初始的数组的和不会超过1000。
- 保证返回的最终结果能被32位整数存下。
思路
- 暴力法 ,见官方题解
https://leetcode-cn.com/problems/target-sum/solution/mu-biao-he-by-leetcode/
- Dp,我做的时候第一反应是用的 dp,但是这里有个困难,dp不能用二维数组表示,因为可能越界,下标为负数,所以可以用 hashmap,dp[i][j] 转化为 i 当 key,j 当 value。
- 转化为 0-1 背包问题。
https://leetcode-cn.com/problems/target-sum/solution/python-dfs-xiang-jie-by-jimmy00745/
代码
1 | public class Solution { |
数组中的第K个最大元素(215)
题目
无序数组第K大的数
示例 1
1 | 输入: [3,2,1,5,6,4] 和 k = 2 |
思路
- 快排
- 大顶堆
- 小顶堆
- 优先级队列实现 == 小顶堆实现
代码
- 快排
1 | class Solution { |
- 大根堆
1 | class Solution { |
- 小根堆
1 | class Solution { |
- 优先级队列
1 | public int findKthLargest(int[] nums, int k) { |
求根号n(69)
题目
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
思路
代码
1 | class Solution { |
如果需要精确到小数:
1 | package 练手算法; |
整数拆分 = 剪绳子(343)
题目
给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 :
1 | 输入: 10 |
思路
第一想法就是 dp,dp[i] 为整数 i,将 i 拆分成至少两个整数的和,其整数的乘积的最大值。
则 dp[i] = Math.max(dp[i],Math.max(dp[i-j],i-j) * j)
代码
1 | class Solution { |
字典序的第K小数字(440)
题目
给定整数 n
和 k
,找到 1
到 n
中字典序第 k
小的数字。
注意:1 ≤ k ≤ n ≤ 109。
示例 :
1 | 输入: |
思路
前缀树,所以思路就是:
- 确定指定前缀下所有子节点数;
- 若 k 属于当前前缀下,则去子树里面看;
- 第 k 个数不属于当前前缀下,就扩大前缀,往后看。
代码
1 | package 二刷LeetCode和剑指offer.链表.三刷链表; |
二叉树展开为链表(114)
题目
给定一个二叉树,原地将它展开为一个单链表。
例如,给定二叉树:
1 | 1 |
将其展开为:
1 | 1 |
思路
其实就是先把根节点的右子树放置到根节点左边,然后将左子树放到右子树的位置,将左子树置为空。
代码
1 | public void flatten(TreeNode root) { |
打开转盘锁(752)
题目
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'
。每个拨轮可以自由旋转:例如把 '9'
变为 '0'
,'0'
变为 '9'
。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000'
,一个代表四个拨轮的数字的字符串。
列表 deadends
包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。
字符串 target
代表可以解锁的数字,你需要给出最小的旋转次数,如果无论如何不能解锁,返回 -1。
示例 1:
1 | 输入:deadends = ["0201","0101","0102","1212","2002"], target = "0202" |
示例 2:
1 | 输入: deadends = ["8888"], target = "0009" |
示例 3:
1 | 输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888" |
示例 4:
1 | 输入: deadends = ["0000"], target = "8888" |
思路
使用 BFS,但是要注意几点:
- 会走回头路。比如说我们从
"0000"
拨到"1000"
,但是等从队列拿出"1000"
时,还会拨出一个"0000"
,这样的话会产生死循环; - 注意终止条件;
- 要对 deaddends 进行处理;
代码
1 | class Solution { |
字符串相加(415)
题目
给定两个字符串形式的非负整数 num1
和num2
,计算它们的和。
注意
num1
和num2
的长度都小于 5100.num1
和num2
都只包含数字0-9
.num1
和num2
都不包含任何前导零。- 你不能使用任何內建 BigInteger 库, 也不能直接将输入的字符串转换为整数形式。
代码
1 | class Solution { |
打家劫舍(198)
题目
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。
示例 1:
1 | 输入:[1,2,3,1] |
示例 2:
1 | 输入:[2,7,9,3,1] |
思路
dp[i] 代表在打劫到第i+1个房子时,偷窃到的最高金额,dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i])。
代码
1 | class Solution { |
打家劫舍 II(213)
题目
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。
示例 1:
1 | 输入: [2,3,2] |
示例 2:
1 | 输入: [1,2,3,1] |
思路
其实就两种情况比大小。
代码
1 | class Solution { |
打家劫舍III(337)
##题目
在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。
计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。
示例 1:
1 | 输入: [3,2,3,null,3,null,1] |
示例 2:
1 | 输入: [3,4,5,1,3,null,1] |
思路
递归 + dp。小偷只有偷根节点和不偷根节点两种选择。
代码
1 | /** |
时间复杂度:O(n)。上文中已分析。
空间复杂度:O(n)。虽然优化过的版本省去了哈希映射的空间,但是栈空间的使用代价依旧是 O(n)O(n),故空间复杂度不变。
恢复二叉搜索树(99)
题目
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下,恢复这棵树。
示例 1:
1 | 输入: [1,3,null,null,2] |
示例 2:
1 | 输入: [3,1,4,null,null,2] |
思路
BST 有个最为重要的性质就是中序遍历是递增的,所以这题意思就是:在一个数组中有两个数顺序错了,如何找到这两个数,将他们的值互换,所以思路就很清晰了:
如果当前遍历的数比上一个要小,说明前面这个数是有问题的,将该数记录下,然后将当前遍历的数也记录下,如果后面的数都是有序的,则说明就是这两个数顺序有问题,将这两个数互换即可,如果后面还出现了有问题的数,则将 errorTwo 给到这个数,互换两个数即可。
代码
1 | /** |
复原IP地址(93)
题目
给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址正好由四个整数(每个整数位于 0 到 255 之间组成),整数之间用 ‘.’ 分隔。
示例:
1 | 输入: "25525511135" |
思路
回溯算法,类似于上文的 ”N皇后问题“,三要素:路径、选择列表、结束条件。
模板如下:
1 | vector<vector<string>> res; |
代码
1 | class Solution { |
有序链表转换为二叉搜索树(109)
题目
给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
1 | 给定的有序链表: [-10, -3, 0, 5, 9], |
思路
分治
代码
1 | /** |
计算数组的小和
题目
数组小和的定义如下:
例如,数组s = [1, 3, 5, 2, 4, 6],在s[0]的左边小于或等于s[0]的数的和为0;在s[1]的左边小于或等于s[1]的数的和为1;在s[2]的左边小于或等于s[2]的数的和为1+3=4;在s[3]的左边小于或等于s[3]的数的和为1;
在s[4]的左边小于或等于s[4]的数的和为1+3+2=6;在s[5]的左边小于或等于s[5]的数的和为1+3+5+2+4=15。所以s的小和为0+1+4+1+6+15=27
给定一个数组s,实现函数返回s的小和
[要求]
时间复杂度为O(nlogn),空间复杂度为O(n)
思路
归并排序的应用,当归并过程中发现左边的数小于右边的数,即得到一组小和。如1 3 5 7 和 2 4 6 8,当左边遍历第一个数,有1 < 2,则1也小于2右边的所有数,即这组小和为1*4。
注意小和结果不能用int存储,会溢出。
代码
1 | import java.util.*; |
Pow(x, n)(50)
题目
实现 pow(x, n) ,即计算 x 的 n 次幂函数。
思路
代码
1 | class Solution { |
N 的阶乘
题目
求 n 的阶乘值
思路
- 递归
代码
- 递归
1 | public class MainClass { |
缺失的第一个正数(41)
题目
给你一个未排序的整数数组 nums
,请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n)
并且只使用常数级别额外空间的解决方案。
示例 1:
1 | 输入:nums = [1,2,0] |
示例 2:
1 | 输入:nums = [3,4,-1,1] |
示例 3:
1 | 输入:nums = [7,8,9,11,12] |
思路
遍历一次数组把大于等于1的和小于等于数组大小的值放到原数组对应位置(注意数组下标从0开始,所以数值3应该放在索引为2的位置),然后再遍历一次数组查当前下标是否和值对应,如果不对应那这个下标就是答案,否则遍历完都没出现那么答案就是数组长度加1。
代码
1 | public class Solution { |
多线程顺序打印 1-100
题目
多线程顺序打印 1-100
代码
1 | package com.company; |