141. 環形鏈表

思路：判斷鏈表中是否有環是經典的算法問題之一。常見的解決方案有多種，其中最經典、有效的一種方法是使用 快慢指針（Floyd’s Cycle-Finding Algorithm）。

• 初始化兩個指針：一個快指針（fast）指向頭節點的下一個節點（head->next），一個慢指針（slow）指向頭節點（head)。
• 移動指針：
  • 慢指針每次移動一步。
  • 快指針每次移動兩步。
• 判斷環的存在：
  • 如果鏈表中存在環，那么快指針和慢指針最終會在環中相遇。
  • 如果鏈表沒有環，快指針會遇到 NULL（鏈表的末尾）。

解答如下：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {//如果頭指針為空或者下一個為空即鏈表只有一個元素//那么這個鏈表就不是循環的if(head == nullptr  || head->next == nullptr ){return false ;}ListNode* slow = head;ListNode* fast = head->next;//循環停止的條件是slow和fast指向同一個元素//或者 fast或fast->next指向NULLwhile(slow != fast){if(fast == nullptr  || fast->next == nullptr ){return false ;}slow = slow->next ;fast = fast->next->next ;}return true ;}
};

循環條件也可以改為其他的形式，或者使用do-while循環，使用do-while循環，則需要對fast和slow的初值進行更改：

//使用do-while循環
class Solution {
public:bool hasCycle(ListNode *head) {//如果頭指針為空或者下一個為空即鏈表只有一個元素//那么這個鏈表就不是循環的if(head == nullptr  || head->next == nullptr ){return false ;}ListNode* slow = head;ListNode* fast = head;//循環停止的條件是slow和fast指向同一個元素//或者 fast或fast->next指向NULLdo{if(fast == nullptr || fast->next == nullptr){return false ;}slow = slow->next ;fast = fast->next->next ;}while(slow != fast);return true ;}
};

另外也可以將fast != nullptr && fast->next != nullptr放在外層：

class Solution {
public:bool hasCycle(ListNode *head) {//如果頭指針為空或者下一個為空即鏈表只有一個元素//那么這個鏈表就不是循環的if(head == nullptr  || head->next == nullptr ){return false ;}ListNode* slow = head;ListNode* fast = head;//循環停止的條件是slow和fast指向同一個元素//或者 fast或fast->next指向NULLwhile(fast != nullptr && fast->next != nullptr){//在循環中應首先移動指針，然后再檢查 slow 和 fast 是否相等slow = slow->next ;fast = fast->next->next ;if(slow == fast){return true ;}}return false ;}
};

524.?通過刪除字母匹配到字典里最長單詞

題目描述：給你一個字符串?s?和一個字符串數組?dictionary?，找出并返回?dictionary?中最長的字符串，該字符串可以通過刪除?s?中的某些字符得到。如果答案不止一個，返回長度最長且字母序最小的字符串。如果答案不存在，則返回空字符串。

思路：開始自己想起來有點亂糟糟的，看了一下官方給的思路，然后理了一下。

在寫的過程中，while塊中的語句些的稍微復雜了一點，看了別人的代碼后改了一下，原來是這樣寫的：完全按照想的邏輯,沒有思考簡化

while(m<slen){//只要還沒將s搜索完就要繼續搜索if(s[m] == dictionary[i][d]){d++;m++;} else{m++;}
}

然后就是if塊中的代碼，寫得亂糟糟的也，看了一下別人的代碼，茅塞頓開，我寫的時候在想，怎么才能順利的存進去第一個滿足要求的字符串，因為最開始沒有目標字符串，怎么比較長度呢，后來知道使用默認構造函數 string ans; 定義一個 std::string 對象時，它會被初始化為一個空字符串，長度為0，所以可以這樣直接比較。

基礎薄弱腦袋空空

正確代碼如下：

class Solution {
public:string findLongestWord(string s, vector<string>& dictionary) {int k = dictionary.size();//長度為4int slen = s.length();//長度為8string obj ;for(int i = 0;i<k;i++){//int cnt = 0;//獲得每一個元素的長度lenint len = dictionary[i].size();//例如第一個元素為ale，長度就為3//下面判斷該元素是不是字符串s的子元素int m=0,d=0;while(m<slen){//只要還沒將s搜索完就要繼續搜索if(s[m] == dictionary[i][d]){d++;} m++;}//cnt==len說明該字符串在字典中存在if(d == len ){if(len > obj.length()){obj = dictionary[i];//有點奇怪，為什么要加一個dictionary[i] < obj這個條件//原題目中字母序最小的字母序最小的字符串是這個意思嘛//比較相同長度的字符串的大小，輸出小的作為最后的結果} else if((len == obj.length()) && dictionary[i] < obj){obj = dictionary[i] ;} else{obj = obj ;}}}return obj;}
};//csdn上的答案
/*class Solution {
public:string findLongestWord(string s, vector<string>& dictionary) {//處理string ans;int n = s.size();//字符串的長度//auto& str : dictionary 是 C++11 引入的范圍基 for 循環的一部分//用于遍歷容器 dictionary 中的每個元素，并使用 str 作為對每個元素的引用。for (auto& str : dictionary){int m = str.size();//dictionary中元素的長度int i = 0, j = 0;while (i < m && j < n){if (str[i] == s[j]) i++;j++;}//處理if (i == m){if (str.size() > ans.size()){ans = str;}else if (str.size() == ans.size() && str < ans){ans = str;}}}return ans;}
};*/

雙指針問題告一小段落，前面還有幾題寫了但是沒有記錄，懶得再整理了力扣上留有痕跡