月のLeetCode 每周刷题之 Week7

2024-02-12 14:18
文章标签 leetcode 刷题 每周 week7

本文主要是介绍月のLeetCode 每周刷题之 Week7，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

958. 二叉树的完全性检验

41. 缺失的第一个正数

918. 环形子数组的最大和

1114. 按序打印

1115. 交替打印 FooBar

329. 矩阵中的最长递增路径

7. 整数反转

24. 两两交换链表中的节点

1143. 最长公共子序列

最长公共子串

5. 最长回文子串

179. 最大数

129. 求根节点到叶节点数字之和

206. 反转链表

102. 二叉树的层序遍历


给定一个二叉树的 root ，确定它是否是一个 完全二叉树 。

在一个 完全二叉树 中，除了最后一个关卡外，所有关卡都是完全被填满的，并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 1 到 2h 节点之间的最后一级 h 。

 

class Solution {
public:int maxIndex=0,n=0;bool isCompleteTree(TreeNode* root) {if(dfs(root,1)==false) return  false;return n==maxIndex;}
​bool dfs(TreeNode*root,int k){if(root==nullptr) return true;if(k>1000) return false;maxIndex=max(maxIndex,k);n++;return dfs(root->left,2*k)&&dfs(root->right,2*k+1);}
};

  • k为当前节点数，n为总结点数，maxIndex为最大节点数

  • 如果总结点数n与最大节点数相同，则是完全二叉树，否则不是

41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

class Solution {
public:int firstMissingPositive(vector<int>& nums) {for(int i=0;i<nums.size();i++){while(nums[i]>0&&nums[i]<=nums.size()&&nums[nums[i]-1]!=nums[i]){swap(nums[i],nums[nums[i]-1]);}}
​for(int i=0;i<nums.size();i++){if(nums[i]!=i+1) return i+1;}return nums.size()+1;}
};

  • 置换法

  • 把num[i]和num[num[i]-1]交换，遍历数组当前元素不再对应下标位置的即为答案

  • 若都在下标位置则为连续数组，及返回数组最大值的下一个元素

918. 环形子数组的最大和

给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。

环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。

子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

 

class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {int sum=0;int maxv=nums[0],minv=nums[0],curmax=0,curmin=0;for(auto &i:nums){curmax=max(curmax+i,i);maxv=max(maxv,curmax);curmin=min(curmin+i,i);minv=min(minv,curmin);sum+=i;}if(maxv>0) return max(maxv,sum-minv);return maxv;}
};

1114. 按序打印

三个不同的线程 A、B、C 将会共用一个 Foo 实例。

线程 A 将会调用 first() 方法
线程 B 将会调用 second() 方法
线程 C 将会调用 third() 方法
请设计修改程序，以确保 second() 方法在 first() 方法之后被执行，third() 方法在 second() 方法之后被执行。

 

class Foo {
public:pthread_mutex_t mutex1,mutex2;Foo() {pthread_mutex_init(&mutex1,nullptr);    //初始化互斥锁pthread_mutex_init(&mutex2,nullptr);
​pthread_mutex_lock(&mutex1);        //给2和3加锁pthread_mutex_lock(&mutex2);}
​void first(function<void()> printFirst) {// printFirst() outputs "first". Do not change or remove this line.printFirst();pthread_mutex_unlock(&mutex1);  //1执行完给2解锁}
​void second(function<void()> printSecond) {// printSecond() outputs "second". Do not change or remove this line.pthread_mutex_lock(&mutex1);      printSecond();pthread_mutex_unlock(&mutex2);  //2执行完给3解锁}
​void third(function<void()> printThird) {// printThird() outputs "third". Do not change or remove this line.pthread_mutex_lock(&mutex2);printThird();}
};

  • 互斥锁

class Foo {
public:pthread_mutex_t mutex1,mutex2;pthread_cond_t cond1,cond2;int k=1;    //条件Foo() {pthread_mutex_init(&mutex1,nullptr);    //初始化条件变量和互斥锁pthread_mutex_init(&mutex2,nullptr);pthread_cond_init(&cond1,nullptr);pthread_cond_init(&cond2,nullptr);
​pthread_mutex_lock(&mutex1);        //  加锁pthread_mutex_lock(&mutex2);}
​void first(function<void()> printFirst) {// printFirst() outputs "first". Do not change or remove this line.printFirst();k++;        pthread_mutex_unlock(&mutex1);  //给2解锁}
​void second(function<void()> printSecond) {// printSecond() outputs "second". Do not change or remove this line.pthread_mutex_lock(&mutex1);      while(k!=2) pthread_cond_wait(&cond1, &mutex1);     //如果k不等于2，则阻塞直到满足条件printSecond();k++;pthread_mutex_unlock(&mutex2);      //给3解锁}
​void third(function<void()> printThird) {// printThird() outputs "third". Do not change or remove this line.pthread_mutex_lock(&mutex2);while(k!=3) pthread_cond_wait(&cond2, &mutex2);//如果k不等于3，则阻塞直到满足条件printThird();}
};

  • 互斥锁+条件变量

1115. 交替打印 FooBar

两个不同的线程将会共用一个 FooBar 实例：

线程 A 将会调用 foo() 方法，而
线程 B 将会调用 bar() 方法
请设计修改程序，以确保 "foobar" 被输出 n 次。

 

class FooBar {
private:int n;pthread_mutex_t mutex1,mutex2;
public:FooBar(int n) {this->n = n;pthread_mutex_init(&mutex1, nullptr);pthread_mutex_init(&mutex2, nullptr);
​
​pthread_mutex_lock(&mutex2);
​}
​void foo(function<void()> printFoo) {for (int i = 0; i < n; i++) {// printFoo() outputs "foo". Do not change or remove this line.pthread_mutex_lock(&mutex1);printFoo();//pthread_mutex_lock(&mutex1);pthread_mutex_unlock(&mutex2);}}
​void bar(function<void()> printBar) {for (int i = 0; i < n; i++) {// printBar() outputs "bar". Do not change or remove this line.pthread_mutex_lock(&mutex2);printBar();//pthread_mutex_lock(&mutex2);pthread_mutex_unlock(&mutex1);}}
};

329. 矩阵中的最长递增路径

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

class Solution {
public:int longestIncreasingPath(vector<vector<int>>& matrix) {
​int ans=0;vector<vector<int>> memo(matrix.size(),vector<int>(matrix[0].size()));//记忆数组for(int i=0;i<matrix.size();i++){for(int j=0;j<matrix[0].size();j++){int maxl=dfs(matrix,i,j,-1,memo);ans=max(ans,maxl);}}return ans;}int dfs(vector<vector<int> >& matrix,int x,int y,int pre,vector<vector<int>>& memo){int maxl=0;if(x<0||x>=matrix.size()||y<0||y>=matrix[0].size()||matrix[x][y]<=pre){return 0;}
​if(memo[x][y]!=0)   //已经遍历过了直接返回之前的结果{return memo[x][y];}   maxl=max(maxl,dfs(matrix,x-1,y,matrix[x][y],memo));maxl=max(maxl,dfs(matrix,x+1,y,matrix[x][y],memo));maxl=max(maxl,dfs(matrix,x,y-1,matrix[x][y],memo));maxl=max(maxl,dfs(matrix,x,y+1,matrix[x][y],memo));memo[x][y]=maxl+1;  //没有遍历过则加入到数组中，要max+1，长度需要+1return maxl+1;}
};

  • dfs+记忆化搜索

7. 整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

 

class Solution {
public:int reverse(int x) {int ans=0;while(x!=0)      {if(ans<INT_MIN/10||ans>INT_MAX/10) return 0;int t=x%10;x/=10;ans=ans*10+t;}return ans;}
};

24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）

class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode *dummy=new ListNode(-1);dummy->next=head;ListNode* cur=dummy;while(cur->next!=nullptr&&cur->next->next!=nullptr){ListNode* t=cur->next;cur->next=t->next;t->next=t->next->next;cur->next->next=t;cur=cur->next->next;}return dummy->next;}
};

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

 

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1));for(int i=1;i<=text1.size();i++){for(int j=1;j<=text2.size();j++){if(text1[i-1]==text2[j-1])  dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}return dp[text1.size()][text2.size()];}
};

最长公共子串

class Solution {
public:/*** longest common substring* @param str1 string字符串 the string* @param str2 string字符串 the string* @return string字符串*/string LCS(string str1, string str2) {// write code hereint maxL=0,lastIndex=0;vector<vector<int>> dp(str1.size()+1,vector<int>(str2.size()+1));for(int i=1;i<=str1.size();i++){for(int j=1;j<=str2.size();j++){if(str1[i-1]==str2[j-1]){dp[i][j]=dp[i-1][j-1]+1;if(maxL<dp[i-1][j-1])    {maxL=dp[i-1][j-1];lastIndex=i;}}elsedp[i][j]=0;}}return str1.substr(lastIndex-maxL-1,maxL+1);}
};

  • dp记录最长子串长度和最长下标

  • 截取字符串

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

class Solution {
public:string longestPalindrome(string s) {if(s.size()==0) return "";int l=0,r=0;int maxStart,maxL=0;int len=1;for(int i=0;i<s.size();i++){l=i-1,r=i+1;while(l>=0&&s[i]==s[l]){len++;l--;}while(r<s.size()&&s[i]==s[r]){len++;r++;}while(l>=0&&r<s.size()&&s[l]==s[r]){len+=2;r++;l--;}if(len>maxL){maxL=len;maxStart=l;     //如果求最大长度去掉这行，返回maxL即可}len=1;}return s.substr(maxStart+1,maxL);}
};

  • 中心拓展法

179. 最大数

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

class Solution {
public:string largestNumber(vector<int>& nums) {vector<string> vec;for(int i=0;i<nums.size();i++){vec.push_back(to_string(nums[i]));}sort(vec.begin(),vec.end(),[](string &a,string &b){return a+b>b+a;});string s;for(auto &a:vec){s+=a;}if(s[0]=='0') return "0";return s;}
};

  • 自定义比较函数

129. 求根节点到叶节点数字之和

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

 

class Solution {
public:int sumNumbers(TreeNode* root) {return dfs(root,0);}
​int dfs(TreeNode *root,int sum){if(root==nullptr) return 0;int s=sum*10+root->val;if(root->left==nullptr&&root->right==nullptr)    {return s;}return dfs(root->left,s)+dfs(root->right,s);}
};

206. 反转链表

class Solution {
public:ListNode* reverseList(ListNode* head) {if(head==nullptr||head->next==nullptr) return head;ListNode *node=reverseList(head->next);head->next->next=head;head->next=nullptr;return node;}
};

  • 递归

102. 二叉树的层序遍历

class Solution {
public:vector<vector<int>> vec;vector<vector<int>> levelOrder(TreeNode* root) {dfs(root,0);return vec;}
​void dfs(TreeNode* root,int level){if(root==nullptr) return;if(level>=vec.size()) vec.push_back({});    //防止后续元素无法加入进去vec[level].push_back(root->val);dfs(root->left,level+1);dfs(root->right,level+1);}
};

  • 递归

这篇关于月のLeetCode 每周刷题之 Week7的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/702745。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
leetcode-24Swap Nodes in Pairs

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L
阅读更多...
leetcode-23Merge k Sorted Lists

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
C语言 | Leetcode C语言题解之第393题UTF-8编码验证

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目： 题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
阅读更多...
【JavaScript】LeetCode：16-20

【JavaScript】LeetCode：16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i，右指针j，从头遍历数组，若j指针指向的元素不在set中，则加入该元素，否则更新结果res，删除集合中i指针指向的元素，进入下一轮循环。 /*** @param
阅读更多...
【每日刷题】Day113

【每日刷题】Day113

【每日刷题】Day113 🥕个人主页：开敲🍉 🔥所属专栏：每日刷题🍍 🌼文章目录🌼 1. 91. 解码方法 - 力扣（LeetCode） 2. LCR 098. 不同路径 - 力扣（LeetCode） 3. 63. 不同路径 II - 力扣（LeetCode） 1. 91. 解码方法 - 力扣（LeetCode） //思路：动态规划。 cl
阅读更多...
LeetCode：64. 最大正方形 动态规划 时间复杂度O(nm)

LeetCode：64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵，找出只包含 1 的最大正方形，并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划
阅读更多...
LeetCode 第414场周赛个人题解

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2