0510刷题
LeetCode 24. 两两交换链表中的节点 LeetCode 24. 两两交换链表中的节点class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
ListNode* cur = dummyHead;
while(cur->next != nullptr && cur->next->next != nullptr) {
ListNode* tmp = cur->next; // 记录临时节点
ListNode* tmp1 = cur->next->next->next; // 记录临时节点
cur->next = cur->next->next; // 步骤一
cur->next->next = tmp; // 步骤二
cur->next->next->next = tmp1; // 步骤三
cur = cur->next->next; // cur移动两位，准备下一轮交换
}
return dummyHead->next;
}
};
思路：
这道题目正常模拟就可以了。
建议使用虚拟头结点，这样会方便很多，要不然每次针对头结点（没有前一个指针指向头结点），还要单独处理。
接下来就是交换相邻两个元素了，此时一定要画图，不画图，操作多个指针很容易乱，而且要操作的先后顺序
初始时，cur指向虚拟头结点，然后进行如下三步：
操作之后，链表如下：
看这个可能就更直观一些了：
面试题 02.07. 链表相交 面试题 02.07. 链表相交class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* tmp1=headA;
ListNode* tmp2=headB;
while(tmp1!=tmp2)
{
if(tmp1) tmp1=tmp1->next;
else tmp1=headB;
if(tmp2) tmp2=tmp2->next;
else tmp2=headA;
}
return tmp1==NULL?NULL:tmp1;
}
};
也即：
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *curA = headA, *curB = headB;
while (curA != curB) {
curA = curA != nullptr ? curA->next : headB;
curB = curB != nullptr ? curB->next : headA;
}
return curA;
}
};
LeetCode 142. 环形链表 II
LeetCode 142. 环形链表 II
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow=head;
ListNode* fast=head;
while(fast!=NULL&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
slow=head;
while(slow!=fast)
{
slow=slow->next;
fast=fast->next;
}
return slow;
}
}
return NULL;
}
};
LeetCode 49. 字母异位词分组
LeetCode 49. 字母异位词分组
自己的解法：思路正确，但是时间复杂度为O(n)，数据量过大时超时了。
class Solution {
public:
bool cmp(string s,string t)
{
int num[26]={0};
for(auto &com:s) num[com-'a']++;
for(auto &com:t) num[com-'a']--;
for(auto &c:num)
{
if(c!=0) return false;
}
return true;
}
vector> groupAnagrams(vector& strs) {
vector> result;
int n=strs.size();
vector flag(n,1);
for(int i=0;i
vector tmp;
if(flag[i]!=0)
{
tmp.push_back(strs[i]);
flag[i]=0;
for(int j=i+1;j
if(flag[j]!=0&&cmp(strs[i],strs[j]))
{
tmp.push_back(strs[j]);
flag[j]=0;
}
}
}
if(tmp.size()!=0) result.push_back(tmp);
}
return result;
}
};
参考答案的做法：
由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。原来的字符串为str，重新排序之后为key，如果mp中有key的键值，则将str压入key键值对应的vector中。
class Solution {
public:
vector> groupAnagrams(vector& strs) {
unordered_map> mp;
for (string& str: strs) {
string key = str;
sort(key.begin(), key.end());
mp[key].emplace_back(str);
}
vector> ans;
for (auto it = mp.begin(); it != mp.end(); ++it) {
ans.emplace_back(it->second);
}
return ans;
}
};
也即：
class Solution {
public:
vector> groupAnagrams(vector& strs) {
unordered_map> umap;
for(auto &str:strs)
{
string tmp=str;
sort(tmp.begin(),tmp.end());
umap[tmp].push_back(str);
}
vector> result;
for(auto &c:umap)
{
result.push_back(c.second);
}
return result;
}
};
LeetCode 438. 找到字符串中所有字母异位词
LeetCode 438. 找到字符串中所有字母异位词
方法：哈希+滑动窗口法
class Solution {
public:
vector findAnagrams(string s, string p) {
int sLen = s.size(), pLen = p.size();
if (sLen < pLen) return {};
vector result;
vector sCount(26);
vector pCount(26);
//统计长度为pLen的字符串中，各个小写字母出现的次数
for (int i = 0; i < pLen; ++i)
{
++sCount[s[i] - 'a'];
++pCount[p[i] - 'a'];
}
//如果相等，则0符合要求
if (sCount == pCount)
{
result.emplace_back(0);
}
//长度为pLen的窗口向右滑动
//移出的元素个数--
//移入的元素个数++
for (int i = 0; i < sLen - pLen; ++i)
{
--sCount[s[i] - 'a'];
++sCount[s[i + pLen] - 'a'];
//相等，则push_back进result
if (sCount == pCount)
{
result.emplace_back(i + 1);
}
}
return result;
}
};
说明：
当字符串 s 的长度小于字符串 p 的长度时，字符串 s 中一定不存在字符串 p 的异位词。
由于子串是连续的，且异位词不会改变字符串中每个字符的个数，所以只有当两个字符串每个字符的个数均相等时，一个字符串才是另一个字符串的异位词。
使用两个数组 sCount和 pCount分别统计 s 和 p 中字母的个数。
由于需要遍历的子串 p 长度均为 pLen ，我们可以使用一个固定长度为 pLen 的滑动窗口来维护 sCount：滑动窗口每向右滑动一次，就多统计一次进入窗口的字符，少统计一次离开窗口的字符。然后，判断 sCount是否与 pCount相等，若相等则意味着 p 的异位词之一是 s 的子串。
