322. 零钱兑换
问题描述
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
解题思路
动态规划，dp[i]表示凑成总金额为i所需要的最少硬币个数
代码实现
class Solution {
public int coinChange(int[] coins, int amount) {
if(amount < 0){
return -1;
}
//dp[i]表示凑成总金额为i所需要的最少硬币个数
int[] dp = new int[amount + 1];
dp[0] = 0;
for(int i = 1; i <= amount; i++){
//凑成amount金额的硬币数量最多为amount个，初始化dp[i]为amount+1等于初始化为正无穷，便于后续取最小值
dp[i] = amount + 1;
for(int coin : coins){
if(i < coin){
continue;
}else{
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
if(dp[amount] == amount + 1){
return -1;
}else{
return dp[amount];
}
}
}
141. 环形链表
问题描述
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
解题思路
快慢指针同时从起点出发，若链表有环，必两个指针一定会相遇。
注意，因为初始情况两个指针都位于头节点，所以应该让指针先出发，然后再判断指针的位置是否指向同一个节点。
代码实现
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null){
return false;
}
ListNode slow = head, fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
return true;
}
}
return false;
}
}
142. 环形链表 II
问题描述
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
解题思路-哈希集合
采用HashSet来保存已访问过的节点，第一个被再次访问的节点即为开始入环的第一个节点。
代码实现-哈希集合
public class Solution {
public ListNode detectCycle(ListNode head) {
Set<ListNode> set = new HashSet<>();
while(head != null){
if(set.contains(head)){
return head;
}
set.add(head);
head = head.next;
}
return null;
}
}
解题思路-双指针
接着上一题的思路，当快慢指针相遇时，让一个新的慢指针指向头节点。然后新旧慢指针同时从头节点、相遇点出发，再次相遇的位置就是入环的第一个节点。
假设链表环前有 a 个节点，环内有 b 个节点，相遇点再走到环的起点有c个节点。
1.第一次相遇时
慢指针路程s=a+b-c；
快指针路程是慢指针路程的两倍2s= a+n*b+b-c,其中b为快指针完整走过的环的总圈数；
两式相减得到s=n*b，因此 a+b-c = n*b，可得a=(n-1)b + c。
2.第二次相遇时
旧的慢指针走过的路程：(n-1)b + c
新的慢指针走过的路程：a
代码实现-双指针
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
//无环，返回null
if(head == null || head.next == null){
return null;
}
//判断链表是否有环
boolean hasCycle = false;
ListNode slow = head, fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
//快慢指针第一次相遇时退出循环
hasCycle = true;
break;
}
}
//无环，返回null
if(!hasCycle){
return null;
}
//让原来的快指针指向头节点，成为新的慢指针
fast = head;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
