简介：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; } };收获矩阵快速幂这种方式十分的快，在解决某些有规律的递推公式上有着十分迅速的解决方式以及是分小的开销。

简介：wy的leetcode刷题记录_Day68声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：2023 6 7前言@TOC2611. 老鼠和奶酪2611. 老鼠和奶酪题目介绍有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。下标为 i 处的奶酪被吃掉的得分为：如果第一只老鼠吃掉，则得分为 reward1[i] 。如果第二只老鼠吃掉，则得分为 reward2[i] 。给你一个正整数数组 reward1 ，一个正整数数组 reward2 ，和一个非负整数 k 。请你返回第一只老鼠恰好吃掉 k 块奶酪的情况下，最大得分为多少。示例 1：输入：reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2 输出：15解释：这个例子中，第一只老鼠吃掉第 2 和 3 块奶酪（下标从 0 开始），第二只老鼠吃掉第 0 和 1 块奶酪。 总得分为 4 + 4 +3 + 4 = 15 。 15 是最高得分。 示例 2：输入：reward1 = [1,1], reward2 = [1,1], k = 2 输出：2 解释：这个例子中，第一只老鼠吃掉第 0 和1 块奶酪（下标从 0 开始），第二只老鼠不吃任何奶酪。 总得分为 1 + 1 = 2 。 2 是最高得分。思路简单的贪心+模拟：新建立一个数组reward3用来记录reward1和reward2的差，我们假设老鼠2吃完了所有的奶酪，但是此时要求老鼠1也需要吃k个并得分最大，这时我们将reward3对应的加入reward2就是reward1中的值，那么我们只需要将reward3中最大的k个加入reward2中即可。代码class Solution { public: int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) { int n=reward1.size(); vector<int> reward3(n); int ans=0; for(int i=0;i<n;i++) { ans+=reward2[i]; reward3[i]=reward1[i] reward2[i]; } sort(reward3.begin(),reward3.end(),greater<int>()); for(int i=0;i<k;i++) { ans+=reward3[i]; } return ans; } };收获简单的贪心+模拟

简介：wy的leetcode刷题记录_Day68声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：2023 6 6前言@TOC1019. 链表中的下一个更大节点2352. 相等行列对题目介绍给你一个下标从 0 开始、大小为 n x n 的整数矩阵 grid ，返回满足 Ri 行和 Cj 列相等的行列对 (Ri, Cj) 的数目。如果行和列以相同的顺序包含相同的元素（即相等的数组），则认为二者是相等的。示例 1：输入：grid = [[3,2,1],[1,7,6],[2,7,7]] 输出：1 解释：存在一对相等行列对：(第 2 行，第 1 列)：[2,7,7]示例 2：输入：grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]] 输出：3 解释：存在三对相等行列对：(第 0 行，第 0 列)：[3,1,2,2](第 2 行, 第 2 列)：[2,4,2,2](第 3 行, 第 2 列)：[2,4,2,2]思路1.暴力解法：提出每一行的元素与每一列的元素进行比对。（简易优化思路：空间换时间，建立2n个序列，分别保留每行和每列的元素，再进行比较）2.哈希表（上面解法的建议优化思路）：首先将矩阵的行放入哈希表中统计次数，哈希表的键可以是将行拼接后的字符串，也可以用各语言内置的数据结构，然后分别统计每一列相等的行有多少，求和即可。代码class Solution { public: int equalPairs(vector<vector<int>>& grid) { int n = grid.size(); map<vector<int>, int> cnt; for (auto row : grid) { cnt[row]++; } int res = 0; for (int j = 0; j < n; j++) { vector<int> arr; for (int i = 0; i < n; i++) { arr.emplace_back(grid[i][j]); } if (cnt.find(arr) != cnt.end()) { res += cnt[arr]; } } return res; } }; 收获简单的模拟题

简介：wy的leetcode刷题记录_Day61声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：2022 12 26前言@TOC1759. 统计同构子字符串的数目今天的每日一题是：1759. 统计同构子字符串的数目题目介绍给你一个字符串 s ，返回 s 中 同构子字符串 的数目。由于答案可能很大，只需返回对 109 + 7 取余 后的结果。同构字符串 的定义为：如果一个字符串中的所有字符都相同，那么该字符串就是同构字符串。子字符串 是字符串中的一个连续字符序列。示例 1： 输入：s = "abbcccaa" 输出：13 解释：同构子字符串如下所列： "a" 出现 3 次。 "aa" 出现 1次。 "b" 出现 2 次。 "bb" 出现 1 次。 "c" 出现 3 次。 "cc" 出现 2 次。 "ccc" 出现 1次。 3 + 1 + 2 + 1 + 3 + 2 + 1 = 13示例 2： 输入：s = "xy" 输出：2 解释：同构子字符串是 "x" 和 "y" 。思路方法一：暴力解法：遍历整个字符串，每一次遍历到不同的字符我们将前面的切除掉，然后计算当前字符串得分，得分规则设当前字符重复n次，得分为递增求和公式temp+temp*(temp 1)/2，超时原因是字符串切割次数过多。（超时）方法二：改进简单模拟：遍历整个字符串，每一次迭代我们不进行字符串的切分，使用一个变量来记录当前对比的字符即可，对于一个字符的重复了n次那么其贡献值为n*(n+1)/2，然后我们再跳到下一个不同的字符，并跟新对比的字符以及出现次数。代码class Solution { public: int countHomogenous(string s) { int n=s.size(); if(n==1) return 1; if(n==0) return 0; int ans=0; for(int i=0;i<n;) { if(i==n) break; int temp=helper(s); if(temp==1) { ans++; i++; } else { ans+=temp+temp*(temp 1)/2; i+=temp; } s=s.substr(temp); } return ans; } int helper(string s) { char Compare=s[0]; int res=1; int n=s.size(); if(n==1) return 1; for(int i=1;i<n;i++) { if(s[i]==Compare) res++; else return res; } return res; } };class Solution { public: int countHomogenous(string s) { long long MOD = 1000000007; int n=s.size(); if(n==1) return 1; if(n==0) return 0; int ans=0; char prev=s[0]; int temp=1; for(int i=1;i<n;i++) { if(i==n) break; //int temp=helper(s); if(prev==s[i]) { temp++; } else{ prev=s[i]; ans+=(temp + 1) * temp / 2; temp=1; } //s=s.substr(temp); } ans+=(long)(long)(temp + 1) * temp / 2%MOD; return ans%MOD; } 收获多观察才能知道自己哪里需要改进

简介：wy的leetcode刷题记录_Day62声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：2022 12 27前言@TOC1750. 删除字符串两端相同字符后的最短长度今天的每日一题是：1750. 删除字符串两端相同字符后的最短长度题目介绍给你一个只包含字符 'a'，'b' 和 'c' 的字符串 s ，你可以执行下面这个操作（5 个步骤）任意次：选择字符串 s 一个 非空 的前缀，这个前缀的所有字符都相同。选择字符串 s 一个 非空 的后缀，这个后缀的所有字符都相同。前缀和后缀在字符串中任意位置都不能有交集。前缀和后缀包含的所有字符都要相同。同时删除前缀和后缀。请你返回对字符串 s 执行上面操作任意次以后（可能 0 次），能得到的 最短长度 。示例 1： 输入：s = "ca" 输出：2 解释：你没法删除任何一个字符，所以字符串长度仍然保持不变。示例 2： 输入：s = "cabaabac" 输出：0 解释：最优操作序列为：选择前缀 "c" 和后缀 "c" 并删除它们，得到 s = "abaaba" 。选择前缀 "a" 和后缀 "a" 并删除它们，得到 s = "baab" 。选择前缀 "b" 和后缀 "b" 并删除它们，得到 s = "aa" 。选择前缀 "a" 和后缀 "a" 并删除它们，得到 s = "" 。思路简单模拟法：采用双指针，分别从字符串的头部和尾部开始遍历，对于每一次迭代我们的目标就是消除当前迭代的前缀和后缀，于是每一个迭代我们执行：从当前头部指针i寻找需要判别的字符判断头指针和尾指针字符是否相等，若相等继续，否则直接返回当前长度寻找前后缀及长度在寻找后缀时需要判断是否前后缀有重复的字符最后当我们的头指针或者尾指针不相等亦或者字符串遍历完比时，我们返回原字符串长度 执行操作的字符串长度即为答案。代码class Solution { public: int minimumLength(string s) { int n=s.size(); int i=0; int j=n 1; int ans=0; while(i<j) { if(s[i]!=s[j]) break; char Compare=s[i]; //找前缀 while(Compare==s[i]) { // if(i<j) // break; i++; ans++; } //找后缀 while(Compare==s[j]) { if(i>=j) break; j ; ans++; } } return n ans; } };收获简单的模拟题108. 将有序数组转换为二叉搜索树108. 将有序数组转换为二叉搜索树题目介绍给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。示例 1：输入：nums = [ 10, 3,0,5,9] 输出：[0, 3,9, 10,null,5]解释：[0, 10,5,null, 3,null,9] 也将被视为正确答案：示例 2：输入：nums = [1,3] 输出：[3,1]解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。思路很正常的将有序数组的中间作为当前迭代的根节点左区间为左子树，右区间为右子树。代码class Solution { private: TreeNode* traversal(vector<int>& nums, int left, int right) { if (left > right) return nullptr; int mid = left + ((right left) / 2); TreeNode* root = new TreeNode(nums[mid]); root >left = traversal(nums, left, mid 1); root >right = traversal(nums, mid + 1, right); return root; } public: TreeNode* sortedArrayToBST(vector<int>& nums) { TreeNode* root = traversal(nums, 0, nums.size() 1); return root; } };收获二叉树刷的时间段有点长中间忘了很多期待二刷