Leetcode每日一题 —— 3741. 三个相等元素之间的最小距离 II

50. Pow(x, n) - 力扣（LeetCode）

这题考察快速幂，很经典的减治 / 二分思想算法。

class Solution { public: double myPow(double x, int n) { // 这题显然考察快速幂算法 if(n==0){ return 1.0L; } if(x==0){ // x=0 的时候必定有 n>0, 0^n=0 return 0.0L; } // 很坑的一点，指数可能是 -2^31，取负后 int 没法表示 long long exp=n; if(n<0){ // 注意 n 可能是负数 // 负数的话先取倒 x=1/x; exp=-(long long)n; } // 接下来就可以愉快计算快速幂了 auto power=[&](auto&& self,long long p)->double{ if(p==0){ return 1.0L; } if(p==1){ return x; } double res=1.0L; if((p&1)==1){ // 如果是奇数，单独拆一次乘法出来 res=x; p--; } double powerRes=self(self, p>>1); return res*powerRes*powerRes; }; return power(power,exp); } };

206. 反转链表 - 力扣（LeetCode）

• 迭代法的话头插法思路非常自然；递归写法稍微复杂一些。

迭代写法：

class Solution { public: ListNode* reverseList(ListNode* head) { // 这题迭代比递归好写 // 头插法很容易能反转链表 ListNode* ptr=head; ListNode* res=nullptr; while(ptr!=nullptr){ ListNode* next=ptr->next; ptr->next=res; res=ptr; ptr=next; } return res; } };

递归写法：

class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* res=nullptr; auto solve=[&](auto&& self, ListNode* curr){ // 这种题首先就可以考虑能否用递归解决 if(curr==nullptr||curr->next==nullptr){ res=curr; return curr; } ListNode* node=self(self,curr->next); node->next=curr; curr->next=nullptr; return curr; }; solve(solve,head); return res; } };

213. 打家劫舍 II - 力扣（LeetCode）

• 这题可以转换回打家劫舍 I。
• 分类讨论进行递推：
  1. 最开始偷了第一间屋子，那么最后一间肯定不能偷，在 [0, n-2] 范围内递推。
  2. 最开始偷了第二间屋子，那么就可以偷最后一间，在 [1, n-1] 范围内递推。

class Solution { public: int rob(vector<int>& nums) { // 如果只有一间屋子，直接偷 if(nums.size()==1){ return nums[0]; } // 其实可以分类讨论来递推 // 1. 如果偷了第一间屋子，那么最后一间肯定不能偷，在 [0, n-2] 范围内递推 // 2. 如果投了第二间屋子，那么就可以偷最后一间，在 [1, n-1] 范围内递推 auto solve=[&](int left,int right){ if(left>right){ return 0; } int prevPrev=0; int prev=nums[left]; for(int i=left+1;i<=right;i++){ int tmpPrev=prev; prev=max(prevPrev+nums[i],prev); prevPrev=tmpPrev; } return prev; }; return max( solve(0, nums.size()-2), solve(1, nums.size()-1) ); } };

234. 回文链表 - 力扣（LeetCode）

• O(n) 时间复杂度，O(1) 额外空间。采用的是快慢指针找到链表中点，慢指针顺带构建一个逆转后的链表。慢指针过中点后，就可以比较后一半链表和逆转后链表的各个节点了。
• 这题要注意备份指针要指向的下一个结点，因为过程中会拆掉原链表来一个逆转链表。

class Solution { public: bool isPalindrome(ListNode* head) { // 需要找到链表的中间节点 // 可以用快慢指针，逆转前半段链表，然后后半段一起扫描进行判断 ListNode* reversed=nullptr; ListNode *fast=head,*slow=head; while(fast!=nullptr){ ListNode* slowNext=slow->next; ListNode* fastNext=fast->next; slow->next=reversed; reversed=slow; slow=slowNext; fast=fastNext; if(fast==nullptr){ // 这里断了说明不是偶数长度链表 // 这个时候 slow 指向最中间节点，这个节点已经加入 reversed // reversed 要忽略最中间这个节点 reversed=reversed->next; break; } fast=fast->next; } // 接着比较 slow 及其之后的节点 bool res=true; while(slow!=nullptr){ if(reversed->val!=slow->val){ res=false; break; } reversed=reversed->next; slow=slow->next; } return res; } };

141. 环形链表 - 力扣（LeetCode）

• 依旧快慢指针，如果有环，两个指针必然在某一刻相遇。

class Solution { public: bool hasCycle(ListNode *head) { // 可以用快慢指针来做，如果有环，快慢指针必然会在某一刻相交 ListNode *fast=head,*slow=head; while(fast!=nullptr){ slow=slow->next; fast=fast->next; if(fast==nullptr){ break; } fast=fast->next; if(slow==fast){ return true; } } return false; } };