环保行业网站建设,网站建设中企动力优,手机qq怎么用wordpress,wordpress如何添加安装导航题目#xff1a;环形链表 解法一#xff1a;哈希表
创建一个哈希表#xff0c;遍历链表先判断哈希表中是否含有要放入哈希表中的节点#xff0c;如果该节点已在哈希表中出现那么说明该链表是环形的#xff1b;如果链表节点出现nullptr那么就退出循环#xff0c;该链表是…题目环形链表 解法一哈希表
创建一个哈希表遍历链表先判断哈希表中是否含有要放入哈希表中的节点如果该节点已在哈希表中出现那么说明该链表是环形的如果链表节点出现nullptr那么就退出循环该链表是非环的。
时间复杂度O(n)
空间复杂度O(n)
class Solution {
public:bool hasCycle(ListNode *head) {unordered_setListNode* 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(vectorstring strs) {for(int i 0;istrs[0].size();i) //以第一个字符串作为基准也可以先选出长度最小的字符串选不选其实都一样{for(int j 1;jstrs.size();j){if((istrs[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;iret.size();i){if(ret[i] ! str[i] || istr.size()-1 )//当字符不相同/字符串长度长于return tmp;tmp.push_back(ret[i]);}return tmp;}string longestCommonPrefix(vectorstring strs) {//解法二两两比较string ret strs[0];for(int i 1;istrs.size();i){ret updateret(ret,strs[i]);}return ret;}
};
