简介：wy的leetcode刷题记录_Day67声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：2023 6 1前言@TOC1019. 链表中的下一个更大节点222. 完全二叉树的节点个数题目介绍给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。示例 1：输入：root = [1,2,3,4,5,6] 输出：6 示例 2：输入：root = [] 输出：0 示例 3：输入：root = [1] 输出：1思路1.无脑DFS（未利用完全二叉树的性质）2.二分查找+位运算（为完全利用完全二叉树的性质）3.利用完全二叉树的性质，完全二叉树的子树中如果不是满二叉树必定只有一个非满二叉树代码/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) * TreeNode(int x) : val(x), left(nullptr), right(nullptr) * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) * }; */ class Solution { public: int ans=0; int countNodes(TreeNode* root) { dfs(root); return ans; } void dfs(TreeNode *node) { if(node ==nullptr) return ; ans++; dfs(node >left); dfs(node >right); } };class Solution { public: int countNodes(TreeNode* root) { if (root == nullptr) { return 0; } int level = 0; TreeNode* node = root; while (node >left != nullptr) { level++; node = node >left; } int low = 1 << level, high = (1 << (level + 1)) 1; while (low < high) { int mid = (high low + 1) / 2 + low; if (exists(root, level, mid)) { low = mid; } else { high = mid 1; } } return low; } bool exists(TreeNode* root, int level, int k) { int bits = 1 << (level 1); TreeNode* node = root; while (node != nullptr && bits > 0) { if (!(bits & k)) { node = node >left; } else { node = node >right; } bits >>= 1; } return node != nullptr; } }; /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) * TreeNode(int x) : val(x), left(nullptr), right(nullptr) * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) * }; */ class Solution { public: int ans=0; int countNodes(TreeNode* root) { if(root==nullptr) return 0; int l_depth=0; int r_depth=0; TreeNode* node=root; while(node >left!= nullptr) { node=node >left; l_depth++; } node=root; while(node >right) { node=node >right; r_depth++; } if(l_depth==r_depth) return pow(2,(l_depth+1)) 1; else return countNodes(root >left)+countNodes(root >right)+1; } }; 收获简单的模拟题

简介：摘要！s

简介：wy的leetcode刷题记录_Day64声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：2023 3 29前言@TOC1641. 统计字典序元音字符串的数目今天的每日一题是：1641. 统计字典序元音字符串的数目题目介绍给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。字符串 s 按 字典序排列 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。示例 1：输入：n = 1 输出：5 解释：仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"] 示例 2：输入：n = 2 输出：15 解释：仅由元音组成的 15 个字典序字符串为["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]。注意，"ea" 不是符合题意的字符串，因为 'e' 在字母表中的位置比 'a' 靠后 示例 3： 输入：n = 33 输出：66045思路归纳总结法：列出表格看图：数学分析法：我们想象有五个盒子，共有n个小球。从左往右盒子编号依次为a、e、i、o、u，我们必须从左往右再拿n个小球出来，每当我们拿出一个小球时，将盒子上的编号填入字符串即可。这样子就转换成这n个小球该如何放入这5个盒子并且盒子可以为空的排列组合问题。我们假设有n+5个球，多出的5个球分别放入a、e、i、o、u，这样剩下n个就可以随便放入了。就是在这n个球中插入四个隔板分成五类，四个隔板在n 1个空中随机分布C（4 n 1）。或者你将n个球盒子不为空和空1个一直到空5个的情况加起来也可以。代码class Solution { public: int countVowelStrings(int n) { vector<vector<int>> dp(n+1,vector<int>(5)); // int dp[n][5]; if(n==1) return 5; for(int i=0;i<5;i++) { dp[0][i]=1; } for(int i=0;i<n+1;i++) { dp[i][0]=1; } for(int i=1;i<n+1;i++) { for(int j=1;j<5;j++) { dp[i][j] = dp[i][j 1] + dp[i 1][j]; } } return dp[n][4]; } };class Solution { public: int countVowelStrings(int n) { return (n + 4) * (n + 3) * (n + 2) * (n + 1) / 24; } }; 收获观察题，最后总结出数学规律。

简介：wy的leetcode刷题记录_Day66声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：2023 4 10前言@TOC1019. 链表中的下一个更大节点今天的每日一题是：1019. 链表中的下一个更大节点题目介绍给定一个长度为 n 的链表 head对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。示例 1：输入：head = [2,1,5] 输出：[5,5,0] 示例 2：输入：head = [2,7,4,3,5] 输出：[7,0,5,5,0]思路一道简单的模拟题，分析题意下来就是，遍历整个节点，对于当前节点我们向后寻找第一个大于该节点的节点值，并将值放入一个vector，如果没有则放入0。代码/** * 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: vector<int> nextLargerNodes(ListNode* head) { ListNode* curr=head; ListNode*next=head >next; vector<int> ans; while(curr >next) { while(next) { if(next >val>curr >val) { ans.push_back(next >val); break; } else { next=next >next; } } if(next==nullptr) { ans.push_back(0); } curr=curr >next; next=curr >next; } ans.push_back(0); return ans; } };收获简单的模拟题OI WIKIOI WIKI从今天起，开始较为系统的学习算法的一些基础，不再盲目刷题了。

简介：wy的leetcode刷题记录_Day63_复工开始！声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：前言考研期间只保持每日一题和可有可无的随机题@TOC1638. 统计只差一个字符的子串数目今天的每日一题是：1638. 统计只差一个字符的子串数目题目介绍给你两个字符串 s 和 t ，请你找出 s 中的非空子串的数目，这些子串满足替换 一个不同字符 以后，是 t 串的子串。换言之，请你找到 s 和 t 串中 恰好 只有一个字符不同的子字符串对的数目。比方说， "computer" and "computation" 只有一个字符不同： 'e'/'a' ，所以这一对子字符串会给答案加 1 。请你返回满足上述条件的不同子字符串对数目。一个 子字符串 是一个字符串中连续的字符。示例 1：输入：s = "aba", t = "baba" 输出：6 解释：以下为只相差 1 个字符的 s 和 t 串的子字符串对： ("aba","baba") ("aba", "baba") ("aba", "baba") ("aba", "baba") ("aba","baba") ("aba", "baba") 加粗部分分别表示 s 和 t 串选出来的子字符串。示例 2： 输入：s = "ab", t = "bb" 输出：3 解释：以下为只相差 1 个字符的 s 和 t 串的子字符串对： ("ab", "bb") ("ab", "bb") ("ab", "bb") 加粗部分分别表示 s 和 t 串选出来的子字符串。示例 3： 输入：s = "a", t = "a" 输出：0示例 4： 输入：s = "abe", t = "bbc" 输出：10思路枚举大法：理解题意之后可以概括为：比较字符串s的字串中是否与t字符串的任意子串差距为1（差距：不同字符串的个数）。整体解法为：使用指针i表示遍历到s字符串的子串的起始位置，指针j表示遍历到t字符串的子串的起始位置，使用计步器k来表示俩个字符串从起始位置的出发距离（子串长度）。外层循环是字符串的起始位置，内层循环是走的步数。使用全局变量ans表示符合条件的字串个数，局部变量diff表示当前走的步数的俩个子串的差距。局部变量diff：1.当diff>1的时候不符合题目条件不需要继续走下去了，变量k的循环可以中断了，然后更新俩个字符串其中之一的起点。2.每更新一次起点diff都需要重新置0。ans:每当走一步之后diff仍然是1，那么当前子字符串符合条件，ans++。代码class Solution { public: int countSubstrings(string s, string t) { int s1=s.size(); int t1=t.size(); int ans=0; for(int i=0;i<s1;i++) { for(int j=0;j<t1;j++) { int diff=0; for(int k=0;k+i<s1&&k+j<t1;k++) { diff+=(s[i+k]==t[j+k]?0:1); if(diff>1) break; else if(diff==1) ans++; } } } return ans; } };收获复工日记！题目还是比较简单的。