322. 零錢兌換
問(wèn)題描述
給定不同面額的硬幣 coins 和一個(gè)總金額 amount找爱。編寫一個(gè)函數(shù)來(lái)計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)涤姊。如果沒(méi)有任何一種硬幣組合能組成總金額授药，返回 -1界弧。
你可以認(rèn)為每種硬幣的數(shù)量是無(wú)限的粟关。
解題思路
動(dòng)態(tài)規(guī)劃统诺，dp[i]表示湊成總金額為i所需要的最少硬幣個(gè)數(shù)
代碼實(shí)現(xiàn)
class Solution {
public int coinChange(int[] coins, int amount) {
if(amount < 0){
return -1;
}
//dp[i]表示湊成總金額為i所需要的最少硬幣個(gè)數(shù)
int[] dp = new int[amount + 1];
dp[0] = 0;
for(int i = 1; i <= amount; i++){
//湊成amount金額的硬幣數(shù)量最多為amount個(gè)袱蚓，初始化dp[i]為amount+1等于初始化為正無(wú)窮肮塞，便于后續(xù)取最小值
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. 環(huán)形鏈表
問(wèn)題描述
給定一個(gè)鏈表版述，判斷鏈表中是否有環(huán)梯澜。
如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過(guò)連續(xù)跟蹤 next 指針再次到達(dá)渴析，則鏈表中存在環(huán)晚伙。 為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來(lái)表示鏈表尾連接到鏈表中的位置（索引從 0 開始）俭茧。 如果 pos 是 -1咆疗，則在該鏈表中沒(méi)有環(huán)。注意：pos 不作為參數(shù)進(jìn)行傳遞母债，僅僅是為了標(biāo)識(shí)鏈表的實(shí)際情況午磁。
如果鏈表中存在環(huán)，則返回 true 场斑。 否則漓踢，返回 false 。
解題思路
快慢指針同時(shí)從起點(diǎn)出發(fā)漏隐，若鏈表有環(huán)喧半，必兩個(gè)指針一定會(huì)相遇。
注意青责，因?yàn)槌跏记闆r兩個(gè)指針都位于頭節(jié)點(diǎn)挺据，所以應(yīng)該讓指針先出發(fā)，然后再判斷指針的位置是否指向同一個(gè)節(jié)點(diǎn)脖隶。
代碼實(shí)現(xiàn)
/**
* 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. 環(huán)形鏈表 II
問(wèn)題描述
給定一個(gè)鏈表扁耐，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。 如果鏈表無(wú)環(huán)产阱，則返回 null婉称。
解題思路-哈希集合
采用HashSet來(lái)保存已訪問(wèn)過(guò)的節(jié)點(diǎn)，第一個(gè)被再次訪問(wèn)的節(jié)點(diǎn)即為開始入環(huán)的第一個(gè)節(jié)點(diǎn)。
代碼實(shí)現(xiàn)-哈希集合
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;
}
}
解題思路-雙指針
接著上一題的思路王暗，當(dāng)快慢指針相遇時(shí)悔据，讓一個(gè)新的慢指針指向頭節(jié)點(diǎn)。然后新舊慢指針同時(shí)從頭節(jié)點(diǎn)俗壹、相遇點(diǎn)出發(fā)科汗，再次相遇的位置就是入環(huán)的第一個(gè)節(jié)點(diǎn)。
假設(shè)鏈表環(huán)前有 a 個(gè)節(jié)點(diǎn)绷雏，環(huán)內(nèi)有 b 個(gè)節(jié)點(diǎn)头滔，相遇點(diǎn)再走到環(huán)的起點(diǎn)有c個(gè)節(jié)點(diǎn)。
1.第一次相遇時(shí)
慢指針路程s=a+b-c涎显；
快指針路程是慢指針路程的兩倍2s= a+n*b+b-c,其中b為快指針完整走過(guò)的環(huán)的總?cè)?shù)坤检；
兩式相減得到s=n*b，因此 a+b-c = n*b棺禾，可得a=(n-1)b + c缀蹄。
2.第二次相遇時(shí)
舊的慢指針走過(guò)的路程：(n-1)b + c
新的慢指針走過(guò)的路程：a
代碼實(shí)現(xiàn)-雙指針
/**
* 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) {
//無(wú)環(huán)，返回null
if(head == null || head.next == null){
return null;
}
//判斷鏈表是否有環(huán)
boolean hasCycle = false;
ListNode slow = head, fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
//快慢指針第一次相遇時(shí)退出循環(huán)
hasCycle = true;
break;
}
}
//無(wú)環(huán)膘婶，返回null
if(!hasCycle){
return null;
}
//讓原來(lái)的快指針指向頭節(jié)點(diǎn)缺前，成為新的慢指針
fast = head;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
