简介：wy的leetcode刷题记录_Day75声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：2024 1 23前言TOC2765. 最长交替子数组今天的每日一题是：2765. 最长交替子数组题目介绍给你一个下标从 0 开始的整数数组 nums 。如果 nums 中长度为 m 的子数组 s 满足以下条件，我们称它是一个 交替子数组 ：m 大于 1 。s1 = s0 + 1 。下标从 0 开始的子数组 s 与数组 [s0, s1, s0, s1,...,s(m 1) %2] 一样。也就是说，s1 s0 = 1 ，s2 s1 = 1 ，s3 s2 = 1 ，s4 s3 = 1，以此类推，直到 s[m 1] s[m 2] = ( 1)m 。请你返回 nums 中所有 交替 子数组中，最长的长度，如果不存在交替子数组，请你返回 1 。子数组是一个数组中一段连续 非空 的元素序列。示例 1：输入：nums = [2,3,4,3,4] 输出：4 解释：交替子数组有 [3,4] ，[3,4,3] 和 [3,4,3,4] 。最长的子数组为 [3,4,3,4] ，长度为4 。 示例 2：输入：nums = [4,5,6] 输出：2 解释：[4,5] 和 [5,6] 是仅有的两个交替子数组。它们长度都为 2 。提示：2 <= nums.length <= 1001 <= nums[i] <= 104思路方法一：暴力法解决：使用二重循环，外层循环遍历子数组的起始位置，内层循环遍历子数组。每当内层循环中子数组遇到不符合条件的字符，推出内层循环，更新最大长度。方法二：优化暴力：一重循环，接上述方法一，我们在内层循环中已经找到本次子数组中不符合条件的字符，当我们按照方法一让下一个字符作为子数组的开始时我们发现因为其满足上一子数组的条件所以不符合，同理直到我们找到的错字符，因此我们只需要以本次不符合条件的字符为子数组新的开始继续遍历即可。感觉自己说的不清楚这里放上别人的话：链接代码class Solution { public: int alternatingSubarray(vector<int>& a) { int n=a.size(); int ans= 1; for(int i=0;i<n 1;i++) { for(int j=i+1;j<n;j++) { int length=j i+1; if(a[j] a[i]==(length 1)%2) { ans=max(ans,length); } else break; } } return ans; } };class Solution { public: int alternatingSubarray(vector<int>& nums) { int n=nums.size(); int ans= 1; int first=0; for(int i=1;i<n;i++) { int length=i first+1; if(nums[i] nums[first]==(length 1)%2) ans=max(ans,length); else { if(nums[i] nums[i 1]==1) { first=i 1; ans=max(ans,2); } else{ first=i; } } } return ans; } };收获稍微复杂一点的模拟题

简介：wy的leetcode刷题记录_Day74声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：2024 1 22前言@TOC670. 最大交换今天的每日一题是：670. 最大交换题目介绍给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。示例 1 :输入: 2736 输出: 7236 解释: 交换数字2和数字7。 示例 2 :输入: 9973 输出: 9973 解释: 不需要交换。注意:给定数字的范围是 [0, 108]思路贪心寻找：根据题意我们只能做一次交换，通过寻找到第一个不符合降序排列的前一个数位就是交换的高位，然后高位之后中靠后的最大数的数位是交换的低位，做出交换。具体：二重循环，首先判断当前字符是否是所有后缀中最大的，若是则跳转到下一个字符；若不是则寻找到靠后的最大数进行交换。代码class Solution { public: int maximumSwap(int num) { string nums=to_string(num); int n=nums.size(); int max=nums[0]; int index=0; int ans=0; int flag=0; for(int i=0;i<n;i++) { max=nums[i]; for(int j=i;j<n;j++) { if(nums[j]>max) { flag=1; max=nums[j]; index=j; } } for(int j=i;j<n;j++) { if(nums[j]==max) { index=j; } } if(flag==1) { nums[index]=nums[i]; nums[i]=max; break; } } for (int i = 0; i < n; i++) { ans += (nums[i] 48) * pow(10, n i 1); } return ans; } };收获本来想着俩三分钟就有思路了但是还是做了好久，一两个星期没写代码有点生疏了，还是得常写常练啊。

简介：wy的leetcode刷题记录_Day72声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：前言@TOC2397. 被列覆盖的最多行数今天的每日一题是：2397. 被列覆盖的最多行数题目介绍给你一个下标从 0 开始、大小为 m x n 的二进制矩阵 matrix ；另给你一个整数 numSelect，表示你必须从 matrix 中选择的 不同 列的数量。如果一行中所有的 1 都被你选中的列所覆盖，则认为这一行被 覆盖 了。形式上，假设 s = {c1, c2, ...., cnumSelect} 是你选择的列的集合。对于矩阵中的某一行 row ，如果满足下述条件，则认为这一行被集合 s 覆盖：对于满足 matrixrow == 1 的每个单元格 matrixrow（0 <= col <= n 1），col 均存在于 s 中，或者row 中 不存在 值为 1 的单元格。你需要从矩阵中选出 numSelect 个列，使集合覆盖的行数最大化。返回一个整数，表示可以由 numSelect 列构成的集合 覆盖 的 最大行数 。示例 1：输入：matrix = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], numSelect = 2 输出：3 解释：图示中显示了一种覆盖 3 行的可行办法。 选择 s = {0, 2} 。第 0 行被覆盖，因为其中没有出现 1 。第 1 行被覆盖，因为值为 1 的两列（即 0 和 2）均存在于 s 中。第 2 行未被覆盖，因为 matrix2 == 1 但是 1 未存在于 s 中。第 3 行被覆盖，因为 matrix2 == 1 且 2 存在于 s 中。 因此，可以覆盖 3 行。 另外 s = {1, 2} 也可以覆盖 3 行，但可以证明无法覆盖更多行。示例 2：输入：matrix = [[1],[0]], numSelect = 1 输出：2 解释：选择唯一的一列，两行都被覆盖了，因为整个矩阵都被覆盖了。 所以我们返回 2 。思路暴力法解决：二进制枚举：使用二进制来表示每一行的1的分布情况以及搜寻情况，具体如下：使用mask[i]表示第i行中的1的分布情况，若mask[i]的二进制数位上为1其对应的矩阵中也为1。threshold用来表示当前遍历的选择列的情况，若threshold的二进制数位上为1则对应列被选中。代码class Solution { public: int maximumRows(vector<vector<int>>& matrix, int numSelect) { int row=matrix.size(); int col=matrix[0].size(); vector<int> mask(row,0);//表示当前行中1的情况 //初始化mask for(int i=0;i<row;i++) { for(int j=0;j<col;j++) { mask[i]+=matrix[i][j]<<(col j 1); } } int curr=0; int ans=0; int threshold=(1<<col); for(int i=1;i<=threshold;i++) { curr=0; if(__builtin_popcount(i)!=numSelect) { continue; } for(int j=0;j<row;j++) { if((mask[j]&i)==mask[j]) { curr++; } } ans=max(curr,ans); } return ans; } };收获通过使用二进制数可以表达的含义有很多可以简化很多操作。1137. 第 N 个泰波那契数1137. 第 N 个泰波那契数题目介绍泰波那契序列 Tn 定义如下： T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2给你整数 n，请返回第 n 个泰波那契数 Tn 的值。示例 1： 输入：n = 4 输出：4 解释： T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4 示例 2：输入：n = 25 输出：1389537思路其实这道题就是对斐波那契数列的一个重定义，只是递归条件增加，递归方程式需要改变一下即可。对于矩阵快速幂也是同理，重新梳理一下递推矩阵即可。代码递归（超时）：class Solution { public: int tribonacci(int n) { if(n<=1) return n; if(n==2) return 1; return tribonacci(n 1)+tribonacci(n 2)+tribonacci(n 3); } };递推（剩去了计算多余的fib数列）:class Solution { public: int tribonacci(int n) { if(n<=1) return n; if(n==2) return 1; int a=0;int b=1;int c=1; int ans=0; for(int i=3;i<=n;i++) { ans=a+b+c; a=b; b=c; c=ans; } return ans; } };矩阵快速幂： class Solution { public: //矩阵乘法 vector<vector<long>> martix_mutiply(vector<vector<long>> &a,vector<vector<long>>& b) { vector<vector<long>> c{{0,0,0},{0,0,0},{0,0,0}}; for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]+a[i][2]*b[2][j]; } } return c; } //快速幂 vector<vector<long>> martix_rapid_pow(vector<vector<long>> &a,int n) { vector<vector<long>> ret{{1,0,0},{0,1,0},{0,0,1}}; while(n>0) { if(n&1) { ret=martix_mutiply(ret,a); } n>>=1; a=martix_mutiply(a,a); } return ret; } int tribonacci(int n) { //矩阵快速幂 if (n < 2) { return n; } vector<vector<long>> q{{1, 1,1}, {1, 0,0},{0,1,0}}; vector<vector<long>> res = martix_rapid_pow(q, n 1); return res[0][0]; } }; 收获重温矩阵快速幂。

简介：wy的leetcode刷题记录_Day71声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：2024 1 3（补）前言@TOC2487. 从链表中移除节点今天的每日一题是：2487. 从链表中移除节点题目介绍给你一个链表的头节点 head 。移除每个右侧有一个更大数值的节点。返回修改后链表的头节点 head 。示例 1：> 输入：head = [5,2,13,3,8] 输出：[13,8] 解释：需要移除的节点是 5 ，2 和 3 。> 节点 13 在节点 5 右侧。节点 13 在节点 2 右侧。节点 8 在节点 3 右侧。示例 2：输入：head = [1,1,1,1] 输出：[1,1,1,1] 解释：每个节点的值都是 1 ，所以没有需要移除的节点。思路方法一：暴力解：通过两重嵌套循环来寻找新链表，具体如下：1.每一轮循环寻找当前链表的最大值将最大值加入新链表2.每一轮循环从上一次循环寻找到的加入新链表的节点开始遍历。（超时，时间复杂度n的2次方）方法二：换个思路：本题其实应该在考察寻找出链表中的右往左找非递减序列 可以从序列尾部开始遍历，俩种做法递归或者模拟栈。方法三：延续方法二的思路，这次我们不使用栈而是直接将链表反转来进行操作最后将符合条件的条件在进行一次反转即可。部分思路参考作者：力扣官方题解代码方法一：暴力/** * Definition for singly linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) * ListNode(int x) : val(x), next(nullptr) * ListNode(int x, ListNode *next) : val(x), next(next) * }; */ class Solution { public: ListNode* removeNodes(ListNode* head) { int maxVal=0; ListNode* maxValPointer=nullptr; ListNode* newHeader=nullptr; ListNode* temp=nullptr; int count=0; while(head) { count++; maxVal=0; maxValPointer=nullptr; while(head) { if(head >val>maxVal) { maxVal=head >val; maxValPointer=head; } head=head >next; } head=maxValPointer >next;//下一次遍历从新节点开始 if(count==1)//如果是头节点则创建新链表 { newHeader=maxValPointer; temp=newHeader; newHeader >next=nullptr; } else//如果是尾节点则加入新链表 { temp >next=maxValPointer; temp=temp >next; temp >next=nullptr; } } return newHeader; } };方法二：递归class Solution { public: ListNode* removeNodes(ListNode* head) { if (head == nullptr) { return nullptr; } head >next = removeNodes(head >next); if (head >next != nullptr && head >val < head >next >val) { return head >next; } else { return head; } } }; 模拟栈/** * Definition for singly linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) * ListNode(int x) : val(x), next(nullptr) * ListNode(int x, ListNode *next) : val(x), next(next) * }; */ class Solution { public: ListNode* removeNodes(ListNode* head) { //换个思路：本题其实应该在考察寻找出链表中的右往左找非递减序列 可以从序列尾部开始遍历 stack<ListNode* > stk; for(;head!=nullptr;head=head >next) { stk.push(head); } while(!stk.empty()) { if(head==nullptr||stk.top() >val>=head >val) { stk.top() >next=head; head=stk.top(); } stk.pop(); } return head; } };方法三：反转链表：class Solution { public: ListNode *reverse(ListNode *head) { ListNode dummy; while (head != nullptr) { ListNode *p = head; head = head >next; p >next = dummy.next; dummy.next = p; } return dummy.next; } ListNode* removeNodes(ListNode* head) { head = reverse(head); for (ListNode *p = head; p >next != nullptr; ) { if (p >val > p >next >val) { p >next = p >next >next; } else { p = p >next; } } return reverse(head); } }; 收获通过暴力模拟提高了解题的速度，手速题秒杀！后续的对时间复杂度的改进是通过对题目的深度解读，发现了另一种思路，转换思路之后得出了一种更为简洁的解法以及时间优化度更高的方法，通过模拟栈和递归俩种写法加深的对函数调用的理解。509. 斐波那契数动态规划基础篇之——509. 斐波那契数题目介绍斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：F(0) = 0，F(1) = 1 F(n) = F(n 1) + F(n 2)，其中 n > 1给定 n ，请计算 F(n) 。示例 1：输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1 示例 2：输入：n = 3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2 示例 3：输入：n = 4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3思路同之前的爬楼梯那一题十分相似都可以采用对应的递归方法或者递推方法以及矩阵快速幂...代码递归：class Solution { public: int fib(int n) { if(n==0||n==1) return n; return fib(n 1)+fib(n 2); } };递推:class Solution { public: int fib(int n) { int a=0; int b=1; int c=a+b; for(int i=2;i<=n;i++) { c=a+b; a=b; b=c; } return c; } };矩阵快速幂：class Solution { public: //矩阵乘法 vector<vector<int>> martix_mutiply(vector<vector<int>> &a,vector<vector<int>>& b) { vector<vector<int>> c{{0,0},{0,0}}; for(int i=0;i<2;i++) { for(int j=0;j<2;j++) { c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]; } } return c; } //快速幂 vector<vector<int>> martix_rapid_pow(vector<vector<int>> &a,int n) { vector<vector<int>> ret{{1,0},{0,1}}; while(n>0) { if(n&1) { ret=martix_mutiply(ret,a); } n>>=1; a=martix_mutiply(a,a); } return ret; } int fib(int n) { //矩阵快速幂 if (n < 2) { return n; } vector<vector<int>> q{{1, 1}, {1, 0}}; vector<vector<int>> res = martix_rapid_pow(q, n 1); return res[0][0]; } };收获巩固矩阵快速幂！

简介：wy的leetcode刷题记录_Day70声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：前言@TOC466. 统计重复个数今天的每日一题是：466. 统计重复个数题目介绍定义 str = [s, n] 表示 str 由 n 个字符串 s 连接构成。例如，str == ["abc", 3] =="abcabcabc" 。如果可以从 s2 中删除某些字符使其变为 s1，则称字符串 s1 可以从字符串 s2 获得。例如，根据定义，s1 = "abc" 可以从 s2 = "abdbec" 获得，仅需要删除加粗且用斜体标识的字符。现在给你两个字符串 s1 和 s2 和两个整数 n1 和 n2 。由此构造得到两个字符串，其中 str1 = [s1, n1]、str2 = [s2, n2] 。请你找出一个最大整数 m ，以满足 str = [str2, m] 可以从 str1 获得。示例 1： 输入：s1 = "acb", n1 = 4, s2 = "ab", n2 = 2 输出：2示例 2： 输入：s1 = "acb", n1 = 1, s2 = "acb", n2 = 1 输出：1思路好好好，三个月没写代码上来给一个hard题，行，我直接CV，写不了一点。看了题解后发现其实就是寻找循环结：通俗一点就是在一个循环结中存在n1个s1中对应n2个s2，即寻找n1与n2的关系。而对于最后一个循环结可能是不完整的，所以对于最后一个循环结直接采用暴力匹配即可。其次，这边不是很懂他这个循环结的寻找方式啊，到时候再看看题解。代码class Solution { public: int getMaxRepetitions(string s1, int n1, string s2, int n2) { if (n1 == 0) { return 0; } int s1cnt = 0, index = 0, s2cnt = 0; // recall 是我们用来找循环节的变量，它是一个哈希映射 // 我们如何找循环节？假设我们遍历了 s1cnt 个 s1，此时匹配到了第 s2cnt 个 s2 中的第 index 个字符 // 如果我们之前遍历了 s1cnt' 个 s1 时，匹配到的是第 s2cnt' 个 s2 中同样的第 index 个字符，那么就有循环节了 // 我们用 (s1cnt', s2cnt', index) 和 (s1cnt, s2cnt, index) 表示两次包含相同 index 的匹配结果 // 那么哈希映射中的键就是 index，值就是 (s1cnt', s2cnt') 这个二元组 // 循环节就是； // 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2 // 以后的每 (s1cnt s1cnt') 个 s1 包含了 (s2cnt s2cnt') 个 s2 // 那么还会剩下 (n1 s1cnt') % (s1cnt s1cnt') 个 s1, 我们对这些与 s2 进行暴力匹配 // 注意 s2 要从第 index 个字符开始匹配 unordered_map<int, pair<int, int>> recall; pair<int, int> pre_loop, in_loop; while (true) { // 我们多遍历一个 s1，看看能不能找到循环节 ++s1cnt; for (char ch: s1) { if (ch == s2[index]) { index += 1; if (index == s2.size()) { ++s2cnt; index = 0; } } } // 还没有找到循环节，所有的 s1 就用完了 if (s1cnt == n1) { return s2cnt / n2; } // 出现了之前的 index，表示找到了循环节 if (recall.count(index)) { auto [s1cnt_prime, s2cnt_prime] = recall[index]; // 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2 pre_loop = {s1cnt_prime, s2cnt_prime}; // 以后的每 (s1cnt s1cnt') 个 s1 包含了 (s2cnt s2cnt') 个 s2 in_loop = {s1cnt s1cnt_prime, s2cnt s2cnt_prime}; break; } else { recall[index] = {s1cnt, s2cnt}; } } // ans 存储的是 S1 包含的 s2 的数量，考虑的之前的 pre_loop 和 in_loop int ans = pre_loop.second + (n1 pre_loop.first) / in_loop.first * in_loop.second; // S1 的末尾还剩下一些 s1，我们暴力进行匹配 int rest = (n1 pre_loop.first) % in_loop.first; for (int i = 0; i < rest; ++i) { for (char ch: s1) { if (ch == s2[index]) { ++index; if (index == s2.size()) { ++ans; index = 0; } } } } // S1 包含 ans 个 s2，那么就包含 ans / n2 个 S2 return ans / n2; } }; 收获没啥收获，太难了，仔细看了下题解能看懂，希望过几天能回来复现一下！70. 爬楼梯本题来自动态规划基础篇之——70. 爬楼梯题目介绍假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？示例 1：输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。1 阶 + 1 阶2 阶示例 2：输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。1 阶 + 1 阶 + 1 阶1 阶 + 2 阶2 阶 + 1 阶思路方法一：一般直接递归，递推函数F(n)=F(n 1)+F(n 2)，(n>=2)，其中F(1)=1,F(2)=2。F(n)表示第n阶台阶有多少种方式走上去，而根据只能通过走一阶和走两阶这二中方式才行，所以得出递推公式。（递归也可以，递推也行）方法二：矩阵快速幂我就不多说了，去看下题解，解的很巧，一般用于其次方程组，非齐次也可以转为为齐次再用这个方法。方法三：通项公式计算机的尽头是数学！代码class Solution { public: int climbStairs(int n) { if(n==1) return 1; if(n==2) return 2; int a1=1; int a2=2; int ans=0; for(int i=3;i<=n;i++) { ans=a1+a2; a1=a2; a2=ans; } return ans; } };收获矩阵快速幂这种方式十分的快，在解决某些有规律的递推公式上有着十分迅速的解决方式以及是分小的开销。