leetcode题解
数组
No1.两数之和
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
明确题目
每种输入只会对应一个答案可以理解为,不需要对数组的长度进行校验。
不能重复利用这个数组中同样的元素:需要进行校验。
所有可能解
蛮力法
通过两次loops,外层循环枚举 x,内层循环枚举 y,然后逐次判断 x + y 是否等于 target。
1 | public int[] twoSum(int[] nums, int target) { |
复杂度分析:
时间复杂度为:O(n^2),空间复杂度:O(1);
HashMap
1 | public int[] twoSum(int[] nums, int target) { |
复杂度分析:
时间复杂度为:只遍历一次数组,O(N),空间复杂度为:O(N),最坏的情况下,HashMap中要存放所有数组数据。
链表
No206.反转链表
反转一个单链表。
示例:
1 | 输入: 1->2->3->4->5->NULL |
明确题目
当前节点指向它的前一节点。
所有可能解
#####记录当前节点和前一个节点
1 | public ListNode reverseList(ListNode head) { |
复杂度分析:
时间复杂度:O(n),空间复杂度为:O(1)。
No141.环形链表
给定一个链表,判断链表中是否有环。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
明确题目
有环的链表的特点是一直会有next节点,同时还有一个特点是,存在一个节点是两个节点的后继节点,无环的链表特点是会有next节点为null。
所有可能解
蛮力法
读取链表下一个节点,直到为null。不可取。
Set存储节点
每次读取下一个节点的时候,判断Set中是否存在该节点,若存在则表示存在环。
1 | public boolean hasCycle(ListNode head) { |
复杂度分析:
时间复杂度为:O(N),空间复杂度为:O(N)。
快慢指针
慢指针步长为1,快指针步长为2。
1 | public boolean hasCycle(ListNode head) { |
判断的时候判断快指针就可以了。
复杂度分析:
时间复杂度为:O(N),空间复杂度为:O(1)。
No160.相交链表
找到两个单链表相交的起始节点。
明确题目
相交的单链表特点:
存在两个节点的后继节点为一个节点。
链表A和链表B未相交部分分别为:A:a1->a2 B:b1->b2->b3,相交部分为:c1->c2->c3,则有
a1->a2->c1->c2->c3->null->b1->b2->b3->c1 长度等于 b1->b2->b3->c1->c2->c3->null->a1->a2->c1。
所有可能解
蛮力法
遍历链表A,嵌套遍历链表B,判断每个A中的节点是否在B中存在。
复杂度分析:
时间复杂度:O(mn),空间复杂度:O(1)
Set存储节点
Set存储链表A所有节点,遍历B链表,能否找到Set中包含的节点。
1 | public ListNode getIntersectionNode(ListNode headA, ListNode headB) { |
复杂度分析:
时间复杂度:分别对A链表和B链表进行了遍历,即O(M + N),空间复杂度为:O(M)或O(N)。
两个指针
1 | public ListNode getIntersectionNode(ListNode headA, ListNode headB) { |
复杂度分析:
时间复杂度:O(M+N),空间复杂度为:O(1)。
合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
1 | 输入:1->2->4, 1->3->4 |
明确题目
从两个链表的第一个节点开始进行比对,判断下一个节点大小,进而进行next指针的指向。
所有可能解
递归
1 | public ListNode mergeTwoLists(ListNode l1, ListNode l2) { |