題目：環(huán)形鏈表

?解法一：哈希表

創(chuàng)建一個(gè)哈希表，遍歷鏈表先判斷哈希表中是否含有要放入哈希表中的節(jié)點(diǎn)，如果該節(jié)點(diǎn)已在哈希表中出現(xiàn)那么說明該鏈表是環(huán)形的；如果鏈表節(jié)點(diǎn)出現(xiàn)nullptr那么就退出循環(huán)，該鏈表是非環(huán)的。

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(n)

class Solution {
public:bool hasCycle(ListNode *head) {unordered_set<ListNode*> hashtable;while(head){if(hashtable.count(head)) //先判斷哈希表中是否有將要放入哈希表中的這個(gè)節(jié)點(diǎn)return true;hashtable.emplace(head);head = head->next;}return false;}
};

解法二：快慢指針

主要思路就是仿照龜兔賽跑，slow指針是龜，fast指針是兔()，如果是環(huán)形鏈表那么龜兔就會(huì)相遇(這個(gè)相遇肯定是兔套了龜若干圈.....)

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(1)

class Solution {
public:bool hasCycle(ListNode *head) {if(nullptr == head)return false;ListNode* slow = head;ListNode* fast = head->next;while(fast){if(slow == fast){return true;}if(nullptr == fast->next){goto end;}else{fast = fast->next->next;}slow = slow->next;}end:return false;}
};

題目：最長公共前綴

解法一：遍歷

對(duì)每個(gè)string字符串的字母按順序一一判斷，也就是簡單遍歷

時(shí)間復(fù)雜度：O(nm)

空間復(fù)雜度：O(1)

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {for(int i = 0;i<strs[0].size();++i) //以第一個(gè)字符串作為基準(zhǔn)，也可以先選出長度最小的字符串，選不選其實(shí)都一樣{for(int j = 1;j<strs.size();++j){if((i>strs[j].size()-1) || (strs[0][i] != strs[j][i]))return strs[0].substr(0,i);}}return strs[0];}
};

解法二：兩兩判斷

兩個(gè)字符串進(jìn)行比較得到一個(gè)string對(duì)象ret(剛開始將ret定義為第一個(gè)字符串)，ret就是這兩個(gè)字符串的公共前綴，以此類推

時(shí)間復(fù)雜度：O(nm)

空間復(fù)雜度：O(m)

class Solution {
public://更新retstring updateret(string& ret,const string& str ){string tmp;for(int i = 0;i<ret.size();++i){if(ret[i] != str[i] || i>str.size()-1 )//當(dāng)字符不相同/字符串長度長于return tmp;tmp.push_back(ret[i]);}return tmp;}string longestCommonPrefix(vector<string>& strs) {//解法二：兩兩比較string ret = strs[0];for(int i = 1;i<strs.size();++i){ret = updateret(ret,strs[i]);}return ret;}
};