leetcode题解

数组

No1.两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

明确题目

每种输入只会对应一个答案可以理解为,不需要对数组的长度进行校验。

不能重复利用这个数组中同样的元素:需要进行校验。

所有可能解

蛮力法

通过两次loops,外层循环枚举 x,内层循环枚举 y,然后逐次判断 x + y 是否等于 target。

1
2
3
4
5
6
7
8
9
10
11
12
public int[] twoSum(int[] nums, int target) {
if(nums.length < 2) return new int[0];

for(int i = 0; i < nums.length -1; i++) {
for(int j = i+1; j < nums.length;j++) {
if(nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[0];
}

复杂度分析:

时间复杂度为:O(n^2),空间复杂度:O(1);

HashMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int[] twoSum(int[] nums, int target) {
if(nums.length < 2) return new int[0];
Map<Integer, Integer> store = new HashMap<>();

for(int i = 0; i < nums.length; i++) {
if(store.containsKey(target - nums[i]) && store.get(target - nums[i]) != nums[i]) {
return new int[]{store.get(target - nums[i]), i};
} else {
store.put(nums[i], i);
}
}
return new int[0];

}

复杂度分析:

时间复杂度为:只遍历一次数组,O(N),空间复杂度为:O(N),最坏的情况下,HashMap中要存放所有数组数据。

链表

No206.反转链表

反转一个单链表。

示例:

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

明确题目

当前节点指向它的前一节点。

所有可能解

#####记录当前节点和前一个节点

1
2
3
4
5
6
7
8
9
10
11
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while(curr != null) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}

复杂度分析:

时间复杂度:O(n),空间复杂度为:O(1)。

No141.环形链表

给定一个链表,判断链表中是否有环。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

明确题目

有环的链表的特点是一直会有next节点,同时还有一个特点是,存在一个节点是两个节点的后继节点,无环的链表特点是会有next节点为null。

所有可能解

蛮力法

读取链表下一个节点,直到为null。不可取。

Set存储节点

每次读取下一个节点的时候,判断Set中是否存在该节点,若存在则表示存在环。

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean hasCycle(ListNode head) {
ListNode curr = head;
Set<ListNode> store = new HashSet<>();
while(curr != null) {
if(store.contains(curr)) {
return true;
} else {
store.add(curr);
curr = curr.next;
}
}
return false;
}

复杂度分析:

时间复杂度为:O(N),空间复杂度为:O(N)。

快慢指针

慢指针步长为1,快指针步长为2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while(slow != fast) {
if(fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}

判断的时候判断快指针就可以了。

复杂度分析:

时间复杂度为: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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> store = new HashSet<>();
ListNode currA = headA;
ListNode currB = headB;
while(currA != null) {
store.add(currA);
currA = currA.next;
}
while(currB != null) {
if(store.contains(currB)) {
return currB;
}
currB = currB.next;
}
return null;
}

复杂度分析:

时间复杂度:分别对A链表和B链表进行了遍历,即O(M + N),空间复杂度为:O(M)或O(N)。

两个指针
1
2
3
4
5
6
7
8
9
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pA = headA;
ListNode pB = headB;
while(pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}

复杂度分析:

时间复杂度:O(M+N),空间复杂度为:O(1)。

合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例:

1
2
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

明确题目

从两个链表的第一个节点开始进行比对,判断下一个节点大小,进而进行next指针的指向。

所有可能解

递归
1
2
3
4
5
6
7
8
9
10
11
12
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;

if(l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
0%