【leetcode】环形链表、最长公共前缀

题目：环形链表

 解法一：哈希表

创建一个哈希表，遍历链表先判断哈希表中是否含有要放入哈希表中的节点，如果该节点已在哈希表中出现那么说明该链表是环形的；如果链表节点出现nullptr那么就退出循环，该链表是非环的。

时间复杂度：O(n)

空间复杂度：O(n)

class Solution {
public:bool hasCycle(ListNode *head) {unordered_set<ListNode*> hashtable;while(head){if(hashtable.count(head)) //先判断哈希表中是否有将要放入哈希表中的这个节点return true;hashtable.emplace(head);head = head->next;}return false;}
};

解法二：快慢指针

主要思路就是仿照龟兔赛跑，slow指针是龟，fast指针是兔()，如果是环形链表那么龟兔就会相遇(这个相遇肯定是兔套了龟若干圈.....)

时间复杂度：O(n)

空间复杂度：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;}
};

题目：最长公共前缀

解法一：遍历

对每个string字符串的字母按顺序一一判断，也就是简单遍历

时间复杂度：O(nm)

空间复杂度：O(1)

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {for(int i = 0;i<strs[0].size();++i) //以第一个字符串作为基准，也可以先选出长度最小的字符串，选不选其实都一样{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];}
};

解法二：两两判断

两个字符串进行比较得到一个string对象ret(刚开始将ret定义为第一个字符串)，ret就是这两个字符串的公共前缀，以此类推

时间复杂度：O(nm)

空间复杂度：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 )//当字符不相同/字符串长度长于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;}
};